Allow std::unordered_*.

base/containers/pair_hash.h

+// Copyright 2016 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.
+//
+
+#ifndef BASE_CONTAINERS_PAIR_HASH_H_
+#define BASE_CONTAINERS_PAIR_HASH_H_
+
+#include <stdint.h>
+
+#include <cstddef>
+#include <utility>
+
+namespace base {
+
+// 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) * rand_odd64 + rand16 * 2^16) % 2^64 / 2^32
+//
+// Contact danakj@chromium.org for any questions.
+inline std::size_t HashInts32(uint32_t value1, uint32_t value2) {
+  uint64_t value1_64 = value1;
+  uint64_t hash64 = (value1_64 << 32) | value2;
+
+  if (sizeof(std::size_t) >= sizeof(uint64_t))
+    return static_cast<std::size_t>(hash64);
+
+  uint64_t odd_random = 481046412LL << 32 | 1025306955LL;
+  uint32_t shift_random = 10121U << 16;
+
+  hash64 = hash64 * odd_random + shift_random;
+  std::size_t high_bits = static_cast<std::size_t>(
+      hash64 >> (8 * (sizeof(uint64_t) - sizeof(std::size_t))));
+  return high_bits;
+}
+
+// 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.
+inline std::size_t HashInts64(uint64_t value1, uint64_t value2) {
+  uint32_t short_random1 = 842304669U;
+  uint32_t short_random2 = 619063811U;
+  uint32_t short_random3 = 937041849U;
+  uint32_t short_random4 = 3309708029U;
+
+  uint32_t value1a = static_cast<uint32_t>(value1 & 0xffffffff);
+  uint32_t value1b = static_cast<uint32_t>((value1 >> 32) & 0xffffffff);
+  uint32_t value2a = static_cast<uint32_t>(value2 & 0xffffffff);
+  uint32_t value2b = static_cast<uint32_t>((value2 >> 32) & 0xffffffff);
+
+  uint64_t product1 = static_cast<uint64_t>(value1a) * short_random1;
+  uint64_t product2 = static_cast<uint64_t>(value1b) * short_random2;
+  uint64_t product3 = static_cast<uint64_t>(value2a) * short_random3;
+  uint64_t product4 = static_cast<uint64_t>(value2b) * short_random4;
+
+  uint64_t hash64 = product1 + product2 + product3 + product4;
+
+  if (sizeof(std::size_t) >= sizeof(uint64_t))
+    return static_cast<std::size_t>(hash64);
+
+  uint64_t odd_random = 1578233944LL << 32 | 194370989LL;
+  uint32_t shift_random = 20591U << 16;
+
+  hash64 = hash64 * odd_random + shift_random;
+  std::size_t high_bits = static_cast<std::size_t>(
+      hash64 >> (8 * (sizeof(uint64_t) - sizeof(std::size_t))));
+  return high_bits;
+}
+
+template<typename T1, typename T2>
+inline std::size_t HashPair(T1 value1, T2 value2) {

[danakj, 2016/01/14 21:29:10]

These helpers can move into an internal namespace?

I'm a bit :/ that this file defines a PairHash and a HashPair.. maybe
internal::HashPair would be enough to differenetiate?

[davidben, 2016/01/14 21:34:34]

They actually do get called directly for types that are pair-like. Though I
guess one could make a temporary pair or something? I was even debating whether
we should standardize on HashPair instead and ditch PairHash because PairHash is
not actually very general-purpose...

I didn't notice this until doing this, but PairHash and HashPair don't work for
arbitrary Type1 and Type2. They have to be numeric types, so it's not even that
good of a name. I left it PairHash because HairPair is also generic, but meant
to ask in review and forgot. :-(

Maybe it should be something like:
HashPair -> HashInts
PairHash -> IntPairHash
pair_hash.h -> ???

[danakj, 2016/01/14 21:47:12]

Oh.. pair-like.. ya. We probably don't want to force hash lookups to construct
pairs.
That seems like it could be reasonable, as it's very clean now to implement your
own hasher. Are there very many more hash keys of std::pair<> than of other
types?
sgtm
sgtm
How about just hash.h. If we add more functions for other standard composite
types, they can probably all go in here. And then that feels like it makes
HashInts a bit more discoverable/belonging/

[davidben, 2016/01/15 00:25:42]

I'm not sure. I'll give it a try and see how commonly that specialization was
used. Intuitively I would think this wouldn't be common, but maybe we have lots
of hash tables on pair<child_id, route_id> or something.
So, there's already a base/hash.h, so we probably shouldn't have a
base/containers/hash.h. But in that case, perhaps HashInts* and IntPairHash (if
not removed) should just go in base/hash.h? Though then that raises more
silliness like base::Hash(std::string) uses base::SuperFastHash which is not the
hash algorithm that StringPiece uses. And it hashes to uint32_t instead of
size_t.

+  // This condition is expected to be compile-time evaluated and optimised away
+  // in release builds.
+  if (sizeof(T1) > sizeof(uint32_t) || (sizeof(T2) > sizeof(uint32_t)))
+    return HashInts64(value1, value2);
+
+  return HashInts32(value1, value2);
+}
+
+// A templated hasher for pairs of integer types.
+template<typename Type1, typename Type2>
+struct PairHash {
+  std::size_t operator()(std::pair<Type1, Type2> value) const {
+    return base::HashPair(value.first, value.second);
+  }
+};
+
+}  // namespace base
+
+#endif  // BASE_CONTAINERS_PAIR_HASH_H_