Problem 11.2

Slot-size bound for chaining

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 that an $\O(\lg{n}/\lg\lg{n})$ upper bound on $\E[M]$, the expected value of $M$.

1. Argue that the probability $Q_k$ that exactly k keys hash to a particular slot is given by $$Q_k = \bigg(\frac{1}{n}\bigg)^k\bigg(1 - > \frac{1}{n}\bigg)^{n-k}\binom{n}{k}$$
2. Let $P_k$ be the probability that $M = k$, that is, probability that the slot containing the most keys contains $k$ keys. Show that $P_k \le nQ_k$.
3. Use Stirling's approximation, equation (3.18), to show that $Q_k < e^k/k^k$.
4. Show that there exists a constant $c > 1$ such that $Q_{k_0} < 1 / n^3$ for $k_0 = c\lg{n}/\lg\lg{n}$. Conclude that $P_k < 1/n^2$ for $k \ge k_0 = c\lg{n}/\lg\lg{n}$.
5. Argue that $$\E[M] \le \Pr\bigg\{M > \frac{c\lg{n}}{\lg\lg{n}}\bigg\} \cdot n + \Pr\bigg\{M \le \frac{c\lg{n}}{\lg\lg{n}}\bigg\} \cdot \frac{c\lg{n}}{\lg\lg{n}}$$ Conclude that $\E[M] = \O(\lg{n}/\lg\lg{n})$.