1
$\begingroup$

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$


Can you explain it, please?

$\endgroup$
0
$\begingroup$

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$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.