Modern non-cryptographic 32- and 64-bit valued hash functions, for example, lookup3, MurmurHash3 and CityHash, have quite sophisticated loops, each iteration of which include many multiplications, XORs and rotates. Why this is needed, since there are good avalanche procedures (32 -> 32 and 64 -> 64 bits), which mix the bits effectively randomly. So, even if this simple loop:

hash = seed;
while (input_len >= 8)
    hash = hash * prime + fetch_8_input_bytes();
... do something for rest 0..7 bytes of input

produce whatever flawed, biased results for similar input (or a certain subset of input), finalizing avalanche:

return good_avalanche(hash)

"fixes" this.

The last deal is direct collisions, but they are often not so important, assuming hash function produce decently little collisions. I think the above multimplication loop does.

What I'm missing?


Insufficient mixing between incorporating blocks of the key radically increases the possibility of collisions - as an example, imagine a hash like the following -

uint32_t badHash(std::vector<uint8_t> key) {
  uint32_t hash = 0;
  for (size_t i = 0; i < key.size(); i++) {
    hash += key[i];
  hash = SomeFunctionWithPerfectAvalanche(hash);
  return hash;

Despite the final avalanche, this function is no better than a checksum at producing a good distribution - it is trivially easy for adjacent blocks to cancel each other out. The situation isn't much improved by multiplying the key block by a prime, or performing any other mix to the key block - I can instantly generate collisions by taking two keys that collide under a simple checksum and then applying the inverse of the per-key-block mix to each block of the colliding pair.

A strong hash function has to perform enough mixing between adjacent blocks to ensure that small changes in the key are overwhelmingly unlikely to cancel each other out. Balancing the amount of work done in mixing each key block and in mixing the hash between key blocks is the tricky part of making a fast and robust hash function.

-Austin, author of MurmurHash

  • $\begingroup$ Thanks, this is insightful. I wrote the function wasn't actually meant. I kept in mind multiplication running hash value by prime and then adding the next block (see updated question body). How would you "break" this function? $\endgroup$
    – leventov
    Nov 1 '14 at 19:53

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.