二次探测哈希表的限制

Question

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

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

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

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

其中我从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到0 的情况size-1.因为休息只是同一个故事一次又一次.

What the story tells up to now:一个简单的分析表明,我需要在大多数size时间进行探测,因为size有时候我开始探测相同的细胞.