Question

Assume that n items are mapped to a hash table of size m (separate chaining) by simple uniform hashing. a. What is the probability that a given row of the hash table has at least 2 items? b. What is the probability that some row of the hash table has at least 2 items?

Answer 1

a) Let us consider as the probability that row '' contain '' elements in the hash table. The probability that a given row (R) has at least K items is computed as

.

This is given as

  

In our problem,

,k = 2

  

b) This problem is almost similar to above problem except that row is not specified here. So, we need to choose the row. There are rows.We can select a row in m ways. The probability that some row has at least k items is :

In our problem,

k = 2