Add 64-bit hash_combine (#3041)

Currently only the low 32-bits of a hash are guaranteed to be shuffled before combining with the other hash, so this PR also adds a 64-bit variant of hash_combine, including a comment on where the constants are coming from.

1 files changed, 9 insertions, 1 deletions

diff --git a/src/support/hash.h b/src/support/hash.h
index 50ecec563..1af462b7e 100644
--- a/src/support/hash.h
+++ b/src/support/hash.h
@@ -30,8 +30,16 @@ template<typename T> inline std::size_t hash(const T& value) {
 // Combines two digests into the first digest. Use instead of `rehash` if
 // `otherDigest` is another digest and not a `size_t` value.
 static inline void hash_combine(std::size_t& digest, std::size_t otherDigest) {
-  // see boost/container_hash/hash.hpp
+  // see: boost/container_hash/hash.hpp
+  // The constant is the N-bits reciprocal of the golden ratio:
+  //  phi = (1 + sqrt(5)) / 2
+#if SIZE_MAX == UINT64_MAX
+  //  trunc(2^64 / phi) = 0x9e3779b97f4a7c15
+  digest ^= otherDigest + 0x9e3779b97f4a7c15 + (digest << 12) + (digest >> 4);
+#else
+  //  trunc(2^32 / phi) = 0x9e3779b9
   digest ^= otherDigest + 0x9e3779b9 + (digest << 6) + (digest >> 2);
+#endif
 }
 
 // Hashes `value` and combines the resulting digest into the existing digest.