Why having a simple multiplication loop and very good avalanche isn't enough to produce well-distributed hash values?

Question

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?

Answer 1

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