0

为什么将偏移量增加 2 有意义？我知道这个算法有效，我已经绘制了导致 ax^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;
      }
4

1 回答 1

0

您在每次迭代中都增加offset了，所以在第 -th 次迭代之后 if 将具有 value 。2n1+2*n

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

因此，在主体的第 ' 次迭代current_pos结束时添加的总量将是from到的总和，暂时忽略模运算。m1+2*nn=0n=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) % array_.size()在每次迭代m中使用循环计数器且无需修改的current_pos情况相同。

于 2020-03-15T02:38:29.537 回答