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

Question

Currently Boost has hash_combine function that outputs 32 bit unsigned integer (to be precise, size_t). Some references:

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'd like to explore on how to create 64 bit version of hash_combine.

The first thing is to get golden ratio or any other irrational number in 64 bit.

The second part is to use shifts. This part rather tricky and I'd like to ask if there are best practices or guide on using shifts to get hash values? Or choosing shifts like the original code:

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

is totally random?

Also how to evaluate the output of hash_combine to make sure that it doesn't create more collisions than the original hash function hash_value?

Answer 1

If you only want a hash_combine that hashes 2 64 bit values into one, and you don't need a new hash function for strings, you could just lift a tiny bit of code from CityHash, something like this (assuming size_t is a 64 bit unsigned integer, add your favorite bit of preprocessor or template trickery to validate that):

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 reproducing this snippet here and elsewhere is OK because it doesn't constitute a 'substantial portion' of the CityHash code, but please check the CityHash sources & license agreement to decide for yourself)