Fix #5293 - changed the way hashcode is improved in hash sets.

The hash code is further improved by using a special value in the hash sets
called a `seed`. For sequential hash tables, this value depends on the size
of the hash table. It determines the number of bits the hashcode should be
rotated. This ensures that hash tables with different sizes use different
bits to compute the position of the element. This way traversing the elements
of the source hash table will yield them in the order where they had similar
hashcodes (and hence, positions) in the source table, but different ones in
the destination table.

Ideally, in the future we want to be able to have a family of hash functions
and assign a different hash function from that family to each hash table
instance. That would statistically almost completely eliminate the possibility
that the hash table element traversal causes excessive collisions.

I should probably @mention extempore here.

1 files changed, 83 insertions, 0 deletions

diff --git a/test/files/run/t5293.scala b/test/files/run/t5293.scala
new file mode 100644
index 0000000000..de1efaec4a
--- /dev/null
+++ b/test/files/run/t5293.scala
@@ -0,0 +1,83 @@
+
+
+
+import scala.collection.JavaConverters._
+
+
+
+object Test extends App {
+  
+  def bench(label: String)(body: => Unit): Long = {
+    val start = System.nanoTime
+
+    0.until(10).foreach(_ => body)
+
+    val end = System.nanoTime
+
+    //println("%s: %s ms".format(label, (end - start) / 1000.0 / 1000.0))
+    
+    end - start
+  }
+  
+  def benchJava(values: java.util.Collection[Int]) = {
+    bench("Java Set") {
+      val set = new java.util.HashSet[Int]
+      
+      set.addAll(values)
+    }
+  }
+
+  def benchScala(values: Iterable[Int]) = {
+    bench("Scala Set") {
+      val set = new scala.collection.mutable.HashSet[Int]
+      
+      set ++= values
+    }
+  }
+  
+  def benchScalaSorted(values: Iterable[Int]) = {
+    bench("Scala Set sorted") {
+      val set = new scala.collection.mutable.HashSet[Int]
+      
+      set ++= values.toArray.sorted
+    }
+  }
+  
+  def benchScalaPar(values: Iterable[Int]) = {
+    bench("Scala ParSet") {
+      val set = new scala.collection.parallel.mutable.ParHashSet[Int] map { x => x }
+      
+      set ++= values
+    }
+  }
+  
+  val values = 0 until 50000
+  val set = scala.collection.mutable.HashSet.empty[Int]
+  
+  set ++= values
+  
+  // warmup
+  for (x <- 0 until 5) {
+    benchJava(set.asJava)
+    benchScala(set)
+    benchScalaPar(set)
+    benchJava(set.asJava)
+    benchScala(set)
+    benchScalaPar(set)
+  }
+  
+  val javaset = benchJava(set.asJava)
+  val scalaset = benchScala(set)
+  val scalaparset = benchScalaPar(set)
+  
+  assert(scalaset < (javaset * 4))
+  assert(scalaparset < (javaset * 4))
+}
+
+
+
+
+
+
+
+