Problem. A hash table data structure consists of:

The array A of m buckets, each capable of holding an arbitrary number of keys.

The hash function h : U {0..m 1} from the universe of keys U to valid indices in the array A. Any key is equally likely to hash to any index, independently from other keys.

When a key k U is inserted, it is hashed with h to obtain an index and put into A under that index: A[h(k)] = k. If another key is already in the same bucket, we call it a collision but still insert the key. (Recall that buckets can hold an arbitrary number of keys.)

Consider inserting n keys into a hash table with m buckets. (a) What is the probability that none of the n keys hash to a particular bucket? (b) What is the expected number of empty buckets? (c) What is the probability that all n keys were inserted and no collision has occurred? (d) What is the probability that the first collision occurs at k-th insertion? (e) What is the probability that exactly k keys hash to a particular bucket?