Suppose that we have a hash table with n slots, with collisions resolved by chaining, and suppose that n keys are inserted into the table. Each key is equally likely to be hashed to each slot. Let M be the maximum number of keys in any slot after all the keys have been inserted. Your mission is to prove an O (lg n/lg lg n) upper bound on E[M], the expected value of M.
a. Argue that the probability Qk that exactly k keys hash to a particular slot is given by Qk = (1/n)k(1 €“ 1/n) n€“k (n/k)..
b. Let Pk be the probability that M = k, that is, the probability that the slot containing the most keys contains k keys. Show that Pk ≤ n Q k..
c. Use Stirling's approximation, equation (3.17), to show that Qk d. Show that there exists a constant c > 1 such that for k0 = clg n/ lg lg n. Conclude that Pk e. Argue that



Conclude that E[M] = O(lg n/ lg lg n)..

Transcribed Image Text:

c lgn n+ Pr Ms Ig lg n clgn clgn E[M]< Pr{M lg lg n Ig lgn