Messages in this thread | | | Date | Thu, 28 Apr 2016 11:32:47 -0700 | Subject | Re: [patch 2/7] lib/hashmod: Add modulo based hash mechanism | From | Linus Torvalds <> |
| |
On Thu, Apr 28, 2016 at 9:42 AM, Thomas Gleixner <tglx@linutronix.de> wrote: > hash_long/hash_ptr() provide really bad hashing for small hash sizes and for > cases where the lower 12 bits (Page size aligned) of the hash value are 0.
Hmm.
hash_long/ptr really shouldn't care about the low bits being zero at all, because it should mix in all the bits (using a prime multiplier and taking the high bits).
That said, numbers rule, so clearly we need to do something. It does strike me that we would be better off just trying to improve hash_long().
In particular, there are people and projects that have worked on nothing but hashing. I'm not sure we should add a new hash algorithm even if the whole "modulo prime" sounds obviously fine in theory. For example, your 64-bit code has obvious problems if there are common patterns in the low and the high 32 bits.. Not a problem for something like hash_ptr(), but it can certainly be a problem for other cases.
It would be a really good idea to have some real hard numbers on the hashing in general, but _particularly_ so if/when we start adding new ones. Have you tested the modulus version with SMhasher, for example?
For example, there's Thomas Wang's hash function which should cascade all the bits.
I'd really hate to add *another* ad-hoc hash when the previous ad-hoc hash has been shown to be bad.
Linus
| |