ソートマップ

ソートマップ

このレッスンでは、 SortedMapインターフェイスを学習します。このインターフェイスに表示される新しいメソッド、 SortedMapの実装の 1 つであるTreeMapの機能、実装間の違い、およびHashMapと比較した利点について説明します。

マップの階層がどのようなものかを見てみましょう。SortedMapインターフェイスとそのTreeMap実装に特に注意してください。今日はこれらに焦点を当てます。

SortedMapインターフェイスはMapインターフェイスを拡張します。これは多くの点でSortedSet ( Setを拡張) に似ています。どちらも、並べ替えられた値を格納および使用するための同様の機能を記述しているからです。

SortedSet は<TValue>と連携して保存しますが、SortedMap は<TKey, TValue>ペアを保存します。これは、すべての要素をキーの昇順で格納するマップです。

SortedMapインターフェースはMapを拡張します。次のメソッドが追加されます。

TreeMap クラス

TreeMapクラスは、SortedMapインターフェイスの実装です。つまり、TreeMap は、 SortedMapによって追加されたすべてのメソッドと、Mapインターフェイスの標準メソッドを実装します。

次のようなコンストラクターを使用してTreeMapオブジェクトを作成できます。

• TreeMap() : ツリーとして実装された空のマップを作成します。

• TreeMap(Map<? extends TKey, ? extends TValue> map) : ツリーを作成し、入力マップからすべての要素を追加します。

• TreeMap(SortedMap<TKey, ? extends TValue> smap) : ツリーを作成し、入力ソート マップからすべての要素を追加します。

• TreeMap(Comparator<? super TKey> comparator) : 空のツリーを作成します。コンパレータは、後で追加されるすべての要素を並べ替えるために使用されます。

ここで、TKey は保存されたペアのキーのタイプであり、TValueはTreeMapに保存されたペアの値のタイプです。

Comparator はSortedMap / TreeMapにとって非常に重要です。これは、マップを並べ替える (つまり順序​​付けする) ためのルールを確立します。コンパレーターを提供しない場合、 SortedMapを作成するときにキーの自然な順序が使用されます。

TreeMap への要素の追加

要素は、put()メソッドを使用してペアとしてマップに追加されます。キーは最初の引数として渡され、値は 2 番目の引数として渡されます。たとえば、学生とその成績のリストを作成するとします。

SortedMap<String, Integer> map =new TreeMap <String,Integer>();

map.put("Anthony", 5);
map.put("Sara", 5);
map.put("Roxy", 5);
map.put("Jeff", 4);
map.put("Nick", 4);
map.put("Oliver", 3);
map.put("Oliver", 5);

System.out.println(map);

結果：

キーと値のペアを追加するときに、キーがコレクションにすでに存在している場合は、古い値が新しい値に置き換えられます。この動作は、同じキーを持つ 2 つのペア("Oliver", 3)と("Oliver", 5)を使用した例で示されています。

作成したコンパレーターの例を見てみましょう。キー文字列の長さによって並べ替えられた要素を保存するとします。キーの長さが等しい場合は、アルファベット順にソートします (文字列の自然な順序)。

class LengthComparator implements Comparator<String> {
  public int compare(String o1, String o2) {
    Integer lenghComparedResult = Integer.compare(o1.length(), o2.length());
    return lenghComparedResult != 0 ? lenghComparedResult : o1.compareTo(o2);
  }
}

SortedMap<String, Integer> lengthComparedMap = new TreeMap<String, Integer>(new LengthComparator());

lengthComparedMap.put("Jeff", 4);
lengthComparedMap.put("Oliver", 5);
lengthComparedMap.put("Roxy", 4);
lengthComaredMap.put("Jan", 4);

結果のシーケンスは次のとおりです。

この動作により、TreeMap はインデックスが数値ではなく単語 ( String ) になる並べ替えられた配列またはリストのようになります。

TreeMap クラスの SortedMap メソッド

1. 最初の生徒のキーを取得する必要がある場合は、firstKey()メソッドを使用できます。

   
   String firstKey = map.firstKey();
   	System.out.println("First key → " + firstKey);
   

   結果:最初のキー → アンソニー

