Longest-probe bound for hashing Suppose that we use an

Chapter 11, Problem 11-1

(choose chapter or problem)

Longest-probe bound for hashing Suppose that we use an open-addressed hash table of size m to store n m=2 items. a. Assuming uniform hashing, show that for i D 1; 2; : : : ; n, the probability is at most 2k that the ith insertion requires strictly more than k probes. b. Show that for i D 1; 2; : : : ; n, the probability is O.1=n2/ that the ith insertion requires more than 2 lg n probes. Let the random variable Xi denote the number of probes required by the ith insertion. You have shown in part (b) that Pr fXi > 2 lg ng D O.1=n2/. Let the random variable X D max1 i n Xi denote the maximum number of probes required by any of the n insertions. c. Show that Pr fX>2 lg ng D O.1=n/. d. Show that the expected length E X of the longest probe sequence is O.lg n/.