3
$\begingroup$

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$?

$\endgroup$
1
  • 1
    $\begingroup$ You have posted three questions about the same analysis in rapid succession. Maybe you should have posted one first, absorbed the answers, and then check if the others did not go in a cloud of epiphany. $\endgroup$
    – Raphael
    Feb 16, 2016 at 23:54

3 Answers 3

3
$\begingroup$

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!)
$\endgroup$
2
  • $\begingroup$ In your analysis, you have assumed that $n$ pigeons go into $m$ holes are random. I don't understand why you have made such an assumption. According to my understanding, SUHA is an assumption that states that given a random variable $K$ following a probability distribution whose range is the universe of keys, $h(K)$ follows a uniform distribution where $h$ is the hash function. Also if $K_1$ and $K_2$ are random variables same as $K$, then $h(K_1)$ and $h(K_2)$ are independent. $\endgroup$
    – Jamāl
    Jan 22, 2021 at 8:55
  • $\begingroup$ The answer by Derek Elkins is what made this understanding click for me. cs.stackexchange.com/questions/87922/… So the reason I don't follow why a pigeon would go to a hole at random is that with a fixed hash function $h$, its fate is already decided so there's no meaning to say that it goes into a hole at random. The randomness could only arise if the keys follow a certain probability distribution. Any insight into your calculations will be helpful. $\endgroup$
    – Jamāl
    Jan 22, 2021 at 8:59
2
$\begingroup$

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$.)

$\endgroup$
4
  • $\begingroup$ sorry for my question, but I am still a bit confused. Usually I think of expectation as a weighted sum so in that case we have $\mathbb{E}[n_j] = \sum_x x Pr[x]$, how does that equation come into play here? In particular $n_j$ must be a random variable and somehow have a distribution...right? In particular it has a distribution over weights, so it has $\mathbb{E}[n_j] = \sum^{m-1}_{x=0} x Pr[n_j = x]$. Is that equation not correct? I've update my question with details concerning this comment if it helps. $\endgroup$ Feb 16, 2016 at 0:34
  • $\begingroup$ The equation is correct, but useless here. You pick $j$ uniformly at random from $\{1,\ldots,m\}$, and this defines $n_j$. You can compute $\Pr[n_j = x] = \frac{1}{m}|\{ j : n_j = x \}|$, but this doesn't really help you compute the expectation of $n_j$. $\endgroup$ Feb 16, 2016 at 7:38
  • $\begingroup$ sorry for being really picky, I just genuinely want to understand your explanation. How does your answer differ from the one that I suggested? Also, What is your expectation over? Is the probability (of whatever event your summing across) $\frac{1}{m}$? More precisely, how does your first expression $\mathbb{E} [n_j]$ become $\frac{1}{m} \sum^m_{j=1} n_j$? Whatever step that was skipped there is what is throwing me off. Thanks for the patience and help Yuval. $\endgroup$ Feb 27, 2016 at 2:54
  • $\begingroup$ In my approach, each value of $j$ has the same probability $1/m$. This distribution is known as the uniform distribution. This calculation works for any hash distribution, uniform or not. $\endgroup$ Feb 27, 2016 at 7:57
2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thanks for this answer Charlie! have you considered accepting it so we know this is the right answer? $\endgroup$ Oct 6, 2022 at 21:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.