diff options
author | Pap LÅ‘rinc <paplorinc@gmail.com> | 2016-11-22 10:59:30 +0200 |
---|---|---|
committer | Adriaan Moors <adriaan@lightbend.com> | 2017-01-05 13:27:04 -0800 |
commit | 26ad9cc73c88bad0140adb7cec583a4d05db498d (patch) | |
tree | d92b6170b36c913acc93d004bbe29741104679de /src/library | |
parent | 5fd422b6aa40855c86d0054e61da774151a3272e (diff) | |
download | scala-26ad9cc73c88bad0140adb7cec583a4d05db498d.tar.gz scala-26ad9cc73c88bad0140adb7cec583a4d05db498d.tar.bz2 scala-26ad9cc73c88bad0140adb7cec583a4d05db498d.zip |
Changed modulo to bitwise AND in hash calculation
(cherry picked from commit 7952525e7119282ec8308a0076db54923f95dc21)
Diffstat (limited to 'src/library')
-rw-r--r-- | src/library/scala/collection/mutable/HashTable.scala | 69 |
1 files changed, 17 insertions, 52 deletions
diff --git a/src/library/scala/collection/mutable/HashTable.scala b/src/library/scala/collection/mutable/HashTable.scala index 81e42f86b3..dd08e3d9fb 100644 --- a/src/library/scala/collection/mutable/HashTable.scala +++ b/src/library/scala/collection/mutable/HashTable.scala @@ -411,58 +411,23 @@ 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 = { + val hash = scala.util.hashing.byteswap32(hcode) + val shift = seed & ((1 << 5) - 1) + (hash >>> shift) | (hash << (32 - shift)) } } |