TAOCP 6.4 Exercise 25
Equation (39) expresses the probability that $N$ distinct keys $K_1,\dots,K_N$ hash into $N$ distinct table positions when each key is assumed to be mapped independently and uniformly into a hash tabl...
Exercise 25. [M19] [M19] Explain why Eq. (39) is true.
Verified: yes
Solve time: 1m09s
Solution
Equation (39) expresses the probability that $N$ distinct keys $K_1,\dots,K_N$ hash into $N$ distinct table positions when each key is assumed to be mapped independently and uniformly into a hash table of size $M$.
Under the uniform hashing assumption, each key $K_i$ takes any of the $M$ values $0,1,\dots,M-1$ with probability $1/M$, independently of the other keys. The event described by Eq. (39) is that no collisions occur, meaning the values $h(K_1),\dots,h(K_N)$ are all distinct.
For $K_1$, there are no restrictions, so any of the $M$ values is admissible. For $K_2$, the condition $h(K_2)\neq h(K_1)$ removes exactly one admissible value, leaving $M-1$ choices. For $K_3$, the values $h(K_1)$ and $h(K_2)$ are already occupied, leaving $M-2$ admissible choices. Continuing in this manner, when placing $K_i$, exactly $i-1$ hash values are already used, leaving $M-(i-1)$ choices.
The total number of outcomes of the hash assignment process is $M^N$, since each of the $N$ keys independently chooses among $M$ values. The number of outcomes with no collisions is
$$ M(M-1)(M-2)\cdots (M-N+1). $$
The required probability is therefore the ratio
$$ \frac{M(M-1)\cdots (M-N+1)}{M^N}. $$
Dividing each factor in the numerator by $M$ yields
$$ \prod_{k=0}^{N-1}\left(1-\frac{k}{M}\right), $$
which is the form stated in Eq. (39).
This completes the proof. ∎