diff options
Diffstat (limited to 'src/library/scala/collection/mutable/HashTable.scala')
| -rw-r--r-- | src/library/scala/collection/mutable/HashTable.scala | 90 |
1 files changed, 27 insertions, 63 deletions
diff --git a/src/library/scala/collection/mutable/HashTable.scala b/src/library/scala/collection/mutable/HashTable.scala index bd6fb508fe..445217ebef 100644 --- a/src/library/scala/collection/mutable/HashTable.scala +++ b/src/library/scala/collection/mutable/HashTable.scala @@ -12,6 +12,9 @@ package scala package collection package mutable +import java.lang.Integer.rotateRight +import scala.util.hashing.byteswap32 + /** This class can be used to construct data structures that are based * on hashtables. Class `HashTable[A]` implements a hashtable * that maps keys of type `A` to values of the fully abstract @@ -360,14 +363,14 @@ trait HashTable[A, Entry >: Null <: HashEntry[A, Entry]] extends HashTable.HashU protected def elemEquals(key1: A, key2: A): Boolean = (key1 == key2) - // 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) = { + /** + * 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): Int = { val ones = table.length - 1 - val improved = improve(hcode, seedvalue) - val shifted = (improved >> (32 - java.lang.Integer.bitCount(ones))) & ones - shifted + val exponent = Integer.numberOfLeadingZeros(ones) + (improve(hcode, seedvalue) >>> exponent) & ones } protected def initWithContents(c: HashTable.Contents[A, Entry]) = { @@ -396,11 +399,11 @@ private[collection] object HashTable { /** The load factor for the hash table (in 0.001 step). */ private[collection] final def defaultLoadFactor: Int = 750 // corresponds to 75% - private[collection] final def loadFactorDenom = 1000 + private[collection] final def loadFactorDenum = 1000 // should be loadFactorDenom, but changing that isn't binary compatible - private[collection] final def newThreshold(_loadFactor: Int, size: Int) = ((size.toLong * _loadFactor) / loadFactorDenom).toInt + private[collection] final def newThreshold(_loadFactor: Int, size: Int) = ((size.toLong * _loadFactor) / loadFactorDenum).toInt - private[collection] final def sizeForThreshold(_loadFactor: Int, thr: Int) = ((thr.toLong * loadFactorDenom) / _loadFactor).toInt + private[collection] final def sizeForThreshold(_loadFactor: Int, thr: Int) = ((thr.toLong * loadFactorDenum) / _loadFactor).toInt private[collection] final def capacity(expectedSize: Int) = if (expectedSize == 0) 1 else powerOfTwo(expectedSize) @@ -411,59 +414,20 @@ private[collection] object HashTable { protected def elemHashCode(key: KeyType) = key.## - protected final def improve(hcode: Int, seed: Int) = { - /* Murmur hash - * m = 0x5bd1e995 - * r = 24 - * note: h = seed = 0 in mmix - * mmix(h,k) = k *= m; k ^= k >> r; k *= m; h *= m; h ^= k; */ - // var k = hcode * 0x5bd1e995 - // k ^= k >> 24 - // k *= 0x5bd1e995 - // k - - /* Another fast multiplicative hash - * by Phil Bagwell - * - * Comment: - * Multiplication doesn't affect all the bits in the same way, so we want to - * multiply twice, "once from each side". - * It would be ideal to reverse all the bits after the first multiplication, - * however, this is more costly. We therefore restrict ourselves only to - * reversing the bytes before final multiplication. This yields a slightly - * worse entropy in the lower 8 bits, but that can be improved by adding: - * - * `i ^= i >> 6` - * - * For performance reasons, we avoid this improvement. - * */ - val i= scala.util.hashing.byteswap32(hcode) - - /* Jenkins hash - * for range 0-10000, output has the msb set to zero */ - // var h = hcode + (hcode << 12) - // h ^= (h >> 22) - // h += (h << 4) - // h ^= (h >> 9) - // h += (h << 10) - // h ^= (h >> 2) - // h += (h << 7) - // h ^= (h >> 12) - // h - - /* OLD VERSION - * quick, but bad for sequence 0-10000 - little entropy in higher bits - * since 2003 */ - // var h: Int = hcode + ~(hcode << 9) - // h = h ^ (h >>> 14) - // h = h + (h << 4) - // h ^ (h >>> 10) - - // the rest of the computation is due to SI-5293 - val rotation = seed % 32 - val rotated = (i >>> rotation) | (i << (32 - rotation)) - rotated - } + /** + * Defer to a high-quality hash in [[scala.util.hashing]]. + * The goal is to distribute across bins as well as possible even if a hash code has low entropy at some bits. + * <p/> + * OLD VERSION - quick, but bad for sequence 0-10000 - little entropy in higher bits - since 2003 + * {{{ + * var h: Int = hcode + ~(hcode << 9) + * h = h ^ (h >>> 14) + * h = h + (h << 4) + * h ^ (h >>> 10) + * }}} + * the rest of the computation is due to SI-5293 + */ + protected final def improve(hcode: Int, seed: Int): Int = rotateRight(byteswap32(hcode), seed) } /** |