# 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.) Mar 3 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. Mar 3 at 13:33
• oh yes. m must be the minimal number. Going to take a look at the the problem you just suggested. Mar 3 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? Mar 3 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? Mar 3 at 14:05
• Probably you mean "has probability of $\frac12$", don't you?
• yes sorry. ofc: $\frac{1}{2}$ Mar 3 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$).