summaryrefslogtreecommitdiff
path: root/src/library
diff options
context:
space:
mode:
authorMartin Odersky <odersky@gmail.com>2007-01-30 15:17:05 +0000
committerMartin Odersky <odersky@gmail.com>2007-01-30 15:17:05 +0000
commit4a64ac9c7b94b249087cd25712dfb547013f5ed4 (patch)
treeaa884033db150ebde48d2027d29bbc5f3723b9f1 /src/library
parent2f4c6a2eb8405eaa6d54a8d29f33f4595da7d1c7 (diff)
downloadscala-4a64ac9c7b94b249087cd25712dfb547013f5ed4.tar.gz
scala-4a64ac9c7b94b249087cd25712dfb547013f5ed4.tar.bz2
scala-4a64ac9c7b94b249087cd25712dfb547013f5ed4.zip
fixed flathashtable.
Diffstat (limited to 'src/library')
-rwxr-xr-xsrc/library/scala/collection/mutable/FlatHashTable.scala27
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