哈希游戏- 哈希游戏平台- 哈希游戏官方网站

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

　　作为例子，表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))

　　哈希函数h是一个能够将n个键值xj的集合映射到一个整数集合的函数h(xi)，其值域范围是0≤h(xj)≤m-l，允许重复。哈希是一个具有查找表功能并且提供平均情况下快速访问的标准方法。例如，当数据包含n个整数键值。某常用哈希函数采用h(x)=x mod m，其中m是一个较小的值，且满足mn/a。a是装载因子，表示记录数和可用地址数的比例关系。m一般选择一个素数，因此如果要求提供一个对1000个整数键值进行哈希的函数，一个程序员可能会建议写出如下函数形式：，h(x)=x mod 1399。并且提供一个装载因子为。a=0.7的表，该表声明能够存放1399个地址。