I'm looking to implement a fast, well-distributed hash table in C#. I'm having trouble choosing my hash-constraining function that takes an arbitrary hash code and "constrains" it so it can be used to index the buckets. There are two options that I see so far:
On one hand, you can make sure your buckets always have a prime number of elements, and to constrain the hash you simply modulo it by the number of buckets. This is, in fact, what .NET's Dictionary does. The problem with this approach is that using % is extremely slow compared to other operations; if you look at the Agner Fog instruction tables,
idiv(which is the assembly code that gets generated for %) has an instruction latency of ~25 cycles for newer Intel processors. Compare this to around 3 for
mul, or 1 for bitwise ops like
On the other hand, you can have the number of buckets always be a power of 2. You will still have to calculate the modulus of the hash so you don't attempt to index outside the array, but this time it will be less expensive. Since for powers of 2
% Nis just
& (N - 1), the constraining is reduced to a masking operation which only takes 1-2 cycles. This is done by Google's sparsehash. The downside of this is that we are counting on users to provide good hashes; masking the hash essentially cuts off part of the hash, so we are no longer taking all bits of the hash into account. If the user's hash is unevenly distributed, for example only the higher bits are filled out or the lower bits are consistently the same, then this approach has a much higher rate of collisions.
I am looking for an algorithm I can use that has the best of both worlds: it takes all bits of the hash into account, and is also faster than using %. It does not necessarily have to be a modulus, just something that is guaranteed to be in the range
0..N-1 (where N is the length of the buckets) and has even distribution for all slots. Does such an algorithm exist?
Thanks for helping.