If your hash is decently uniform and fills 32 bits, you can avoid the modulus with
i = ((uint64_t)hash * (uint64_t)size) >> 32; i = ((uint64_t)hash * (uint64_t)size) >> 32;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...
(0xffffffff*101)>>32 is 100, which is the expected maximum.
As you say the algorithm was correct.
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-...
[2] https://github.com/dotnet/runtime/blob/c22f7f8c73766830b3262...
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.