This is a question from CLRS

Q) Suppose that we have a hash table with n slots, with collisions resolved by chain-ing, 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.

a) Argue that the probability Q$_{k}$ that exactly $k$ keys hash to a particular slot is given by

Q$_{k}$ = ($\frac{1}{n})$$^{k}$(1-$\frac{1}{n}$)$^{n-k}$ $\binom{n}{k}$.

Which is pretty straight forward as hashing of a particular key at any slot is binomial trial with prob. of success = ($\frac{1}{n}$) and prob. of failure = (1-$\frac{1}{n}$) . So according to binomial trial

probability that exactly k keys hash to a particular slot is

Q$_{k}$ = ($\frac{1}{n})$$^{k}$(1-$\frac{1}{n}$)$^{n-k}$ $\binom{n}{k}$.

b) Let P$_{k}$ be the probability that $M = k$, that is, the probability that the slot containing the most keys contains $k$ keys. Show that $P_{k} \leq nQ_{k}$.

Which is, that a particular slot contains exactly $k$ keys and other slots less than $k$ keys.

Pr (a slot contains less than $k$ keys)= It contains 0 keys or It contains 1 key or It contains 2 keys........ or it contains k-1 keys

Given by

($\frac{1}{n})$$^{0}$(1-$\frac{1}{n}$)$^{n-0}$ $\binom{n}{0}$ + ($\frac{1}{n})$$^{1}$(1-$\frac{1}{n}$)$^{n-1}$ $\binom{n}{1}$+......+ ($\frac{1}{n})$$^{k-1}$(1-$\frac{1}{n}$)$^{n-(k-1)}$ $\binom{n}{k-1}$.

So $P_{k}$ = $Q_{k}$ . Pr (a slot contains less than $k$ keys) = $\left(\frac{1}{n}\right)^k\left(1-\frac{1}{n}\right)^{n-k}\binom{n}{k}\times\Bigg(\left(\frac{1}{n}\right)^{0}\left(1-\frac{1}{n}\right)^{n-0} \binom{n}{0} + \left(\frac{1}{n}\right)^{1}\left(1-\frac{1}{n}\right)^{n-1}\binom{n}{1}+\cdots+ \left(\frac{1}{n}\right)^{k-1}\left(1-\frac{1}{n}\right)^{n-(k-1)}\binom{n}{k-1}\Bigg)$

My question is that how do i converge this. ?


To solve the task you should consider events $E_i$ which is that $i-$slot has $k$ elements hashed into and all other slots have less elements. Thus, $Pr(E_i) \le Q_k.$

From above $Pr(M=k) \le \Sigma_{i=1}^nE_i = nE_i \le nQ_k.$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.