什么是完美哈希函数
就是没有冲突的哈希函数，也就是，函数 H 将 N 个 KEY 值映射到 M 个整数上，这里 M>=N ，而且，对于任意的 KEY1 ，KEY2 ，H( KEY1 ) != H( KEY2 ) ，并且，如果 M = = N ，则 H 是最小完美哈希函数（Minimal Perfect Hash Function，简称MPHF）。
什么时候使用PHF和MPHF
通常情况下，PHF或MPHF是针对静态集合的。也就是，在使用PHF或MPHF时，所有的 KEY 值是事先已知并且固定的。不过，有针对动态集合的一个算法（我没有仔细看，不敢肯定）。
使用PHF和MPHF的一般流程
1. （准备阶段）将已知的所有的 KEY 值传给PHF或MPHF生成算法，生成PHF或MPHF以及相应的数据；
2. （使用阶段）调用已有的PHF或MPHF以及相应的数据快速计算哈希值并进行相应的操作。
其实在实际使用中我们只关心步骤2，但步骤1的生成算法却是PHF或MPHF的关键。
PHF和MPHF生成程序库
GNU的完美哈希函数生成程序，可以生成PHF和MPHF，生成MPHF时和输入数据以及参数设置的关系比较大。使用的应该是比较简单的算法，生成的效率不高，当数据量大时，程序就没什么反应了。生成的结果是代码（里面包含有数据，直接组织在代码里），移植性非常好。很多编译器对保留字的处理都采用gperf来建立完美哈希函数。Windows版的可执行文件可以从
下载，源代码可以从
下载，一篇介绍论文在
，说明书在
，说明书中文翻译在
这里。
易用性： 5
稳定性： 5
移植性： 5
效率（针对大数据量）： 2
MPHF： 2
巴西的这个哥们发了很多MPHF方面的论文。CMPH应该他和其他几个人开发的开源的生成MPHF的程序库。这里面封装了4个算法，而且设计了一个程序框架（搞不懂他们为什么要设计这样一个框架，用MPHF的人不会像他们做研究那样会一次使用那么多个算法的，而这样一个框架明显增加了使用的难度）。里面有几个算法是针对大数据量的，但简单试了试，发现并不像他们论文里宣称的那样高效，而且由于是一个框架，生成的MPHF并不能直接脱离他们的环境来使用。是他们在SourceForge上的链接。
易用性： 3
稳定性： 2
移植性： 2
效率（针对大数据量）： 2
MPHF： 5
又一个牛人写的生成MPHF的算法，注意了，他写这个纯粹是为了好玩，考！
简单试了试，可以直接生成代码，但不是很好用，针对大数据量效率也不行。
易用性： 3
稳定性： 3
移植性： 4
效率（针对大数据量）： 3
MPHF： 5
又又一个牛人写的生成MPHF的算法，比较好用，可以处理大数据量的集合，而且比较有特色的是关键字不仅仅可以是字符串，还可以是整数等。
易用性： 5
稳定性： 5
移植性： 4
效率（针对大数据量）： 5
MPHF： 5
以上都是用C/C++来实现的PHF或MPHF生成程序考，这是一个用Python实现的MPHF生成程序。还是比较好用的，遗憾的是对大数据量效率不行。
易用性： 5
稳定性： 5
移植性： 4
效率（针对大数据量）： 3
MPHF： 5
PHF和MPHF生成算法
我一贯坚持的是拿来主义（只要不存在法律和道德风险），所以对PHF和MPHF的生成算法我只是浅尝辄止，不敢在这里唧唧歪歪。下面给出一些链接，想研究这些算法好好看这些论文吧。论文按大概时间顺序排列，最新的在最前面。
阅读(1672) | 评论(0) | 转发(0) |
