HashMapについて英語で説明すると、より役に立つと思います。

HashMapとは？ キーと値は何でもかまいません。 たとえば、ゲームを作成する場合、すべてのユーザー名を文字列のリストで表されるフレンド リストにリンクすることがあります。 ソートされた配列は、バイナリ検索で O(log n) で特定の値を見つけることができます。 しかし、HashMapは特定のキーが含まれているかどうかをO(1)でチェックすることができる。 すべてのキーは一意でなければならない。

ハッシュマップはどのように動作するのか

ハッシュマップはバックグラウンドで配列を使用する。 配列の各要素は別のデータ構造 (通常、リンク リストまたはバイナリ検索ツリー) です。 HashMap は、配列内のキーの値をどこに配置するかを決定するために、キーに対する関数を使用します。 たとえば、HashMapが文字列を受け入れる場合、以下のようなハッシュ関数が考えられます。

A. Return the ASCII value of the first letter.B. Return the sum of the ASCII values of every character in the String.C. Return the ASCII value of the last character in the String.

返された値は、配列に入るインデックスを決定します。

But Wait! There’s a Problem!

return Math.abs(number%hashMapArray.length);

衝突:

複数のキーがあると、ハッシュ関数が同じインデックスを生成する可能性はないのでしょうか。 はい。 たとえば、文字列のハッシュ マップで上記の最初のハッシュ関数を使用した場合、同じ文字で始まる 2 つの文字列は、同じ配列インデックスを生成します。

衝突を扱う手法の1つにChainingというものがあります。 配列の各要素はリンクリスト (または同様のデータ構造) であるため、同じハッシュ値を持つ複数のキーは、同じリンクリストまたは「バケット」に配置されます。 その後、ハッシュマップはハッシュ関数でハッシュコードを計算し、特定のリンクリストに同じキーを持つ値があるかどうかを検索することで、値を取り出すことができるようになっています。

良いハッシュ関数は、衝突を避けるように書かなければなりません。

チェーン接続の利点:

配列がオーバーフローしない

データを簡単に削除できる

チェーン接続の欠点：

– バケットに非常に長いリンクリストが含まれると、パフォーマンスが落ちることがある

バケットの数に対するエントリの合計数は負荷率（load factor）と呼ばれています。 ロードファクターが低すぎる場合、多くのスペースが浪費されます。 ロードファクターが高すぎると、ハッシュの利点が失われます。 ロードファクターの良い妥協点は0.75

である。