JavaTreeMapとHashMap

投稿日: 2019-10-19 2022-10-17
タグ: Java, Java Collections, Java Map

1. 序章

この記事では、2つのMap実装を比較します。TreeMapとHashMapです。

どちらの実装も、Java Collections フレームワークの不可欠な部分を形成し、データをキーと値のペアとして格納します。

2. 違い

2.1. 実装

最初に、ハッシュテーブルベースの実装であるHashMapについて説明します。 AbstractMap クラスを拡張し、Mapインターフェースを実装します。 HashMap は、hashingの原則に基づいて機能します。

このMap実装は通常、バケット化されたハッシュテーブルとして機能しますが、バケットが大きくなりすぎると、TreeNodesのノードに変換されます。 java.util.TreeMap。

HashMapの内部については、に焦点を当てた記事を参照してください。

一方、 TreeMap は、 AbstractMap クラスを拡張し、NavigableMapインターフェイスを実装します。 TreeMap は、マップ要素を Red-Black ツリーに格納します。これは、 Self-Balancing Binary SearchTreeです。

また、 TreeMapのの内部については、ここで焦点を当てた記事を参照してください。

2.2. 注文

HashMapは、要素がMapに配置される方法を保証するものではありません。

つまり、 HashMapのキーと値を反復処理している間は順序を想定できません：

@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 オブジェクトを自然な順序で並べ替えることができない場合は、コンパレータまたは比較可能を使用して、要素がマップ：

@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を使用している場合、compare （）メソッドの実装に依存します null 値が処理されます。

3. パフォーマンス分析

パフォーマンスは、ユースケースが与えられた場合のデータ構造の適合性を理解するのに役立つ最も重要なメトリックです。

このセクションでは、HashMapおよびTreeMapのパフォーマンスの包括的な分析を提供します。

3.1. HashMap

HashMap、はハッシュテーブルベースの実装であり、内部的に配列ベースのデータ構造を使用して、ハッシュ関数に従って要素を編成します。

HashMap 期待される一定時間のパフォーマンスを提供します O（1） のようなほとんどの操作のために追加（） 、 削除する（） と contains（）。したがって、それはよりも大幅に高速です TreeMap 。

ハッシュテーブルで妥当な仮定の下で要素を検索する平均時間は次のとおりです。 O（1）。しかし、の不適切な実装ハッシュ関数バケット内の値の分散が不十分になり、次の結果になる可能性があります。

メモリオーバーヘッド–多くのバケットは未使用のままです
パフォーマンスの低下– 衝突の数が多いほど、パフォーマンスは低下します

Java 8より前は、衝突を処理するための唯一の好ましい方法は個別の連鎖でした。衝突がある場合、または2つの異なる要素が同じハッシュを持っている場合は、通常、リンクリストieを使用して実装されます。次に、valueは、両方のアイテムを同じリンクリストに格納します。

したがって、最悪の場合、 HashMap、で要素を検索するのは、リンクリスト ie O（n）で要素を検索するのと同じくらい長くかかる可能性があります。 ] 時間。

ただし、 JEP 180 が登場したことで、要素の配置方法の実装に微妙な変更が加えられました。 HashMap。

仕様によると、バケットが大きくなりすぎて十分なノードが含まれる場合、バケットは TreeNodes のモードに変換され、それぞれがTreeMapのモードと同様に構造化されます。

したがって、ハッシュの衝突が多い場合、最悪の場合のパフォーマンスは O（n）から O（log n）に向上します。

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

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

TREEIFY_THRESHOLD の値は8であり、バケットのリンクリストではなくツリーを使用するためのしきい値カウントを効果的に示します。

それは明らかです：

A HashMap は、データを保持するために必要なメモリよりもはるかに多くのメモリを必要とします
HashMapは70%– 75% fullを超えてはなりません。近づくと、サイズが変更され、エントリが再ハッシュされます
再ハッシュにはnの操作が必要ですが、これにはコストがかかり、一定時間の挿入は O（n）のオーダーになります。
これは、HashMapにオブジェクトを挿入する順序を決定するハッシュアルゴリズムです。

HashMapのパフォーマンスは、 HashMap オブジェクトの作成時に、カスタムの初期容量と負荷率を設定することで調整できます。

ただし、次の場合はHashMapを選択する必要があります。

コレクション内で維持するアイテムの数はわかっています
自然な順序でアイテムを抽出したくない

上記の状況では、 HashMap は、一定時間の挿入、検索、および削除を提供するため、最適な選択です。

3.2. ツリーマップ

A TreeMap は、カスタムコンパレータを使用して要素を並べ替える機能を備えた階層ツリーにデータを格納します。

そのパフォーマンスの要約：

TreeMap は、 add（）、 remove（）、などのほとんどの操作で O（log（n））のパフォーマンスを提供します] contains（）
A ツリーマップは、連続領域を使用するハッシュマップとは異なり、アイテムを保持するために必要な量のメモリのみを使用するため、メモリを節約できます（ハッシュマップと比較して）メモリの
ツリーは、意図したパフォーマンスを維持するためにバランスを維持する必要があります。これにはかなりの労力が必要であるため、実装が複雑になります。

次の場合は常に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. 同時アクセス

両方のマップ実装が同期されていないため、同時アクセスを自分で管理する必要があります。

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

提供されたマップの同期ビューを取得するには、 Collections.synchronizedMap（mapName）を明示的に使用する必要があります。

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

Iterator は、 Map が何らかの方法で変更された場合、およびイテレーターが作成された後はいつでも、ConcurrentModificationExceptionをスローします。

さらに、イテレータのremoveメソッドを使用して、反復中にMapを変更できます。

例を見てみましょう：

@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の相違点と類似点を示しました。

いつものように、この記事のコード例はGitHubでから入手できます。

getdocs

13036