blob: 20e8f249ff3f765089fb763d0c7e8e76e94f7101 (
plain) (
blame)
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
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
|
/* __ *\
** ________ ___ / / ___ Scala API **
** / __/ __// _ | / / / _ | (c) 2003-2008, LAMP/EPFL **
** __\ \/ /__/ __ |/ /__/ __ | http://www.scala-lang.org/ **
** /____/\___/_/ |_/____/_/ | | **
** |/ **
\* */
// $Id$
package scala.collection.mutable
/** This class can be used to construct data structures that are based
* on hashtables. Class <code>HashTable[A]</code> implements a hashtable
* that maps keys of type <code>A</code> to values of the fully abstract
* member type <code>Entry</code>. Classes that make use of <code>HashTable</code>
* have to provide an implementation for <code>Entry</code>
*
* There are mainly two parameters that affect the performance of a hashtable:
* the <i>initial size</i> and the <i>load factor</i>. The <i>size</i>
* refers to the number of <i>buckets</i> in the hashtable, and the <i>load
* factor</i> is a measure of how full the hashtable is allowed to get before
* its size is automatically doubled. Both parameters may be changed by
* overriding the corresponding values in class <code>HashTable</code>.
*
* @author Matthias Zenger
* @author Martin Odersky
* @version 2.0, 31/12/2006
*/
trait HashTable[A] extends AnyRef {
protected type Entry >: Null <: HashEntry[A, Entry]
/** The load factor for the hash table (in 0.001 step).
*/
protected def loadFactor: Int = 750 // corresponds to 75%
protected final val loadFactorDenum = 1000;
/** The initial size of the hash table.
*/
protected def initialSize: Int = 16
/** The initial threshold
*/
protected def initialThreshold: Int = newThreshold(initialSize)
/** The actual hash table.
*/
protected var table: Array[HashEntry[A, Entry]] =
if (initialSize == 0) null else new Array(initialSize)
/** The number of mappings contained in this hash table.
*/
protected var tableSize: Int = 0
/** The next size value at which to resize (capacity * load factor).
*/
protected var threshold: Int = initialThreshold
/** Returns the size of this hash table.
*/
def size = tableSize
protected def findEntry(key: A): Entry = {
val h = index(elemHashCode(key))
var e = table(h).asInstanceOf[Entry]
while (e != null && !elemEquals(e.key, key)) e = e.next
e
}
protected def addEntry(e: Entry) {
val h = index(elemHashCode(e.key))
e.next = table(h).asInstanceOf[Entry]
table(h) = e
tableSize = tableSize + 1
if (tableSize > threshold)
resize(2 * table.length)
}
protected def removeEntry(key: A) : Option[Entry] = {
val h = index(elemHashCode(key))
var e = table(h).asInstanceOf[Entry]
if (e != null) {
if (elemEquals(e.key, key)) {
table(h) = e.next
tableSize = tableSize - 1
return Some(e)
} else {
var e1 = e.next
while (e1 != null && !elemEquals(e1.key, key)) {
e = e1
e1 = e1.next
}
if (e1 != null) {
e.next = e1.next
tableSize = tableSize - 1
return Some(e1)
}
}
}
None
}
protected def entries: Iterator[Entry] = new Iterator[Entry] {
val iterTable = table
var idx = table.length - 1
var es = iterTable(idx).asInstanceOf[Entry]
scan()
def hasNext = es != null
def next = {
val res = es
es = es.next
scan()
res
}
def scan() {
while (es == null && idx > 0) {
idx = idx - 1
es = iterTable(idx).asInstanceOf[Entry]
}
}
}
def clear() {
var i = table.length - 1
while (i >= 0) { table(i) = null; i = i - 1 }
tableSize = 0
}
private def newThreshold(size: Int) =
((size.toLong * loadFactor)/loadFactorDenum).toInt
private def resize(newSize: Int) = {
val oldTable = table
table = new Array(newSize)
var i = oldTable.length - 1
while (i >= 0) {
var e = oldTable(i)
while (e != null) {
val h = index(elemHashCode(e.key))
val e1 = e.next
e.next = table(h).asInstanceOf[Entry]
table(h) = e
e = e1
}
i = i - 1
}
threshold = newThreshold(newSize)
}
protected def elemEquals(key1: A, key2: A): Boolean = (key1 == key2)
protected def elemHashCode(key: A) = key.hashCode()
protected final def improve(hcode: Int) = {
var h: Int = hcode + ~(hcode << 9)
h = h ^ (h >>> 14)
h = h + (h << 4)
h ^ (h >>> 10)
}
protected final def index(hcode: Int) = improve(hcode) & (table.length - 1)
}
trait HashEntry[A, E] {
val key: A
var next: E = _
}
|
