GATE IT 2007 | Question: 28

Question

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$.

• A. $5$
• B. $6$
• C. $7$
• D. $10$

Comments

Does anybody know what the official answer to this question in the answer key is? I'm getting 7 as the answer.

---

rawan no official keys in 2007

---

To understand the probability calculation this may help

https://gateoverflow.in/2272/gate1997-12

---

thanks brother it hepled me a lot. Now I understood the whole concept.

---

This question is feel like birthday paradox

watch this video  then read arjun sir’s comment you will get easily

https://www.youtube.com/watch?v=ofTb57aZHZs

---

Thank you for the video.

---

Thanks for the video.

---

Which is the correct answer here D or B?

Personally I am getting ‘D’ as the answer.

---

After hashing of $\text{how many keys}$ will the probability that any new key hashed collides with an existing one exceed $0.5$.

If we insert a new key then it will collide with existing one and probability of collision $> 0.5$

 $\therefore \text{Probability of collision > 0.5}$

$1 – \text{P(No collision)>0.5}$

Let’s see if we insert $5$ keys then what happens:

$1-(1\times (\frac{20-1}{20})\times (\frac{20-2}{20})\times (\frac{20-3}{20})\times (\frac{20-4}{20}))$
$1-(1\times \frac{19}{20}\times \frac{18}{20}\times \frac{17}{20}\times \frac{16}{20})$
$1-0.5814 = 0.4186$

$\color{Red}0.4186<0.5$

Now we see if $6^{th}$ key inserted what will happen:

$1-(1\times (\frac{20-1}{20})\times (\frac{20-2}{20})\times (\frac{20-3}{20})\times (\frac{20-4}{20})\times (\frac{20-5}{20}))$
$1-(1\times \frac{19}{20}\times \frac{18}{20}\times \frac{17}{20}\times \frac{16}{20}\times \frac{15}{20})$
$1-0.43605 = 0.56395$

$\color{Green}0.56395>0.5$

But the question which is asked a bit ambiguous statement.
My thought:
After hashing of “how many keys” will the probability that any new key hashed collides with an existing one exceed $0.5$.

After hashing of $5$ keys probability that any new key $(6^{th})$ hashed collides with an existing one exceed $0.5$.

Means After hashing of $5$ keys if we hash a new key $(6^{th})$ which collides with an existing one then the probability of collision will exceed $0.5$. which is TRUE.

According to me the ans should be: $A. 5$

$D. 10$ can’t possible as there probability will be equal to $0.5$. Here, $11$ should be ans where probability exceed $0.5$.

---

Similar question asked here:

https://gateoverflow.in/3284/gate-it-2008-question-23

---

@Akash 15

Yes, i agree with you Akash 

---

The Question
A hash table has 20 slots.

Keys are placed randomly into these 20 slots.

We want to know:

After how many inserted keys is it more likely than not that at least one collision has happened?

A collision means:

Two different keys go to the same slot.
Very Important Interpretation
The question does not ask:

“What is the chance that the next key collides?”

Instead, it asks:

“After inserting several keys, what is the probability that some collision has already occurred?”

This is exactly like the birthday paradox.

Step 1: First Key
Insert 1 key.

It goes into some slot.
No collision is possible.
Probability of collision = 0

Step 2: Second Key
To avoid collision, the second key must go to one of the remaining 19 empty slots.

Probability of no collision:


19/20 = 0.95
Probability of collision:


1 - 0.95 = 0.05
Only 5%.

Step 3: Third Key
Two slots are occupied.

To avoid collision, the third key must go to one of 18 empty slots.

Probability of no collision so far:


(19/20) × (18/20)
= 0.855
Probability of at least one collision:


1 - 0.855 = 0.145
14.5%.

Continue Multiplying
Every new key must avoid all previously used slots.

After 4 Keys
No collision:


(19/20)(18/20)(17/20)
≈ 0.72675
Collision:


1 - 0.72675 = 0.27325
27.3%.

After 5 Keys
No collision:


≈ 0.5814
Collision:


≈ 0.4186
41.9%.

Still less than 50%.

After 6 Keys
No collision:


≈ 0.436
Collision:


≈ 0.564
56.4%.

Now it is greater than 50%.

Answer 1

The question is a bit ambiguous.

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

Here, 'new key hashed' is the ambiguity. It can mean the probability of a collision in the next 'hash', or the probability of a collision in any of the hashes of the 'new keys' starting from the first insertion. For the first case answer must be $10$ to get probability equal to $0.5$, and so $11$ must be the answer for probability $> 0.5$. Thus we can conclude from given choices, it is the second case. 

So, we need to find $n$ such that after $n$ hashes, probability of collision (in any of the $n$ hashes)  $> 0.5$. 

Probability that there will be a collision after $n$ hashes (a collision happened in at least one of those $n$ hashes) $= 1 - $Probability that there was no collision in the first $n$ hashes

