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 and, or, or xor.

  • 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 % N is 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.

  • 1
    Look up the avalanche effect, as well as the explanation in murmurhash3 (smhasher). However, the fundamental point in your question is not addressed by adopting a better hash function. Instead, it is a question about why users don't adopt the same better hash function in the first place, and a solicitation for countermeasures (as if users are maliciously lazy). – rwong Sep 6 '16 at 16:49
  • For fast modulo (2^N +/- 1), see stackoverflow.com/questions/763137/… – rwong Sep 6 '16 at 16:56
  • @rwong I am sorry, but I'm not quite sure what your comment has to do with my post. I do not control the hash provided by the user, so I'm not looking for a better hash function. I also don't understand what you mean by "maliciously lazy users." – James Ko Sep 6 '16 at 16:58
  • 4
    If the hash function is poor, there is nothing the hash table implementer can do to "fix" the poor distribution. Modulo a prime number does not repair a poor hash. Consider a hash function producing as output, multiples of a prime number. I have seen such a problem in real production code. – Frank Hileman Sep 7 '16 at 5:17

Modern hash table implementations do not use the modulo function. They often use power of two sized tables and chop off unneeded bits. An ideal hash function would allow this. The use of modulo combined with prime number table sizes arose in the days when hash functions were generally poor, as they often are in .net development. I recommend reading about SipHash, a modern hash function, then reading about some other modern functions, such as xxHash.

I should explain why .net hash functions are often poor. In .net, programmers are often forced to implement hash functions by overriding GetHashcode. But .net does not provide the tools needed to ensure the programmer created functions are high-quality, namely:

  • encapsulation of the hash state in a structure or class
  • hash "add" functions, which add new data to the hash state (add a byte array, or a double, for example)
  • a hash "finalize" function, to produce the avalanche
  • encapsulation of the hash result -- in .net you get one choice, a 32 bit signed integer.

For more information about using a hash function result as a hash table index, please see the definitions of universal forms of hashing in this paper: Faster 64-bit universal hashing using carry-less multiplications

To use AND while still keeping all bits, use XOR too.

For an example, temp = (hash & 0xFFFF) ^ ( hash >> 16); index = (temp & 0xFF) ^ (temp >> 8);.

For this example, there's no modulo and all 32 bits of hash effect the 8-bit index. However, whether or not it's faster than DIV is something that depends on too many factors, and it can easily be slower than DIV in some cases (e.g. large hash and tiny index).

  • This is always going to be faster than DIV/IDIV, however I don't think it answers my question-- index will be in the range [0..255]. I need something in the range [0..n-1], where n is the number of buckets. – James Ko Sep 10 '16 at 21:37
  • @JamesKo But if you're implementing a dictionary, you also control the number of buckets (to a certain degree). So, instead of prime numbers, you could choose powers of two. (Whether doing so would be actually a good idea, I can't tell you.) – svick Sep 11 '16 at 19:28
  • @svick For powers of 2 we could do a simple mask operation. As mentioned in the question, I am looking for a cheap way to do this with prime numbers so even poorly-distributed hashes are accomodated. – James Ko Sep 20 '16 at 3:16

You can take advantage of the fact that many prime integers have a modular multiplicative inverse. See this article. You have satisfied one of the constraints by making your bucket index prime and the modulus 2^n, which are inherently relatively prime.

The article describes the algorithm to find a number such that multiplying by that number, and ignoring overflow, will yield the same result as if you had divided by the bucket index size.

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.