TAOCP 6.4 Exercise 42
Let $M$ be the number of hash addresses and let $n$ be the number of occupied cells at the moment a new key $K$ is inserted by Algorithm C.
Exercise 42. [M20] [M20] Derive (17), the probability that Algorithm C succeeds immediately.
Verified: yes
Solve time: 1m21s
Solution
Let $M$ be the number of hash addresses and let $n$ be the number of occupied cells at the moment a new key $K$ is inserted by Algorithm C. Under the uniform hashing assumption, the address $h(K)$ is equally likely to be any of the $M$ cells, independent of the placement of the $n$ stored keys.
Algorithm C succeeds immediately precisely when the first probe examines an empty cell, that is, when $h(K)$ is not among the occupied addresses.
Since exactly $n$ of the $M$ addresses are occupied, exactly $M-n$ addresses are empty. The probability that a uniformly chosen address is empty is therefore
$$ \frac{M-n}{M}. $$
Writing $\alpha = n/M$ for the loading density, this becomes $1 - \alpha$.
Thus the probability that Algorithm C succeeds immediately is
$$ \boxed{1 - \frac{n}{M}}. $$
This completes the derivation. ∎