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

We have two cases which are mutually exclusive

1. A chain of length exactly 3
2. A chain of length 4

Our required probability will be the sum of these 2 cases. 

$\text{Probability of length exactly } 3 = \text{No. of ways of selecting a slot} \times \text{Probability of exactly 3 hashing going to that slot} \\= {}^mC_1 \times 4C1 \times \frac{1}{m} \frac{1}{m} \frac{1}{m} \frac{m-1}{m}\\=  4 \frac {m-1}{m^3}$

$\text{Probability of length }4 = \text{No. of ways of selecting a slot} \times \text{Probability of 4 hashing going to that slot} \\= {}^mC_1 \times \frac{1}{m} \frac{1}{m} \frac{1}{m} \frac{1}{m}\\= \frac {1}{m^3}$

So, our required probability $= 4. \frac {m-1}{m^3} + \frac {1}{m^3} \\= \frac{4.m-3}{m^3}$.

Comments

Why are we not permuting the elements inside the chain itself?

eg For a chain of length 3 with 3 elements chosen from 1,2,3,4

(Let 1,2,3 are chosen) The chain could be $1\rightarrow 2\rightarrow 3$

or $2\rightarrow 3\rightarrow 1$ and so on 3! permutations.

---

In hashing we do mod n operation. So elements are in ascending order. hence no permutation. 2 ->3 -> 1 order is not there.

---

But this option is not in the question. Is it the right answer?

Answer 2

Consider any one slot among N slots.The probability  that three elements will be entered in  same slot is 1/m*1/m*1/m = m^-3.As there are m slot you can choose any slot among m slot.So answer is m*m^-3 = m^-2

Answer 3

Solution to exactly similar kind of problem

Comments

To the point SP

---

good explanation !

Answer 4

I think that should be a probablity question of selecting 3 slots each time

mC3*(1/m)^3*(1-1/m)^m-3