# Relation between size of hashtable and number of values to keep expected number of collisions below/equal to 1

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)

• The birthday paradox comes to mind – 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.