Java TreeMapとHashMapの比較
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で利用可能]です。