c++ - Hashtables：当第二个哈希函数返回表大小的倍数时进行双重哈希

Question

我正在 C++ 中实现一个 HashTable，通过双散列使用开放寻址。

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

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

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

似乎给我造成问题的是，有时，某些键在受到第二个哈希函数的影响时，会返回一个值，该值是（主要）表大小的倍数。在这些情况下，探测序列中的所有索引都是相同的。例如，当：

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). _ 理想的是，步幅是一个以表格大小为模的环的生成器（这是一种时髦的说法，即您的探针最终会覆盖整个表格），或者至少有一个很大的周期。由于您的表大小是素数，这意味着您必须避免 0。