SERVER-12157 Replace implementation of StringMapDefaultHash::operator()

with Murmur3. This has proven to be more effective in terms of speed
and collision rates.

2 files changed, 58 insertions, 3 deletions

diff --git a/src/mongo/base/string_data.cpp b/src/mongo/base/string_data.cpp
index 31ab21f1144..51f05fb6839 100644
--- a/src/mongo/base/string_data.cpp
+++ b/src/mongo/base/string_data.cpp
@@ -20,14 +20,33 @@
 
 namespace mongo {
 
+    namespace {
+
+        template <int SizeofSizeT>
+        size_t murmur3(const StringData& str);
+
+        template <>
+        size_t murmur3<4>(const StringData& str) {
+            uint32_t hash;
+            MurmurHash3_x86_32(str.rawData(), str.size(), 0, &hash);
+            return hash;
+        }
+
+        template <>
+        size_t murmur3<8>(const StringData& str) {
+            uint64_t hash[2];
+            MurmurHash3_x64_128(str.rawData(), str.size(), 0, hash);
+            return static_cast<size_t>(hash[0]);
+        }
+
+    }  // namespace
+
     std::ostream& operator<<(std::ostream& stream, const StringData& value) {
         return stream.write(value.rawData(), value.size());
     }
 
     size_t StringData::Hasher::operator() (const StringData& str) const {
-        unsigned out;
-        MurmurHash3_x86_32(str.rawData(), str.size(), 0, &out);
-        return out;
+        return murmur3<sizeof(size_t)>(str);
     }
 
 } // namespace mongo
diff --git a/src/mongo/base/string_data_test.cpp b/src/mongo/base/string_data_test.cpp
index 2ec32039aab..977d670079e 100644
--- a/src/mongo/base/string_data_test.cpp
+++ b/src/mongo/base/string_data_test.cpp
@@ -137,6 +137,42 @@ namespace {
         ASSERT_EQUALS( string("foo").find( "" ), StringData("foo").find( "" ) );
     }
 
+    // Helper function for Test(Hasher, Str1)
+    template <int SizeofSizeT>
+    void SDHasher_check(void);
+
+    template <>
+    void SDHasher_check<4>(void) {
+        ASSERT_EQUALS(StringData::Hasher()(""),
+            static_cast<size_t>(0));
+        ASSERT_EQUALS(StringData::Hasher()("foo"),
+            static_cast<size_t>(4138058784));
+        ASSERT_EQUALS(StringData::Hasher()("pizza"),
+            static_cast<size_t>(3587803311));
+        ASSERT_EQUALS(StringData::Hasher()("mongo"),
+            static_cast<size_t>(3724335885));
+        ASSERT_EQUALS(StringData::Hasher()("murmur"),
+            static_cast<size_t>(1945310157));
+    }
+
+    template <>
+    void SDHasher_check<8>(void) {
+        ASSERT_EQUALS(StringData::Hasher()(""),
+            static_cast<size_t>(0));
+        ASSERT_EQUALS(StringData::Hasher()("foo"),
+            static_cast<size_t>(16316970633193145697UL));
+        ASSERT_EQUALS(StringData::Hasher()("pizza"),
+            static_cast<size_t>(12165495155477134356UL));
+        ASSERT_EQUALS(StringData::Hasher()("mongo"),
+            static_cast<size_t>(2861051452199491487UL));
+        ASSERT_EQUALS(StringData::Hasher()("murmur"),
+            static_cast<size_t>(18237957392784716687UL));
+    }
+
+    TEST(Hasher, Str1) {
+        SDHasher_check<sizeof(size_t)>();
+    }
+
     TEST(Rfind, Char1) {
         ASSERT_EQUALS( string::npos, StringData( "foo" ).rfind( 'a' ) );