Add methods for hashing pairs of integer values.

base/hash_tables.h

 // Copyright (c) 2011 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 //
 
 //
 // Deal with the differences between Microsoft and GNU implemenations
 // of hash_map. Allows all platforms to use |base::hash_map| and
 // |base::hash_set|.
 //  eg:
@@ skipping 13 matching lines @@
 #include "build/build_config.h"
 
 #include "base/string16.h"
 
 #if defined(COMPILER_MSVC)
 #include <hash_map>
 #include <hash_set>
 
 #define BASE_HASH_NAMESPACE stdext
 
+template <typename Key>
+struct hash : public BASE_HASH_NAMESPACE::hash_compare<Key> {
+};
+
 #elif defined(COMPILER_GCC)
 #if defined(OS_ANDROID)
 #define BASE_HASH_NAMESPACE std
 #else
 #define BASE_HASH_NAMESPACE __gnu_cxx
 #endif
 
 // This is a hack to disable the gcc 4.4 warning about hash_map and hash_set
 // being deprecated.  We can get rid of this when we upgrade to VS2008 and we
 // can use <tr1/unordered_map> and <tr1/unordered_set>.
@@ skipping 54 matching lines @@
           result = (result * 131) + *i; \
         return result; \
       } \
     }
 
 DEFINE_STRING_HASH(std::string);
 DEFINE_STRING_HASH(string16);
 
 #undef DEFINE_STRING_HASH
 
+// Implement hashing for pairs of at-most 32 bit integer values.
+// We use randomly-generated 32-bit and 64-bit values to produce a hash code.
+// If the hash code is 64-bit then we can be very efficient to produce a
+// universal hash function. When size_t is 64 bits, the algorithm, as described
+// in Section 4 of "UMAC: Fast and Secure Message Authentication" by Black,
+// Halevi, Krawczyk, Krovetz, and Rogaway, is:
+//
+//   h64(x32, y32) = ((x32 + rand32) % 2^32)((y32 + rand32) % 2^32) % 2^64

[jar (doing other things), 2012/09/17 22:01:13]

a) It appears that the second modulus operator (mod 2^64) is of no value, since
multiplying two 32 bit numbers (the result of a mod 2^32 operation) always
produces a result that is less than 2^64.

b) The distribution of the product of two numbers is, I believe, well known to
be very non-uniformly distributed, assuming the original numbers were uniformly
distributed.

For example: try multiplying all the numbers from 0-9 by all the numbers from
0-9. That is an example of multiplying all numbers up modulo 10^1 by all numbers
modulo 10^1, and getting a result that is reduced modular 10^2. The results are
VERY skewed toward low numbers.   Note that 10% of the results are zero, none
are over 90,  1% are over 80 (re: 81), and the mean is going to be a mere 12.96.
 Bottom line: This instigates a lot of collisions, and in a relatively poor
hash.

A **MUCH** better 64 bit hash of two 32 bits numbers in to concatenate them
(i.e., multiply one by 2^32, and add to the second).

+//
+// When size_t is 32 bits, we turn the 64-bit hash code above back into
+// 32 bits by using multiply-add hashing. This algorithm, as described in
+// Theorem 6 of "Efficient Strongly Universal and Optimally Universal Hashing"
+// by Woelfel, is:
+//
+//   h32(x32, y32) = (h64(x32, y32) * randOdd64 + rand32 * 2^32) % 2^64 / 2^32

[jar (doing other things), 2012/09/17 22:01:13]

Here, the addition of rand32 * 2^32 is useless, for mixing purposes.  It does
not increase or decrease collisions.

Once you take that away, you can see that this has appears to do little more
than you'd get from taking only the upper 32 bits of a 64 bit hash.

What am I missing?

+
+#define DEFINE_32BIT_PAIR_HASH(type1, type2) \
+    template<> \
+    struct hash<std::pair<type1, type2> > { \
+      std::size_t operator()(std::pair<type1, type2> value) const { \
+        uint32 shortRandom1 = 698340900U; \
+        uint32 shortRandom2 = 2638093458U; \
+        \
+        uint32 sum1 = value.first + shortRandom1; \
+        uint32 sum2 = value.second + shortRandom2; \
+        uint64 hash64 = static_cast<uint64>(sum1) * sum2; \
+        \
+        if (sizeof(std::size_t) >= sizeof(uint64)) \
+          return static_cast<std::size_t>(hash64); \
+        \
+        uint64 longRandom1 = 885644242649267641LL; \
+        uint64 longRandom2 = 1614045628LL << 32; \
+        \
+        hash64 = hash64 * longRandom1 + longRandom2; \
+        std::size_t highBits = static_cast<std::size_t>( \
+            hash64 >> (sizeof(uint64) - sizeof(std::size_t))); \
+        return highBits; \
+      } \
+      \
+      size_t operator()(const std::pair<type1, type2>& a, \
+                        const std::pair<type1, type2>& b) const { \
+        return a < b; \
+      } \
+    }; \
+
+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 above algorithms for 32-bit integers, but treat each 64-bit
+// value as 2 32-bit values.
+
+#define DEFINE_64BIT_PAIR_HASH(type1, type2) \
+    template<> \
+    struct hash<std::pair<type1, type2> > { \
+      std::size_t operator()(std::pair<type1, type2> value) const { \
+        uint32 shortRandom1 = 673537332U; \
+        uint32 shortRandom2 = 2309950629U; \
+        uint32 shortRandom3 = 29379286U; \
+        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); \
+        \
+        uint32 sum1 = value1a + shortRandom1; \
+        uint32 sum2 = value1b + shortRandom2; \
+        uint32 sum3 = value2a + shortRandom3; \
+        uint32 sum4 = value2b + shortRandom4; \
+        uint64 hash64 = static_cast<uint64>(sum1) * sum2 + \
+                        static_cast<uint64>(sum3) * sum4; \
+        \
+        if (sizeof(std::size_t) >= sizeof(uint64)) \
+          return static_cast<std::size_t>(hash64); \
+        \
+        uint64 longRandom1 = 629146275505555501LL; \
+        uint64 longRandom2 = 45557137LL << 32; \
+        \
+        hash64 = hash64 * longRandom1 + longRandom2; \
+        std::size_t highBits = static_cast<std::size_t>( \
+            hash64 >> (sizeof(uint64) - sizeof(std::size_t))); \
+        return highBits; \
+      } \
+      size_t operator()(const std::pair<type1, type2>& a, \
+                        const std::pair<type1, type2>& b) const { \
+        return a < b; \
+      } \
+    };
+
+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
+
 }  // namespace BASE_HASH_NAMESPACE
 
 #else  // COMPILER
 #error define BASE_HASH_NAMESPACE for your compiler
 #endif  // COMPILER
 
 namespace base {
 using BASE_HASH_NAMESPACE::hash_map;
 using BASE_HASH_NAMESPACE::hash_set;
 }
 
 #endif  // BASE_HASH_TABLES_H_