对哈希表进行二次探测的限制

Question

我正在做一个程序，比较哈希表中线性探测、二次探测和单独链接所需的平均访问量和最大访问量。

我已经做了3个案例的元素插入部分。在从哈希表中查找元素时，我需要有一个结束搜索的限制。在单独链接的情况下，我可以在下一个指针为空时停止。对于线性探测，当探测整个表（即表的大小）时，我可以停止。在二次探测中，我应该使用什么作为极限？桌子大小可以吗？

我的二次探测函数是这样的

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

其中i从0到无穷大不等。请帮帮我。

Answer 1

对于这些问题，分两部分分析i的增长：

第一个间隔：i从0到size-1

在这种情况下，我目前还没有解决方案。希望能更新。

第二间隔：i从size到infinity

在这种情况下，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的情况。因为休息只是一次又一次的故事。

What the story tells up to now:一个简单的分析表明，我最多需要探测size次，因为超过size次，我开始探测相同的细胞。

Answer 2

请参阅此链接。如果您的表大小是2的幂，并且您使用的是reprobe函数f（i）=i*（i+1）/2，则可以保证遍历整个表。如果您的表大小是素数，则可以保证遍历至少一半的表。一般来说，您可以检查是否在某个时刻返回到原点。如果发生这种情况，你需要重新洗一洗。

Answer 3

在Excel中进行一些模拟后，似乎只需要测试迭代到i=size/2。这是在使用将连续完美正方形添加到单个散列位置的标准方法时发生的。

如果重新访问某个位置，则可以退出的答案不允许测试二次探针方法可以达到的所有可能位置，至少不允许测试所有阵列大小。（我测试了数组大小21，发现I=5重新访问了与I=2相同的位置，但I=6产生了以前未计算的位置。）