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$
9
  • $\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
    Commented Feb 15, 2016 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
    Commented Feb 15, 2016 at 2:19
  • $\begingroup$ Your answer should be less than 1. For example the answer given below is 0.517 $\endgroup$
    – NoChance
    Commented Feb 15, 2016 at 2:27
  • $\begingroup$ @NoChance my answer is less than 1: ".604" $\endgroup$
    – user311927
    Commented Feb 15, 2016 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
    Commented Feb 15, 2016 at 2:35

1 Answer 1

2
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Can you please explain what i did wrong? $\endgroup$
    – user311927
    Commented Feb 15, 2016 at 2:06

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .