ディクショナリ

ハッシュ関数

キーの文字列から 32 ビットの数を作ります。FNV-1a は 1 文字ずつ XOR してから決まった素数を掛けます [1]。

記号: $c_i$ は $i$ 文字目の文字コード、$\oplus$ は XOR です。

文字コードの和は悪い例です。文字の並べ替えで同じ値になるので、tea と eat や k01 と k10 がぶつかります。連番は値が 1 ずつずれるので、隣り合う場所に並んで塊を作ります。

番号の決め方

場所の数は 2 のべき乗にします。番号はハッシュの下位 $b$ ビットで、割り算が要りません。

上のビットは番号に効かないので、下位のビットがよく混ざっている必要があります。FNV-1a の一番下のビットは全部の文字の一番下のビットの XOR で、下から 2〜7 ビット目にも似た弱さがあります。ハッシュを右へずらして XOR すると上のビットも混ざります [1]。

負荷率と調べる回数

負荷率はキーの数を場所の数で割った値です。ハッシュが均一にばらつくとき、1 回の検索で調べる回数の平均は負荷率だけで決まります [3][4]。見つからないときは空きの場所や空の列を見た 1 回も数えます。

記号: $n$ はキーの数、$m$ は場所の数です。一様ハッシュはキーごとに全部の場所を乱数の順に調べる模型で、ダブルハッシュ法はこれに近い回数になります [3]。線形探査法は負荷率が 1 に近づくと、見つからないときの回数が急に増えます。

衝突の解き方

• チェイン法: 場所ごとに列を持ち、同じ番号のキーを列につなぐ。負荷率は 1 を超えてもよい
• 開番地法: キーを場所に直接置く。埋まっていれば決まった順番でほかの場所を調べる [2]

開番地法の 3 つの方法は、$i$ 回目に調べる場所の決め方が違います。

記号: $s_0$ はハッシュで決まる番号、$d$ は 2 つ目のハッシュで決める歩幅です。

• 線形探査法: 隣へ進むので、埋まった場所が続く塊ができる。塊に当たったキーは塊の端に付くので、塊はさらに伸びる [3]
• 二次探査法: 間を 1・2・3 … と広げるので、近くの塊を飛び越える。$m$ が 2 のべき乗なら、三角数の順で全部の場所を 1 回ずつ通る。同じ番号から始まるキーどうしは同じ順に進む
• ダブルハッシュ法: 同じ番号から始まるキーでも歩幅が違うので、別の順に進む。歩幅を奇数にすると $m$ と互いに素になり、全部の場所を通る [4]

削除

開番地法で場所を空きに戻すと、その先へ進んだキーの道が途切れて見つからなくなります。そこで削除済みの印を置きます。検索は印を飛ばして進み、追加は印の場所を使えます [4]。印が増えると調べる回数も増えるので、拡張のときに印を捨てて入れ直します。

ロビンフッド・ハッシュ法は印を置かず、後ろのキーを 1 つずつ前へ詰めます。空きか、自分の番号にいるキーに当たったら止めます。

ロビンフッド・ハッシュ法

線形探査法と同じ順に進み、手に持ったキーより自分の番号に近いキーに会うと入れ替えます。遠くから来たキーを優先するので、距離のばらつきが小さくなります [5][6]。検索はいまの距離より短い距離のキーに当たったら打ち切れます。

記号: $s$ はキーのいる場所、$s_0$ はそのキーの番号です。

カッコウ・ハッシュ法

表を 2 つに分け、2 つのハッシュで表 1 と表 2 に 1 か所ずつ場所を決めます。検索と削除は 2 か所だけ見ます [7]。

追加は空いている方へ入れます。両方埋まっていれば前のキーを追い出し、追い出したキーをもう一方の表の場所へ移します。追い出しが輪になって終わらないことがあり、回数の上限を超えたら表を作り直します。負荷率が 1/2 より小さければ、追加は償却した期待値で $O(1)$ です [7]。

入れた順を保つ辞書

番号の表と項目の配列に分けます。項目は追加の順に配列の最後へ置き、番号の表には項目の番号だけを入れます。順に取り出すときは項目の配列を前から読みます。Python の dict は 3.6 でこの作りになり、記憶は 3.5 より 20〜25 % 減りました [8]。3.7 からは入れた順を保つことが言語の仕様です [9]。

