hashing

Question

Consider a hash table with 10 slots. Collisions are resolved using linear probing. The probability that if first 3 slots are unfilled and 4th insertions leads to a collisions

Comments

$\frac{63}{1000}$ ??

---

first 3 slot and no collision tiil 3 insertion = $\frac{7}{10}\times \frac{6}{10}\times\frac{5}{10}$

Now 4rth one lead to Collision = $\frac{7}{10}\times \frac{6}{10}\times\frac{5}{10}\times \frac{3}{10} = \frac{63}{1000}$

---

How 4 th one probabilty will be 3/10

Please explain?

---

Since linear probing is used ..The 1st element will have the 7 places(as first 3 has to be empty) to get a position out of 10 places so 7/10

 

now for the 2nd element it would get the probability of 6/10 (here linear probing is used for the collision resolution not Chaining)

Similarly 3rd key has the probability of 5/10

Now For the 4th insertion Which indeed lead to a collision it has only 3 choices(to have a collision it must attack the places which are filled by above 3 elements) out of 10 places so 3/10

So the answer is 7/10 * 6/10 * 5/10 * 3/10