Test by Bikram | Data Structures | Test 2 | Question: 9

Question

Suppose you have a hash table that can hold $100$ elements. It currently stores $30$ elements (in one of $30$ possible different locations in the hash table).  The probability that your next two inserts will cause at least one collision is  ( by assuming a totally random hash function)   __________

Comments

We need to round off till 2 decimals ..

0.5170 is taken as wrong answer :(

Answer 1

Second Method to solve this problem :-
3 cases are possible when we insert 2 elements in hash table

Case 1- Collision on First insertion and Not Collision on Second Insertion

            P(case-1) = (30/100)* (69/100) = 0.207

Case 2- Not Collision on First insertion and Collision on Second Insertion

            P(case-2) = (70/100)* (31/100) =0.217

Case 3- Collision on both First insertion and Second Insertion

       P(case-3) = (30/100)*(31/100) = 0.093

Finally,

 Required Probability = P(Case-1) or P(Case-2) or P(Case-3)

                              =0.207 + 0.217 + 0.093 = 0.517

Note - This method is only efficient when number of insertion is less.

Comments

@ShiveshRoy @Bikram shouldnt it be 30/100 and 30/100 for collision on first insertion means that we are hasihng to one of the 30 possible options and 2nd time collision also means that we are hashing again to one of these 30 slots ... pls explain ..

Answer 2

1-p0 = 1- (70/100 * 69/100 )

Comments

@shivesh

very good solution, if possible write this as an answer . Good solve.

---

Sure @Bikram Sir..

---

@ShiveshRoy sir please clarify my doubt in your solution. If chaining is used for collision resolving (instead of probing) then won't the cases give different answer? ex case1 : (30/100)*(70/100) because there will still be 70 free slots after the 1st collision. Likewise for the other cases.