番号の表の探す順番は次の式です。perturb はハッシュから始めて 5 ビットずつ右へずらすので、ハッシュの上のビットも順に番号へ入ります [10]。

削除は番号の表に削除済みの印を置き、項目を空けます。項目の配列は拡張のときに詰めます。

拡張

負荷率が上限を超えたら場所の数を 2 倍にして、全部のキーを入れ直します。1 回の拡張では全部のキーが動きますが、次の拡張まで同じくらいの数の追加ができます。入れ直す数の合計はキーの数の 2 倍より少ないので、1 回の追加あたりは償却で $O(1)$ です [4]。

計算量

調べる回数で表します。平均は負荷率を上限より下に保ち、ハッシュが均一にばらつくときの値です。最悪は多くのキーが同じ番号に集まったときです。* は確率の上での値です。カッコウ・ハッシュ法の追加は償却した期待値です [7]。

出典

1. FNV-1aL. Noll, K. Vo, D. Eastlake 3rd, T. Hansen, The FNV Non-Cryptographic Hash Algorithm, RFC 9923, 2026
2. 開番地法と線形探査法W. W. Peterson, Addressing for Random-Access Storage, IBM Journal of Research and Development, Vol. 1, No. 2, pp. 130–146, 1957
3. 調べる回数の式と塊D. E. Knuth, The Art of Computer Programming, Vol. 3: Sorting and Searching, 2nd ed., Addison-Wesley, 1998, Section 6.4
4. 削除済みの印、ダブルハッシュ法の歩幅、拡張の償却T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022, Chapters 11 and 16
5. ロビンフッド・ハッシュ法P. Celis, P.-Å. Larson, J. I. Munro, Robin Hood hashing, 26th Annual Symposium on Foundations of Computer Science, pp. 281–288, 1985
6. ロビンフッド・ハッシュ法（学位論文）P. Celis, Robin Hood Hashing, Ph.D. thesis, University of Waterloo, 1986, Technical Report CS-86-14
7. カッコウ・ハッシュ法R. Pagh, F. F. Rodler, Cuckoo hashing, Journal of Algorithms, Vol. 51, No. 2, pp. 122–144, 2004
8. 入れた順を保つ dict の作りPython Software Foundation, What's New In Python 3.6, https://docs.python.org/3/whatsnew/3.6.html
9. 入れた順を言語の仕様にPython Software Foundation, What's New In Python 3.7, https://docs.python.org/3/whatsnew/3.7.html
10. dict の探す順番CPython, Objects/dictobject.c, https://github.com/python/cpython/blob/main/Objects/dictobject.c
11. 2 つ目のハッシュの混ぜ方A. Appleby, MurmurHash3（SMHasher）, https://github.com/aappleby/smhasher

このツールで決めたこと

• 調べる回数は読んだ場所・列のノード・項目の数
• FNV-1a の値は XOR で畳まずにそのまま番号に使う
• 移動はキーを書き直した数で、拡張の入れ直しも数える
• 回数は工程ごとに 0 から数える
• 拡張しないときの場所の数は、負荷率が 0.75 以下になる最小の 2 のべき乗（8 以上）。カッコウ・ハッシュ法はその 2 倍を 2 つの表に分ける
• 拡張するときは 8 個の場所から始める
• チェイン法以外は、拡張しない設定でも空きがなくなる追加の前に 2 倍にする
• 負荷率には削除済みの印も数える。拡張のときに印を捨てる
• 2 つ目のハッシュは、FNV-1a に 0x9e3779b9 を XOR して MurmurHash3 の最後の混ぜ方（fmix32）を通した値 [11]。文字コードの和を選んでも FNV-1a から作る
• 2 つ目のハッシュはダブルハッシュ法の歩幅とカッコウ・ハッシュ法の表 2 の番号に使う
• ダブルハッシュ法の歩幅は、2 つ目のハッシュの下位 $b$ ビットの一番下を 1 にした奇数
• カッコウ・ハッシュ法の追い出しは $2{\log }_{2}m+2$ 回まで（$m$ は 2 つの表の場所の合計）。超えたら 2 倍の表に入れ直し、ハッシュ関数は変えない
• 入れた順を保つ辞書の perturb は 32 ビットのハッシュから始める。CPython は 64 ビットのハッシュを使う
• 操作の表の回数は、英単語 24 個で 8 通りのデータを試した 1 回の平均