SI-9789 use quadratic probing in OpenHashMap

The original probe sequence, taken from Python's hash table code, is
exponential, jumping around in the hash table with poor memory locality.
This replaces the probe algorithm with the more conventional quadratic
probing.

This also adds tests to the benchmarking code using AnyRef keys, which
have pseudorandom hash codes (unlike Ints, whose hash code is simply
the Int itself).  The intensity of the benchmarking is reduced to make
the tests complete within 9 hours, by removing unnecessary sampling.

1 files changed, 6 insertions, 12 deletions

diff --git a/src/library/scala/collection/mutable/OpenHashMap.scala b/src/library/scala/collection/mutable/OpenHashMap.scala
index 5f8f5b9a0a..c86357efad 100644
--- a/src/library/scala/collection/mutable/OpenHashMap.scala
+++ b/src/library/scala/collection/mutable/OpenHashMap.scala
@@ -108,16 +108,13 @@ extends AbstractMap[Key, Value]
     * @param hash hash value for `key`
     */
   private[this] def findIndex(key: Key, hash: Int): Int = {
-    var j = hash
-
     var index = hash & mask
-    var perturb = index
+    var j = 0
     while(table(index) != null &&
           !(table(index).hash == hash &&
             table(index).key == key)){
-      j = 5 * j + 1 + perturb
-      perturb >>= 5
-      index = j & mask
+      j += 1
+      index = (index + j) & mask
     }
     index
   }
@@ -172,20 +169,17 @@ extends AbstractMap[Key, Value]
 
   def get(key : Key) : Option[Value] = {
     val hash = hashOf(key)
-
-    var j = hash
     var index = hash & mask
-    var perturb = index
     var entry = table(index)
+    var j = 0
     while(entry != null){
       if (entry.hash == hash &&
           entry.key == key){
         return entry.value
       }
 
-      j = 5 * j + 1 + perturb
-      perturb >>= 5
-      index = j & mask
+      j += 1
+      index = (index + j) & mask
       entry = table(index)
     }
     None