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 ?

  • 1
    $\begingroup$ 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. $\endgroup$ – Brian Tung Aug 2 '18 at 23:56

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$

  • $\begingroup$ 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. $\endgroup$ – Henning Makholm Aug 3 '18 at 0:35
  • $\begingroup$ Don't we consider here the probability of collision among the first 10 keys ? $\endgroup$ – radhika Aug 4 '18 at 9:12

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.