Suppose our hash table has slots. Under the simple uniform hashing assumption, what is the minimum number of distinct elements that needs to be inserted to ensure that the probability of a hash collision is at least ?
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
The probability that there are no collision after n insertions is Q n = 1 0 0 0 n 1 0 0 0 × 9 9 9 × ⋯ × ( 1 0 0 0 − n + 1 ) . Hence the probability that there exist a collision is P n = 1 − Q n . The problem wants us to find n such that P n ≥ 0 . 5 → Q n ≤ 0 . 5 . Iterate through all n to find such answer.