# A hash table has space for $75$ records, then the probability of collision before the table is $6\%$ full

A hash table has space for $75$ records, then the probability of collision before the table is $6\%$ full

1. $0.25$
2. $0.20$
3. $0.35$
4. $0.30$

$\color{Green}{\text{My attempt:}}$

Table has $75$ slots. So, for $6\%$ filling it must take $6$ slots. Now, the question is like this- collision before $6\%$ full. This should mean the first collision happened before the $6th$ entry is made. So, the first collision can happen from $2nd$ entry (for $1st$ entry there won't be a collision) to $6th$ entry. So required probability

$=\cfrac{75\times 1}{75^2}+\cfrac{75\times74\times 2}{75^3}+\cfrac{75\times74\times73\times 3}{75^4}+\cfrac{75\times74\times73\times 72\times4}{75^5}+\cfrac{75\times74\times73\times 72\times71\times5}{75^6}=0.1854$

$\color{Red}{\text{Somewhere it explained as:}}$

To make the table $6\%$ full, we need to insert at least $\lceil{\cfrac{75\times 6}{100}}\rceil = 5$ values.

probability of collision during first insertion $= 0$

probability of collision during second insertion $= 1/75$

probability of collision during third insertion $= 2/75$

probability of collision during fourth insertion $= 3/75$

probability of collision during fifth insertion $= 4/75$

So, total probability of collision to make the table $6\%$ full $= (1+2+3+4)/75 = 0.13$

$\color{blue}{\text{Another explanation is given as :}}$

Explanation: On $.75^{th}$ insertion probability of collision $= 1/75$

On $1.5^{th}$ insertion probability of collision $= 2/75$

On $2.25^{th}$ insertion probability of collision $= 3/75$

On $3^{th}$ insertion probability of collision $= 4/75$

On $3.75^{th}$ insertion probability of collision $= 5/75$

So the required probability is $1+2+3+4+5/75 = 0.20$

First explanation is correct. Alternative solution is:

Table has $75$ slots. So, for $6\%$ filling it must take $6$ slots. Probability of no collision for first $6$ entries $= \cfrac{^{75}P_6}{ 75^6} = 0.814586387$

Therefore, at least one collision occurs in $6$ entries

$= 1 - \text{Probability of no collision for first$6$entries }$

$= 1 - 0.814586387$

$= 0.185413613$

• Thanks for nice explanation. – 1 0 Jul 7 '17 at 10:37