hashprobabilityhash-collisionmurmurhash

Does Murmurhash have collisions on 32-bit inputs?

Consider the standard Murmurhash, giving 32-bit output values.

Suppose that we apply it on 32-bit inputs -- are there collisions?

In other words, does Murmurmash basically encodes a permutation when applied to 32-bit inputs? If collisions exist, can anyone give an example (scanning random inputs didn't yield any)?

Solution

  • I assume you mean MurmurHash3, 32 bit, and specially the 32-bit fmix method:

    FORCE_INLINE uint32_t fmix32 ( uint32_t h )
{
  h ^= h >> 16;
  h *= 0x85ebca6b;
  h ^= h >> 13;
  h *= 0xc2b2ae35;
  h ^= h >> 16;

  return h;
}

    If not, then you need to better specify what you mean.

    For the above, there are no collisions (two distinct inputs won't result in the same output). There is only one entry that returns the input value: 0.

    As there are not "that many" 32-bit values, you can actually iterate over all of them to verify, in a couple of minutes. This will require some memory for a bit field, but that's it.

    Btw, there is also a way to reverse the function (get the input from the output).