Changed hash code strategy in hash table - now ...

Changed hash code strategy in hash table - now taking most significant bits when transforming the hash code into an index.

2 files changed, 32 insertions, 1 deletions

diff --git a/src/library/scala/collection/mutable/HashTable.scala b/src/library/scala/collection/mutable/HashTable.scala
index b924a38dde..f44209286a 100644
--- a/src/library/scala/collection/mutable/HashTable.scala
+++ b/src/library/scala/collection/mutable/HashTable.scala
@@ -237,7 +237,13 @@ trait HashTable[A] {
     h ^ (h >>> 10)
   }
 
-  protected final def index(hcode: Int) = improve(hcode) & (table.length - 1)
+  // Note:
+  // we take the most significant bits of the hashcode, not the lower ones
+  // this is of crucial importance when populating the table in parallel
+  protected final def index(hcode: Int) = {
+    val ones = table.length - 1
+    (improve(hcode) >> (32 - java.lang.Integer.bitCount(ones))) & ones
+  }
 }
 
 private[collection] object HashTable {
diff --git a/src/library/scala/collection/parallel/mutable/ParHashTable.scala b/src/library/scala/collection/parallel/mutable/ParHashTable.scala
new file mode 100644
index 0000000000..9e356b7fb4
--- /dev/null
+++ b/src/library/scala/collection/parallel/mutable/ParHashTable.scala
@@ -0,0 +1,25 @@
+package scala.collection
+package parallel.mutable
+
+
+
+
+import collection.mutable.HashEntry
+
+
+
+
+/** Provides functionality for hash tables with linked list buckets,
+ *  enriching the data structure by fulfilling certain requirements
+ *  for their parallel construction and iteration.
+ */
+trait ParHashTable[K] {
+
+  protected type Entry >: Null <: HashEntry[K, Entry]
+
+}
+
+
+
+
+