##### 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)/1000^{3}

B) (999x998x997)/1000^{3}

C) (997x996x995)/1000^{3}

D) (997x996x995)/(3!x1000^{3})

**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)/1000^{3}

**Ans (A)**