ハッシュテーブルは、ハッシュ関数でキーをバケット番号に変換します。適切な関数と負荷率なら検索は平均O(1)ですが、異なるキーが同じバケットに対応して衝突することがあります。
7バケットで挿入・検索・衝突処理を体験するハッシュテーブルシミュレーター
1. 衝突の処理方法を選択
2. キーの挿入・検索
文字コードの合計を7で割った余りをバケット番号にします。
保存したキー数0
負荷率（キー数÷バケット数）0.00
今回調べたスロット数0
cat、act、tacは文字コードの合計が同じなので、この例では衝突します。「衝突の例を挿入」で同様の5キーを追加できます。
ハッシュ関数
この例は文字コードを合計し、バケット数で割った余りを使います。簡単ですが文字の順序を無視するため、衝突しやすい関数です。実用的な関数は文字の値と位置を混ぜ、キーを均等に分散させます。
衝突への2つの対処法
チェイン法は各バケットにリストを持たせます。複数のキーを保存できますが、チェーンが長くなると線形探索が必要です。
線形探索法は連続するスロットを調べ、空きを探します。検索も同じ経路をたどり、空きで終了します。テーブルが埋まるとクラスタリングで性能が低下するため、設計に応じて負荷率0.7前後などで拡張します。