Hash Crash Revolutions

Relevant wiki: Coupon Collector Problem

Assume that we have a total of $n$ slots, of which $m-1$ distinct slots are occupied. Then let's first compute the number of additional elements that need to be inserted so that $m$ distinct slots are occupied. Clearly, the probability that a newly inserted element occupies a previously unoccupied slot is $p_{\text{succ}}(m)=\frac{n-m+1}{n}$ . Hence we need $\frac{1}{p_{\text{succ}}(m)}=\frac{n}{n-m+1}$ additional element, in expectation, for the required transition. As a result, total number of elements $N$ required, in expectation to fill up the entire Hash table is $N=\sum_{m=1}^{n}\frac{n}{n-m+1}=nH_n,$ where $H_n$ is the $n$ th harmonic number, which may be readily computed.