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.
diff --git a/src/support/hash.h b/src/support/hash.h
index 50ecec5..1af462b 100644
--- a/src/support/hash.h
+++ b/src/support/hash.h
@@ -30,8 +30,16 @@
// 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.
