Minimal Perfect Hash(最小完全ハッシュ関数)

WebGraph Freameworkで，URLからIDを返すモジュール(http://mg4j.dsi.unimi.it/docs/it/unimi/dsi/mg4j/util/MinimalPerfectHash.html)があるのだが，最初「結果返すのやは」とか思ったけど，よく見てみればハッシュ関数なのだから当間えっちゃ当たり前だったorz

で，ずーと前にやった記憶があるのだが，すっかり忘れていたので，ハッシュについてちょいと調べてみた

040705 - Hashing (4)

http://www.radiumsoftware.com/0407.html#040705

Minimal Perfect Hashing

http://burtleburtle.net/bob/hash/perfect.html

概要だけなら上，詳細は下で．（日本語と英語って話もあるがｗ）

で，このWebGraphで使っているハッシュ(MinimalPerfectHashクラス)は最小完全ハッシュであるが，さらに順番も保存するハッシュ関数を使ってる．また，SignedMinimalPerfectHashの派生クラスは，URLのシグネチャも記録して登録されているURLだったか確認することができる．
調べるURLが既に登録されているとわかっているなら，MinimalPerfectHashクラスで，登録されているか調べるにはSignedMinimalPerfectHashの派生クラスで，という使い分けをするのでしょう．