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

[Francois Fayard via llvm-dev]

> On Jan 10, 2017, at 2:31 AM, Chris Lattner <sabre at nondot.org> wrote:
> 
> As others have pointed out, 37 does have some nice properties (by being prime), but we’ve also had it from the very early days.  I wouldn’t say that it has been extremely well considered at all.
> 
> -Chris

Thanks for your reply. But I am not sure to understand the last sentence. Does it mean that this hash function has been criticized before? Do you also think that it can be improved?

I am sorry to insist on that, but I don’t see any advantage of using hash(k) = c * k with c being a primer number. What is important is choosing c such that gcd(c, m) = 1 for any size m of the hash table. This is the case for c = 1. As a consequence, I don’t see any benefit in using c = 37 over c = 1. Moreover, all those hash functions are badly considered for a reason : they behave very poorly when the keys are of the form d * k0 + k1.

I really think that this hash function could be improved. But to know if it's worth it, I would like to know if having a better hash for integer types would benefit LLVM.

François Fayard

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170110/6ae904fc/attachment.html>