ハッシュテーブル

コンピュータサイエンスにおいて、ハッシュテーブル（ハッシュマップ)はキーを値にマッピングできる連想配列の機能を持ったデータ構造です。ハッシュテーブルはハッシュ関数を使ってバケットやスロットの配列へのインデックスを計算し、そこから目的の値を見つけることができます。

理想的には、ハッシュ関数は各キーを一意のバケットに割り当てますが、ほとんどのハッシュテーブルは不完全なハッシュ関数を採用しているため、複数のキーに対して同じインデックスを生成した時にハッシュの衝突が起こります。このような衝突は何らかの方法で対処する必要があります。

チェイン法によるハッシュの衝突の解決例