# After hashing of how many keys will the probability that any new key hashed collides with an existing one exceed 0.5?

Consider a hash function that distributes keys uniformly. The hash table size is 20.

Here I am getting answer 11 considering the fact that probability will of collision will be 50% more only when we already have 10 entries in the hash table and we are about to map one more entry in the hash table .

Is this approach correct ?

• That's fine, provided you are only looking at the probability of the new key colliding. If you are looking for the probability of a collision having occurred at some point before now, then you might be looking at the birthday problem. – Brian Tung Aug 2 '18 at 23:56

## 1 Answer

The probability of collision in each entry will be $\dfrac{1}{20}$

After inserting $k$ values the probability becomes $\dfrac12$

Then we have $\dfrac{1}{20}\times k=\dfrac12$

Therefore, $k=10$

• Not quite -- the probablity at $k=10$ will be lower than $\frac12$ due to the risk that there may be collisions among the first $10$ keys. – Henning Makholm Aug 3 '18 at 0:35
• Don't we consider here the probability of collision among the first 10 keys ? – radhika Aug 4 '18 at 9:12