CodeGym /Java Course /モジュール 1 /ソートマップ

ソートマップ

モジュール 1
レベル 19 , レッスン 2
使用可能

ソートマップ

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

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

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

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

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

方法 説明
TKey firstKey() マップの最初の要素のキーを返します。
TKey lastKey() マップの最後の要素のキーを返します。
SortedMap<TKey, TValue> headMap(TKey end) 元のSortedMap のキー終了要素までのすべての要素を含むSortedMapを返します。
SortedMap<TKey, Tvalue> tailMap(K start) キーstartを持つ要素から始まる、元のSortedMapのすべての要素を含むSortedMapを返します(両端を含む)
SortedMap<TKey, TValue> subMap(TKey start, TKey end) キーstartを持つ要素からキーendを持つ要素(end は含まない)まで、元のSortedMapのすべての要素を含むSortedMapを返します。

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);

結果:

{アンソニー=5、ニック=4、オリバー=5、ロキシー=5、サラ=5、ジェフ=4}

キーと値のペアを追加するときに、キーがコレクションにすでに存在している場合は、古い値が新しい値に置き換えられます。この動作は、同じキーを持つ 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);

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

length比較マップ: {Jan=4、Jeff=4、Roxy=4、Oliver=5}

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

ほぼすべての型が KeyType または ValueType になる可能性があることに注意することが重要です。KeyType にはいくつかの小さな追加要件があり、コレクションを詳しく調べるときにそれらについて学びます。

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を使用するとタスクがより複雑になることを示しています。

コメント
TO VIEW ALL COMMENTS OR TO MAKE A COMMENT,
GO TO FULL VERSION