6.1k views

Consider a hash function that distributes keys uniformly. The hash table size is $20$. After hashing of how many keys will the probability that any new key hashed collides with an existing one exceed $0.5$.

1. $5$
2. $6$
3. $7$
4. $10$
in DS
edited | 6.1k views
0
Does anybody know what the official answer to this question in the answer key is? I'm getting 7 as the answer.

0.5 < $\frac{Number / of / elements / already / inserted + 1}{20}$

==> 20 x 0.5 <  Number of elements already inserted + 1

==> Number of elements already inserted > 20 x 0.5 -1

==> Number of elements already inserted > 9

by Active (1.4k points)

Let's take example key mod 20

Ans consider 0 to 5 filled

If new number index is 0 then 6 collision

If position is 1 then 5 collision

As well for all 6 position

All collision value is 21 and free slots are 14 now here probability is greater than. 5
by (27 points)
ans 10
by Loyal (5.2k points)
+4
I think it's answer is (A) that is after insertion of 5 keys, the insertion of new key will exceed 0.5...

and (10) not be the answer.. even if I think in that way that insert 10 keys.. then we have 10 slots vacat.. probability of collision = 10 / 20 = 0.5.. He used the word "exceed".. exceed means greater than.. It doesn't mean "greater and equal", but it is equal.. !!

explaination:

probability of inserting a new key is not independent they depends on previous insertions. So basically it is a conditional probability.. p("insetion of new key" | "insertion of m keys")

We are asking to insert the new key with probablity exceeds 0.5

0.5 < probabiltity of collision when (m + 1) keys are inserted!!

=> 0.5 < 1 - p(all are hashed to a different location)

after insertion of 5 keys

p(all are...) = 1 * 19/20 * 18/20 * 17/18 * 16/20 = 0.581  => 1 - 0.581 = 0.418 < 0.5..

after insertion of 6 th keys

it exeedes 0.5..

so, after hashing of 5 keys new key hashsed collides with an existing one exceed 0.5..