1前書き

この記事では、2つの

Map

実装を比較します。


TreeMap

と

HashMap

。

どちらの実装もJavaの

Collection

Frameworkの不可欠な部分を構成し、

key-value

のペアとしてデータを格納します。


2違い


2.1. 実装

まずハッシュテーブルベースの実装である

HashMap

について説明します。それは

AbstractMap

クラスを拡張し、

Map

インターフェースを実装します。

HashMap

は


hashing


の原理に基づいて動作します。

この

Map

の実装は通常、ハッシュ化された

hash table

として機能しますが、

バケットが大きくなりすぎると

TreeNodes


のノードに変換されます。

あなたは

に焦点を当てた記事

で

HashMapの

内部についてより多くを見つけることができます。

一方、

TreeMap

は

AbstractMap

クラスを拡張し、

NavigableMap

インターフェースを実装します。

TreeMap

はマップ要素を

Red-Black

ツリーに格納します。これは

Self-Balancing

Binary Search Tree


です。

そして、あなたは

ここで焦点を絞った記事

の中にある__TreeMapの内部構造についてもっと見つけることができます。


2.2. 注文


  • HashMap

    は、要素が

    Map

    ** に配置されている方法を保証するものではありません。

つまり、**

HashMap

の

keys

と

values

を繰り返し処理している間は、任意の順序を想定できません。 

@Test
public void whenInsertObjectsHashMap__thenRandomOrder() {
    Map<Integer, String> hashmap = new HashMap<>();
    hashmap.put(3, "TreeMap");
    hashmap.put(2, "vs");
    hashmap.put(1, "HashMap");

    assertThat(hashmap.keySet(), containsInAnyOrder(1, 2, 3));
}

ただし、

TreeMap

内の項目は、それらの自然順** に従ってソートされます。


TreeMap

オブジェクトを自然な順序で並べ替えることができない場合、

Map内で要素が配置される順序を定義するために

Comparator

または

Comparable__を使用することができます。 

@Test
public void whenInsertObjectsTreeMap__thenNaturalOrder() {
    Map<Integer, String> treemap = new TreeMap<>();
    treemap.put(3, "TreeMap");
    treemap.put(2, "vs");
    treemap.put(1, "HashMap");

    assertThat(treemap.keySet(), contains(1, 2, 3));
}


2.3.

Null

値


HashMap

では、最大で1つの

null


key

と多数の

null

値を格納できます。

例を見てみましょう。 

@Test
public void whenInsertNullInHashMap__thenInsertsNull() {
    Map<Integer, String> hashmap = new HashMap<>();
    hashmap.put(null, null);

    assertNull(hashmap.get(null));
}

ただし、

TreeMap

では

null


key

を使用できませんが、多くの

null

値を含めることができます。


compareTo（）

メソッドまたは

compare（）

メソッドが

NullPointerExceptionをスローするため、

null__キーは使用できません。 

@Test(expected = NullPointerException.class)
public void whenInsertNullInTreeMap__thenException() {
    Map<Integer, String> treemap = new TreeMap<>();
    treemap.put(null, "NullPointerException");
}

  • ユーザー定義の

    Comparator

    と一緒に

    TreeMap

    を使用する場合、それは

    null

    値がどのように扱われるかについてcompare

    __（）

    __メソッドの実装に依存します。**


3パフォーマンス分析

パフォーマンスは、ユースケースを考慮したデータ構造の適合性を理解するのに役立つ最も重要な測定基準です。

このセクションでは、

HashMap

と__TreeMapのパフォーマンスの包括的な分析を行います


3.1.

HashMap


  • ハッシュテーブルベースの実装である

    HashMapは、

    hash関数__。に従って要素を整理するために、配列ベースのデータ構造を内部的に使用します。


HashMap

は、

add（）

、

remove（）

、および

contains（）のようなほとんどの操作で予想される一定時間のパフォーマンス

O（1）__を提供します。

ハッシュテーブルで妥当な仮定の下で要素を検索するための平均時間は__O（1）です。

  • メモリオーバーヘッド – 多くのバケットは未使用のまま

  • パフォーマンスの低下

    –

    衝突数が多いほど、

性能を下げる

  • Java 8より前のバージョンでは、

    Separate Chaining

    が衝突を処理する唯一の好ましい方法でした。** 衝突がある場合、または2つの異なる要素が同じハッシュ値を持つ場合は、リンクリストを使用して実装します。同じリンクリスト。

したがって、__HashMap内の要素の検索は、最悪の場合、リンクリスト内の要素の検索と同じくらいの時間がかかります。

  • しかし、http://openjdk.java.net/jeps/180[JEP 180]が登場すると、要素が

    __

    HashMapに配置される方法の実装に微妙な変更が加えられました。

仕様によると、バケットが大きくなりすぎて十分なノードを含む場合、それらは

TreeNodes

のモードに変換され、それぞれは

TreeMap

のモードと同様に構造化されます。

  • したがって、高いハッシュ衝突の場合、最悪の場合のパフォーマンスは

    O（n）

    から__O（log n）に向上します。

