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} $$