How to create a good hash_combine with 64-bit output (inspired by boost :: hash_combine)

Question

Boost currently has a hash_combine function that outputs a 32-bit unsigned integer (more precisely, size_t). Some links:

http://www.boost.org/doc/libs/1_43_0/doc/html/hash/reference.html#boost.hash_combine

http://www.boost.org/doc/libs/1_43_0/doc/html/hash/combine.html

Magic number in boost :: hash_combine

I would like to learn how to create a 64-bit version of hash_combine.

First of all, you need to get the golden ratio or any other irrational number of 64 bits.

The second part is the use of shifts. This part is quite complicated, and I would like to ask if there are best practices or guidelines for using shifts to get hash values? Or select shifts, such as source code:

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

is completely random?

Also, how do you evaluate the output of hash_combine to ensure that it does not create more collisions than the original hash function hash_value ?

Answer 1

If you want hash_combine to hash 2 64-bit values ​​into one, and you don't need a new hash function for strings, you can just pick up a tiny bit of code from CityHash, something like this (assuming size_t is 64- unsigned bit integer, add your favorite preprocessor bit or pattern trick to check this):

 template <class T> inline void hash_combine(std::size_t& seed, const T& v) { std::hash<T> hasher; const std::size_t kMul = 0x9ddfea08eb382d69ULL; std::size_t a = (hasher(v) ^ seed) * kMul; a ^= (a >> 47); std::size_t b = (seed ^ a) * kMul; b ^= (b >> 47); seed = b * kMul; } 

(I think that playing this snippet here and elsewhere is fine, because it is not an “essential part” of CityHash code, but please check the sources and CityHash license agreement to decide for yourself)

Answer 2

Read http://burtleburtle.net/bob/hash/doobs.html for some basic information about the design of the hash function, and the rest of the articles at http://burtleburtle.net/bob/hash/ for more details. CityHash has been tested with http://code.google.com/p/smhasher/ , and you might check your hash_combine using the same testuite.

Although I am not an expert in hashing, projects of the latest hash functions make me believe that using the 2-shift boost hash_combine() technique is no longer up-to-date and can be improved.