Question

Suppose a hash table contains k buckets and holds n values, where
k, n≥2, and suppose that the hash function obeys the simple uniform hashing
assumption:

- Hash function distributes records among the buckets randomly, each with equal probability

- Each record's location is independent of the location of all the other records

(a) What is the expected number of buckets that contain exactly 1 value?
Hint: Define Ej,m as the event that bucket j contains exactly the mth value,
and no other values. Then define Ej as the event that bucket j contains
exactly one value. Find Pr(Ej), using the fact that Ej is the union of the
disjoint events Ej,m. Finally, define indicator variables Ij for each event
Ej, and use linearity of expectation to find the answer.
(b) What is the expected number of buckets that contain 2 or more values?
Hint: Use the values from the previous calculation and from
Example 29.32, instead of calculating this directly.

Answer 1