11.5 Perfect hashing
11.5-1 \(\star\)
Suppose that we insert \(n\) keys into a hash table of size \(m\) using open addressing and uniform hashing. Let \(p(n, m)\) be the probability that no collisions occur. Show that \(p(n, m) \le e^{-n(n - 1) / 2m}\). (\(\textit{Hint:}\) See equation \(\text{(3.12)}\).) Argue that when \(n\) exceeds \(\sqrt m\), the probability of avoiding collisions goes rapidly to zero.
\[
\begin{aligned}
p(n, m) & = \frac{m}{m} \cdot \frac{m - 1}{m} \cdots \frac{m - n + 1}{m} \\\\
& = \frac{m \cdot (m - 1) \cdots (m - n + 1)}{m^n}.
\end{aligned}
\]
\[
\begin{aligned}
(m - i) \cdot (m - n + i)
& = (m - \frac{n}{2} + \frac{n}{2} - i) \cdot (m - \frac{n}{2} - \frac{n}{2} + i) \\\\
& = (m - \frac{n}{2})^2 - (i - \frac{n}{2})^2 \\\\
& \le (m - \frac{n}{2})^2.
\end{aligned}
\]
\[
\begin{aligned}
p(n, m) & \le \frac{m \cdot (m - \frac{n}{2})^{n - 1}}{m^n} \\\\
& = (1 - \frac{n}{2m}) ^ {n - 1}.
\end{aligned}
\]
Based on equation \(\text{(3.12)}\), \(e^x \ge 1 + x\),
\[
\begin{aligned}
p(n, m) & \le (e^{-n / 2m})^{n - 1} \\\\
& = e^{-n(n - 1) / 2m}.
\end{aligned}
\]
本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用