開発者ドキュメント

JavaのTreeMapガイド


1概要

この記事では、Java Collections Framework(JCF)から

Map

インターフェースの

TreeMap

実装を探ります。


TreeMap

は、そのエントリをそのキーの自然な順序に従ってソートしたままにしておくマップ実装です。構築時にユーザーが指定した場合は、コンパレータを使用することをお勧めします。

以前は、


HashMap





LinkedHashMap


の実装について説明してきましたが、これらのクラスがどのように機能するかについてはかなりの情報があります。

この記事を読む前に、前述の記事を読んでおくことを強くお勧めします。


2

TreeMap


でのデフォルトのソート

デフォルトでは、

TreeMap

はすべてのエントリを自然な順序で並べ替えます。整数の場合は昇順、文字列の場合はアルファベット順です。

テストの自然順序付けを見てみましょう。

@Test
public void givenTreeMap__whenOrdersEntriesNaturally__thenCorrect() {
    TreeMap<Integer, String> map = new TreeMap<>();
    map.put(3, "val");
    map.put(2, "val");
    map.put(1, "val");
    map.put(5, "val");
    map.put(4, "val");

    assertEquals("[1, 2, 3, 4, 5]", map.keySet().toString());
}

整数キーを順序どおりに配置していませんが、キーセットを取得する際には、キーが昇順に維持されていることを確認してください。これは整数の自然な順序です。

同様に、文字列を使用すると、それらは自然な順序、すなわちアルファベット順にソートされます。

@Test
public void givenTreeMap__whenOrdersEntriesNaturally__thenCorrect2() {
    TreeMap<String, String> map = new TreeMap<>();
    map.put("c", "val");
    map.put("b", "val");
    map.put("a", "val");
    map.put("e", "val");
    map.put("d", "val");

    assertEquals("[a, b, c, d, e]", map.keySet().toString());
}

ハッシュマップおよびリンクハッシュマップとは異なり、

TreeMap

はエントリを格納するために配列を使用しないため、ハッシュの原則をどこにも使用しません。


3

TreeMap


でのカスタムソート


TreeMap

の自然な順序付けに満足できない場合は、ツリーマップの作成中にコンパレータを使用して順序付けに関する独自の規則を定義することもできます。

以下の例では、整数キーを降順に並べます。

@Test
public void givenTreeMap__whenOrdersEntriesByComparator__thenCorrect() {
    TreeMap<Integer, String> map =
      new TreeMap<>(Comparator.reverseOrder());
    map.put(3, "val");
    map.put(2, "val");
    map.put(1, "val");
    map.put(5, "val");
    map.put(4, "val");

    assertEquals("[5, 4, 3, 2, 1]", map.keySet().toString());
}

ハッシュマップは保存されているキーの順序を保証するものではなく、特にこの順序が時間の経過と共に変わらないことを保証するものではありませんが、ツリーマップはキーが常に指定の順序に従ってソートされることを保証します。


4

TreeMap

ソートの重要性


TreeMap

はすべてのエントリをソートされた順序で格納します。

ツリーマップのこの属性により、次のようなクエリを実行できます。 「最大」を見つける、「最小」を見つける、特定の値より小さいまたは大きいすべてのキーを見つけるなど

以下のコードは、これらのケースのごく一部をカバーしています。

@Test
public void givenTreeMap__whenPerformsQueries__thenCorrect() {
    TreeMap<Integer, String> map = new TreeMap<>();
    map.put(3, "val");
    map.put(2, "val");
    map.put(1, "val");
    map.put(5, "val");
    map.put(4, "val");

    Integer highestKey = map.lastKey();
    Integer lowestKey = map.firstKey();
    Set<Integer> keysLessThan3 = map.headMap(3).keySet();
    Set<Integer> keysGreaterThanEqTo3 = map.tailMap(3).keySet();

    assertEquals(new Integer(5), highestKey);
    assertEquals(new Integer(1), lowestKey);
    assertEquals("[1, 2]", keysLessThan3.toString());
    assertEquals("[3, 4, 5]", keysGreaterThanEqTo3.toString());
}


5

TreeMap


の内部実装


TreeMap



NavigableMap

インターフェースを実装し、それが赤黒木の原則に基づいた内部作業に基づいている:

public class TreeMap<K,V> extends AbstractMap<K,V>
  implements NavigableMap<K,V>, Cloneable, java.io.Serializable

赤黒木の原理はこの記事の範囲を超えていますが、それらがどのように

TreeMap

に収まるかを理解するために覚えておくべき重要なことがあります。

  • まず第一に、赤黒の木はノードからなるデータ構造です。空に根があり、枝が下に伸びている倒立マンゴーの木の絵。ルートはツリーに追加された最初の要素を含みます。

原則として、ルートから始めて、任意のノードの左ブランチにある要素は、常にノード自体の要素よりも小さいということです。右側のものは常に大きいです。これより大きいか小さいかを定義するのは、前に見たように、構成要素の自然な順序付けまたは構築時の定義済みコンパレータによって決定されます。

この規則は、ツリーマップのエントリが常にソートされた予測可能な順序になることを保証します。

  • 次に** 、赤黒の木は自己均衡二分探索木です。

この属性と上記のことから、search、get、put、removeのような基本的な操作では対数時間

O(log n)

が必要です。

ここで自己バランスをとることが重要です。エントリの挿入と削除を続けていくうちに、一方の端ではより長く成長し、他方の端ではより短く成長するツリーを描きます。

これは、操作がより短いブランチではより短く、ルートから最も遠いブランチではより長い時間がかかることを意味しますが、これは起こりたくないことです。

そのため、これは赤黒の木のデザインで大事にされます。すべての挿入および削除に対して、任意のエッジ上のツリーの最大高さは

O(log n)

に維持されます。つまり、ツリーは継続的にバランスを取ります。

ハッシュマップおよびリンクハッシュマップと同様に、ツリーマップは同期されていないため、マルチスレッド環境で使用するための規則は他の2つのマップ実装の規則と似ています。

** 6. 正しい地図の選択

**



HashMap





LinkedHashMap


の実装については、以前と今では

TreeMap

を見てきました。

  • ハッシュマップ** は迅速な保存と検索操作を提供する汎用のマップ実装として良いです。しかし、それは混沌とした並びに並んでいないエントリの配置のために不十分です。

基になる配列の容量全体が、エントリ数だけではなくトラバーサルに影響を与えるため、反復回数が多いシナリオではパフォーマンスが低下します。

  • リンクハッシュマップ** はハッシュマップの優れた属性を持ち、エントリに順序を追加します。容量に関係なく、エントリ数のみが考慮されるため、反復が多い場所ではパフォーマンスが向上します。

  • ツリーマップは、キーのソート方法を完全に制御することによって次のレベルへの順序付けを行います。反対に、他の2つの方法よりも一般的なパフォーマンスが劣ります。

  • リンクハッシュマップは、ツリーマップ** のパフォーマンスペナルティを招くことなく、ハッシュマップの順序付けにおける混乱を軽減すると言えます。


7. 結論

この記事では、JavaのTreeMapクラスとその内部実装について説明しました。これは、一連の一般的なMapインターフェース実装の最後のものであるため、他の2つのインターフェースとの関連で最適な場所について簡単に説明しました。

この記事で使用されているすべての例の完全なソースコードはhttps://github.com/eugenp/tutorials/tree/master/java-collections-maps[GitHubプロジェクト]にあります。

モバイルバージョンを終了