This is an exam question from my algorithms and data structures course.

You imagine an hash function with h: U->{0,..m} (this is from the original question, but i think m-1 would be correct) and n values to hash. You want to keep the expected number of collisions below or equal to 1. How do you determine m in dependence to n.

My initial idea was following formula to determine the number of collisions: $n- E(\text{occupied locations}) = n-m+E(\text{empty locations}) \\$
$= n-m+m(1-\frac{1}{m})^n$

For our question this would give: $ 1 \geq n-m+m(1-\frac{1}{m})^n$

I know that following solution would have been correct (and i know why now):

$E[x]=\frac{n(n-1)}{2} \cdot \frac{1}{m} = m \geq \frac{n(n-1)}{2}$

Well i know i did not solve the first Equation for m (i do not know how), but my question is if both solutions would be correct and if not why?

I got the first Equation from Darthmouth ([Link]:https://math.dartmouth.edu/archive/m19w03/public_html/Section6-5.pdf)

  • $\begingroup$ The birthday paradox comes to mind $\endgroup$ – ratchet freak Mar 29 '18 at 12:22

No, your solution is wrong. The expected number of collisions is not $n- E(\text{occupied locations})$, so you went wrong in the first step of your approach. Try working through a small example or two and hopefully you will see why.

It's possible that your confusion has to do with how we count the number of collisions. If items A,B,C all go into the same hash bucket, we consider that as 3 collisions: A,B are a collision, B,C are a collision, and A,C are a collision.


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.