最小完美哈希函数(深入搜索引擎)

最小完美哈希函数

哈希函数h是一个能够将n个键值x j的集合映射到一个整数集合的函数h(x i)，其值域范围是0≤h(x j)≤m-l，允许重复。哈希是一个具有查找表功能并且提供平均情况下快速访问的标准方法。例如，当数

据包含n个整数键值。某常用哈希函数采用h(x)=x mod m，其中m 是一个较小的值，且满足m>n/a。a是装载因子，表示记录数和可用地址数的比例关系。m一般选择一个素数，因此如果要求提供一个对1000个整数键值进行哈希的函数，一个程序员可能会建议写出如下函数形式：，h(x)=x mod 1399。并且提供一个装载因子为。a=0.7的表，该表声明能够存放1399个地址。

a越小，两个不同键值在相同哈希值相互冲突的可能性就越小，然而冲突总是不可避免。第1次考虑这个问题时，事实可能让人吃惊，最好的例子莫过于著名的生日悖论(birthday paradox)。假定一年有365天，那么要组合多少个人，才能使得出现生日相同的人这一概率超过0.5呢？换句话说，给定一个365个哈希槽(hashslot)。随机选择多少个键值才能够使得出现冲突的概率超过0.5?当首次面对这样一个问题时，一般的反应肯定是认为需要很多人才行。事实上，答案是只需区区23人。找到一个能够满足现实大小要求且无冲突的哈希函数的几率小到几乎可以忽略25。例如，一个1000个键值和1399个随机选择的槽，完全没有冲突的概率为 2.35×10-217（概率的计算诱导公式将在下一节中给出，以公式4.1代入m=1399和n=1000得到），如何才能最好地处理这些不可避免冲突？这一话题将在本节中以大段篇幅展开，这里我们正是要找到其中万里挑一的能够避免所有冲突的哈

希函数。

25可以试图在一群人中做这样一个有趣的实验，笔者曾在讲述哈希表的课上和同学们做

过多次这样的实验。有一项很重要的事情往往被我们忽略，即参加者必须事先在纸上写下他们的生日（或者其他任意日子）。然后才能开始核对的工作，这样才能消除神奇的负反馈。在我们的实验中，除非这样做了，否则也许必须找到366个同学才能遇到第1次碰撞，也许这乜存在心理学悖论吧。

如果在一般的哈希函数中再增加一条额外的性质，即对于任意的x i和x j，当且仅当i=j时才有h(x i)=h(x j)，这就是完美哈希函数(perfect hash function)。这里，当对一个键值集合L进行哈希时，不可能出现任何冲突。

如果哈希函数不仅是完美的，并映射到的值域范围为m=n，n个键值中的任意一个都一一映射到唯一整数（该整数是介于1~n的某个整数），这时表的装载因子是a = 1.0，因此该函数称为“最小完美哈希函数”(minimal perfect hash function)，或者简记为“MPHF”。一个MPHF保证了任何一个键值只需进行一次探测(one-probe)访问，并且表中不包含无用槽。

最后，如果哈希函数还具有这样的性质，即若x i

当煞，一个MPHF或者OPMPHF对某一个键值集合L有效，但可能对另一个集合就不“完美”了，因此这里不过是对一个单一静态集合预先计算( precalculated)了查找函数。然而在空间节省很大，并且预先计算被授权的场合下才能这么做。

作为例子，表4-3给出了我们曾经使用过的12个键值的一个OPMPHF。这个哈希函数的推导过程在下节中将展开讨论。构造的过程预先假定存在两个一般的哈希函数h1(t)和h2(t)，它们都是将字符串映射到范围O~m-1的一个整数。其中m≥n，并且允许重复。一种定义方法是用数值来表示基数为36的字符串，与前面提到的一样，最后计算权重之后得到wj，

这里t[i]是用基数为36的值描述的术语中第f个字符，|t|表示术语t的长度。那么不同的权重集合W1[i]和W2[i]中的i为1≤i≤|t|，这样就导出了两个不同的函数h1(t)和h2(t)。与这两个函数一起，还需要一个特别的数组g。它需要继续把O...m-1映射到O...n-1，如表4-3 (b)所示。

给某个字符串t，采用OPMPHF h(t)的方法计算公式为：

h(t)=g(h1(t))+ n g(h2(t))

这里+n表示加法执行后还需对n取模，即先把两个数相加。然后把这个数除以n，最后取余数(例如4 +n7=2)。换句话说，首先计算两个非完美哈希函数的值，用映射g分别计算这两个哈希函数的值。然后将其相加后对n取模，例子字典中的计算结果可以在表4-3 (a)的第4列中找到。如同变戏法一样，最后的哈希值确实就是字符串列表中的原位置26。

表4-3最小完美哈希函数表

(b)哈希函数g

的索引术语集进行计算的话，那么就不必存放字符串或者字符串指

针。只需要存储f t值，而术语t的倒排文件地址直接从数组中的第h(t)

位置就能找到。

26译者注：可以看出在表4-3 (a)中最后计算的h(t)值从0—11顺序摊列，可知h即保序，又单射且满射，这些性质符合OPMPHF的定义要求。

27译者注：这里其实表达的是通过字符串本身能够建立与其编号对应的关系，假定我们已知单词“bed”的三个字母的编码分别为ABC，其在字典中按序排放的顺序为R，那么函数h(t)的就是从ABC计算出R的公式。

这里有一个难题，描述哈希函数h需要多少存储空间？一个

MPHF至少需要1.44n比特的存储空间(Fox及Heath等1992)，更典

型的很容易计算出对于大数的n，MPHF大约需要每个键值4个—20

比特。而描述OPMPHF所需要的空间还要更大，大约需要至少nlogn

比特的存储空间（Fox等1991）。在OPMPHF中，两个哈希函数h1

和h2可以有较小的权重表W1和W2描述，因此它们需要的空间可

以忽略不计；另一方面，数组g有m个项，即便是紧凑存放，也需

要占用mlogn比特。下一节将要介绍的方法采用了m= 1.25n的比例

关系。这也是为什么在表4-3的例子中，n(n= 12)个字符串m=15的数

组g来处理。即数组g占用了25比特每字符串，或者，在实际的带

有索引项的术语存储为4字节的整数28。对于假定n=1 000 000个单

词的字典，大约需要1.25×4×1 000 000=5 MB的存储开销，另外8

MB依然需要存放磁盘指针( disk pointer)和术语词频。从整体上看，

如果OPMPHF被实际使用的话，与3-in-4的前端编码所需的15.5 MB