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

a. 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}.\]

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 \le n Q_k\).

c. Use Stirling's approximation, equation \(\text{(3.18)}\), to show that \(Q_k < e^k / k^k\).

d. 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\).

e. Argue that

\[\text 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 \(\text E[M] = O(\lg n / \lg\lg n)\).

(Removed)

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用