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

[Joerg Sonnenberger via llvm-dev]

On Mon, Jan 09, 2017 at 11:10:05AM +0100, Francois Fayard via llvm-dev wrote:
> I have been very surprised by the hash function used for integers which
> is hash(k) = 37 * k. This kind of hashing function does not change the
> lowest bits of k, and if your keys happen to all be a multiple of 8,
> you end up not using about 90% of the slot as a direct access in an
> open addressing hash table. By the way, does anyone know the rationale
> behind using 37?

37 is a prime. Multiples of 8 that are otherwise evenly distributed will
map to different slots in the output space.

> In order to improve this, it could be nice to use a better hash
> function such as the Knuth hash which is defined as:

64bit multiplications are very expensive on many 32bit platforms. It is
certainly an order of magnitude slower than the existing hash.

Joerg