C++ – Why is boost::hash_combine the best way to combine hash-values?

by

It being the “best” is argumentative.

It being “good”, or even “very good”, at least superficially, is easy.

seed ^= hasher(v) + 0x9e3779b9 + (seed<<6) + (seed>>2);

We’ll presume seed is a previous result of hasher or this algorithm.

^= means that the bits on the left and bits on the right all change the bits of the result.

hasher(v) is presumed to be a decent hash on v. But the rest is defence in case it isn’t a decent hash.

0x9e3779b9 is a 32 bit value (it could be extended to 64 bit if size_t was 64 bit arguably) that contains half 0s and half 1s. It is basically a random series of 0s and 1s done by approximating particular irrational constant as a base-2 fixed point value. This helps ensure that if the hasher returns bad values, we still get a smear of 1s and 0s in our output.

(seed<<6) + (seed>>2) is a bit shuffle of the incoming seed.

Imagine the 0x constant was missing. Imagine the hasher returns the constant 0x01000 for almost every v passed in. Now, each bit of the seed is spread out over the next iteration of the hash, during which it is again spread out.

The seed ^= (seed<<6) + (seed>>2) 0x00001000 becomes 0x00041400 after one iteration. Then 0x00859500. As you repeat the operation, any set bits are “smeared out” over the output bits. Eventually the right and left bits collide, and carry moves the set bit from “even locations” to “odd locations”.

The bits dependent on the value of an input seed grows relatively fast and in complex ways as the combine operation recurses on the seed operation. Adding causes carries, which smear things even more. The 0x constant adds a bunch of pseudo-random bits that make boring hash values occupy more than a few bits of the hash space after being combined.

It is asymmetric thanks to addition (combining the hashes of "dog" and "god" gives different results), it handles boring hash values (mapping characters to their ascii value, which only involves twiddling a handful of bits). And, it is reasonably fast.

Slower hash combines that are cryptographically strong can be better in other situations. I, naively, would presume that making the shifts be a combination of even and odd shifts might be a good idea (but maybe addition, which moves even bits from odd bits, makes that less of a problem: after 3 iterations, incoming lone seed bits will collide and add and cause a carry).

The downside to this kind of analysis is that it only takes one mistake to make a hash function really bad. Pointing out all the good things doesn’t help that much. So another thing that makes it good now is that it is reasonably famous and in an open-source repository, and I haven’t heard anyone point out why it is bad.

More Related Contents:

  1. How do I combine hash values in C++0x?
  2. Hash an arbitrary precision value (boost::multiprecision::cpp_int)
  3. Sorting zipped (locked) containers in C++ using boost or the STL
  4. Compile time string hashing
  5. Is this behavior of vector::resize(size_type n) under C++11 and Boost.Container correct?
  6. How to specialize std::hash::operator() for user-defined type in unordered containers?
  7. Magic number in boost::hash_combine
  8. Why can’t clang with libc++ in c++0x mode link this boost::program_options example?
  9. Why is std::function not equality comparable?
  10. when g++ static link pthread, cause Segmentation fault, why?
  11. Should we pass a shared_ptr by reference or by value?
  12. Choosing between std::map and std::unordered_map [duplicate]
  13. Why user-defined move-constructor disables the implicit copy-constructor?
  14. Which Boost features overlap with C++11?
  15. Doing a static_assert that a template type is another template
  16. Using vector as a buffer without initializing it on resize()
  17. What is the default hash function used in C++ std::unordered_map?
  18. Where is shared_ptr?
  19. Is it smart to replace boost::thread and boost::mutex with c++11 equivalents?
  20. C++11 equivalent to boost shared_mutex
  21. Difference between C++11 std::bind and boost::bind
  22. Comparing 3 modern c++ ways to convert integral values to strings
  23. When must you pass io_context to boost::asio::spawn? (C++)
  24. std::tuple get() member function
  25. error for hash function of pair of ints
  26. Assert that code does NOT compile
  27. Using Boost adaptors with C++11 lambdas
  28. Enforcing statement order in C++
  29. How to store functional objects with different signatures in a container?
  30. Should the Copy-and-Swap Idiom become the Copy-and-Move Idiom in C++11?

Leave a Comment