单独链接与开放寻址中的哈希函数

Question

我正在阅读Weiss的数据结构书，我对分离链接中的哈希函数与开放寻址中的哈希函数之间的区别感到困惑。

在单独的链接中，哈希函数定义为：

hash(x) = x mod tableSize

而在开放寻址中：

h_i(x) = (hash(x) + f(i)) mod tableSize

其中 i 是试验次数，f(i( 是函数，例如 f(i( = i 表示

线性探测，f(i( = i^2 表示二次探测等。

我有两个问题：

1(在分离链接中，使用哈希函数是否有意义：

hash(x) = x mod 10

当表大小等于时，假设 11？

2(在开放寻址中，我们是否总是必须通过tableSize修改键(+间隙(两次？

Answer 1

1(不是真的。这将是正确的，但效率不高。如果您mod小于表大小，则表顶部至少有一个存储桶未使用。如果有特定的原因选择要mod的值(如果您正在寻找某些属性，可能会有(，那么您可以将表格修剪到该大小并避免浪费。

2(这不是真正必要的(((a mod c) + b) mod c是多余的(，而且这不是唯一的定义。稍微一般一些，你有h_i(x) = f(x, i) mod tableSize，一些明显的选择f包括

• f(x, i) = x + i(线性探测(
• 某些常数a和b != 0的f(x, i) = x + a * i + b * i * i(二次探测(
• f(x, i) = h1(x) + i * h2(x)一些合适的哈希函数h1和h2(双哈希(

最后一个特别容易受到溢出的影响，这可能会弄乱一些属性，因此您可能希望执行一些计算来模化表大小(特别是如果这是一个质数，因为这样你就有一个很好的字段可以工作(。

此外，您总是会在需要之前使用f(x, i) mod tablesize f(x, i + 1) ，所以您不妨以增量方式计算f，在每一步您都按表大小进行修改，因为无论如何您都必须这样做。

但我们当然不仅限于这些形式的f，或者实际上不限于我们寻找开放位置的开放寻址方案。Cuckoo 散列(和变体(有两个候选位置来插入一个项目，如果两个地方都已满，它将踢出一个项目并将其移动到其 alt 位置(也可能替换一个项目((注意避免无限循环(。这样，查找只有两个位置可供查看，而不是可能查看整个表。它有很多变体。