How to find the expected number of insertions before a Hash table is full?

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.

• en.wikipedia.org/wiki/Coupon_collector's_problem seems relevant. (Also, as a side note, a conventional hash table implementation will never be full because it will be grown when you get close, and crash when it has no more room to grow.) Commented Mar 3, 2021 at 13:22
• "I would think that the expected number of insertions of elements is $m$" The minimal possible number of insertions to fill the table is $m$. If there are any collisions (assuming you don't place those somewhere else in the same table), you get more than $m$ insertions. Commented Mar 3, 2021 at 13:33
• oh yes. m must be the minimal number. Going to take a look at the the problem you just suggested. Commented Mar 3, 2021 at 13:36
• @Arthur it makes sense. What would happen if I add the following: What is the expected number of insertions if I had two different hash tables to choose from? Let's say that picking either one of the two tables has probability of $\frac{1}{m}$. I.e. What would be the exp. # insertions before any of the two hash tables gets full? Commented Mar 3, 2021 at 14:05

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.$$
• nice. What if I add the following: What would be the expected number of insertions if I had two different hash tables to choose from? Let's say that picking either one of the two tables has probability of $\frac{1}{2}$. I.e. What would be the exp. # insertions before any of the two hash tables gets full? Commented Mar 3, 2021 at 14:05
• Probably you mean "has probability of $\frac12$", don't you?
• yes sorry. ofc: $\frac{1}{2}$ Commented Mar 3, 2021 at 14:09
• That is an interesting problem. I would suggest you to ask it in a separate question. You can even generalize and ask about $n$ tables (each being chosen with probability $\frac1n$).