Add methods for hashing pairs of integer values.

base/hash_tables.h

Index: base/hash_tables.h
diff --git a/base/hash_tables.h b/base/hash_tables.h
index 14119eda510ccd43826d535567dde134f4885fe8..b2e4a72b81711f1aff435146b797b163cdf85de7 100644
--- a/base/hash_tables.h
+++ b/base/hash_tables.h
@@ -111,6 +111,144 @@ DEFINE_STRING_HASH(string16);
 #error define BASE_HASH_NAMESPACE for your compiler
 #endif  // COMPILER
 
+#if defined(COMPILER_MSVC)
+
+#define DEFINE_PAIR_HASH_FUNCTION_START(type1, type2) \
+    template<> \
+    inline std::size_t hash_value<std::pair<type1, type2> >( \
+        const std::pair<type1, type2>& value)
+
+#define DEFINE_PAIR_HASH_FUNCTION_END()
+
+#elif defined(COMPILER_GCC)
+
+#define DEFINE_PAIR_HASH_FUNCTION_START(type1, type2) \
+    template<> \
+    struct hash<std::pair<type1, type2> > { \
+      std::size_t operator()(std::pair<type1, type2> value) const
+
+#define DEFINE_PAIR_HASH_FUNCTION_END() \
+    };
+
+#else
+#error define DEFINE_PAIR_HASH_FUNCTION_START for your compiler
+#endif // COMPILER
+
+namespace BASE_HASH_NAMESPACE {
+
+// Implement hashing for pairs of at-most 32 bit integer values.
+// When size_t is 32 bits, we turn the 64-bit hash code into 32 bits by using
+// multiply-add hashing. This algorithm, as described in
+// Theorem 4.3.3 of the thesis "Über die Komplexität der Multiplikation in
+// eingeschränkten Branchingprogrammmodellen" by Woelfel, is:
+//
+//   h32(x32, y32) = (h64(x32, y32) * randOdd64 + rand16 * 2^16) % 2^64 / 2^32
+
+#define DEFINE_32BIT_PAIR_HASH(type1, type2) \
+    DEFINE_PAIR_HASH_FUNCTION_START(type1, type2) { \
+      uint64 first = value.first; \
+      uint32 second = value.second; \
+      uint64 hash64 = (first << 32) | second; \
+      \
+      if (sizeof(std::size_t) >= sizeof(uint64)) \
+        return static_cast<std::size_t>(hash64); \
+      \
+      uint64 oddRandom = 885644242649267641LL; \

[jar (doing other things), 2012/09/24 20:52:21]

FWIW: This is a strange odd number: about 2^56, hence the first 8 bits are zero.
 I don't know if it is singnificant... but it is surprising.

+      uint32 shiftRandom = 10141U << 16; \
+      \
+      hash64 = hash64 * oddRandom + shiftRandom; \
+      std::size_t highBits = static_cast<std::size_t>( \
+          hash64 >> (sizeof(uint64) - sizeof(std::size_t))); \
+      return highBits; \
+    } \
+  DEFINE_PAIR_HASH_FUNCTION_END();
+
+DEFINE_32BIT_PAIR_HASH(short, short);
+DEFINE_32BIT_PAIR_HASH(short, unsigned short);
+DEFINE_32BIT_PAIR_HASH(short, int);
+DEFINE_32BIT_PAIR_HASH(short, unsigned);
+DEFINE_32BIT_PAIR_HASH(unsigned short, short);
+DEFINE_32BIT_PAIR_HASH(unsigned short, unsigned short);
+DEFINE_32BIT_PAIR_HASH(unsigned short, int);
+DEFINE_32BIT_PAIR_HASH(unsigned short, unsigned);
+DEFINE_32BIT_PAIR_HASH(int, short);
+DEFINE_32BIT_PAIR_HASH(int, unsigned short);
+DEFINE_32BIT_PAIR_HASH(int, int);
+DEFINE_32BIT_PAIR_HASH(int, unsigned);
+DEFINE_32BIT_PAIR_HASH(unsigned, short);
+DEFINE_32BIT_PAIR_HASH(unsigned, unsigned short);
+DEFINE_32BIT_PAIR_HASH(unsigned, int);
+DEFINE_32BIT_PAIR_HASH(unsigned, unsigned);
+
+#undef DEFINE_32BIT_PAIR_HASH
+
+// Implement hashing for pairs of up-to 64-bit integer values.
+// We use the compound integer hash method to produce a 64-bit hash code, by
+// breaking the two 64-bit inputs into 4 32-bit values:
+// http://opendatastructures.org/versions/edition-0.1d/ods-java/node33.html#SECTION00832000000000000000
+// Then we reduce our result to 32 bits if required, similar to above.
+
+#define DEFINE_64BIT_PAIR_HASH(type1, type2) \
+    DEFINE_PAIR_HASH_FUNCTION_START(type1, type2) { \
+      uint32 shortRandom1 = 673537332U; \
+      uint32 shortRandom2 = 2309950629U; \
+      uint32 shortRandom3 = 29379286U; \

[jar (doing other things), 2012/09/24 20:52:21]

This was a strange choice for a random odd number.  The range of choices is
0-(2^32 - 1).  You chose a number that is about 2^25.  Hence you chose to have
the first 7 bits set at zero.   I guess "every number" is a random number, but
it is generally only a 1 in 128 chance that you'd have so many leading zeros. 
The consequence of this is that when you do the multiply (by a 32 bit number),
that the high order 7 bits of the 64-bit result will always be zero.  Since the
next step in your process is close to discarding the low order 32 bits, you've
effectively started your hashing by mapping 32 bits to 25 bits.  As a result, I
think your hash will tend to drop a lot of the distinction in the item
multiplied, which means it will have a lot of collisions (right out of the gate,
and not caused by the limitation of the resulting hash size).

This is the second CL that has me concerned about the quality of the hash you
are proposing.  Can you look to find an actual hash, rather than a theoretical
paper that asks you to "choose a random number," and use that as a basis?  An
"actual" hash, with specific constants, will have been analyzed, and have
presumably better properties.

[danakj, 2012/09/24 21:09:03]

All the random numbers were generated using random.org.

There are lots of "hashes" around that do not use random seeds and are not
provably good, but I don't really understand the resistance to a random seed in
the algorithm.

+      uint32 shortRandom4 = 2611985739U; \
+      \
+      uint64 value1 = value.first; \
+      uint64 value2 = value.second; \
+      uint32 value1a = static_cast<uint32>(value1 & 0xffffffff); \
+      uint32 value1b = static_cast<uint32>((value1 >> 32) & 0xffffffff); \
+      uint32 value2a = static_cast<uint32>(value2 & 0xffffffff); \
+      uint32 value2b = static_cast<uint32>((value2 >> 32) & 0xffffffff); \
+      \
+      uint64 product1 = static_cast<uint64>(value1a) * shortRandom1; \
+      uint64 product2 = static_cast<uint64>(value1b) * shortRandom2; \
+      uint64 product3 = static_cast<uint64>(value2a) * shortRandom3; \
+      uint64 product4 = static_cast<uint64>(value2b) * shortRandom4; \
+      \
+      uint64 hash64 = product1 + product2 + product3 + product4; \
+      \
+      if (sizeof(std::size_t) >= sizeof(uint64)) \
+        return static_cast<std::size_t>(hash64); \
+      \
+      uint64 oddRandom = 629146275505555501LL; \
+      uint32 shiftRandom = 25582U << 16; \
+      \
+      hash64 = hash64 * oddRandom + shiftRandom; \
+      std::size_t highBits = static_cast<std::size_t>( \
+          hash64 >> (sizeof(uint64) - sizeof(std::size_t))); \
+      return highBits; \
+    } \
+  DEFINE_PAIR_HASH_FUNCTION_END();
+
+DEFINE_64BIT_PAIR_HASH(short, int64);
+DEFINE_64BIT_PAIR_HASH(short, uint64);
+DEFINE_64BIT_PAIR_HASH(unsigned short, int64);
+DEFINE_64BIT_PAIR_HASH(unsigned short, uint64);
+DEFINE_64BIT_PAIR_HASH(int, int64);
+DEFINE_64BIT_PAIR_HASH(int, uint64);
+DEFINE_64BIT_PAIR_HASH(unsigned, int64);
+DEFINE_64BIT_PAIR_HASH(unsigned, uint64);
+DEFINE_64BIT_PAIR_HASH(int64, short);
+DEFINE_64BIT_PAIR_HASH(int64, unsigned short);
+DEFINE_64BIT_PAIR_HASH(int64, int);
+DEFINE_64BIT_PAIR_HASH(int64, unsigned);
+DEFINE_64BIT_PAIR_HASH(int64, int64);
+DEFINE_64BIT_PAIR_HASH(int64, uint64);
+DEFINE_64BIT_PAIR_HASH(uint64, short);
+DEFINE_64BIT_PAIR_HASH(uint64, unsigned short);
+DEFINE_64BIT_PAIR_HASH(uint64, int);
+DEFINE_64BIT_PAIR_HASH(uint64, unsigned);
+DEFINE_64BIT_PAIR_HASH(uint64, int64);
+DEFINE_64BIT_PAIR_HASH(uint64, uint64);
+
+#undef DEFINE_64BIT_PAIR_HASH
+}
+
+#undef DEFINE_PAIR_HASH_FUNCTION_START
+#undef DEFINE_PAIR_HASH_FUNCTION_END
+
 namespace base {
 using BASE_HASH_NAMESPACE::hash_map;
 using BASE_HASH_NAMESPACE::hash_set;