[整理]完美哈希函数(Perfect Hash Function)

算法实现

该算法的实现方法是这样的。先构造两个普通的哈希函数h1(x)和h2(x),还有一个用数组实现的函数g(x)。使得h(x)=g(h1(x))+g(h2(x)) mod n,其中n是参数的总个数，H(x)就是最终的有序最小完美哈希函数了。

以上是定义，说不清楚，举个例子就明白了。取一个n为12的数据集。

首先构造这三个函数：
函数h1和h2:

函数g:

算法函数生成

首先随意设定一个数，比如是7，设为g(7)=1,因为我们已知g(5)+g(7) mod 12=1，所以可以推论出g(5)=0。因为g(5)+g(9) mod 12=0，所以可以推出g(9)=0，以此类推就可以了。但要注意的是千万不能重复设定一个数两次，这样就会形成一个环，永远也推不完。所以遇到已经推算过的数的时候，要检测环的存在。这样下去，就可以猜出全部的值了。

现在需要的就是分析这个凑的过程的运行效率问题。这个就要涉及到h1,h2这两个函数的值域大小，如果越大，越容易凑出一个g函数，但是g函数的参数域就会比较大，存储这个g函数的数据就需要占用更多的空间。相反如果值域越小，在凑的时候就非常容易出现环，需要更长的时间才能凑出这个g函数。

怎么办呢？

我们可以使用3个的h函数来降低形成环的可能，就是这样h(x)=g(h1(x))+g(h2(x))+g(h3(x)) mod n，这样虽然推理g函数的过程会复杂一些，但是很有效，有实验分析表明，当h函数的值域大约参数域的1.23倍的时候，这个g函数的创建尝试次数是常数。

至此，这个算法介绍完了。这个方法是从《Managing Gigabytes》这本书看到的，这里的讲述更浅显一些。

参考：http://www.yankay.com/introduction-to-opmphf/

参考：http://blog.csdn.net/chixinmuzi/article/details/1727195