Assume that a sequence of n distinct items is mapped to a hash table of size m using separate chaining and a simple uniform hashing function.
1) How many ways are there to place the items into bins?
2) What is the probability that at least one bin of the hash table is empty?
3) Assume that n = m. What is the probability that there is no collision?
4) What is the expected number of empty slots? What does this approximate to when n = m and n becomes large?
5) What is the expected number of insert operations that do not cause a collision (i.e. place an item into an empty bin) ? What does this approximate to when n = m and n becomes large?