recategorized by
860 views

2 Answers

Best answer
10 votes
10 votes
Sample space is 20^3 triples (xl,x2,x3), in which each xi is in [1,2, .... ,20].
Each triple has weight 1/ (20^3) .
The required probability is P(A)=l·P(B), where B is the event in which all three keys hash to different locations i.e. no collision.

P(B)= 20 * 19 * 18 / 20^3  = 0.855,  Hence P(A)= 1- 0.855 =  0.145
selected by
3 votes
3 votes
it is a problem of counting
total sample space   20 ^ 3
the no of ways collision is possible are below:
any 2 keys are hashed in one table entry , and left one is mapped to one of the rest 19 entries

such 3 cases are possible i.e. (K1 , K2)  K3  OR  (K1 , K3 ) k2  OR (K2 , k3) K1  == >  3 *  (20 * 19)

another one possibility when all 3 keys are hashed to same entry   i.e  20

total =   (  3 *  (20 * 19)  +  20  )  /   20 ^3  

option b..
Answer:

Related questions

0 votes
0 votes
1 answer
3
Bikram asked Jan 16, 2017
316 views
How many times $fibon$$\left ( 3 \right )$ is called during invocation of $fibon$ $\left ( 6 \right )$?$fibon(x) = fibon(x-1) + fibon(x-2)$$fibon(0) = 1$$fibon(1) = 1$345...