散列表二次探测限制

Question

我正在编写一个程序，比较哈希表中使用线性探测、二次探测和拉链法时所需的平均访问次数和最大访问次数。

我已经完成了三种情况下元素的插入部分。在从哈希表中查找元素时，我需要设定一个结束搜索的限制。 对于拉链法情况下，当下一个指针为空时，我可以停止搜索。 对于线性探测情况下，我可以在遍历整个表格（即表格大小）后停止搜索。 那么，对于二次探测，我应该使用什么限制呢？是表格大小吗？

我的二次探测函数如下：

newKey = (key + i*i) % size;

其中i的取值范围为0到无穷大。请帮助我...

- Arun Babu

---

可能有更有效的序列，比如质数... - Tony Delroy

Answer 1

针对这类问题，将 i 的增长分成两个部分来分析：

第一个区间： i 从 0 增加到 size-1

目前我还没有针对这种情况的解决方案。希望能够更新。

第二个区间： i 从 size 增加到 无限大

在这种情况下，i 可以表示为 i = size + k，然后

newKey = (key + i*i) % size 
       = (key + (size+k)*(size+k)) % size
       = (key + size*size + 2*k*size + k*k) % size
       = (key + k*k) % size

所以，当 i 达到size后，我们肯定会开始探测先前已经探测过的单元格。因此，您只需要考虑 i 从0到size-1的情况。因为其余部分只是一遍又一遍地重复相同的故事。

到目前为止，故事告诉我们：简单的分析表明，我最多需要探测size次，因为超过size次后，我开始探测相同的单元格。

- Seçkin Savaşçı

Answer 2

请查看此链接。如果您的表大小是2的幂次方，并且您正在使用重新探测函数f(i)=i*(i+1)/2，则保证可以遍历整个表。如果您的表大小是质数，则保证至少遍历一半的表。通常，您可以检查是否在某个点回到原始点。如果发生这种情况，则需要重新散列。

- user172818

Answer 3

在Excel中进行了一些模拟后，似乎只需要迭代到i = size / 2就可以测试所有需要测试的内容。这是使用将连续完美平方数添加到单哈希位置的标准方法时。

如果一个位置被重新访问，那么你可以退出，这个答案将不允许测试由二次探测法可能到达的所有可能位置，至少对于所有数组大小都不行。（我测试了数组大小为21，发现i=5重新访问了与i=2相同的位置，但i=6产生了一个之前未计算的位置。）

- Bill Gage