18 ハッシュテーブル
1. ハッシュテーブルとは
ハッシュテーブル（hash table）とは、キー（key）から
値（value）を取り出すための超高速なデータ構造です。
「キーを計算で配列の番号に変換して、その場所に値を格納する」という仕組みで、
探索・挿入・削除がいずれも平均 O(1) で行えます。
身近な例：電話帳。「人名（キー）」を入力すると「電話番号（値）」がすぐに引ける。
プログラミングでは「辞書（dict）」「連想配列」「マップ（Map）」などと呼ばれます。
2. ハッシュ関数
ハッシュ関数（hash function）とは、キーを配列の添字（インデックス）に変換する関数です。
どんなキーが来ても、決まった範囲の整数を返します。
ハッシュ関数の例
○ 整数型: hash(文字列型: key, 整数型: size)
整数型: sum ← 0
for ( i を 0 から key の長さ - 1 まで 1 ずつ増やす )
sum ← sum + key[i] の文字コード
endfor
return sum MOD size // 配列サイズの範囲に収める
ハッシュ関数に求められる条件：
- 計算が速い（O(1) 相当）
- 結果が均等にばらつく（同じ番号が偏らない）
- 同じキーからは必ず同じハッシュ値を返す
3. ハッシュテーブルの仕組み
キーから計算したハッシュ値を配列の添字として使い、その場所に値を格納します。
4. ハッシュ衝突
異なるキーから同じハッシュ値が出てしまうことをハッシュ衝突（collision）といいます。
実用上は完全に避けることができず、対策が必要です。
例：
hash("apple") = 3
hash("grape") = 3 ← 同じ場所に格納したい！衝突
対策①：チェイン法（オープンハッシュ法）
同じ添字に複数の値を保存するため、各スロットを連結リストにする。
対策②：開番地法（オープンアドレス法）
衝突したら、次の空きスロットを探して入れる。
// hash("apple")=3 だが、3 がすでに埋まっていたら
// → 4 をチェック → 4 も埋まっていたら → 5 をチェック → ...
// 空きが見つかった場所に格納する（線形探査法）
| 方式 | 長所 | 短所 |
|---|
| チェイン法 | 削除が簡単・実装も容易 | 連結リストの追加メモリが必要 |
| 開番地法 | メモリが追加で要らない | 削除が複雑・テーブルが埋まると遅い |
5. ハッシュテーブルの計算量
| 操作 | 平均 | 最悪 |
|---|
| 挿入 | O(1) | O(n) |
| 検索 | O(1) | O(n) |
| 削除 | O(1) | O(n) |
最悪 O(n) になる場合：
ハッシュ関数が悪く、すべてのキーが同じ添字に集まってしまうと、連結リストを全部たどることになり O(n) になります。
実用上は良いハッシュ関数を選ぶことで平均 O(1) を維持できます。
6. ハッシュテーブルの使い所
| 用途 | 例 |
|---|
| キーから値を素早く取り出す | 辞書アプリ、データベースのインデックス |
| 重複の検出 | 「この単語は前に出てきた？」を高速判定 |
| カウント（出現回数） | テキスト内の単語頻度カウント |
| キャッシュ | 計算結果を保存して再利用 |
| パスワード保存 | パスワード自体ではなくハッシュ値を保存 |
7. 配列・連結リスト・ハッシュテーブルの比較
| 操作 | 配列 | 連結リスト | ハッシュテーブル |
|---|
| 添字アクセス | O(1) | O(n) | — |
| キーで検索 | O(n) | O(n) | O(1) |
| 挿入 | O(n) | O(1) ※ | O(1) |
| 削除 | O(n) | O(1) ※ | O(1) |
| 順序保持 | あり | あり | なし |
※ノードを把握済みの場合
8. 理解度チェック問題
問題18-1
ハッシュ関数の役割として正しいものはどれですか。
解説を表示
正解：イ
ハッシュ関数はキーを配列の添字に変換します。これにより、キーから O(1) で格納場所が決まります。
問題18-2
ハッシュテーブルにおける「ハッシュ衝突」とは何ですか。
解説を表示
正解：ウ
「衝突」は、別のキーが同じ添字を返してしまう状況。ハッシュ関数の性質上避けられないため、対策（チェイン法・開番地法）が必要。
問題18-3
ハッシュテーブルの検索の平均計算量はどれですか。
解説を表示
正解：ア
ハッシュ関数の計算 1 回で添字が決まり、その場所を直接アクセスするため平均 O(1)。
ただし衝突が多いと最悪で O(n) になります。
問題18-4
サイズ 7 のハッシュテーブルに、ハッシュ関数 hash(x) = x MOD 7 を使って次の値を順に格納します。
[15, 22, 8, 12]
このうち、衝突が起きるのはどの値ですか。
解説を表示
正解：イ
15 MOD 7 = 1
22 MOD 7 = 1 ← 15 と同じ添字！衝突
8 MOD 7 = 1 ← また衝突
12 MOD 7 = 5
最初に衝突するのは 22。
問題18-5
次のうち、ハッシュテーブルが特に効果を発揮する場面はどれですか。
解説を表示
正解：ア
ハッシュテーブルは「キーから値を引く」操作に最適化されている。
イ・ウ（順序や範囲）は二分探索木のほうが得意。エはキューが得意。