为什么该算法适用于二次探测？

Question

为什么将偏移量增加2才有意义？我知道该算法有效，我已经将结果绘制成x ^ 2类型的图，但我看不到它。有人可以简单地解释一下吗？谢谢！

        size_t FindPos(const HashedObj & x) const {
        size_t offset = 1;
        size_t current_pos = InternalHash(x);

        while (array_[current_pos].info_ != EMPTY && array_[current_pos].element_ != x) {
           current_pos += offset;  
           offset += 2;
           if (current_pos >= array_.size())
              current_pos -= array_.size();
           }
       return current_pos;
      }

Answer 1

您在每次迭代中将offset增加2，因此在第n次迭代后，如果其值将为1+2*n。

您在每次迭代中将其添加到current_pos。因此，在第一个迭代中，您将1+0*2添加到current_pos，在第二个迭代中，您添加1+1*2，在第三个1+2*2中，依此类推。]

[因此，在主体的第current_pos次迭代结束时加到m上的总量将是1+2*n从n=0到n=m-1的总和，暂时忽略了模运算。

使用加法线性，该和可以写为m + 2 * sum(n for n=0 to m-1)。剩余的总和可以显示为m*(m-1)/2，因此总和为

m + 2 * m*(m-1)/2 = m**2
因此，此方法与在每次迭代中都使用current_pos + m**2 mod size()相同，其中m是循环计数器，而无需修改current_pos会。