2. 最後の生徒のキーを取得する必要がある場合は、lastKey()メソッドを使用できます。

   
   String lastKey = map.lastKey();
   System.out.println("Last key → " + lastKey);
   

   結果:最後のキー → ジェフ

3. キー「 Sara 」を持つオブジェクトの後にあるすべてのオブジェクトを取得します。

   
   Map<String, Integer> tailMap = map.tailMap("Sara");
            	System.out.println("tailMap: " + tailMap);
   

   結果: tailMap: {Sara=5, Jeff=4}

4. キー「 Nick 」を持つオブジェクトの前にあるすべてのオブジェクトを取得します。

   
   System.out.println("headMap: " + headMap);
    Map<String, Integer> headMap = map.headMap("Nick");
   

   結果: headMap: {Anthony=5}

5. キー「 Oliver 」を持つオブジェクトの後、およびキー「 Sara 」を持つオブジェクトの前にあるすべてのオブジェクトを取得します。

   
   Map<String, Integer> subMap = map.subMap("Oliver", "Sara");	
   System.out.println("subMap: " + subMap);
   

   結果:サブマップ: {オリバー=5、ロキシー=5}

HashMap と SortedMap/TreeMap の比較

要素がどのように順序付けされ、格納されるかについて説明します。

• HashMap では反復処理時の順序が保証されないため、新しい要素が追加されると順序が完全に変わる可能性があります。

• TreeMapでは、順序は、 compareTo()メソッド (または提供されるComparator )に従ったキーの「自然順序付け」に基づいています。また、 TreeMap は、この並べ替え順序に依存するメソッドを含むSortedMapインターフェイスを実装していることを忘れないでください。

次に、パフォーマンスと速度について検討します。

• HashMapはハッシュ キーに基づくマップです。O(1)、定数時間で要素を挿入および取得できますこれをサポートするには、キーでhashCode()とquals()。

• TreeMap はツリーベースのマップです。その挿入およびフェッチ操作には対数時間、つまりO(log n)。これはマップ内の要素の数に依存します。これは、キーまたは外部コンパレーターによって提供されるある種の比較メカニズムを要素に持たせるために必要です。このメカニズムにより、反復順序が決定されます。

これらの要素は、どのコレクションをいつ使用するかを決定するのに役立ちます。

値を特定の順序で保存する必要がある場合、選択は明らかです。 SortedMap が必要です。HashMapよりも少し遅いですが、重要なタスクを実行します。

前述したように、SortedMap は、値がいつ追加されたかに関係なく、マップ内の最初 (または最後の) キー、値、またはキーと値のペアを提供します。HashMap実装ではこれを行うことはできません。

たとえば、キー (生徒の名前) と値 (生徒の成績) を含むマップを考えてみましょう。逆アルファベット順のリストを操作したいとします。

1.

SortedMap<String, Integer> sorted = new TreeMap<String,Integer>(Comparator.reverseOrder());
sorted.put("Anthony", 5);
sorted.put("Sara", 5);
sorted.put("Jeff", 4);

String firstKeyFromSortedMapVariant = sorted.firstKey();

Integer markFromSortedMap = sorted.get(firstKeyFromSortedMapVariant);
System.out.println(firstKeyFromSortedMapVariant + " - " + markFromSortedMap);

2.

HashMap<String, Integer> hash = new HashMap<String,Integer>();
hash.put("Anthony", 5);
hash.put("Sara", 5);
hash.put("Jeff", 4);

SortedSet<String> keySetOfHashMap = new TreeSet<String>(Comparator.reverseOrder());
// Or sort manually, storing elements in an array or list (preserving the insertion order)
keySetOfHashMap.addAll(hash.keySet());
String firstKeyFromHashMapVariant = keySetOfHashMap.first();


Integer markFromHashMap = hash.get(firstKeyFromHashMapVariant);
System.out.println(firstKeyFromHashMapVariant + " - " + markFromHashMap);

この例は、HashMapが格納の順序もマップから要素を取得する順序も保証しないため、 HashMapを使用するとタスクがより複雑になることを示しています。