Improve WTF::HashTable performance by changing probing method

Source/wtf/HashFunctions.h

 /*
  * Copyright (C) 2005, 2006, 2008 Apple Inc. All rights reserved.
  *
  * This library is free software; you can redistribute it and/or
  * modify it under the terms of the GNU Library General Public
  * License as published by the Free Software Foundation; either
  * version 2 of the License, or (at your option) any later version.
  *
  * This library is distributed in the hope that it will be useful,
  * but WITHOUT ANY WARRANTY; without even the implied warranty of
@@ skipping 14 matching lines @@
 #include <stdint.h>
 
 namespace WTF {
 
     template<size_t size> struct IntTypes;
     template<> struct IntTypes<1> { typedef int8_t SignedType; typedef uint8_t UnsignedType; };
     template<> struct IntTypes<2> { typedef int16_t SignedType; typedef uint16_t UnsignedType; };
     template<> struct IntTypes<4> { typedef int32_t SignedType; typedef uint32_t UnsignedType; };
     template<> struct IntTypes<8> { typedef int64_t SignedType; typedef uint64_t UnsignedType; };
 
-    // integer hash function
-
-    // Thomas Wang's 32 Bit Mix Function: http://www.cris.com/~Ttwang/tech/inthash.htm
     inline unsigned intHash(uint8_t key8)
     {
-        unsigned key = key8;
-        key += ~(key << 15);
-        key ^= (key >> 10);
-        key += (key << 3);
-        key ^= (key >> 6);
-        key += ~(key << 11);
-        key ^= (key >> 16);
-        return key;
+        return key8;
     }
 
-    // Thomas Wang's 32 Bit Mix Function: http://www.cris.com/~Ttwang/tech/inthash.htm
     inline unsigned intHash(uint16_t key16)
     {
-        unsigned key = key16;
-        key += ~(key << 15);
-        key ^= (key >> 10);
-        key += (key << 3);
-        key ^= (key >> 6);
-        key += ~(key << 11);
-        key ^= (key >> 16);
-        return key;
+        return key16;
     }
 
-    // Thomas Wang's 32 Bit Mix Function: http://www.cris.com/~Ttwang/tech/inthash.htm
     inline unsigned intHash(uint32_t key) 
     {
-        key += ~(key << 15);
-        key ^= (key >> 10);
-        key += (key << 3);
-        key ^= (key >> 6);
-        key += ~(key << 11);
-        key ^= (key >> 16);
-        return key;
+        return key ^ (key >> 16);
     }
-    
-    // Thomas Wang's 64 bit Mix Function: http://www.cris.com/~Ttwang/tech/inthash.htm
+
     inline unsigned intHash(uint64_t key)
     {
-        key += ~(key << 32);
-        key ^= (key >> 22);
-        key += ~(key << 13);
-        key ^= (key >> 8);
-        key += (key << 3);
-        key ^= (key >> 15);
-        key += ~(key << 27);
-        key ^= (key >> 31);
+        key ^= key >> 32;
+        key ^= key >> 16;
         return static_cast<unsigned>(key);
     }
 
     // Compound integer hash method: http://opendatastructures.org/versions/edition-0.1d/ods-java/node33.html#SECTION00832000000000000000
     inline unsigned pairIntHash(unsigned key1, unsigned key2)
     {
         unsigned shortRandom1 = 277951225; // A random 32-bit value.
         unsigned shortRandom2 = 95187966; // A random 32-bit value.
         uint64_t longRandom = 19248658165952622LL; // A random 64-bit value.
 
@@ skipping 23 matching lines @@
 
     // pointer identity hash function
 
     template<typename T> struct PtrHash {
         static unsigned hash(T key)
         {
 #if COMPILER(MSVC)
 #pragma warning(push)
 #pragma warning(disable: 4244) // work around what seems to be a bug in MSVC's conversion warnings
 #endif
-            return IntHash<uintptr_t>::hash(reinterpret_cast<uintptr_t>(key));
+            uintptr_t keyIntPtr = reinterpret_cast<uintptr_t>(key);
+            keyIntPtr ^= keyIntPtr >> 6;
+            return IntHash<uintptr_t>::hash(keyIntPtr);
 #if COMPILER(MSVC)
 #pragma warning(pop)
 #endif
         }
         static bool equal(T a, T b) { return a == b; }
         static const bool safeToCompareToEmptyOrDeleted = true;
     };
     template<typename P> struct PtrHash<RefPtr<P> > : PtrHash<P*> {
         using PtrHash<P*>::hash;
         static unsigned hash(const RefPtr<P>& key) { return hash(key.get()); }
@@ skipping 72 matching lines @@
 
     template<typename T, typename U> struct DefaultHash<std::pair<T, U> > { typedef PairHash<T, U> Hash; };
 
 } // namespace WTF
 
 using WTF::DefaultHash;
 using WTF::IntHash;
 using WTF::PtrHash;
 
 #endif // WTF_HashFunctions_h