diff options
author | Martin Odersky <odersky@gmail.com> | 2007-01-30 15:17:05 +0000 |
---|---|---|
committer | Martin Odersky <odersky@gmail.com> | 2007-01-30 15:17:05 +0000 |
commit | 4a64ac9c7b94b249087cd25712dfb547013f5ed4 (patch) | |
tree | aa884033db150ebde48d2027d29bbc5f3723b9f1 /src/library | |
parent | 2f4c6a2eb8405eaa6d54a8d29f33f4595da7d1c7 (diff) | |
download | scala-4a64ac9c7b94b249087cd25712dfb547013f5ed4.tar.gz scala-4a64ac9c7b94b249087cd25712dfb547013f5ed4.tar.bz2 scala-4a64ac9c7b94b249087cd25712dfb547013f5ed4.zip |
fixed flathashtable.
Diffstat (limited to 'src/library')
-rwxr-xr-x | src/library/scala/collection/mutable/FlatHashTable.scala | 27 |
1 files changed, 18 insertions, 9 deletions
diff --git a/src/library/scala/collection/mutable/FlatHashTable.scala b/src/library/scala/collection/mutable/FlatHashTable.scala index aee4cb7fc8..6bb6af59f3 100755 --- a/src/library/scala/collection/mutable/FlatHashTable.scala +++ b/src/library/scala/collection/mutable/FlatHashTable.scala @@ -6,11 +6,13 @@ package scala.collection.mutable +import Predef._ + trait FlatHashTable[A] { - /** The load factor for the hash table. + /** The load factor for the hash table; must be < 0.5f */ - protected def loadFactor: Float = 0.5f + protected def loadFactor: Float = 0.45f /** The initial size of the hash table. */ @@ -67,9 +69,11 @@ trait FlatHashTable[A] { } def removeEntry(elem: A) { - def precedes(i: int, j: int, base: int) = - if (base <= i) i <= j || j < base - else i <= j && j < base + def precedes(i: int, j: int) = { + val d = table.length >> 2 + if (i <= j) j - i < d + else i - j > d + } var h = index(elemHashCode(elem)) var entry = table(h) while (null != entry) { @@ -78,13 +82,15 @@ trait FlatHashTable[A] { var h1 = (h0 + 1) % table.length while (null != table(h1)) { val h2 = index(elemHashCode(table(h1).asInstanceOf[A])) - if (h2 != h1 && precedes(h2, h0, h)) { + //Console.println("shift at "+h1+":"+table(h1)+" with h2 = "+h2+"?") + if (h2 != h1 && precedes(h2, h0)) { + //Console.println("shift "+h1+" to "+h0+"!") table(h0) = table(h1) h0 = h1 } h1 = (h1 + 1) % table.length } - table(h1) = null + table(h0) = null tableSize = tableSize - 1 return } @@ -128,8 +134,11 @@ trait FlatHashTable[A] { protected final def index(hcode: Int) = improve(hcode) & (table.length - 1) - private def newThreshold(size: Int) = - (size * loadFactor).asInstanceOf[Int] + private def newThreshold(size: Int) = { + val lf = loadFactor + assert(lf < 0.5f, "loadFactor too large; must be < 0.5") + (size * lf).asInstanceOf[Int] + } protected def clear() { var i = table.length - 1 |