ハッシュテーブルは、キーと値のマッピングであり、挿入、削除、検索（指定されたキーに関連付けられた値を探すこと）の操作を非常に高速で実行できます。 これらの操作の平均時間計算量はO(1)であり、これは定数時間です。
では、どのようにしてそれを達成するのでしょうか？
実装の詳細を見てみましょう。 キーは人の名前を表す文字列で、値は個人の情報を含むオブジェクトであると仮定します。 最初に、オブジェクト（値）を格納するための配列が必要です。
しかし、どのようにして、与えられた文字列（キー）から対応する配列インデックスを直接知ることができるでしょうか？
それがハッシュ関数の役割です。
ハッシュ関数は、キーをハッシュコードに変換し、それを配列インデックスにマッピングします。 関係は「キー → ハッシュコード → 配列インデックス」です。
そして、キーの可能性は無限ですが、ハッシュコードの可能性は有限であり、配列の長さを可能なハッシュコードの数と同じにするのは現実的ではありません。 したがって、可能なハッシュコードの数は可能なキーの数よりも少なく、可能な配列インデックスの数は可能なハッシュコードの数よりも少なくなります。
その結果、異なるキーが同じハッシュコードにマッピングされたり、異なるハッシュコードでも同じ配列インデックスに対応することがあります。
これがハッシュの衝突です。 複数のキーがハッシュテーブル内での同じ場所にマッピングされます。
では、この問題をどのように解決するのでしょうか？
解決方法の一つはチェイニングと呼ばれます。
チェイニングで使用されるアプローチは、単なる配列ではなく、連結リストの配列を使用することです。 したがって、キー「Peter」と「Fuzuki」がどちらも配列インデックス 0 にマップされる場合、以下のように表示されます。
P0とP1は値としてPersonオブジェクトを表します。
重要なポイントとして、キーは対応する値と一緒に保存しておく必要があります。 そうでないと、検索操作時に「Peter」というキーが渡されたとしても、キーを追跡しないとどの値を返すのか分からなくなってしまいます。
参考文献:
- Data Structures: Hash Tables by HackerRank