perfect hash function(完全ハッシュ関数)に関する調査。
perfect hash functionとは
wikipediaにはperfect hash functionは以下のようにまとまっている。
ハッシュ関数が単射の場合、すなわち正しい入力に対して必ず異なるハッシュ値が対応する場合、これを完全 (perfect) だという。このような関数を使えば、1つのハッシュテーブルで目的のエントリを直接探すことができ、それ以外の探索の手間が生じない。
完全ハッシュ関数は、入力される範囲が予め分かっていて変化しない場合のみ成立する。例えば英語の月の名前を0から11の整数にマッピングするとか、ある辞書に掲載されている単語にハッシュ値を割り当てるといった場合である。入力の集合を与えられると、それに対応した完全ハッシュ関数を実行する最適化されたサブルーチンを出力する生成器がいくつか存在する（例えば、GNU gperf）。
wikipedi:ハッシュ関数より引用
つまりハッシュ関数で、keyが絶対に衝突せずに必ず個々のkeyのハッシュ値が必ず一意に定まるのがperfect hashingです。特徴としては、衝突がないため検索が極めて高速であること。昨今のオープンソースのソフトウェアではGNU gperfというperfect hashingのハッシュ関数を生成してくれるソフトが多く用いられている。さくっと使ってみたい場合はgperfを試してみるのが良いでしょう。gperfは複数のkey, valueのデータセットを探索できるハッシュ関数を生成してくれて、CやC++で用いることができる便利なユーティリティです。
perfect hashingはどのようなケースで有効か
Using a perfect hash function is best in situations where there is a large set, S, which is not updated frequently, and many lookups into it. Efficient solutions to performing updates are known as dynamic perfect hashing, but these methods are relatively complicated to implement. A simple alternative to perfect hashing, which also allows dynamic updates, is cuckoo hashing.
wikipedia:perfect hash function より引用
上記の引用した内容のようにperfect hashingは以下のようなケースで有効です。
- 更新が無い莫大なkey、valueのデータセット
- かつkeyの探索(lookup)が高頻度の場合
ダイナミックに更新が必要な場合は、dynamic perfect hashingというアルゴリズムがあるが複雑らしいです。また、シンプルであるがダイナミックに更新できるもにcuckoo hashingというのがあるらしい。ちょっとこれは興味があるから別の機会に調査してみよう。
関連事項
perfect hasingと似たアルゴリズムでminimal perfect hash function(最小完全ハッシュ関数)がある。
n 個のキーに対する完全ハッシュ関数が最小 (minimal) であるとは、その値域が n 個の連続な整数（通常 0 から n-1）の場合である。単に参照が単純化されるだけでなく、ハッシュテーブルもコンパクトになり、空きスロットができない。最小完全ハッシュ関数は単なる完全ハッシュ関数よりも求めるのが難しい。
wikipedi:ハッシュ関数より引用
最小完全ハッシュ関数は、perfect hashingでかつ、ハッシュテーブルとてもコンパクトになる。詳しい調査は別のエントリーでしようと思う。最小完全ハッシュ関数は多くの実装あり、具体的にはなどがある。