7,624 views
12 votes
12 votes

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)

  1. $m^{–2}$
  2. $m^{–4}$
  3. $m^{–3} (m – 1)$
  4. $3m^{–1}$

6 Answers

Best answer
36 votes
36 votes

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

edited by
6 votes
6 votes
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
0 votes
0 votes
I think that should be a probablity question of selecting 3 slots each time

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

Related questions

0 votes
0 votes
1 answer
1
tishhaagrawal asked Dec 16, 2023
315 views
Below is my approach to solving this question, can anyone please explain if I am doing it the right way?Let X = #free slotssince, m =7 and n = 3So, $4 \leqslant x\leqsla...
2 votes
2 votes
1 answer
4
Arjun asked Jan 11, 2016
461 views
How do you compare associativity (in cache) to chaining in hash table?