ハッシュマップ準備 （データ構造）

序文

ハッシュマップの項を書くための準備です. 誰でも知っていると言われそうだが, 社内教育用のノートにするつもり.

ハッシュマップ用ハッシュ関数

ハッシュマップ用のハッシュ関数への要求は, 以下の２つぐらいだろうか.

• 高速であること.
• 衝突が少ないこと.

私の手持ちでは以下の4つを実装している.

• Bernstein hash function
• Fowler–Noll–Vo hash function (FNV)
• MurmurHash
• xxHash

手元で32bit乱数や16バイトのASCIIランダム文字列でテストをしてみると,
MurmurHashとxxHashは衝突が少ない. Bernsteinは衝突が多い, FNVはたまに衝突がある.

16バイトだとMurmurHashとxxHashが, Bernstein, FNVより速くなる.
MurmurHashやxxHashなど最近の高速を謳ったハッシュ関数は, 32bitや64bitといった単位で纏めて処理する.
xxHashの方がMurmurHashより高速だが, MurmurHashでも実用として問題ないレベル.
FNVの利点はコード量が小さいこと, メモリが32KBとかの場合役立つかもしれない.

キーが高々数十文字までの文字列のハッシュマップに使う場合の話で, 用途によって使い分ける.
完全ハッシュが前提なら, そうでない場合と違ったハッシュマップ実装も考えられる.