Problem 11.1

Longest probe bound for hashing

Suppose that we use an open-addressed hash table of size $m$ to store $n \le m/2$ items.

  1. Assuming uniform hashing, show that for $i = 1, 2, \ldots, n$, the probability is at most $2^{-k}$ that the $i$th insertion requires strictly more than $k$ probes.
  2. Show that for $i = 1, 2, \ldots, n$, the probability is $\O(1/n^2)$ that the $i$th insertion requires more than $2\lg{n}$ probes.

Let the random variable $X_i$ denote the number of probes required by the $i$th insertion. You have shown in part (b) that $\Pr\{X_i > 2\lg{n}\} = \O(1/n^2)$. Let the random variable $X = max_{1 \le i \le n}X_i$ denote the maximum number of probes required by any of the $n$ insertions.

  1. Show that $\Pr\{X > 2\lg{n}\} = \O(1/n)$.
  2. Show that the expected length $\E[X]$ of the longest probe sequence is $\O(\lg{n})$.