Problem 11.3

Quadratic probing

Suppose that we are given a key $k$ to search for in 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$.

  1. 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 (11.5).
  2. Prove that this algorithm examines every table position in the worst case.