二次探测哈希表的限制

Question

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

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

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

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

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

Answer 1

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

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

Answer 2

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

Answer 3

对于此类问题，请将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的情况。因为Rest只是一次又一次的相同故事。

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