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

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的情况。因为休息只是一次又一次的同一个故事。

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