布谷鸟哈希中的"新哈希函数"是什么？

Question

我正在阅读Pagh和Rodle的杜鹃哈希,我无法理解这一段的含义:

可能会发生此过程循环,如图1(b)所示.因此,迭代次数受第2.3节中规定的值"MaxLoop"的限制.如果达到了这个迭代次数,我们将使用新的哈希函数重新表达表中的键,并再次尝试使用无嵌套键.没有必要为重新分配分配新表:我们可能只是通过表来删除并执行通常的插入过程,所有键都发现不在表中的预期位置.

使用新的哈希函数意味着什么？
在插入算法中,调整表的大小.我们是否应该以某种方式使用散列函数的"池"？我们如何创建这个池？

Answer 1

是的，正如他们所说，他们期待新的哈希函数。幸运的是，它们不需要一堆新算法，只需要对当前数据集进行稍微不同的哈希行为。

看一下论文的 2.1 节，然后是附录 A。它讨论了随机通用哈希函数的构造。

一个简单的、希望具有说明性的示例是，假设您有一些您喜欢的普通哈希函数，该函数对字节块进行操作。我们就这样称呼它H(x)。您想用它来生成一系列新的、略有不同的哈希函数H_n(x)。好吧，如果H(x)很好，并且您的要求很弱，您可以定义H_n(x) = H(concat(n,x))。您对 的行为没有很好的强有力的保证H_n(x)，但您希望它们中的大多数都是不同的。