ハッシュテーブルとは？
ハッシュテーブル(Hash Table)は、キー(key)をハッシュ関数で配列インデックスに変換し、平均O(1)で値を保存・検索する構造です。Pythonの dict、Javaの HashMap、JavaScriptの Map/オブジェクトはすべてこの原理で動きます。
核心の一行: 「キーを計算して直接その場所へ行く」。 整列や逐次探索なしに、キーさえわかれば位置を計算して直接アクセスします。
核心: ハッシュ関数 + 衝突処理
ハッシュ関数は任意のキーを整数に変え、% 容量 で配列インデックスを作ります。良いハッシュ関数はキーをインデックス全体に均等にばらまきます。
問題は衝突(collision) — 異なるキーが同じインデックスを指す場合です。代表的な解決策が2つあります。
- •チェイニング(chaining): 各バケットを連結リストにし、衝突した項目を連ねる。
- •開番地法(open addressing): 衝突したら一定の規則(線形探索など)で次の空きを探す。
動作原理
ステップ1. 挿入: idx = hash(key) % cap のバケットに(キー, 値)を入れます。埋まっていれば衝突処理規則に従います。
ステップ2. 検索: 同じ方法で idx を求め、そのバケット内でキーを直接比較して目的の項目を探します(ハッシュが同じでもキーは異なり得るため)。
ステップ3. リサイズ(再ハッシュ): 充填率(負荷率)が閾値を超えたら配列を拡張し、全項目を新容量で再ハッシュします。衝突が減り平均性能が保たれます。
AlgoNoteの可視化は、キーがどのバケットに入るか、衝突がどう解かれるかをステップごとに示します。
時間計算量と空間計算量
| 操作 | 平均 | 最悪 |
|---|---|---|
| 挿入/検索/削除 | O(1) | O(n) |
| 空間 | O(n) | O(n) |
最悪(全キーが1バケットに集中)はO(n)ですが、良いハッシュ関数と適切な負荷率管理で平均O(1)が得られます。
例で追ってみる
容量5、チェイニング、hash(k)=k とします。
- •12挿入 → 12%5=2番バケット
- •17挿入 → 17%5=2番バケット → 12と衝突 → 同じバケットに連ねる(チェイニング)
- •検索17 → 2番バケットのリストを辿りキー17を見つける
よくあるミス
- •悪いハッシュ関数: インデックスが偏ると衝突が急増しO(n)に近づきます。
- •負荷率の放置: リサイズしないとバケットごとに項目が積もり遅くなります。
- •可変キーの使用: 入れた後にキーを変えるとハッシュ値が変わり再び見つけられません。
AlgoNoteで直接確認しましょう
キーがハッシュされバケットに入り、衝突がチェイニングで解かれる過程をAlgoNoteでステップごとに確認できます。