什么是杜鹃哈希中的“新哈希函数”？

Question

我读约杜鹃从Pagh和Rodle哈希和我不理解本段的含义：

可能发生的是这个过程循环，如示于图1（b）中。 因此，迭代次数以2.3.3节规定的值“MaxLoop”到 为界。如果达到这个迭代次数，我们使用新的哈希函数重新哈希表中的键，并再次尝试 以适应无嵌套键。不需要 为重新散列分配新的表格：我们可以简单地通过 表格来删除并在所有发现不在表格中的预期位置的键盘上执行通常的插入过程。

这是什么意思使用新的哈希函数？
在插入算法中，表格被调整大小。我们是否应该有一个哈希函数的“池”来使用？我们如何创建这个池？

Answer 1

是的，他们正在期待新的散列函数，就像他们说的那样。幸运的是，它们不需要一堆新的算法，只是当前数据集的散列行为略有不同。

看看论文的第2.1节，然后看附录A.它讨论了随机universal hash functions的构造。

一个简单的，有希望说明的例子是假设你有一些你喜欢的常规散列函数，它是以字节块为单位进行操作的。我们将其称为H(x)。你想用它来产生一系列新的，稍有不同的散列函数H_n(x)。那么，如果H(x)是好的，并且你的要求很弱，你可以定义H_n(x) = H(concat(n,x))。你对H_n(x)的行为没有很好的保证，但你会期望他们中的大部分会有所不同。