Problem 1

A hash table allocates a slot based upon a hash function to an item. Typically, you hash n items drawn from a much larger set of possible items, m. In perfect hashing, if you have n slots in your hash table, and you hash n items, then each slot in the hash table will be filled and there will be no empty spaces. Sadly, it is often difficult to perfectly hash.

Assume your hash function satisfies the simple uniform hashing property.

(a) What is the probability that a particular slot in a hash table of size n is empty after hashing n items? (Alternative: how many empty slots will there be?)

(b) What is the probability that a particular slot has exactly one item? (alternative: how many slots will have one item, expected)

(Note: this problem looks impossibly difficult, but there is a reduction function that will convert it in linear time to a problem in Chapter 5, on probabilistic algorithms. Search well, my students!)