diff options
author | Aleksandar Pokopec <aleksandar.prokopec@epfl.ch> | 2010-10-20 20:19:48 +0000 |
---|---|---|
committer | Aleksandar Pokopec <aleksandar.prokopec@epfl.ch> | 2010-10-20 20:19:48 +0000 |
commit | 2f7197c50b31386118a660833828ea720bf9d239 (patch) | |
tree | 1db8c52c3b3a1383ac05fab1c477ce6913d04d79 | |
parent | d33724e24bbb0a5b2cb650f207a283f59ad68dd5 (diff) | |
download | scala-2f7197c50b31386118a660833828ea720bf9d239.tar.gz scala-2f7197c50b31386118a660833828ea720bf9d239.tar.bz2 scala-2f7197c50b31386118a660833828ea720bf9d239.zip |
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.
-rw-r--r-- | src/library/scala/collection/mutable/HashTable.scala | 8 | ||||
-rw-r--r-- | src/library/scala/collection/parallel/mutable/ParHashTable.scala | 25 |
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] + +} + + + + + |