Expected Number of empty slots when hashing

Question

I have n keys and a hash table of size n.

I am trying to figure out the expected number of empty slots.

I know the uniform Hashing Assumption states that every key is equally likely to go into any of the slots.

So far, I have come up with n keys each with equal chance of n slots, so n^2 possible combinations.

I am unsure of where to go from here, any points in the right direction would be appreciated! Thanks.

Answer 1

First, the number of possible combinations is not n^2 but n^n since each of the n keys has n possibilities to land in a slot.

Next, due to all slots being symmetric, the expected number of empty slots E = n * P, where P is the probability that each single slot ends up empty. This is due to linearity of expectation which holds even when the random values are dependent.

Now, note that the probability Q that a single key does not land in this slot is Q = (n - 1) / n.

Since there are n keys, the probability P that no key lands in a fixed slot is Q ^ n.

Summing all that up, we have E = n * ((n - 1) / n)^n. The limit of (n - 1/n)^n is 1/e (see here), thus the expected number of empty slots is n / e.