字符串哈希函数

字符串哈希函数哈希函数h是一个能够将n个键值xj的集合映射到一个整数集合的函数h(xi)，其值域范围是0≤h(xj)≤m-l，允许重复。哈希是一个具有查找表功能并且提供平均情况下快速访问的标准方法。例如，当数据包含n个整数键值。某常用哈希函数采用h(x)=xmodm，其中m是一个较小的值，且满足mn/a。a是装载因子，表示记录数和可用地址数的比例关系。m一般选择一个素数，因此如果要求提供一个对1000个整数键值进行哈希的函数，一个程序员可能会建议写出如下函数形式：，h(x)=xmod1399。并且提供一个装载因子为。a=0.7的表，该表声明能够存放1399个地址。a越小，两个不同键值在相同哈希值相互冲突的可能性就越小，然而冲突总是不可避免。第1次考虑这个问题时，事实可能让人吃惊，最好的例子莫过于著名的生日悖论(birthdayparadox)。假定一年有365天，那么要组合多少个人，才能使得出现生日相同的人这一概率超过0.5呢？换句话说，给定一个365个哈希槽(hashslot)。随机选择多少个键值才能够使得出现冲突的概率超过0.5?当首次面对这样一个问题时，一般的反应肯定是认为需要很多人才行。事实上，答案是只需区区23人。找到一个能够满足现实大小要求且无冲突的哈希函数的几率小到几乎可以忽略25。例如，一个1000个键值和1399个随机选择的槽，完全没有冲突的概率为2.35×10-217（概率的计算诱导公式将在下一节中给出，以公式4.1代入m=1399和n=1000得到），如何才能最好地处理这些不可避免冲突？这一话题将在本节中以大段篇幅展开，这里我们正是要找到其中万里挑一的能够避免所有冲突的哈希函数。如果在一般的哈希函数中再增加一条额外的性质，即对于任意的xi和xj，当且仅当i=j时才有h(xi)=h(xj)，这就是完美哈希函数(perfecthashfunction)。这里，当对一个键值集合L进行哈希时，不可能出现任何冲突。如果哈希函数不仅是完美的，并映射到的值域范围为m=n，n个键值中的任意一个都一一映射到唯一整数（该整数是介于1~n的某个整数），这时表的装载因子是a=1.0，因此该函数称为“最小完美哈希函数”(minimalperfecthashfunction)，或者简记为“MPHF”。一个MPHF保证了任何一个键值只需进行一次探测(one-probe)访问，并且表中不包含无用槽。最后，如果哈希函数还具有这样的性质，即若xixj，则有h(xi)h(xj)，这称为“保序性”(orderpreserving)。给定一个保序的最小完美哈希函数（简写为“OPMPHF”，读作“oomph!”），那么键值可以在常量时间内找到，而不需要任何空间开销。并且如果需要的话，还可以按序访问。一个OPMPHF能够直接且简单地返回一个键值的序号。当煞，一个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，采用OPMPHFh(t)的方法计算公式为：h(t)=g(h1(t))+ng(h2(t))这里+n表示加法执行后还需对n取模，即先把两个数相加。然后把这个数除以n，最后取余数(例如4+n7=2)。换句话说，首先计算两个非完美哈希函数的值，用映射g分别计算这两个哈希函数的值。然后将其相加后对n取模，例子字典中的计算结果可以在表4-3(a)的第4列中找到。如同变戏法一样，最后的哈希值确实就是字符串列表中的原位置.