DAWG(4-1): 完全ハッシュ関数 - sileのブログ四回目の前半。 DAWGのキーに一意なIDをマッピングするための最小完全ハッシュ関数を実装。 ※ ただし今回実装分は、"最小"のつかないただの完全ハッシュ関数まで 参考元 『Simple and Space-Efficient Minimal Perfect Hash Functions』*1を参考にした。 ただし、まだ実装に必要な箇所に軽く目を通しただけなので、詳細は理解していない。 ※ いつものことだけど、ちゃんと知りたい人はもとの論文を参照のこと 概要 とりあえず現状での理解。※ 間違っている可能性あり! 定義: 完全ハッシュ関数(PHF, perfect hash function): N個のキーを0からM未満の一意な値(整数値?)にマッピングする関数 ※ M >= N 最小完全ハッシュ関数(MPHF, minimal perfect hash function): N個のキーを0
