2
$\begingroup$

So i have a hash table that can hold 100 elements. It currently stores 30 elements. What is the probability that the next 2 inserts will result in at least one collision?

What i did was figure out the sample space to be 100*100=10000, representing all the possible number of different insertions for the 2 insertions (for example: first insertion being in 5th index and second insertion being in 74th index).

Then I tried to get elements of the sample space, which is in the form of (index of first insertion, index of second insertion) that have collisions. First, I counted 30 collisions from the first insertion and multiplied that by 100 since there are 100 possibilities for the second insertion for each of the first insertion. This would get the count of collisions that are guaranteed from first insertion. Then I multiplied this by 2 since there are also 30 collisions from the second insertion and I had to multiply that by 100 since there are 100 possibilities for the first insertion for each of the second insertion. This would get the count of collisions that are guaranteed from second insertion. Since this is overcounting the number of collisions that are the same(For example: if there was a collision at 5th index, first and second insertion being at the 5th index), I subtracted 30 since thats the count of occupied indexes.

Then I added 70 in the case of the first insert not causing collision but the second one causing collision by being inserted in the same place as the first.(For example both insertions being in 7th index when originally index 7 wasnt occupied before the first insertion)

I got .604 as my final answer: (2*30*100-30+70)/10000

Is this the correct answer and approach?

$\endgroup$
  • $\begingroup$ The answer would be somewhat similar to the "Birthday Match" problem in some sense. This may provide a good read:preshing.com/20110504/hash-collision-probabilities $\endgroup$ – NoChance Feb 15 '16 at 2:16
  • $\begingroup$ @NoChance I know I can solve it by using "1- P(no collision)". I just want to know if my way is correct. $\endgroup$ – user311927 Feb 15 '16 at 2:19
  • $\begingroup$ Your answer should be less than 1. For example the answer given below is 0.517 $\endgroup$ – NoChance Feb 15 '16 at 2:27
  • $\begingroup$ @NoChance my answer is less than 1: ".604" $\endgroup$ – user311927 Feb 15 '16 at 2:30
  • $\begingroup$ fine, I don't get what do you mean by "I found all the combinations of first and second inserts that would result in collisions: 2*30*100=6000. 30*100 is for counting the number of collisions from first insert and second insert being anything." $\endgroup$ – NoChance Feb 15 '16 at 2:35
2
$\begingroup$

$$P(\text{Colllision}) = 1 - P(\text{no collision}) = 1 - {70\over100}\cdot{69\over 100}.$$

$\endgroup$
  • $\begingroup$ Can you please explain what i did wrong? $\endgroup$ – user311927 Feb 15 '16 at 2:06

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.