Daniel Lemire's blog

, 3 min read

Hashing and the Birthday paradox: a cautionary tale

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

  1. Itman says:

    A single collision is not necessarily bad.

  2. Itman says:

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

  3. Itman says:

    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.

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

  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.

  6. Graham says:

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