Quadratic probing variant scheme

Question

Suppose that we are given a key $k$ to search for in a hash table with positions $0, 1, \dots , m-1$, and suppose that we have a hash function $h$ mapping the key space into the set $\{0, 1, \dots , m-1 \}$. The search scheme is as follows:

1. Compute the value $i \gets h(k)$, and set $j \gets 0$.
2. Probe in position $i$ for the desired key $k$. If you find it, or if this position is empty, terminate the search.
3. Set $j \gets (j + 1)\bmod{m}$ and $ i \gets (i+j)\bmod{m}$, and return to step 2.

Question: Show that this scheme is an instance of the general "quadratic probing" scheme by exhibiting the appropriate constants $c_1, c_2$ for the equation: $$h(k,i) = (h(k) + c_1i+c_2i^2) \bmod{m}, \text{ where } i=0,\dots, m-1$$ and $h(k) = k \bmod {m}$.

Attempt:

What we did here is to consider $j$ as a for loop and substitute in $i$:

$$i_0 = h(k), j_0 = 0$$

If we did not find the item and the termination case is not fulfilled, we probe:

$$i_1 = h(k) + j_0 = h(k), j_1 = j_0 + 1 = 1$$

If we did not find the item and the termination case is not fulfilled, we probe:

\begin{gather} i_2 = h(k) + j_1 = h(k) + 1, j_2 = j_1 + 1 = 2 \\ \vdots \\ i_i = h(k) + j_1 = h(k) + 1 + \cdots + (i-1), j_i = i \end{gather}

Problem: Now I realized that sequence $1 + \dots + (i-1)$ gives quadratic term, but it's not from $i=0, \dots, i$ so that I can sum all values as one term is missing, which is the $i$th term. What do you think please?

Problem 2: Prove that this algorithm examines every table position in the worst case. I would like to ask you here about general approach to solve this question not detailed solution. So, here it's sufficient as I understood to show that for two probing sequences, we won't end up in the same slot and that guarantees that we will examine every single slot in the hash table. Could you please explain if this approach sounds right for you and what would you propose in this case please?

Answer 1

The $i$'th value probed by your algorithm (counting from $1$) is $$ h(k) + 1 + \cdots + i-1 \equiv h(k) + \frac{i(i-1)}{2} \equiv h(k) - \frac{1}{2} i + \frac{1}{2} i^2 \pmod{m}, $$ which is of the required form.

In order to show that you examine every table position in the worst case, you need to show that for each $j \in \{0,\ldots,m-1\}$ there exists $i \geq 0$ such that $\frac{i(i-1)}{2} \equiv j \pmod{m}$. This happens to be the case iff $m$ is a power of 2.

Indeed, suppose first that $m$ is odd, and consider the sequence $h(0,0),\ldots,h(0,m-1)$. We have $$ h(0,i) = \frac{i(i-1)}{2} \equiv \frac{(m-i)(m-i+1)}{2} = h(0,m+1-i) \pmod{m}, $$ and so the sequence is palindromic. Since $h(0,i)$ only depends on $i \bmod{m}$, this implies that $h(0,i)$ only goes over $\frac{m+1}{2}$ different values.

If $m$ is not a power of 2, then it has some odd factor $m' > 1$. If $h(0,i)$ went over all values in $\{0,\ldots,m-1\}$, then $h(0,i) \bmod{m'}$ would have gone over all values in $\{0,\ldots,m'-1\}$, which we have seen above to be false.

Conversely, suppose that $m$ is a power of 2. If $0 \leq i < j < m$ then $$ h(0,j) - h(0,i) \equiv (1 + \cdots + j) - (1 + \cdots + i) \equiv (i+1) + \cdots + j \equiv \frac{(j-i)(i+j+1)}{2} \pmod{m}. $$ Exactly one of $j-i,i+j+1$ is even. Moreover, $1 \leq j-i \leq m-1$ and $2 \leq i+j+1 \leq 2m-2$. Hence after division by 2, none of these can be a multiple of $m$. Thus $h(0,0),\ldots,h(0,m-1)$ are all different, and so they go over all possible values.