edited by
1,419 views
1 votes
1 votes
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)   __________
edited by

2 Answers

Best answer
8 votes
8 votes

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.

selected by
5 votes
5 votes
1-p0 = 1- (70/100 * 69/100 )
Answer:

Related questions

0 votes
0 votes
1 answer
1
Bikram asked Nov 26, 2016
135 views
The following keys are inserted in an empty binary search tree (and height of the root of tree is $1$).Keys are: $11, 10, 1, 9, 7, 4, 3, 2, 6, 8, 5, 12$The height of the ...
0 votes
0 votes
1 answer
3
Bikram asked Nov 26, 2016
1,637 views
Three algorithms do the same task. Algorithm One is $O(N)$ and Algorithm Two is $O(\log N)$ and Algorithm Three is $O(N1/2)$. Which algorithm should execute the fastest f...
1 votes
1 votes
3 answers
4