Longest-probe bound for hashing

A hash table of size m is used to store n items, with n ≤ m/2. Open addressing is used for collision resolution.

a. Assuming uniform hashing, show that for i = 1, 2, ..., n, the probability that the ith insertion requires strictly more than k probes is at most 2-k.

b. Show that for i = 1, 2, ..., n, the probability that the ith insertion requires more than 2 lg n probes is at most 1/n2.Let the random variable Xi denote the number of probes required by the ith insertion. You have shown in part (b) that Pr {Xi > 2lg n} ≤ 1/n2. Let the random variable X = max1≤i≤n Xi denote the maximum number of probes required by any of the n insertions.

c. Show that Pr{X > 2lg n} ≤ 1/n.

d. Show that the expected length E[X] of the longest probe sequence is O(lg n).