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 < ek / kk..
d. Show that there exists a constant c > 1 such that for k0 = clg n/ lg lg n. Conclude that Pk < 1/n2< for k ≥ k0 = c lg n/ lg lg n..
e. Argue that

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

  • CreatedJuly 13, 2010
  • Files Included
Post your question