JavaHashMap負荷率

投稿日: 2022-10-16 2022-10-16
タグ: Java Collections, Java Map

1. 概要

この記事では、Javaの HashMap の負荷率の重要性と、それがマップのパフォーマンスにどのように影響するかを説明します。

2. HashMap とは何ですか？

HashMap クラスはJavaコレクションフレームワークに属し、Mapインターフェースの基本的な実装を提供します。キーと値のペアでデータを保存したい場合に使用できます。これらのキーと値のペアはマップエントリと呼ばれ、Map.Entryクラスで表されます。

3. HashMap内部

負荷率について説明する前に、いくつかの用語を確認しましょう。

- ハッシュ
- 容量
- しきい値
- 再ハッシュ
- 衝突

HashMap は、ハッシュの原理に基づいて機能します—オブジェクトデータをいくつかの代表的な整数値にマップするアルゴリズムです。ハッシュ関数はキーオブジェクトに適用され、キーと値のペアを格納および取得するためにバケットのインデックスを計算します。

Capacityは、HashMap内のバケットの数です。初期容量は、 M apが作成されたときの容量です。最後に、HashMapのデフォルトの初期容量は16です。

HashMap の要素数が増えると、容量が拡張されます。負荷率は、マップの容量をいつ増やすかを決定する尺度です。デフォルトの負荷率は75です。 % of容量。

HashMapのしきい値は、おおよそ現在の容量と負荷率の積です。再ハッシュは、すでに保存されているエントリのハッシュコードを再計算するプロセスです。簡単に言うと、ハッシュテーブルのエントリ数がしきい値を超えると、 Map が再ハッシュされ、以前の約2倍のバケット数になります。

ハッシュ関数が2つの異なるキーに対して同じバケット位置を返すと、衝突が発生します。

HashMapを作成しましょう。

Map<String, String> mapWithDefaultParams = new HashMap<>();
mapWithDefaultParams.put("1", "one");
mapWithDefaultParams.put("2", "two");
mapWithDefaultParams.put("3", "three");
mapWithDefaultParams.put("4", "four");

マップの構造は次のとおりです。

ご覧のとおり、 HashMap は、デフォルトの初期容量（16）とデフォルトの負荷率（0.75）で作成されました。また、しきい値は16 * 0.75 = 12です。これは、12番目のエントリ（キーと値のペア）が追加された後、容量が16から32に増加することを意味します。

4. カスタム初期容量と負荷率

前のセクションでは、デフォルトのコンストラクターを使用してHashMapを作成しました。次のセクションでは、初期容量と負荷率をコンストラクターに渡すHashMapを作成する方法を説明します。

4.1. 初期容量あり

まず、初期容量でMapを作成しましょう。

Map<String, String> mapWithInitialCapacity = new HashMap<>(5);

初期容量（5）とデフォルトの負荷率（0.75）で空のMapを作成します。

4.2. 初期容量と負荷率

同様に、初期容量と負荷率の両方を使用してMapを作成できます。

Map<String, String> mapWithInitialCapacityAndLF = new HashMap<>(5, 0.5f);

ここでは、初期容量が5、負荷率が0.5の空のMapを作成します。

5. パフォーマンス

初期容量と負荷率を柔軟に選択できますが、それらを賢く選択する必要があります。どちらもマップのパフォーマンスに影響します。これらのパラメーターがパフォーマンスにどのように関連しているかを詳しく見ていきましょう。

5.1. 複雑

ご存知のように、 HashMap は、キーと値のペアを格納するためのベースとして内部的にハッシュコードを使用します。 hashCode（）メソッドが適切に記述されている場合、HashMapはすべてのバケットにアイテムを分散します。したがって、 HashMapは、一定時間O（1）でエントリを格納および取得します。

ただし、アイテム数を増やしてバケットサイズを固定すると問題が発生します。各バケットにより多くのアイテムが含まれ、時間の複雑さを妨げます。

解決策は、アイテムの数が増えたときにバケットの数を増やすことができるということです。その後、すべてのバケットにアイテムを再配布できます。このようにして、各バケットに一定数のアイテムを保持し、 O（1）の時間計算量を維持することができます。

ここで、負荷率は、バケットの数を増やすタイミングを決定するのに役立ちます。負荷率が低くなると、空きバケットが増えるため、衝突の可能性が低くなります。これにより、マップのパフォーマンスが向上します。したがって、時間計算量を低くするには、負荷率を低く保つ必要があります。

HashMap は通常、 O（n）のスペースの複雑さを持ちます。ここで、nはエントリの数です。 負荷率の値を高くすると、スペースオーバーヘッドは減少しますが、ルックアップコストは増加します。

5.2. 再ハッシュ

マップのアイテム数がしきい値を超えると、マップの容量が2倍になります。前述のように、容量を増やす場合は、すべてのエントリ（既存のエントリと新しいエントリを含む）をすべてのバケットに均等に分散する必要があります。ここでは、再ハッシュが必要です。つまり、既存のキーと値のペアごとに、容量を増やしてパラメーターとしてハッシュコードを再度計算します。

基本的に、負荷率が高くなると、複雑さが増します。再ハッシュは、すべての操作で低い負荷率と低い複雑さを維持するために行われます。

マップを初期化しましょう：

Map<String, String> mapWithInitialCapacityAndLF = new HashMap<>(5,0.75f);
mapWithInitialCapacityAndLF.put("1", "one");
mapWithInitialCapacityAndLF.put("2", "two");
mapWithInitialCapacityAndLF.put("3", "three");
mapWithInitialCapacityAndLF.put("4", "four");
mapWithInitialCapacityAndLF.put("5", "five");

そして、マップの構造を見てみましょう。

それでは、マップにエントリを追加しましょう。

mapWithInitialCapacityAndLF.put("6", "Six");
mapWithInitialCapacityAndLF.put("7", "Seven");
//.. more entries
mapWithInitialCapacityAndLF.put("15", "fifteen");

そして、Map構造をもう一度観察してみましょう。

再ハッシュは複雑さを低く抑えるのに役立ちますが、コストのかかるプロセスです。大量のデータを保存する必要がある場合は、十分な容量のHashMapを作成する必要があります。これは、自動再ハッシュよりも効率的です。

5.3. 衝突

衝突はハッシュコードアルゴリズムの不良が原因で発生する可能性があり、マップのパフォーマンスが低下することがよくあります。

Java 8より前のバージョンでは、Javaの HashMap は、 LinkedList を使用してマップエントリを格納することにより、衝突を処理します。キーが別のエントリがすでに存在する同じバケットにある場合、そのキーはLinkedListの先頭に追加されます。最悪の場合、これにより複雑さが O（n）に増加します。

この問題を回避するために、Java 8以降のバージョンでは、 LinkedList の代わりにバランスツリー（赤黒木とも呼ばれます）を使用して、衝突したエントリを格納します。これにより、 HashMapの最悪の場合のパフォーマンスがO（n）から O（log n）に向上します。

HashMap 最初に使用します LinkedList。次に、エントリの数が特定のしきい値を超えると、 LinkedList バランスの取れた二分木で。 TREEIFY_THRESHOLD定数がこのしきい値を決定します。現在、この値は8です。つまり、同じバケットに8つを超える要素がある場合、Mapはツリーを使用してそれらを保持します。

6. 結論

この記事では、最も一般的なデータ構造の1つであるHashMapについて説明しました。また、負荷率と容量がパフォーマンスにどのように影響するかについても説明しました。

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

getdocs

13036