From 03255440de05dba07732cb7e261a87a57815eb9b Mon Sep 17 00:00:00 2001 From: "bmeurer@chromium.org" Date: Mon, 6 Oct 2014 15:23:59 +0000 Subject: [PATCH] Don't use identity as hash function for integers. Also slightly improve hashing of floats/doubles. TEST=unittests R=jarin@chromium.org Review URL: https://codereview.chromium.org/632713002 git-svn-id: https://v8.googlecode.com/svn/branches/bleeding_edge@24420 ce2b1a6d-e550-0410-aec6-3dcde31c8c00 --- src/base/functional.cc | 17 +++++++++++++++-- src/base/functional.h | 6 +++--- test/unittests/base/functional-unittest.cc | 2 +- 3 files changed, 19 insertions(+), 6 deletions(-) diff --git a/src/base/functional.cc b/src/base/functional.cc index c4a61ad..4c0f3c8 100644 --- a/src/base/functional.cc +++ b/src/base/functional.cc @@ -64,6 +64,19 @@ size_t hash_combine(size_t seed, size_t value) { } +// Thomas Wang, Integer Hash Functions. +// http://www.concentric.net/~Ttwang/tech/inthash.htm +size_t hash_value(unsigned int v) { + v = ~v + (v << 15); // v = (v << 15) - v - 1; + v = v ^ (v >> 12); + v = v + (v << 2); + v = v ^ (v >> 4); + v = v * 2057; // v = (v + (v << 3)) + (v << 11); + v = v ^ (v >> 16); + return v; +} + + size_t hash_value(unsigned long v) { // NOLINT(runtime/int) return hash_value_unsigned(v); } @@ -76,13 +89,13 @@ size_t hash_value(unsigned long long v) { // NOLINT(runtime/int) size_t hash_value(float v) { // 0 and -0 both hash to zero. - return v != 0.0f ? hash_value(bit_cast(v)) : 0; + return v != 0.0f ? hash_value_unsigned(bit_cast(v)) : 0; } size_t hash_value(double v) { // 0 and -0 both hash to zero. - return v != 0.0 ? hash_value(bit_cast(v)) : 0; + return v != 0.0 ? hash_value_unsigned(bit_cast(v)) : 0; } } // namespace base diff --git a/src/base/functional.h b/src/base/functional.h index 60f93dd..d815c72 100644 --- a/src/base/functional.h +++ b/src/base/functional.h @@ -76,11 +76,11 @@ inline size_t hash_combine(T const& v, Ts const&... vs) { V8_BASE_HASH_VALUE_TRIVIAL(bool) V8_BASE_HASH_VALUE_TRIVIAL(unsigned char) V8_BASE_HASH_VALUE_TRIVIAL(unsigned short) // NOLINT(runtime/int) -V8_BASE_HASH_VALUE_TRIVIAL(unsigned int) #undef V8_BASE_HASH_VALUE_TRIVIAL -size_t hash_value(unsigned long v); // NOLINT(runtime/int) -size_t hash_value(unsigned long long v); // NOLINT(runtime/int) +size_t hash_value(unsigned int); +size_t hash_value(unsigned long); // NOLINT(runtime/int) +size_t hash_value(unsigned long long); // NOLINT(runtime/int) #define V8_BASE_HASH_VALUE_SIGNED(type) \ inline size_t hash_value(signed type v) { \ diff --git a/test/unittests/base/functional-unittest.cc b/test/unittests/base/functional-unittest.cc index e6f260f..4015485 100644 --- a/test/unittests/base/functional-unittest.cc +++ b/test/unittests/base/functional-unittest.cc @@ -83,7 +83,7 @@ TYPED_TEST(FunctionalTest, HashIsStateless) { TYPED_TEST(FunctionalTest, HashIsOkish) { const size_t kValues = 128; - const size_t kMinHashes = kValues / (sizeof(uint64_t) / sizeof(size_t)); + const size_t kMinHashes = kValues / 4; std::set vs; while (vs.size() != kValues) { TypeParam v; -- 2.7.4