Gate academy

Question

Suppose that we have a hash table with n slots with collisions resolved by chaining. Suppose that n keys are inserted into the table What is the probability of k keys being mapped to a single slot. Each key is equally likely to be hashed to each slot. Find the probability P(k) that exactly k keys hash into a particular slot is given by-

(A) (1/n)^k * (1- 1/n)^(n-k)

(B) (1/n)^k * (1- 1/n)^(n-k) * nCk

(C) (1/k)^k * (1-1/k)^(n-k) * nCk

(D) None of the above

Answer 1

Probability that keys being mapped to single slot  = (1/n).

Probability that keys being mapped to remaining (n-1) slots = (n-1) / n .

Therefore ,

given 'k' keys to be mapped to single slot. So we have nCk such combinations, and in these combinations

'k' keys to be mapped to single slot = (1/n)^k and

remaining (n-k) keys to be mapped to remaining (n-1) slots = ((n-1)/n)^(n-k) = (1-1/n)^(n-k) .

So answer is (1/n)^k * (1- 1/n)^(n-k) * nCk. option B.