2 ms·

Testing this using a size of 101, it only appears to give results up to 50. In fact in general appears to only give numbers up to size / 2, should that have bee

Testing this using a size of 101, it only appears to give results up to 50. In fact in general appears to only give numbers up to size / 2, should that have been >> 31? edit: Nevermind, I was converting to Uint but should have been returning Int, this gives results in (-50,50). Adding size / 2 will get you back to the range (0,size-1) that you would want for assigning buckets. I was also going to ask you why it needed to be "decently uniform" but then implementing it saw that the first thousand numbers all hash to the same value. In fact, the first 21,262,215 numbers all hash to the same value with size = 101. Given that .net implements Int32.GetHashCode(value) as "return value"[1], I would avoid this trick in practice in .net. Please correct me if I've stuffed up my implementation! https://referencesource.microsoft.com/#mscorlib/system/int32.cs,86 https://referencesource.microsoft.com/#mscorlib/system/int32...

dzaima 4y ago
might you have used a signed hash value instead of unsigned? (or just one that never sets the top bit) (0xffffffff*101)>>32 is 100, which is the expected maximum.
- xnorswap 4y ago
  Yes this was it thanks, I was trying to fit it around where I use GetHashCode in my workflow which is signed in .net. As you say the algorithm was correct.
  - 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 ago
      It 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.

dzaima 4y ago

might you have used a signed hash value instead of unsigned? (or just one that never sets the top bit) (0xffffffff*101)>>32 is 100, which is the expected maximum.

xnorswap 4y ago
Yes this was it thanks, I was trying to fit it around where I use GetHashCode in my workflow which is signed in .net. As you say the algorithm was correct.
- 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 ago
    It 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.