ハッシュ表：連鎖法

連鎖法はハッシュ関数でキーをバケットへ写します。ここでは h(k) = k mod capacity。衝突したキーは同じバケットの鎖に置き、操作はその鎖だけを調べます。ハッシュの分布がよく負荷率を一定に保てば、平均 O(1) です。

部屋番号の剰余で郵便受けを選び、同じ受け箱の封筒から自分のものを探す形です。衝突の費用は箱の中の検索になります。

連鎖法の仕組み

capacity 個のバケットを持ち、各バケットにキーの鎖を保存します。まず h(k) を計算してそのバケットへ移り、ほかは調べません。

insert(k) はキーを順に比較します。既存キーなら変更せず返します。このレッスンは集合であり、値の更新ではありません。なければ鎖の先頭へ追加します。実際の連結リストの先頭挿入は O(1) ですが、表示する Python の chain.insert(0, ...) は配列リストを使い、要素移動で O(鎖長) を要します。重複検査を含む全体の界は同じでも、この実装の追加部分だけを定数時間とは呼べません。

get(k) は鎖内の一致位置か -1 を返します。delete(k) は一致を外して True を返し、残りをつなぎ直します。墓石は不要で、別のバケットには影響しません。リンク型なら隣接参照の変更ですが、表示する配列リストの削除は同じバケットの後続を移します。

三操作の骨格はハッシュ、鎖の走査、判定です。表全体の衝突を、一バケット内の探索に変えます。

操作をステップで追う

既定は五つの空バケットで、h(k) = k mod 5 です。

1. insert(7)：7 % 5 = 2。空のバケット 2 に追加し [7]。
2. insert(12)：12 % 5 = 2 で衝突。[2][0] = 7 と比較して一致せず、先頭へ追加。[12, 7]。
3. insert(3)：3 % 5 = 3。バケット 3 を [3] にし、2 は走査しない。
4. insert(17)：17 % 5 = 2。[2][0] = 12、[2][1] = 7 と比較し、先頭へ追加。[17, 12, 7]。
5. get(12)：2 に移り、17 の後に位置 1 の 12 を発見。表に四キーあっても比較は二回。
6. delete(12)：同じく 17 を通過し、深さ 1 で一致を削除。バケット 2 は [17, 7]。

get(22) も 2 に写りますが、全鎖を調べて未発見です。失敗検索は鎖全体の長さを支払います。

表示は一鎖六ノードまでで、超過時は表示深度の制約と説明します。1920×1080 の画面に収めるためで、構造の限界ではありません。衝突が続けば鎖は伸ばせますが遅くなります。

画面はバケットを縦、鎖を右へ並べます。カーソルが比較し、一致が緑になり、新キーが先頭へ入ります。ハッシュ、走査、変更の確定を別々に示します。

時間・空間計算量

負荷率 α = n / capacity は一バケット当たりの平均項目数です。

詳しい平均界は O(1 + α) で、一回のハッシュと期待される鎖内探索です。連鎖法は α が 1 を超えられます。オープンアドレス法は新キー用のスロットを必要とします。全キーが一バケットなら長さ n の鎖へ退化します。意図的な衝突入力もあり、適切なハッシュ設計や対象型に応じたランダムシードが対策になります。

空間は n 項目と m バケットの O(n + m)。空でもバケット配列を持ちます。

境界ケース

• 重複挿入：一致で変更なし。キーと値の辞書なら値を更新できるが、このレッスンは集合。
• 空バケット：挿入は即追加。検索・削除は長さ 0 で未発見。
• ないキーの削除：全走査後 False。表は変わらない。
• 全キー衝突：正しさは維持し、探索だけが長くなる。

よくある間違い

• 項目数が容量を超えられないと思う。 1000 バケットに 5000 項目なら平均五つです。拡張閾値は性能目標によるもので、0.75 や 1.0 が普遍の規則ではありません。
• 拡張しない。 バケット数を固定してキーを増やすと鎖が伸びます。負荷率に応じて拡張し、再分配します。
• 重複検査を省く。 複製があると検索は先の一つ、削除も一つだけになり、集合の契約を壊します。
• 単純な剰余が全入力に適すると思う。 規則的なキーは一部に集中します。MurmurHash、SipHash などのビット混合や、対応する型へのシード付きハッシュを検討します。全言語・全キー型が同じ仕組みとは限りません。
• メモリアクセスを無視する。 リンク型は削除が単純で高負荷率も扱えますが、ノードをたどります。連続配列のオープンアドレス法は適切な負荷でキャッシュに有利です。