Why does this algorithm work for Quadratic Probing?

Question

Why does incrementing offset by 2 make sense? I know this algorithm works, I have plotted the results resulting in a x^2 type graph but I just can't see it. Could someone explain it in simple terms? Thank you!

        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

You are increasing offset by 2 in every iteration, so after the n-th iteration if will have value 1+2*n.

You are adding this to current_pos in each iteration. So in the first iteration you are adding 1+0*2 to current_pos, in the second you are adding 1+1*2, in the third 1+2*2 and so on.

The total amount added to current_pos by the end of the m'th iteration of the body will therefore be the sum of 1+2*n from n=0 to n=m-1, neglecting the modulo operation for a moment.

Using linearity of addition, this sum can be written as m + 2 * sum(n for n=0 to m-1). The remaining sum can be shown to evaluate to m*(m-1)/2, so that the total is

m + 2 * m*(m-1)/2 = m**2

So this method does the same as using (current_pos + m**2) % array_.size() in each iteration with m being the loop counter and without modifying current_pos would.