ハッシュ表のサイズ
http://d.hatena.ne.jp/zariganitosh/20090716とhttp://d.hatena.ne.jp/odz/20090718/1247922506の話。
定義域と値域からハッシュ表のサイズを考えてみる。登場人物はハッシュ関数と折り畳み関数の二つ。
ハッシュ関数
例えば、文字列から32ビット整数に変換するハッシュ関数を考えてみよう。文字列の最大長をNとすると2^(8*N)程度の極めて巨大な定義域を持つ。値域は2^32である。
理想的なハッシュ関数は適当な入力に対して値域全体に均等に分布した結果を返す。この分布の均等さをエントロピーとして表現すると比較しやすい。
折り畳み関数
定義域＝ハッシュ関数の値域、値域＝ハッシュ表のサイズとなる適当な関数である。理想的な折り畳み関数は均等に分布した入力に対して均等に分布した出力を返す。
ハッシュ関数のエントロピーが十分に高い場合
この場合は折り畳み関数として素数による剰余を使うと損をする可能性が高い。何故かというと、均等な入力の剰余を取った結果が均等に分布するのは、定義域の公約数で剰余を取る場合のみだからだ。
2の巾乗を返す典型的なハッシュ関数に対しては2の巾乗サイズのハッシュ表が最適である。
