edited by
28,941 views
62 votes
62 votes

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$
edited by

11 Answers

0 votes
0 votes
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

Answer (D) 10
0 votes
0 votes
Answer is 6

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
–3 votes
–3 votes
ans 10
Answer:

Related questions