What is the formal analysis with Simple Uniform Hashing that the load factor is $\alpha = \frac{n}{m}$

Question

Recall the definition of the load factor is the average number of elements in a chain for hashing for a table $T$ of size $m$ (with $n$ elements in consideration). Let $n_j = T[j]$ be the size of the chain for entry $j$. In this case the definition of the load factor should be:

$$ \mathbb{E}[n_j] = \mathbb{E}[T[j]] = \alpha = \frac{n}{m}$$

I was wondering, why is the above statement correct under the Simple Uniform Hashing (i.e. the probability that any given element is equally likely to hash into any of the $m$ slots or in equations $Pr[h(k_i) = h(k_j)] = \frac{1}{m}$)? In particular, I find it difficult to understand what exactly distribution (or what random variables to define) in order to compute the expectation. What distribution is the expectation taken over with respect to?

CLRS talks about this on page 259 but they never quite explain in detail why it is $\frac{n}{m}$ or ignore (leave out) the probabilistic analysis.

---

After some thinking I realized that $n_j$ is a random variable and it depends on how the hash function $h$ distributes keys (and I guess also in the keys one might get). So a realization of $n_j$ will be in the set $\{ 0, ..., m-1 \}$, since the table can only have a $0$ elements up to $m$ elements. Hence to calculate the expected length of $n_j$ we compute:

$$\mathbb{E}[n_j] = \sum^{m-1}_{x=0} x \Pr[n_j = x]$$

but my question is, how does one determine the distribution for $x$?

Answer 1

The mean chain length is the sum of the chain lengths divided by the number of chains. The sum of the chain lengths is, by definition $n$ and the number of chains is $m$. This is by far the easiest way to calculate it, and it's true even if the SUHA doesn't hold.

But since you asked, let's look at the distribution of the chain lengths.

Suppose you're putting $n$ pigeons into $m$ pigeonholes at random. Examine one pigeon hole (say, pigeonhole number 1). The number of pigeons that are assigned to this pigeonhole follows a binomial distribution; the probability that there are $k$ pigeons in that particular pigeonhole is ${n \choose k} p^k (1-p)^{n-k}$ where $p = \frac{1}{m}$.

So the expected number of pigeons in that pigeonhole is:

$$\sum_{k=0}^{n} k {n \choose k} p^k (1-p)^{n-k}$$ $$= \sum_{k=0}^{n} np {{n-1} \choose {k-1}} p^{k-1} (1-p)^{n-k}$$ $$= np \sum_{k=0}^{n-1} {{n-1} \choose {k}} p^k (1-p)^{n-1-k}$$ $$= np \left(p + (1-p)\right)^{n-1}$$ $$= \frac{n}{m}$$

By the way, if we want to reason about the number of chains of length $k$ in a hash table, for large enough $m$, it's well-approximated by a Poisson distribution.

The expected proportion of hash slots with chain length $k$ is:

$$\hbox{Pr}(\lambda,k) \approx \frac{e^{-\lambda} \lambda^k}{k!}$$

where $\lambda$ is the load factor. Note that $\lambda$ is also the mean of a Poisson distribution, so once again, the expected value of the chain length is the load factor.

You can learn a lot from this. For example:

• If the load factor is 1, the expected proportion of hash chains of length 0 and the expected proportion of hash chains of length 1 are both $\frac{1}{e}$.
• If you have a hash table with $m$ slots, there is a 50% chance of a collision after you insert $\sqrt{m}$ items. (Exercise: prove this!)

Answer 2

This has nothing to do with any property of the hash function. Rather, $$\mathbb{E}[n_j] = \frac{1}{m} \sum_{j=1}^m n_j = \frac{1}{m} \cdot n = \frac{n}{m}.$$ (This is under the assumption that by $\mathbb{E}[n_j]$ you mean the expectation of $n_j$ over uniformly chosen $j$.)

Answer 3

We want to calculate the expected length of a chain using SUHA (evenly distributed keys). Denote the length of a specific slot $j$ to be $N_j$. The length of this chain depends on how many of the $n$ keys that we hash, are successful to go to that slot. So lets count how many times a element goes to that slot with an indicator variable:

$$ X_i= \begin{cases} 1, \text{if ith key goes to slot } j\\ 0, \text{otherwise} \end{cases} $$

Therefore we can express the length of a chain with respect to this indicator variable as follows:

$$N_j = \sum^n_{i=1} X_i$$

now we can just ask what is the expected value of the variable above:

$$ \mathbb{E} [ N_j ] = \mathbb{E} [ \sum^n_{i=1} X_i ]$$

by linearity of expectation we have and that the expectation of an indicator r.v. is its probability we have:

$$ \sum^n_{i=1} \mathbb{E} [ X_i ] = \sum^n_{i=1} Pr[ X_i = 1 ]$$

and using the SUHA i.e. $Pr[h(k_i) = j] = \frac{1}{m} $ for all slots $j \in \{0,...,m-1 \} $ we get:

$$ \sum^n_{i=1} Pr[ X_i = 1 ] = \sum^n_{i=1} \frac{1}{m} = \frac{n}{m} $$

as required. This analysis holds for any slot $j$, so they all have the same expected length.