c++ - 双散列函数在 C++ 中是如何工作的？

Question

我正在阅读有关 HashTable 的内容，并找到了一个易于理解的好来源。

但是我对双散列函数感到困惑。这是双重哈希函数的详细信息。

双散列使用在发生冲突时将第二个散列函数应用于密钥的想法。第二个散列函数的结果将是要插入的碰撞点的位置数。

第二个功能有几个要求：

it must never evaluate to 0
must make sure that all cells can be probed

一个流行的第二个哈希函数是： Hash2(key) = R - (key % R) 其中 R 是一个小于表大小的素数。

这是双哈希函数的图像。

现在混乱开始了。正如他们在图像中所说的那样。49 应该在索引的7位置上。[9]那么实际位置将是[6]为什么他们将 49 放在[0]索引处？其他剩余整数也一样。

当没有空索引时会发生什么？

Answer 1

图像是错误的，可能会使用不同的散列方法。

当没有空单元格时，您必须重新散列。请参阅双散列部分下方的“使用重新散列进行散列”部分。

Answer 2

确实形象不对。基本思想是通过第二个具有函数给出的值跳过任何地方，如果已经被占用，则继续跳过相同的号码。的地方，直到找到一个空单元格。为此，第二个哈希函数不得返回 0。

更多解释请看这里。