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
    Commented Mar 3, 2021 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
    Commented Mar 3, 2021 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$ Commented Mar 3, 2021 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$ Commented Mar 3, 2021 at 14:05

1 Answer 1

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .