1
$\begingroup$

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?

slots

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.

$\endgroup$
4
  • 2
    $\begingroup$ 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.) $\endgroup$
    – Arthur
    Mar 3 at 13:22
  • 1
    $\begingroup$ "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. $\endgroup$
    – Arthur
    Mar 3 at 13:33
  • $\begingroup$ oh yes. m must be the minimal number. Going to take a look at the the problem you just suggested. $\endgroup$ Mar 3 at 13:36
  • $\begingroup$ @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? $\endgroup$ Mar 3 at 14:05
1
$\begingroup$

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. $$

$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$ Mar 3 at 14:05
  • $\begingroup$ Probably you mean "has probability of $\frac12$", don't you? $\endgroup$
    – user
    Mar 3 at 14:08
  • $\begingroup$ yes sorry. ofc: $\frac{1}{2}$ $\endgroup$ Mar 3 at 14:09
  • 1
    $\begingroup$ 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$). $\endgroup$
    – user
    Mar 3 at 14:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.