Example on Hashing + Probability

Consider a hash table with 1000 slots collisons are resolved using chaining. Assuming simple uniform hashing, what is the probability that the first 3 slots are unfilled after the first 3 insertions ?

A) (997x997x997)/10003

B) (999x998x997)/10003

C) (997x996x995)/10003

D) (997x996x995)/(3!x10003)

Answer

Consider a hash table with 1000 slots,

Now, According to the question if we want to insert such that first 3 slots are unfilled, for that we need to choose from the rest of the 997 slots.

Therefore,

I : Event such that after 1st insertion first three slots are unfilled

II: Event such that after 2nd insertion first three slots are unfilled

III: Event such that after 3rd insertion first three slots are unfilled

and because collision is resolved by chaining, the respective probabilities are

P(I) = 997/1000

P(II) = 997/1000

P(III) = 997/1000

Hence,

P(I ∩ II ∩ III ) = P(I) x P (II) x P(III) = (997x997x997)/10003

Ans (A)

0Comment