If I have a hash table with $m$ slots and each slot has $1/m$ probability of being picked for an insertion of an element. What is the expected number of insertions before all slots are full?
I would think that the expected number of insertions of elements is $m$ but not sure because an element can also hash to another element's slot? Reason for this thought is: $$\mathbb{E}[X]=\sum_x^{m}Pr[X=x] = \sum_x^{m}\frac{1}{m}=1$$
Where after $m$ insertions where each insertion has $1/m$ probability, the hash table is full. I don't care about what to do with the elements that collide. For simplicity sake we can just discard them.
Best Answer
This question is well-known as Coupon collector problem, so that the expected number of insertions until all slots are full is: $$\mathbb{E}[X]=m H_m $$ where $H_m$ is the harmonic number: $$ H_m=\sum_{k=1}^m\frac1k. $$