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$?
What is the formal analysis with Simple Uniform Hashing that the load factor is $\alpha = \frac{n}{m}$
algorithm analysis;probability theory;hash;hash tables;hashing