2
$\begingroup$

I'm trying to help my daughter with her CS assignment on hashing. She has an input list of about 4000 English words, each 5 letters long. The prof has limited her to 4000 output buckets (digests? -- it's been a long time since I did this stuff). And the output from the hashing function is an int modulo 4000.

Her naive hash function gets about 1500 collisions. To get something for comparison, I found a handful of hashing functions here and here. I ended up trying almost all of them (oat, fnv, djb, another djb, sax, elf, jsw, and a crc adaptation), because every single one of them got about 1500 collisions. That sure seems like a lot. I'm starting to think maybe we're missing something fundamental. Or not. I don't know.

(I was able to reduce collisions significantly by increasing the number of output buckets to 200k, and returning hash mod 200k from the functions. Naturally, this isn't allowed for the assignment.)

I'm not sure what questions to ask, but the first one that comes to mind is, does 1500 collisions sound about right when using such a small number of output buckets? Or does it sound more like we're doing something totally wrong outside the hashing function? (Presumably not inside it, given that we tried so many different ones.) Or maybe I should ask, is there a way to find out whether 1500 collisions is about right?

$\endgroup$

migrated from cstheory.stackexchange.com Mar 6 '18 at 2:41

This question came from our site for theoretical computer scientists and researchers in related fields.

  • $\begingroup$ @JanJohannsen Done. Forgive me, I usually read the question guidelines on the SE sites, but I was lazy this time. $\endgroup$ – GreatBigBore Mar 5 '18 at 14:50
4
$\begingroup$

Depending on how you count collisions, we can expect either about 2000 collisions, or about 1472 collisions. The latter is in close agreement with what you observe, so yes, 1500 collisions looks about right to me.

Counting collisions pairwise

I think the most natural way to count collisions is "pairwise". For instance, if A, B, and C all hash into the same bucket, let's count that as 3 collisions. If A, B, C, and D hash to the same bucket, let's count that as 6 collisions (not 4, but 6: the 6 collisions are AB, AC, AD, BC, BD, and CD). And so on. In general if there are $k$ items in a bucket, that causes ${k \choose 2}$ collisions, with this method of counting collisions.

Then, you can use linearity of expectation to estimate the number of collisions, assuming the hash function is good. Let $X_{i,j}$ be an indicator random variable that is $1$ if objects $i,j$ hash to the same bucket, or $0$ otherwise. Let $Y=\sum_{i<j} X_{i,j}$ be the sum of these random variables. Then $Y$ counts the number of collisions.

Can we estimate a typical value for $Y$? Well, we can compute the expected value of $Y$ in a straightforward way:

$$\mathbb{E}[Y] = \sum_{i<j} \mathbb{E}[X_{i,j}] = \sum_{i<j} {1 \over 4000} = {4000 \choose 2} {1 \over 4000} = {3999 \over 2} \approx 2000,$$

using the fact that $\mathbb{E}[X_{i,j}] = \Pr[X_{i,j}=1] = {1 \over 4000}$ since there is a 1 in 4000 chance that object $j$ hashes to the same bucket as object $i$ (assuming a good hash function). Typically, the observed value of $Y$ will be near its expected value. So, that'd predict that you see about 1500 collisions. That's a consequence of the number of buckets and the number of items hashed.

In general, if you hash $n$ items into $m$ buckets using a good hash function, you should expect to see about ${n^2 \over 2m}$ collisions, on average, using this method for counting collisions.

Counting collisions by bucket size

On reading your comment, it sounds like you are counting collisions differently. If there are $k \ge 1$ items in a bucket, it sounds like you are counting that as $k-1$ collisions. How does that affect things? Well, it makes the calculation more complicated. I'll share a much terser analysis for this case, without showing all the details.

Let $N_i$ denote the number of items in bucket $i$. If the hash function is good, the number of items in a bucket should follow approximately the Poisson distribution with parameter $\lambda = n/m$. In your case, we have $\lambda=1$. The total number of collisions (the way you are counting it) is

$$N = \sum_i \max(N_i-1,0).$$

Now,

$$\begin{align*} \mathbb{E}[\max(N_i-1,0)] &= 1 \cdot {\lambda^2 e^{-\lambda} \over 2!} + 2 \cdot {\lambda^3 e^{-\lambda} \over 3!} + 3 \cdot {\lambda^4 e^{-\lambda} \over 4!} + \cdots\\ &= \lambda e^{-\lambda} + \lambda^2 - \lambda. \end{align*}$$

(Don't ask me how I summed the series; black magic.) It follows that

$$\mathbb{E}[N] = \sum_i \mathbb{E}[\max(N_i-1,0)] = (\lambda e^{-\lambda} + \lambda^2 - \lambda) n.$$

In your case $\lambda=1$ and $n=4000$, so we predict $1/e \times 4000 \approx 1472$ collisions. That has very close agreement with what you are observing empirically, so practice and theory seem to be in close agreement.

$\endgroup$
  • $\begingroup$ I don't quite follow the arithmetic. Isn't $3999/2 \approx 1999.5$? $\endgroup$ – Geoffrey Irving Mar 5 '18 at 5:07
  • 1
    $\begingroup$ @GeoffreyIrving, oops, you're absolutely right. That rather affects the answer. I've updated my answer accordingly, but now I don't have as good an explanation for what the poster is seeing. $\endgroup$ – D.W. Mar 5 '18 at 5:24
  • 1
    $\begingroup$ $4000/e \approx 1471 \approx 1500$, which is probably not a coincidence. $\endgroup$ – Geoffrey Irving Mar 5 '18 at 6:01
  • 1
    $\begingroup$ @GreatBigBore, OK, see revised answer. I now show how to estimate the number of collisions under two different ways of counting collisions, and now the 1500 number you are seeing makes sense. $\endgroup$ – D.W. Mar 5 '18 at 7:23
  • 2
    $\begingroup$ @GeoffreyIrving, hah, you were absolutely right! See the second half of the answer (after my edits), to see where the $1/e$ comes from. $\endgroup$ – D.W. Mar 5 '18 at 7:23

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.