1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
|
import scala.collection.immutable._
object Test extends App {
def test1() {
// test that a HashTrieMap with one leaf element is not created!
val x = HashMap.empty + (1->1) + (2->2)
if(x.getClass.getSimpleName != "HashTrieMap")
println("A hash map containing two non-colliding values should be a HashTrieMap")
val y = x - 1
if(y.getClass.getSimpleName != "HashMap1")
println("A hash map containing one element should always use HashMap1")
}
def test2() {
// class that always causes hash collisions
case class Collision(value:Int) { override def hashCode = 0 }
// create a set that should have a collison
val x = HashMap.empty + (Collision(0)->0) + (Collision(1) ->0)
if(x.getClass.getSimpleName != "HashMapCollision1")
println("HashMap of size >1 with collisions should use HashMapCollision")
// remove the collision again by removing all but one element
val y = x - Collision(0)
if(y.getClass.getSimpleName != "HashMap1")
println("HashMap of size 1 should use HashMap1" + y.getClass)
}
def test3() {
// finds an int x such that improved(x) differs in the first bit to improved(0),
// which is the worst case for the HashTrieSet
def findWorstCaseInts() {
// copy of improve from HashSet
def improve(hcode: Int) = {
var h: Int = hcode + ~(hcode << 9)
h = h ^ (h >>> 14)
h = h + (h << 4)
h ^ (h >>> 10)
}
// find two hashes which have a large separation
val x = 0
var y = 1
val ix = improve(x)
while(y!=0 && improve(y)!=ix+(1<<31))
y+=1
printf("%s %s %x %x\n",x,y,improve(x), improve(y))
}
// this is not done every test run since it would slow down ant test.suite too much.
// findWorstCaseInts()
// two numbers that are immediately adiacent when fed through HashSet.improve
val h0 = 0
val h1 = 1270889724
// h is the hashcode, i is ignored for the hashcode but relevant for equality
case class Collision(h:Int, i:Int) {
override def hashCode = h
}
val a = Collision(h0,0)->0
val b = Collision(h0,1)->0
val c = Collision(h1,0)->0
// create a HashSetCollision1
val x = HashMap(a) + b
if(x.getClass.getSimpleName != "HashMapCollision1")
println("x should be a HashMapCollision")
StructureTests.validate(x)
//StructureTests.printStructure(x)
require(x.size==2 && x.contains(a._1) && x.contains(b._1))
// go from a HashSetCollision1 to a HashTrieSet with maximum depth
val y = x + c
if(y.getClass.getSimpleName != "HashTrieMap")
println("y should be a HashTrieMap")
StructureTests.validate(y)
// StructureTests.printStructure(y)
require(y.size==3 && y.contains(a._1) && y.contains(b._1) && y.contains(c._1))
// go from a HashSet1 directly to a HashTrieSet with maximum depth
val z = HashMap(a) + c
if(y.getClass.getSimpleName != "HashTrieMap")
println("y should be a HashTrieMap")
StructureTests.validate(z)
// StructureTests.printStructure(z)
require(z.size == 2 && z.contains(a._1) && z.contains(c._1))
}
test1()
test2()
test3()
}
package scala.collection.immutable {
object StructureTests {
def printStructure(x:HashMap[_,_], prefix:String="") {
x match {
case m:HashMap.HashTrieMap[_,_] =>
println(prefix+m.getClass.getSimpleName + " " + m.size)
m.elems.foreach(child => printStructure(child, prefix + " "))
case m:HashMap.HashMapCollision1[_,_] =>
println(prefix+m.getClass.getSimpleName + " " + m.kvs.size)
case m:HashMap.HashMap1[_,_] =>
println(prefix+m.getClass.getSimpleName + " " + m.head)
case _ =>
println(prefix+"empty")
}
}
def validate(x:HashMap[_,_]) {
x match {
case m:HashMap.HashTrieMap[_,_] =>
require(m.elems.size>1 || (m.elems.size==1 && m.elems(0).isInstanceOf[HashMap.HashTrieMap[_,_]]))
m.elems.foreach(validate _)
case m:HashMap.HashMapCollision1[_,_] =>
require(m.kvs.size>1)
case m:HashMap.HashMap1[_,_] =>
case _ =>
}
}
}
}
|
