ほとんどのJava開発者は、MAP、特にHashmapを使用しています。 HashMapは、データを保存して取得するためのシンプルだが強力な方法です。しかし、ハッシュマップが内部的にどのように機能するかを知っている開発者は何人いますか？数日前、私はこの基本的なデータ構造を深く理解するために、java.util.hashmap（Java 7およびJava 8を含む）の多くのソースコードを読みました。この投稿では、java.util.hashmapの実装について説明し、Java 8の実装に追加された新しい機能について説明し、ハッシュマップを使用する際のパフォーマンス、メモリ、およびいくつかの既知の問題について説明します。
内部ストレージ
Java Hashmapクラスは、Map <K、V>インターフェイスを実装します。このインターフェイスの主な方法には次のものがあります。
v put（k key、v value）v get（object key）v remover（object key）boolean containsKey（オブジェクトキー）
HashMapは、内部クラスのエントリ<K、V>を使用してデータを保存します。この内部クラスは、2つの追加データを持つ単純なキー価値ペアです。
Hashmapがリンクリストなどのオブジェクトを保存できるように、別のエントリへの参照。
キーを表すために使用されるハッシュ値。この値を保存すると、ハッシュマップが必要になるたびにキーに対応するハッシュ値を再生することを防ぐことができます。
これは、Java 7の下のエントリ<K、V>のコードの一部です。
静的クラスエントリ<k、v>はmap.entry <k、v> {final k key; v value; entry <k、v> next; int hash;…}を実装します。HashMapは、データを複数の単方向リスト（バケツまたはコンテナオービンと呼ばれることもあります）に保存します。すべてのリストはエントリアレイ（エントリ<k、v> []アレイ）に登録され、この内部配列のデフォルトの長さは16です。
次の図は、無視可能なオブジェクトの配列を含むハッシュマップインスタンスの内部ストレージについて説明しています。各オブジェクトは別のオブジェクトに接続されているため、リンクリストが作成されます。
同じハッシュ値を持つすべてのキーは、同じリンクリスト（バケット）に配置されます。異なるハッシュを持つキーは、同じバケツに入る可能性があります。
ユーザーがput（k key、v value）またはget（object key）を呼び出すと、プログラムはオブジェクトが入力するバケットのインデックスを計算します。プログラムは、対応するリストを繰り返して、同じキーを持つエントリオブジェクトを見つけます（キーのequals（）メソッドを使用）。
get（）を呼び出す場合、プログラムは値に対応するエントリオブジェクトを返します（エントリオブジェクトが存在する場合）。
（k key、v value）の呼び出しの場合、エントリオブジェクトが既に存在する場合、プログラムは値を新しい値に置き換えます。そうしないと、プログラムは一方向リンクリストのヘッダーに新しいエントリ（キーと値）を作成します。
バケットのインデックス（リンクリスト）は、マップの3つのステップで生成されます。
最初にキーのハッシュコードを取得します。
このプログラムは、キーの悪いハッシュ関数をブロックするハッシュコードを繰り返します。これにより、すべてのデータが内部配列の同じインデックス（バケット）に配置される可能性があるためです。
このプログラムは、重複したハッシュコードを取得し、配列長（最小1）のビットマスクを使用します。この操作により、インデックスが配列のサイズよりも大きくならないようにします。計算された最適なモジュラス関数と考えることができます。
インデックスを生成するためのソースコードは次のとおりです。
// keystatic int hash（int h）{h ^ =（h >>> 20） ^（h >>> 12）のハッシュコードを取得するJava 7の「rehash」関数。 0：（h = key.hashcode（）） ^（h >>> 16）;} // rehashed hashstatic ind indexfor（int h、int length）{return h＆（length-1）;}からインデックスを返す関数より効率的に動作するには、内側の配列のサイズが2のパワーでなければなりません。理由を確認しましょう。
配列の長さが17であると仮定すると、マスクの値は16（配列の長さ1）です。 16のバイナリ表現は0…010000であるため、任意の値hに対して「h＆16」の結果は16または0です。これは、長さ17のアレイが2つのバケットにのみ適用できることを意味します。1つは0、もう1つは16であり、あまり効率的ではありません。ただし、アレイの長さを16などの電源に設定すると、ビットワイズインデックスが「H＆15」に機能します。 15のバイナリ表現は0…001111であり、インデックス式による値出力は0〜15の範囲であるため、長さ16の配列を完全に使用できます。例えば：
H = 952の場合、そのバイナリ表現は0..011101111000で、対応するインデックスは0…01000 = 8です
H = 1576の場合、そのバイナリ表現は0..011000101000で、対応するインデックスは0…01000 = 8です
H = 12356146の場合、そのバイナリ表現は0..01011111001000101010010の場合、対応するインデックスは0…00010 = 2です。
H = 59843の場合、そのバイナリ表現は0..01110100111000011である場合、対応するインデックスは0…00011 = 3です
このメカニズムは開発者に対して透明です。長さ37のハッシュマップを選択すると、マップは37（64）を超える次の電力値を内部配列の長さとして自動的に選択します。
自動的にサイズを変更します
インデックスを取得した後、get（）、put（）、またはremove（）メソッドは、対応するリンクリストにアクセスして、指定されたキーのエントリオブジェクトが既に存在するかどうかを確認します。この方法では、このメカニズムがパフォーマンスの問題を引き起こす可能性があります。この方法では、エントリオブジェクトが存在するかどうかを確認するためにリスト全体に反復する必要があります。内部配列の長さにデフォルト値が16で、2,000,000のレコードを保存する必要があると仮定します。最良のケースでは、リンクされたリストごとに125,000個のエントリオブジェクトがあります（2,000,000/16）。 get（）、remove（）、およびput（）メソッドは、実行されるたびに125,000回の反復が必要です。これを回避するために、HashMapは内部配列の長さを増やすことができ、リンクリストに少数のエントリオブジェクトのみが保持されるようにします。
ハッシュマップを作成すると、次のコンストラクターを介して初期の長さとロードファクターを指定できます。
</pre> public hashmap（int initialcapacity、float loadfactor）<pre>
パラメーターを指定していない場合、デフォルトの初期容量値は16で、デフォルトのLoadFactor値は0.75です。 InitialCapacityは、内部配列のリンクリストの長さを表します。
Put（…）メソッドを使用して新しいキー値ペアをマップに追加すると、メソッドは内側の配列の長さを増やす必要があるかどうかをチェックします。これを達成するために、マップは2つのデータを保存します。
マップサイズ：Hashmapのレコード数を表します。 HashMapに挿入または削除するときに値を更新します。
しきい値：内部配列*loadFactorの長さに等しく、このしきい値は、内部配列の長さが調整されるたびに同時に更新されます。
新しいエントリオブジェクトを追加する前に、Put（…）メソッドは、現在のマップのサイズがしきい値よりも大きいかどうかを確認します。しきい値よりも大きい場合、現在の内部配列の2倍の長さの新しい配列が作成されます。新しい配列のサイズが変更されたため、インデックス関数（つまり、ビット操作の結果が「キーのハッシュ値」を返すビット操作の結果」も変更されます。配列のサイズを変更すると、2つの新しいバケット（リンクリスト）が作成され、既存のすべてのエントリオブジェクトをバケットに再割り当てします。配列のサイズを調整するという目標は、リンクリストのサイズを縮小して、put（）、remove（）、およびget（）メソッドの実行時間を短縮することです。同じハッシュ値のキーに対応するすべてのエントリオブジェクトについて、それらはサイズ変更後に同じバケツに割り当てられます。ただし、2つのエントリオブジェクトのハッシュ値が異なる場合、それらは以前に同じバケツの上にあった場合、調整後、それらがまだ同じバケツの上にいるという保証はありません。
この画像は、調整前および調整後の内部配列の状況を説明しています。アレイの長さを調整する前に、エントリオブジェクトEを取得するために、マップは5つの要素を含むリンクリストを反復する必要があります。配列の長さを調整した後、同じget（）メソッドは、2つの要素を含むリンクリストをトラバースする必要があるため、配列の長さを調整した後のget（）メソッドの実行速度は2回増加します。
スレッドの安全
あなたがすでにHashmapに非常に精通しているなら、あなたはそれがスレッド安全ではないことを間違いなく知っていますが、なぜですか？たとえば、既存のデータのみをマップに挿入する作家スレッド、マップからデータを読み取るリーダースレッドがあるとします。なぜそれが機能しないのですか？
自動サイズ変更メカニズムの下では、スレッドがオブジェクトを追加または取得しようとする場合、マップは古いインデックス値を使用して、エントリオブジェクトが配置されている新しいバケットが見つかりません。
最悪の場合、2つのスレッドが同時にデータを挿入すると、2つのput（）呼び出しが同時に開始され、配列が自動的にサイズ変更されます。 2つのスレッドがリンクリストを同時に変更するため、マップがリンクリストの内部ループで終了する可能性があります。内部ループを使用してリストからデータを取得しようとすると、get（）メソッドは終了しません。
Hashtableは、上記の発生を防ぐスレッドセーフ実装を提供します。ただし、すべての同期CRUD操作は非常に遅いためです。たとえば、スレッド1コールが取得され（key1）、スレッド2コールが取得（key2）、およびスレッド2コールが取得（key3）を取得し、指定された時間に1つのスレッドのみが値を取得できますが、3つのスレッドはすべてこれらのデータに同時にアクセスできます。
Java 5以来、より優れたスレッドセーフハッシュマップの実装：concurrenthashmapがあります。同時マップの場合、バケットのみが同期されるため、複数のスレッドが同じバケットを使用しないか、内部配列をサイズ変更しない場合、Get（）、remove（）、またはput（）メソッドを同時に呼び出すことができます。マルチスレッドアプリケーションでは、このアプローチがより良い選択です。
債券の不変性
ハッシュマップの鍵として文字列と整数を使用するのが良い実装なのはなぜですか？主に彼らが不変だからです！自分で鍵としてクラスを作成することを選択したが、クラスが不変であることを保証することができない場合は、ハッシュマップ内でデータを失う可能性があります。
次のユースケースを見てみましょう。
内部価値が「1」であるキーがあります。
オブジェクトをハッシュマップに挿入すると、そのキーは「1」です。
HashMapは、キーのハッシュコード（つまり "1"）からハッシュ値を生成します。
マップは、新しく作成されたレコードにこのハッシュ値を保存します。
キーの内部値を変更し、「2」に変更します。
キーのハッシュ値は変更されましたが、ハッシュマップはこれを知りません（古いハッシュ値が保存されているため）。
修正されたキーによって対応するオブジェクトを取得しようとします。
マップ新しいキーのハッシュ値（つまり "2"）を計算して、エントリオブジェクトが配置されているリンクリスト（バケット）を見つけます。
ケース1：キーを変更したため、マップは間違ったバケット内のエントリオブジェクトを探しようとしますが、見つかりません。
ケース2：修正されたキーによって生成されたバケツと古いキーによって生成されたバケツが同じであることが幸運です。マップはリンクリストを横断し、同じキーを持つエントリオブジェクトが見つかりました。ただし、キーを見つけるために、MAPは最初にequals（）メソッドを呼び出すことにより、キーのハッシュ値を比較します。変更されたキーは異なるハッシュ値を生成するため（古いハッシュ値はレコードに保存されています）、マップにはリンクリストに対応するエントリオブジェクトを見つける方法はありません。
次に、2つのキー価値ペアをマップに挿入してから、最初のキーを変更して2つのオブジェクトを取得しようとするJavaの例です。マップから返された2番目のオブジェクトのみが、最初のオブジェクトがハッシュマップで「失われた」ことがわかります。
public class mutablekeytest {public static void main（string [] args）{class mykey {integer i; public void seti（integer i）{this.i = i;} public mykey（this.i = i;}@overridepublic int hashcode（）{return i;}@ridepublic（ mykeyのinstance）{return I. equals（（（mykey）obj）.i）;} elsereturn false;}}}}}}}}}}}}}} mymap = new hashmap <>（）; mykey key1 = new mykey（1）; mykey key2 = new mykey（2）; mymap.put（key1）; " + 1）;" + 1）; mymap.int " + 1）; key1key1.seti（3）; string test1 = mymap.get（key1）; string test2 = mymap.get（key2）; system.out.println（ "test1 =" + test1 + "test2 =" + test2）;}}}上記のコードの出力は「test1 = null test2 = test 2」です。予想されるように、MAPには、変更されたキー1に対応する文字列1を取得する機能がありません。
Java 8の改善
Java 8では、Hashmapの内部実装が大幅に変更されています。実際、Java 7は1000行のコードを使用してそれを実装しますが、Java 8は2000行のコードを使用します。前述のことのほとんどは、リンクされたリストを使用してエントリオブジェクトを保存することを除いて、Java 8でまだ正しいです。 Java 8では、引き続き配列を使用していますが、以前のエントリオブジェクトと同じ情報を含むノードに保存され、リンクされたリストも使用します。
Java 8のノードを実装するコードの一部は次のとおりです。
静的クラスノード<k、v>はmap.entry <k、v> {final int hash; final k key; v value; node <k、v> next;では、Java 7と比較して大きな違いは何ですか？さて、ノードはTreenodeに拡張できます。 TreeNodeは、より多くの情報を保存できる赤と黒の木のデータ構造であるため、O（log（n））の複雑さの下で要素を追加、削除、または取得できます。次の例では、TreeNodeによって保存されたすべての情報について説明します。
静的最終クラスTreeNode <k、v> linkedhashmap.entry <k、v> {final int hash; //ノード<k、v> final kキーから継承。 //ノード<k、v> v値から継承。 // node <k、v> node <k、v> nextから継承。 //ノード<k、v> entry <k、v>前、v>後、// linkedhashmap.entry <k、v> parent; treenode <k、v> left; treenode <k、v> right; treenode <k、v> prev; prev; boolean red;赤と黒の木は、自己バランスのとれたバイナリ検索ツリーです。その内部メカニズムは、ノードを追加または削除するかどうかにかかわらず、その長さが常にログ（n）であることを保証します。このタイプのツリーを使用することの最も重要な利点は、内部テーブル内の多くのデータが同じインデックス（バケット）を持っている場合であることです。この時点で、ツリーの検索の複雑さはo（log（n））であり、リンクリストの場合、同じ操作を実行するための複雑さはo（n）です。
ご覧のとおり、リンクリストよりも多くのデータをツリーに保存します。継承の原則によれば、内部テーブルにはノード（リンクリスト）またはTreenode（赤と黒の木）を含めることができます。 Oracleは、次のルールに従ってこれらの2つのデータ構造を使用することを決定します。
- 内部テーブルの指定されたインデックス（バケット）の場合、ノードの数が8を超える場合、リンクされたリストは赤と黒の木に変換されます。
- 内部テーブルの指定されたインデックス（バケット）の場合、ノードの数が6未満の場合、赤と黒の木はリンクリストに変換されます。
この画像では、Java 8 Hashmapの内部配列について説明します。これには、ツリー（バケット0）とリンクされたリスト（バケット1、2、および3）の両方が含まれています。バケット0は、8つ以上のノードが含まれているため、ツリー構造です。
メモリオーバーヘッド
Java 7
Hashmapを使用すると、いくつかのメモリが消費されます。 Java 7では、Hashmapが入力オブジェクトへのキー値のペアをカプセル化すると、エントリオブジェクトには次の情報が含まれています。
次のレコードへの参照事前計算されたハッシュ値（整数）
キーへの参照と値への参照
さらに、Java 7のHashMapは、エントリオブジェクトの内部配列を使用します。 Java 7 HashmapにN要素が含まれており、その内部配列に容量があるとし、追加のメモリ消費量は次のとおりです。
sizeof（integer）* n + sizeof（参照）*（3* n + c）
で：
整数のサイズは4バイトです
参照のサイズは、JVM、オペレーティングシステム、プロセッサに依存しますが、通常は4バイトです。
つまり、総メモリオーバーヘッドは通常、16 * n + 4 *容量バイトであることを意味します。
注：アフターマップが自動的にサイズ変更されますが、容量の値はNより大きい2の次の最小電力です。
注：Java 7から、Hashmapは怠zyなロードメカニズムを採用しています。これは、Hashmapのサイズを指定したとしても、PUT（）メソッドを最初に使用する前にメモリに割り当てられない内部配列（4*容量バイトを消費する）を指定することを意味します。
Java 8
Java 8の実装では、ノードがエントリと同じデータを保存するか、6つの参照とブールプロパティを追加する可能性があるため、メモリ使用量の計算がより複雑になります（TreeNodeかどうかを指定）。
すべてのノードが単なるノードである場合、Java 8 Hashmapで消費されるメモリは、Java 7 Hashmapで消費されたメモリと同じです。
すべてのノードがTreeNodeの場合、Java 8 Hashmapによって消費されるメモリは次のようになります。
n * sizeof（integer） + n * sizeof（boolean） + sizeof（参照） *（9 * n +容量）
ほとんどの標準JVMでは、上記の式の結果は44 * n + 4 *容量バイトです。
パフォーマンスの問題
非対称ハッシュマップvsバランスのとれたハッシュマップ
最良のケースでは、get（）とput（）メソッドの両方にo（1）の複雑さのみがあります。ただし、キーのハッシュ関数を気にしない場合、put（）およびget（）メソッドは非常にゆっくりと実行される場合があります。 put（）およびget（）メソッドの効率的な実行は、内部配列（バケット）の異なるインデックスに割り当てられているデータに依存します。キーのハッシュ関数が適切に設計されていない場合、非対称パーティションが取得されます（内部データのサイズに関係なく）。すべてのput（）およびget（）メソッドは、最大のリンクリストを使用します。これは、リンクリスト内のすべてのレコードを反復する必要があるため、実行が遅くなります。最悪の場合（データのほとんどが同じバケットにある場合）、時間の複雑さはO（n）になります。
これが視覚的な例です。最初のグラフは非対称ハッシュマップを記述し、2番目のグラフは均等化されたハッシュマップを記述します。
Skewedhashmap
この非対称のハッシュマップでは、get（）およびput（）メソッドをバケット0で実行するのに時間がかかります。レコードKの取得には6回の反復が必要です。
このバランスの取れたハッシュマップでは、レコードKを取得するには3回の反復だけが必要です。これら2つのハッシュマップは同じ量のデータを保存し、内部配列は同じサイズです。唯一の違いは、キーのハッシュ関数です。これは、レコードを異なるバケツに配布するために使用されます。
Javaで書かれた極端な例を次に示します。この例では、ハッシュ関数を使用してすべてのデータを同じリンクリスト（バケット）に配置し、2,000,000個のデータを追加しました。
public class test {public static void main（string [] args）{class mykey {integer i; public mykey（this.i = i;}@overridepublic int hashcode（）{return 1;}@overridepublic boolean equals（object obj）{…}}} begin = new <<<<; Hashmap <>（2_500_000,1）;私のマシンの構成はCore i5-2500k @ 3.6gであり、Java 8U40で実行するのに45分以上かかります（45分後にプロセスを停止しました）。同じコードを実行すると、このようなハッシュ関数を使用します。
@overridepublic int hashcode（）{int key = 2097152-1; return key+2097152*i;}実行するには46秒かかりますが、これは以前よりもはるかに優れています！新しいハッシュ関数は、ハッシュパーティションを処理するときに古いハッシュ関数よりも合理的であるため、PUT（）メソッドを呼び出すのはより速いです。今すぐ同じコードを実行しますが、以下のハッシュ関数を使用すると、より良いハッシュパーティションが提供されます。
@overridepublic int hashcode（）{return i;}今では2秒しかかかりません！
ハッシュ機能がどれほど重要かを理解できることを願っています。 Java 7で同じテストを実行した場合、1つ目と2番目のテストは悪化します（Java 7のPut（）メソッドにはO（n）の複雑さがあり、Java 8の複雑さにはO（log（n））があります。
HashMapを使用する場合、キーを最も可能性の高いバケツに広げることができるキーのハッシュ関数を見つける必要があります。これを行うには、ハッシュの競合を避ける必要があります。文字列オブジェクトは、優れたハッシュ機能を備えているため、非常に良い鍵です。整数は、ハッシュが独自の価値であるため、良いことです。
オーバーヘッドのサイズ変更
大量のデータを保存する必要がある場合は、ハッシュマップを作成するときに初期容量を指定する必要があります。これは、希望するサイズに近い必要があります。
これを行わない場合、マップはデフォルトサイズ、つまり16、係数の値は0.75を使用します。 Put（）メソッドへの最初の11個の呼び出しは非常に高速になりますが、12番目（16*0.75）の呼び出しは、長さ32（および対応するリンクリスト/ツリー）を備えた新しい内部配列を作成し、13〜22回目の呼び出しは非常に速くなりますが、23番目（32*0.75）の呼び出しは、新しい内部アレイ（再び）を再作成します。 Put（）メソッドが48番目、96、192nd…と呼ばれると、内部サイズ変更操作がトリガーされます。データの量が大きくない場合、内部配列の再構築の動作は非常に高速になりますが、データの量が多い場合、費やされる時間は数秒から分の範囲です。初期化中にマップの希望のサイズを指定することにより、操作のサイズを変更することによって引き起こされる消費を回避できます。
ただし、ここには欠点もあります。たとえば、2^28などの配列を非常に大きく設定しますが、アレイで2^26バケットを使用するだけで、多くのメモリを無駄にします（この例では約2^30バイト）。
結論は
単純なユースケースの場合、Hashmapがどのように機能するかを知る必要はありません。これは、O（1）、O（n）、およびO（log（n））の違いがわからないためです。しかし、この頻繁に使用されるデータ構造の背後にあるメカニズムを理解することは常に有益です。さらに、これはJava開発者のポジションに関する典型的なインタビューの質問です。
大量のデータ量については、ハッシュマップがどのように機能するかを理解し、キーのハッシュ関数の重要性を理解することが非常に重要になります。
この記事が、ハッシュマップの実装を深く理解するのに役立つことを願っています。