If you meet a stranger, the probability that he will have the same birth date as yourself is probably less than 1%. It is roughly 1/365 if you make simplifying assumptions. The Birthday paradox is the observation that given a full classroom (say 60 students), it is almost certain that two students will have the same birth date.

Our software routinely relies on hashing functions, which are just (randomly chosen) maps from elements to values. When two distinct elements have the same hash value, we say that there is a collision. In many applications, collisions are a bad thing.

If you choose hash values in a small set (say {0,1,2,3}), collisions are likely. Hence, we typically pick hash values from large sets (say all 32-bit integers).

Still, software hashing is subject to the Birthday paradox. How bad is it? Assuming that hashing is perfectly random, Steven Pigeon worked out some of the mathematics. To have a significant (50%) risk to find a collision when using 128-bit hash values, quintillions of elements are required. For 32-bit hash values, the result is not so good: only 77,000 elements are required.

But can you trust these results when working with actual hash values in your software? Probably not. For example, hash values generated by your software might not even be random. (In such a case, the probability of a collision is either 1 or 0 and the Birthday paradox does not apply.) And if it is random, as with the Ruby language, it is unlikely to be truly random…

(At this point, some people might object that hashing cannot be random… as the same element must always be mapped to the same hash value… and this is true, except that you can generate and store a random map on demand.)

In practice, you will be lucky if you get strong universality. Strong universality means that if you take any two distinct elements and hash them, the result is as good as perfectly random. However, it tells you little about what happens if you hash thousands of elements simultaneously.

I decided to test this out experimentally. I wrote a small Java benchmark. I picked some collection of strings: I grow the size of the set as a parameter. My collision probability estimation routine is crude, but it should give us some idea:

Number of elements   Strongly universal   Perfectly random 
100 0% 0%
1000 100% 0%
10000 100% 1.6%
77163 100% 50.1%

As we can see, the strongly universal function fares much worse than a purely random hashing function would. With just 1000 items, you are sure to encounter a collision! Of course, I cheated in the sense that I tweaked the test case until I got this bad result. But that is exactly what an adversary desiring to crashing your software might do.

In this case, we used a hash function with strong theoretical properties (Multilinear). If you use Java’s hashCode method, then you are in much worse shape: the strings “Ace” and ”BDe” always collide!

The mathematical results from the Birthday paradox should be viewed as best case scenarios. Hashing might be much less reliable in practice.

Source code: The source code of my example is on GitHub.

6 Comments

  1. A single collision is not necessarily bad.

    Comment by Itman — 18/6/2013 @ 10:55

  2. No. My only point is that treating hash values as if they are truly random can be misleading.

    Comment by Daniel Lemire — 18/6/2013 @ 13:19

  3. Of course, they are not. The question, is how far do they diverge from randomness?

    Comment by Itman — 18/6/2013 @ 13:24

  4. BTW, there are methods to avoid collisions: perfect hashing & cuckoo hashing. I have not tried the latter, but the former seems to be a 2-3x times slower than regular hashing on average despite having “ideal” properties.

    Comment by Itman — 18/6/2013 @ 13:28

  5. @Itman

    Cuckoo hashing assumes some degree of “randomness” (as measured by k-wise independence). So while it is interesting in how it deals with collisions, it does not do away with the question of how much randomness is involved.

    Comment by Daniel Lemire — 18/6/2013 @ 14:08

  6. I like the fact that a man named Pigeon is investigating the Pigeonhole Principle.

    Comment by Graham — 19/6/2013 @ 3:58

Sorry, the comment form is closed at this time.

« Blog's main page

Powered by WordPress