1 歩ずつ動かす
命令の列 (左から順に実行する)
- insert 12
- insert 7
- insert 3
- insert 22
- search 22
- search 8
- search 10
- ハッシュ値の計算
- なし
- 使うバケット
- なし
- いま使っているバケット、比べているノード
- 付けたばかりのノード
- 見つかったノード、同じキーがあったノード
1 歩目 / 全 22 歩実行した命令 0 個比べた回数 0 回入っているキー 0 個
バケットは 0 から 4 までの 5 つ、どれも空です。7 個の命令を順に実行します。
いま動いている疑似コードの行
- 1insert(key) と search(key)
- 2i = key を 5 で割った余り (ハッシュ値)。バケット i を選ぶ
- 3バケット i の鎖を、先頭から順に key と比べる
- 4同じキーがあれば、search は見つかって終わる (insert は入れない)
- 5最後まで無ければ、search は無いと分かって終わる
- 6insert は、鎖の最後に key のノードを付ける
見本を変える
予想してみる
いまは 1 歩目です。
12 は、どのバケットに入るでしょう。
今回わかること
- キーから入れる場所 (バケット) を計算で決める、ハッシュ関数の役目
- 別のキーが同じバケットになる衝突と、鎖でつなぐ方法 (チェイン法)
- 比べる回数が、バケットの鎖の長さで決まること
前提
- 割り算の余り
- 連結リスト (ノードが次のノードを指す形)
どんな入れ物か
ハッシュテーブルは、キーを計算して入れる場所 (バケット) を決める入れ物です。キーを 5 で割った余りのように、キーから番号を決める計算をハッシュ関数と呼びます。探すときも同じ計算で場所が分かるので、全部を見て回る必要がありません。
別のキーが同じ番号になることがあり、これを衝突と呼びます。チェイン法では、バケットごとに連結リストを持ち、同じバケットに入ったキーを鎖のようにつなぎます。探すときは、そのバケットの鎖だけを比べます。
手順と具体例
- 1キーからハッシュ値を求め、バケットを選ぶ
- 2そのバケットの鎖を、先頭から順にキーと比べる
- 3同じキーがあれば、search は見つかって終わる (insert は入れない)
- 4最後まで無ければ、search は「無い」で終わり、insert は鎖の最後に付ける
| 命令 | バケット | 比べた回数 | 結果 |
|---|---|---|---|
| insert 12 | 2 | 0 回 | 付けた |
| insert 7 | 2 | 1 回 | 付けた |
| insert 3 | 3 | 0 回 | 付けた |
| insert 22 | 2 | 2 回 | 付けた |
| search 22 | 2 | 3 回 | 見つかった |
| search 8 | 3 | 1 回 | 無い |
| search 10 | 0 | 0 回 | 無い |
比べる回数と計算量
| 場合 | 比べる回数 | 計算量 |
|---|---|---|
| キーがばらけている | 0 回から 1 回ほど (鎖が短い) | O(1) |
| 平均 | 鎖の長さの平均 (キーの数 ÷ バケットの数) | O(1) |
| 全部が同じバケットに集まる | n 回 (1 本の鎖を全部) | O(n) |
n はキーの数です。実際のハッシュテーブルは、キーが増えるとバケットの数も増やして鎖を短く保つので、平均では O(1) と呼びます。この見本はバケットが 5 つで決まっているため、キーが増えるほど鎖が長くなります。「全部ぶつかる例」では、20 を探すのに 4 回かかります。
使いどころ
向いているとき
- キーから値を直接引きたいとき (辞書、名簿、出てきた回数の数え上げ)
- 「もう入っているか」を何度も確かめたいとき (重複の検出)
向いていないとき
- キーを小さい順に取り出したいとき (二分探索木などを使う)
- ハッシュ値が偏りやすいキーのとき (鎖が長くなって遅い)
コード
疑似コード
- 1insert(key) と search(key)
- 2i = key を 5 で割った余り (ハッシュ値)。バケット i を選ぶ
- 3バケット i の鎖を、先頭から順に key と比べる
- 4同じキーがあれば、search は見つかって終わる (insert は入れない)
- 5最後まで無ければ、search は無いと分かって終わる
- 6insert は、鎖の最後に key のノードを付ける
実際のコード
python実行可能
出力
▶ 実行ボタンを押すと結果がここに表示されます
Python と JavaScript は、書き換えて「実行」を押すと、その場で結果が出ます。Java は読むだけの欄です。
よくある疑問
- 衝突が起きたら、エラーになりますか？
- なりません。チェイン法では、同じバケットのキーを鎖でつなぐだけです。ただし鎖が長くなるほど、比べる回数が増えます。
- ハッシュ関数に「5 で割った余り」を使うのは、なぜですか？
- 計算が一瞬で終わり、結果が必ず 0 から 4 に収まるからです。実際のハッシュ関数は、文字列のようなキーを数に直してから、バケットの数で割った余りを取ります。
- ほかの鎖を調べないのに、無いと言い切れるのはなぜですか？
- 同じキーは、必ず同じバケットに入るからです。ほかのバケットは、そのキーの入る場所ではありません。
