11-3 Quadratic probing

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

  1. Compute the value $j = h(k)$, and set $i = 0$.
  2. Probe in position $j$ for the desired key $k$. If you find it, or if this position is empty, terminate the search.
  3. Set $i = i + 1$. If $i$ now equals $m$, the table is full, so terminate the search. Otherwise, set $j = (i + j) \mod m$, and return to step 2.

Assume that $m$ is a power of $2$.

a. Show that this scheme is an instance of the general "quadratic probing" scheme by exhibiting the appropriate constants $c_1$ and $c_2$ for equation $\text{(11.5)}$.

b. Prove that this algorithm examines every table position in the worst case.

a. From how the probe-sequence computation is specified, it is easy to see that the probe sequence is

$$\langle h(k), h(k) + 1, h(k) + 1 + 2, h(k) + 1 + 2 + 3, \ldots, h(k) + 1 + 2 + 3 + \cdots + i, \ldots \rangle,$$

where all arithmetic is modulo $m$. Starting the probe numbers from $0$, the $i$th probe is offset (modulo $m$) from $h(k)$ by

$$\sum_{j = 0}^i j = \frac{i(i + 1)}{2} = \frac{1}{2}i^2 + \frac{1}{2}i.$$

Thus, we can write the probe sequence as

$$h'(k, i) = \Big(h(k) + \frac{1}{2} i + \frac{1}{2} i^2 \Big) \mod m,$$

which demonstrates that this scheme is a special case of quadratic probing.

b. Let $h'(k, i)$ denote the ith probe of our scheme. We saw in part (a) that $h'(k, i) = (h(k) + i(i + 1) / 2) \mod m$. To show that our algorithm examines every table position in the worst case, we show that for a given key, each of the first $m$ probes hashes to a distinct value. That is, for any key $k$ and for any probe numbers $i$ and $j$ such that $0 \le i < j < m$, we have $h'(k, i) \ne h'(k, j)$. We do so by showing that $h'(k, i) = h'(k, j)$ yields a contradiction.

Let us assume that there exists a key $k$ and probe numbers $i$ and $j$ satsifying $0 \le i < j < m$ for which $h'(k, i) = h'(k, j)$. Then

$$h(k) + i(i + 1) / 2 = h(k) + j(j + 1) / 2 \mod m,$$

which in turn implies that

$$i(i + 1) / 2 = j(j + 1) / 2 \mod m,$$

or

$$j(j + 1) / 2 - i(i + 1) / 2 = 0 \mod m.$$

Since $j(j + 1) / 2 - i(i + 1) / 2 = (j - i)(j + i + 1) / 2$, we have

$$(j - i)(j + i + 1) / 2 = 0 \mod m.$$

The factors $j - i$ and $j + i + 1$ must have different parities, i.e., $j - i$ is even if and only if $j + i + 1$ is odd. (Work out the various cases in which $i$ and $j$ are even and odd.) Since $(j - i)(j + i + 1) / 2 = 0 \mod m$, we have $(j - i)(j + i + 1) / 2 = rm$ for some integer $r$ or, equivalently, $(j - i)(j + i + 1) = r \cdot 2m$. Using the assumption that $m$ is a power of $2$, let $m = 2^p$ for some nonnegative integer $p$, so that now we have $(j - i)(j + i + 1) = r \cdot 2^{p + 1}$. Because exactly one of the factors $j - i$ and $j + i + 1$ is even, $2^{p + 1}$ must divide one of the factors. It cannot be $j - i$, since $j - i < m < 2^{p + 1}$. But it also cannot be $j + i + 1$, since $j + i + 1 \le (m - 1) + (m - 2) + 1 = 2m - 2 < 2^{p + 1}$. Thus we have derived the contradiction that $2^{p + 1}$ divides neither of the factors $j - i$ and $j + i + 1$. We conclude that $h'(k, i) \ne h'(k, j)$.