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

Question

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

performancealgorithmdictionaryhashhashtable

5

我正在阅读Pagh和Rodle的《杜鹃哈希》（cuckoo hashing）一文，但无法理解以下段落的含义： “这个过程可能会出现循环，如图1(b)所示。因此，迭代次数受到一个“MaxLoop”值的限制，该值将在2.3节中指定。如果达到了这个迭代次数，我们将使用新的哈希函数对表中的键进行重新哈希，并尝试再次容纳该无巢键。无需为重新哈希分配新表：我们只需简单地遍历表，删除并对所有未在其目标位置上的键执行常规插入操作即可。”

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

回答：当最大循环次数(MaxLoop)被耗尽时，杜鹃哈希会使用新的哈希函数对表中的键进行重新哈希，以尝试再次容纳无巢键。不需要重新分配新的表，只需要通过遍历表，删除未在目标位置上的键，并对它们进行常规的插入操作即可。至于如何创建哈希函数的“池子”，该文章没有给出相关信息。

- Jim

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Jay Kominek · Accepted Answer

是的，他们正在期待新的哈希函数，就像他们所说的那样。幸运的是，他们并不需要一堆新算法，只需要在您当前的数据集上稍微改变哈希行为即可。

请看论文2.1节和附录A。它讨论了随机通用哈希函数的构建。

一个简单而有启发性的例子是，假设您有一些正常的哈希函数，它对字节块进行操作。我们将其称为H(x)。您想使用它来产生一族新的、略微不同的哈希函数H_n(x)。好吧，如果H(x)很好，并且您的要求不高，您可以定义H_n(x) = H(concat(n,x))。您没有关于H_n(x)行为的强大保证，但您会期望它们中的大多数是不同的。