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

Francois Fayard via llvm-dev llvm-dev at lists.llvm.org
Tue Jan 10 03:12:43 PST 2017


> 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.

François Fayard



More information about the llvm-dev mailing list