Question

Consider a hash table with $m$ slots that uses chaining for collision resolution. The table is initially empty. What is the probability that after 4 keys are inserted that at least a chain of size 3 is created? (Assume simple uniform hashing is used)

• A. $m^{–2}$
• B. $m^{–4}$
• C. $m^{–3} (m – 1)$
• D. $3m^{–1}$

Comments

is it (m^2+m-1)/m^4 ?

becoz here its atleast 3 is asked... 3 0r 4 possibilities..

Answer 1

The probability of placing them at different place so than collision does not occur at all is P :

P = (m/m )* (m-1 / m) * ((m-2)/m) * ((m-3)/m)

The probability of getting collision and hence a chain of 2 , 3 , 4 is = 1 -P

From 1-P we have to eliminate the chain of length 2 :

Case 1 : Three elements are placed in different place and one collides with any three of them (Q)

Q = (m/m) * ((m-1)/m) * ((m-2)/m) * (1/m) * 3

Case 2 : out of 4 elements there is chain of length 2 ,2  (R)

R = (m/m) * 1/m * (m-1)/m * 1/m + m/m * (m-1) / m * 1/m * 1/m ( It collides with first key and then with second key) + m/m * (m-1)/m * 1/m * 1/m ( it collides with second key first than with first key )

Therefore i think the ans will be 1-(P+Q+R) .

Comments

@arjun sir plz check this if it is done correctly or not .

---

Hi, you got the mistake here?

---

@Arjun sir actually i saw your solution above and i had one doubt which i mentioned in your ans below . Actually i was thinking that arrangement will be different like  1/m * 1/m * 1/m * m-1 /m and 1/m * m-1/m * 1/m * 1/m  are different arrangements  but your ans says its same .......

I think you said so becoz once keys are given we know its position to place so such thing will not arise ..... plz correct me if i am mistaken ...

Answer 2

Chain of three means , all 4 elements are hashed into single slot ,

 

So , is it (1/m)^4 ?

Comments

I don't know the answer . Need some one to explain it

---

c for atleast 3 case it will be m ways for 1st element... 1 way for 2nd element for collision to occur and 3rd elemnt also will have 1 way for collision and 4th can have m ways...

for atleast 4 case it will be m ways for 1st element and for rest element 1 ways

therefore m^2+m ways... but 1 way is repeating in atleast 3 and 4... that is when all will be in same slot therefore (m^2+m-1)/m^4 ways

---

chain of not length 3 ,size 3 i.e 3 elements in the chain