Magic number in boost::hash_combine

by

The magic number is supposed to be 32 random bits, where each is equally likely to be 0 or 1, and with no simple correlation between the bits. A common way to find a string of such bits is to use the binary expansion of an irrational number; in this case, that number is the reciprocal of the golden ratio:

phi = (1 + sqrt(5)) / 2
2^32 / phi = 0x9e3779b9

So including this number “randomly” changes each bit of the seed; as you say, this means that consecutive values will be far apart. Including the shifted versions of the old seed makes sure that, even if hash_value() has a fairly small range of values, differences will soon be spread across all the bits.

More Related Contents:

  1. Sorting zipped (locked) containers in C++ using boost or the STL
  2. How do I combine hash values in C++0x?
  3. C++ – Why is boost::hash_combine the best way to combine hash-values?
  4. Fast String Hashing Algorithm with low collision rates with 32 bit integer [closed]
  5. Hash an arbitrary precision value (boost::multiprecision::cpp_int)
  6. Cut set of a graph, Boost Graph Library
  7. Calculate mean and standard deviation from a vector of samples in C++ using Boost
  8. Why do I need strand per connection when using boost::asio?
  9. Weighted random numbers
  10. Example for boost shared_mutex (multiple reads/one write)?
  11. Rounding up to the nearest multiple of a number
  12. Finding all the subsets of a set
  13. Efficient implementation of log2(__m256d) in AVX2
  14. Why can’t clang with libc++ in c++0x mode link this boost::program_options example?
  15. When should I use raw pointers over smart pointers?
  16. How to use boost bind with a member function
  17. Parse quoted strings with boost::spirit
  18. C++: Converting Hexadecimal to Decimal
  19. Printing prime numbers from 1 through 100
  20. Use channel hiearchy of Boost.Log for severity and sink filtering
  21. Circular lock-free buffer
  22. Thread safe implementation of circular buffer
  23. Does boost have a datatype for set operations that is simpler than the STL?
  24. Efficiently getting all divisors of a given number
  25. How to build boost Version 1.58.0 using Visual Studio 2015 (Enterprise)
  26. How to print boost::any to a stream?
  27. Building boost with Visual Studio 2013 (Express)
  28. How to determine the Boost version on a system?
  29. Using shared_ptr in dll-interfaces
  30. Strange exception throw – assign: Operation not permitted

Leave a Comment