c++ - 哈希表 : Double hashing when the second hash function returns a multiple of the table size

Question

我正在用 C++ 实现一个哈希表，通过双重哈希使用开放寻址。

我理解双重哈希背后的基本原理是:

indexInProbingSequence = (originalIndex + i * hashFunction2(key)) % tableSize

我想我已经正确地实现了这部分。这是一项家庭作业，类(class)的政策是我不能就任何特定的代码征求意见，所以你必须在这方面相信我。

似乎给我带来问题的是，有时，某些键在执行第二个哈希函数时返回的值是(主要)表大小的倍数。在这些情况下，探测序列中的所有索引都是相同的。例如，当:

originalIndex = 32
hashFunction2(key) = 3035446
tableSize = 211

探测顺序是:

(32 + 1 * 3035446) % 211 == 32
(32 + 2 * 3035446) % 211 == 32

等等。

我错过了什么？

Answer 1

我认为您没有遗漏任何内容，特别是当 hashFunction2(key) == 0 时，无论表大小如何都会出现问题。

使用 (hashFunction2(key) % (tableSize - 1) + 1) 代替 hashFunction2(key)。步幅最好是环的生成器，以表格大小为模(这是一种时髦的说法，你的探测最终覆盖了整个表格)，否则至少有一个很大的周期。由于您的 table 大小是素数，这意味着您必须避免 0。