$= 1 - 1. \frac{19}{20} . \frac{18}{20} \dots \frac{20-n+1}{20}$. 

So, we need,

$0.5 < 1 - 1. \frac{19}{20} . \frac{18}{20} \dots \frac{20-n+1}{20}$. 

$\implies \frac{19}{20} . \frac{18}{20} \dots \frac{20-n+1}{20} < 0.5$.

For $n=5$, we get, $0.5814$ and for $n=6$, we get $0.43605$. So, answer should be $n = 6$.

Correct Answer: $B$

Comments

@nidhi_kumari

No, this method is incorrect. 

If you take hash table size as 50, then the answer we get through Arjun Sir's Method is 9, but this method gives the answer as 8.

---

This is the corrected calculation, you intended to perform

---

@nidhi_kumari

NO, it's a flawed approach; it calculates something else, not what's asked in the question
if we follow your approach then we'll be finding expected number of collisions

When you calculate: 1/20 + 2/20 + 3/20 + 4/20 + 5/20 = 15/20 = 0.75

here, 0.75 is the expected number of collisions when hashing 6 keys

Answer 2

He has asked "after how many insertion" or in which insertion probability will be >= 0.5

So after 10 keys has been inserted probability of collision will be 0.5

We can simply think like this :there are 20 slots out of which 10 are full. So there is half probability of collision. if there were less than 10 values prob. of collision would never exceed 1/2 rather it would decrease.

So answer less than 10 is not possible at all

Correct answer is (D) only.

Also probability in 'k' th insertion is  (k-1)/20

(k-1)/20 >=0.5

which gives k>=11

means in 11 th insertion we get required prob .  OR after inserting 10 values prob will exceed 0.5

Comments

This is the most logical and beautiful solution of this question.

---

It is important to note that 

Also probability in k ^th insertion is  (k-1)/20 

It means the probability of collision at k^th insertion ,it is not the probability of first collision at k^th insertion like in this question  https://gateoverflow.in/2272/gate1997-12 c part   :)

---

waoo what a beautiful sol u given with best logic

---

Not correct solution

because when we are inserting keys the probability goes like 1/20+ 1/19+ 1/18..... + 1/14  

after this if you insert new key it is possible then probability of collision exceeds 0.5

so after inserting 7 keys now if you insert one more key probability of collision will exceed 0.5

So ans is C) 7

Answer 3

Ans: D (10)

Comments

I think answer is (D).

• These three links are supporting your answer and are logical too.

https://math.stackexchange.com/questions/2870603/after-hashing-of-how-many-keys-will-the-probability-that-any-new-key-hashed-coll

https://www.geeksforgeeks.org/gate-gate-it-2007-question-28/

https://prepinsta.com/questions-hash-tables-sapient-razorfish/

 

• But below given link is supporting answer selected as best answer and giving the same explanation as above.

https://gatecse.in/w/images/4/4c/Hashng.pdf

 

---

Isn't this same as "The probability of collision on the (i+1)th insertion exceeding 0.5?

https://gateoverflow.in/2272/gate1997-12

Part C. Here we considered the probabilities of no collisions till i insertions in the solution. Why didn't we consider it here?

---

@Kuljeet Shan 

The probability of collision for 11th insertion (after 10 hashing) will be exactly 10/20 =0.5

After 11 hashing (for 12th) prob. of collision>0.5

 

Answer 4

tell me if this approach is right or wrong
chances of collision of first element =0
chances of collision of 2nd element is 1/20

chances of collision of 3rd element is 2/20
.
.
.
.
and so on
we have to insert elements till our probability doesnt exceed 0.5 and the moment it exceeds 0.5 we take that nth number as our answer
probability = 0+1/20+2/20+3/20+4/20+...... so on till our value doesnt exceed 0.5
we can see for 5 elements our probability becomes => (0+1/20+2/20+3/20+4/20) which is equal to 0.5
now when we include 6 th element our probabilty will become 0.5+5/20 which is greater than 0.5 so 6 should be answer

Comments

NO, it's a flawed approach; it calculates something else, not what's asked in the question
if we follow your approach then we'll be finding expected number of collisions

When you calculate: 1/20 + 2/20 + 3/20 + 4/20 + 5/20 = 15/20 = 0.75

then 0.75 is the expected number of collisions when hashing 6 keys

Answer 5

After the 10th insertion, probability of collision of new key hashed= 10/20= 0.5

After 11th insertion, probability of collision of new key hashed= 11/20 > 0.5

We are asked after which insertion, probability of collision of new key hashed exceeds 0.5. So it should be 11.

Comments

nice concept

Answer 6

Very Simple Question:

When first key is inserted : probability of collision: 0

When Second key is inserted : probability of collision: 1/20 , because there is only one place at which collision is possible out of 20 places

When Third key is inserted : probability of collision: 2/20... and so on.

Answer is :10