二次探测哈希表的限制

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

请参阅this link。如果你的表格大小是2的幂，并且你正在使用一个反函数函数f（i）= i *（i + 1）/ 2，那么你可以保证遍历整个表格。如果你的桌子尺寸是一个素数，你肯定会遍历至少一半的桌子。一般来说，你可以检查一下你是否回到了原点。如果发生这种情况，你需要重新哈希。