MADE EASY 2016 TEST SERIES

Question

Given a hash table with 6 keys and 10 slots, with simple uniform hashing. If collisions are resolved by chaining then the probability that first slot ends up empty?

Answer 1

The probability that given m slots , a key will be mapped to that slot = 1 / m

So probability of not mapping to that slot =  1 - 1/m

                                                           =   (m-1) / m

So P(1st slot remains empty even after n insertions) = P(none of the n keys map into the 1st slot)

                                                                            =   ((m-1)/m)ⁿ  [Follows from multiplication principle]

Here we have m  =  10 and n = 6 , So

P(1st slot remains empty even after n insertions)   =    (9/10)⁶

                                                                          =    0.9⁶

                                                                          =    0.531 correct to 3 decimal places