この変換を実行するコードを以下に示します。 

if(binCount >= TREEIFY__THRESHOLD - 1) {
    treeifyBin(tab, hash);
}


TREEIFY

THRESHOLD__の値は8で、バケットのリンクリストではなくツリーを使用するためのしきい値の数を実質的に表します。

それは明らかです:


  • HashMap

    はデータを保持するのに必要な量よりもはるかに多くのメモリを必要とします。


  • HashMap

    は、70％以上75％以下ではいけません。近づいたら

サイズが変更され、エントリが再ハッシュされます
** 再ハッシュは

n

操作を必要とします。

時間挿入は順番になります

O（n）

** 挿入順序を決めるのはハッシュアルゴリズムです。


HashMap

内のオブジェクト


  • HashMap

    オブジェクトの作成時に、カスタム

    初期容量

    と

    load factor

    ** を設定することで、

    HashMap

    のパフォーマンスを調整できます。

ただし、以下の場合は

HashMap

を選択する必要があります。

  • コレクション内に保持する項目数

  • 自然な順序でアイテムを抽出したくない

上記の状況下では、

HashMap

が最適な選択です。なぜなら、それは一定時間の挿入、検索、削除を提供するからです。


3.2.

TreeMap



TreeMap

は、カスタム__Comparatorの助けを借りて要素をソートする機能を持つ階層ツリーにデータを格納します。

そのパフォーマンスのまとめ


  • TreeMap

    は、ほとんどの操作で

    O（log（n））

    のパフォーマンスを提供します。


add（）

、

remove（）

、および

contains（）

のように
**

Treemap

は（__HashMapと比較して）メモリを節約できます。

アイテムを保持するために必要なメモリ量だけを使用
連続したメモリ領域を使用する

HashMap

** 木はその意図を保つためにバランスを保つべきです

性能、これはかなりの量の努力を必要とし、それ故に実施を複雑にする。

私たちはいつでも

TreeMap

に行くべきです:

  • メモリの制限を考慮する必要があります

  • いくつのアイテムをメモリに保存する必要があるのか​​わかりません

  • 自然な順序でオブジェクトを抽出したい

  • アイテムが一貫して追加および削除される場合


  • O（log n）

    検索時間を受け入れます


4類似点


4.1. ユニークな要素


TreeMap

と

HashMap

はどちらも重複キーをサポートしていません。追加すると、前の要素をオーバーライドします（エラーも例外もなし）。 

@Test
public void givenHashMapAndTreeMap__whenputDuplicates__thenOnlyUnique() {
    Map<Integer, String> treeMap = new HashMap<>();
    treeMap.put(1, "Baeldung");
    treeMap.put(1, "Baeldung");

    assertTrue(treeMap.size() == 1);

    Map<Integer, String> treeMap2 = new TreeMap<>();
    treeMap2.put(1, "Baeldung");
    treeMap2.put(1, "Baeldung");

    assertTrue(treeMap2.size() == 1);
}


4.2. 同時アクセス

  • 両方の

    Map

    実装は

    Synchronized

    ** ではなく、私たちは自分自身で並行アクセスを管理する必要があります。

複数のスレッドが同時にそれらにアクセスし、少なくとも1つのスレッドがそれらを変更するたびに、両方とも外部で同期させる必要があります。

提供された地図の同期ビューを取得するには、

Collections.synchronizedMap（mapName）

を明示的に使用する必要があります。


4.3. フェイルファーストイテレータ


Map

が何らかの方法で変更された場合、およびイテレータが作成された時点で、

Iterator

が

ConcurrentModificationException

をスローします。

さらに、反復中に

Map

を変更するには、反復子のremoveメソッドを使用できます。

例を見てみましょう。 

@Test
public void whenModifyMapDuringIteration__thenThrowExecption() {
    Map<Integer, String> hashmap = new HashMap<>();
    hashmap.put(1, "One");
    hashmap.put(2, "Two");

    Executable executable = () -> hashmap
      .forEach((key,value) -> hashmap.remove(1));

    assertThrows(ConcurrentModificationException.class, executable);
}


5どの実装を使用しますか？

一般的に、どちらの実装にもそれぞれ長所と短所がありますが、それは私たちの選択を左右する根本的な期待と要件を理解するためのものです。

要約すると:

  • エントリをソートしておきたい場合は、

    TreeMap

    を使用してください

  • メモリよりもパフォーマンスを優先する場合は、

    HashMap

    を使用する必要があります。

消費
**

TreeMap

はより重要な局所性を持っているので、私たちは考えるかもしれません

比較的近いオブジェクトにアクセスしたい場合
自然な順序に従って
**

HashMap

は、

initialCapacity

および

loadFactor

を使用して調整できます。

これは

TreeMap

では不可能です
** 挿入順を保持したい場合は

LinkedHashMap

を使用できます

一定時間アクセスの恩恵を受けながら


6. 結論

この記事では、

TreeMap

と

HashMap

の違いと類似点を示しました。

いつものように、この記事のコード例はhttps://github.com/eugenp/tutorials/tree/master/java-collections-maps[GitHubで利用可能]です。