2
$\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
    $\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 '16 at 23:54
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$

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$
  • $\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$ – Charlie Parker Feb 16 '16 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$ – Yuval Filmus Feb 16 '16 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$ – Charlie Parker Feb 27 '16 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$ – Yuval Filmus Feb 27 '16 at 7:57
0
$\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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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