Hashing and the Birthday paradox: a cautionary tale

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.

Published by

Daniel Lemire

A computer science professor at the University of Quebec (TELUQ).

6 thoughts on “Hashing and the Birthday paradox: a cautionary tale”

  1. 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.

  2. @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.

Leave a Reply

Your email address will not be published. Required fields are marked *

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax