logo

JavaでのHashMapの仕組み


ハッシュとは何ですか

これは、オブジェクトを整数値に変換するプロセスです。整数値は、インデックス作成と高速な検索に役立ちます。

ハッシュマップとは

HashMap は Java コレクション フレームワークの一部です。ハッシュと呼ばれる手法が使用されます。マップインターフェイスを実装します。データをKeyとValueのペアに格納します。 HashMap にはノードの配列が含まれており、ノードはクラスとして表されます。キーと値を格納するために内部で配列と LinkedList データ構造を使用します。 HashMap には 4 つのフィールドがあります。

JavaでのHashMapの仕組み

HashMap の内部動作を理解する前に、hashCode() メソッドとquals() メソッドについて理解しておく必要があります。

Pythonソートタプル
    等しい():2 つのオブジェクトが等しいかどうかをチェックします。キーが等しいかどうかを比較します。 Objectクラスのメソッドです。上書きすることができます。 equals() メソッドをオーバーライドする場合は、hashCode() メソッドをオーバーライドすることが必須です。ハッシュコード():オブジェクトクラスのメソッドです。オブジェクトのメモリ参照を整数形式で返します。メソッドから受け取った値がバケット番号として使用されます。バケット番号は、マップ内の要素のアドレスです。 null Keyのハッシュコードは0です。バケット:ノードの配列をバケットと呼びます。各ノードは LinkedList のようなデータ構造を持っています。複数のノードが同じバケットを共有できます。容量が違うのかもしれません。
JavaでのHashMapの仕組み

HashMap にキーと値のペアを挿入する

put() メソッドを使用して、キーと値のペアを HashMap に挿入します。 HashMap のデフォルトのサイズは 16 (0 ~ 15) です。

次の例では、HashMap に 3 つの (キー、値) ペアを挿入します。

 HashMap map = new HashMap(); map.put('Aman', 19); map.put('Sunny', 29); map.put('Ritesh', 39); 

キーと値のペアが HashMap に保存されるインデックスを見てみましょう。 put() メソッドを呼び出すと、キー「Aman」のハッシュ コードが計算されます。 「Aman」のハッシュ コードが 2657860 であるとします。キーをメモリに保存するには、インデックスを計算する必要があります。

指数の計算

インデックスにより配列のサイズが最小化されます。インデックスの計算式は次のとおりです。

 Index = hashcode(Key) & (n-1) 

ここで、n は配列のサイズです。したがって、「Aman」のインデックス値は次のようになります。

 Index = 2657860 & (16-1) = 4 

値 4 は、キーと値が HashMap に格納される計算されたインデックス値です。

ホバリングCSS
JavaでのHashMapの仕組み

ハッシュ衝突

これは、計算されたインデックス値が 2 つ以上のキーで同じである場合に当てはまります。別のキー「Sunny」のハッシュ コードを計算してみましょう。 「Sunny」のハッシュ コードが 63281940 であるとします。キーをメモリに保存するには、インデックス式を使用してインデックスを計算する必要があります。

 Index=63281940 & (16-1) = 4 

値 4 は、キーが HashMap に保存される計算されたインデックス値です。この場合、equals() メソッドは両方のキーが等しいかどうかをチェックします。キーが同じ場合は、値を現在の値に置き換えます。それ以外の場合は、LinkedList を通じてこのノード オブジェクトを既存のノード オブジェクトに接続します。したがって、両方のキーはインデックス 4 に格納されます。

JavaでのHashMapの仕組み

同様に、キー「Ritesh」を保存します。キーのハッシュ コードが 2349873 であるとします。インデックス値は 1 になります。したがって、このキーはインデックス 1 に格納されます。

JavaでのHashMapの仕組み

HashMap の get() メソッド

get() メソッドは、キーによって値を取得するために使用されます。 Key が分からない場合、値は取得されません。 get(K Key) メソッドが呼び出されると、Key のハッシュ コードが計算されます。

キー「Aman」を取得する必要があるとします。次のメソッドが呼び出されます。

並べ替えられた配列リスト
 map.get(new Key('Aman')); 

ハッシュ コードは 2657860 として生成されます。次に、インデックス式を使用して 2657860 のインデックス値を計算します。上で計算したように、インデックス値は 4 になります。 get() メソッドは、インデックス値 4 を検索します。最初の要素 Key と指定された Key を比較します。両方のキーが等しい場合は値を返し、そうでない場合はノード内の次の要素が存在するかどうかを確認します。このシナリオでは、これはノードの最初の要素として検出され、値 19 を返します。

別のキー「Sunny」を取得しましょう。

キー「Sunny」のハッシュ コードは 63281940 です。 put() メソッドで計算したように、63281940 の計算されたインデックス値は 4 です。配列のインデックス 4 に移動し、最初の要素のキーと指定されたキーを比較します。キーも比較します。このシナリオでは、指定されたキーは 2 番目の要素であり、ノードの次の要素は null です。 2 番目の要素 Key と指定された Key を比較し、値 29 を返します。ノードの次の要素が null の場合は null を返します。