3 ms·
The algorithm above is a 64bit to 32bit reduction method. It performs a 64bit mult and then discards the lower 32bit. I'm not sure if Daniel Lemire invented it
by Genbox 4y ago
The algorithm above is a 64bit to 32bit reduction method. It performs a 64bit mult and then discards the lower 32bit. I'm not sure if Daniel Lemire invented it as a alternative to modulo, as I've seen the method used before, but he certainly made it popular[1]
There is a 64bit version as well (2x64bit -> 64bit), that when compiled using 128bit multiplication is quite fast too.
The method made it's way into .NET runtime[2]. It is used in HashSet, Dictionary and ConcurrentDictionary today.
[1] https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/ https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-...
[2] https://github.com/dotnet/runtime/blob/c22f7f8c73766830b3262b72ae73e1015d4ed9ee/src/libraries/System.Private.CoreLib/src/System/Collections/HashHelpers.cs#L99 https://github.com/dotnet/runtime/blob/c22f7f8c73766830b3262...
- fanf2 4y agoIt is in my 1990 edition of Cormen, Leiserson & Rivest, chapter 12 “hash tables” section 12.3.2 “the multiplication method”, though they don’t explain the non-power-of-2 case in detail. In this section of CLR the hash function is multiplication by A where 0 < A < 1, and take the fractional part of the result. In practice, as they explain, you can multiply by A * 2^32 and keep only the lower 32 bits of the result. Anyway, that gives you a full 32 bit hash (if A is good). Then multiply by m (the size of the hash table) and take the floor (or drop the lower 32 bits of a 64 bit integer result). In CLR they discuss the case where m is a power of 2 and you don’t have a double-width multiply, so they pull the modulus out of the lower word, but the basic idea is still there.