[llvm-dev] Default hashing function for integers (DenseMapInfo.h)

Francois Fayard via llvm-dev
2017-01-10T11:12:43Z

> The reason for avoiding c=1 is the trivial aliasing set for power-of-two
> differences. Those tend to be fairly common in any data set.

That’s where I completely disagree. Multiplying by 37 won’t help.
Suppose that you have two integers a and b such that a = b (modulo 8). You also
have 37 a = 37 b (modulo 8), and multiplying by 37 does not change anything
here. Prime numbers are useful for the size of the hash table and kill those
trivial aliasing which is why hash(k) = k is a decent hash for those tables. But
I really don’t see any benefit in multiplying by a prime number.

> E.g. the current hash is simple, avoids some of the
> obvious bad cases and is itself decently fast. Anything else needs
> careful analysis of the data.

It disagree on the fact that it avoids obvious bad cases.