algorithm - 二次探测哈希表的限制

Question

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

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

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

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

其中 i 从 0 变化到无穷大。请帮我..

score 8 · Accepted Answer

对于此类问题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时间我开始探测相同的细胞。

score 0 · Accepted Answer

请参阅此链接。如果您的表大小是 2 的幂并且您正在使用重新探测函数 f(i)=i*(i+1)/2，则可以保证遍历整个表。如果你的表大小是一个素数，那么保证你至少遍历了一半的表。一般来说，您可以检查您是否在某个时候回到了原始点。如果发生这种情况，您需要重新散列。

score 0 · Accepted Answer

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

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

3 回答 3