1 | |
|
2 | |
|
3 | |
|
4 | |
|
5 | |
|
6 | |
package jaggregate.internal; |
7 | |
|
8 | |
import jaggregate.Pair; |
9 | |
import jaggregate.UnaryFunctor; |
10 | |
import static jaggregate.internal.Casting.*; |
11 | |
|
12 | |
|
13 | |
|
14 | |
|
15 | |
|
16 | |
|
17 | |
|
18 | |
|
19 | |
|
20 | |
|
21 | |
public class HashingContainer<K, V> { |
22 | |
private static final int DEFAULT_INITIAL_CAPACITY = 16; |
23 | |
private static final double DEFAULT_LOAD_FACTOR = 0.75; |
24 | |
|
25 | |
private Object[] buckets; |
26 | |
private int numberOfElements; |
27 | |
private final EquivalenceTester equivalenceTester; |
28 | |
|
29 | |
|
30 | |
|
31 | |
|
32 | |
|
33 | |
|
34 | |
|
35 | |
public HashingContainer( EquivalenceTester equivalenceTester ) { |
36 | 2329 | this( DEFAULT_INITIAL_CAPACITY, equivalenceTester ); |
37 | 2329 | } |
38 | |
|
39 | |
|
40 | |
|
41 | |
|
42 | |
|
43 | |
|
44 | |
|
45 | |
|
46 | 2335 | public HashingContainer( int capacity, EquivalenceTester equivalenceTester ) { |
47 | 2335 | this.equivalenceTester = equivalenceTester; |
48 | 2335 | buckets = new Object[ capacity ]; |
49 | 2335 | numberOfElements = 0; |
50 | 2335 | } |
51 | |
|
52 | |
|
53 | |
|
54 | |
|
55 | |
|
56 | |
|
57 | |
|
58 | |
|
59 | |
|
60 | |
public V put( K key, V value ) { |
61 | 9149 | int hashIndex = hash( key ); |
62 | 9149 | Node<K, V> hashed = cast( buckets[ hashIndex ] ); |
63 | |
|
64 | 9149 | if ( hashed == null ) { |
65 | 7453 | buckets[ hashIndex ] = new Node<K, V>( key, value, null ); |
66 | 7453 | ++numberOfElements; |
67 | 7453 | rehash(); |
68 | 7453 | return null; |
69 | |
} |
70 | |
|
71 | 1879 | while ( hashed.nextNode != null && !areEqual( key, hashed.key() ) ) |
72 | 183 | hashed = hashed.nextNode; |
73 | |
|
74 | 1696 | if ( areEqual( key, hashed.key() ) ) { |
75 | 616 | V oldValue = hashed.value(); |
76 | 616 | hashed.pair.setValue( value ); |
77 | 616 | return oldValue; |
78 | |
} |
79 | |
else { |
80 | 1080 | hashed.nextNode = new Node<K, V>( key, value, null ); |
81 | 1080 | ++numberOfElements; |
82 | 1080 | rehash(); |
83 | 1080 | return null; |
84 | |
} |
85 | |
} |
86 | |
|
87 | |
|
88 | |
|
89 | |
|
90 | |
|
91 | |
|
92 | |
|
93 | |
|
94 | |
public V get( K key ) { |
95 | 6574 | int hashIndex = hash( key ); |
96 | 6574 | Node<K, V> hashed = cast( buckets[ hashIndex ] ); |
97 | |
|
98 | 6864 | while ( hashed != null && !areEqual( key, hashed.key() ) ) |
99 | 290 | hashed = hashed.nextNode; |
100 | |
|
101 | 6574 | return hashed == null ? null : hashed.value(); |
102 | |
} |
103 | |
|
104 | |
|
105 | |
|
106 | |
|
107 | |
|
108 | |
|
109 | |
|
110 | |
|
111 | |
public V remove( K key ) { |
112 | 1403 | int hashIndex = hash( key ); |
113 | 1403 | Node<K, V> hashed = cast( buckets[ hashIndex ] ); |
114 | 1403 | Node<K, V> current = hashed; |
115 | |
Node<K, V> next; |
116 | |
|
117 | 1699 | for ( ; current != null; hashed = current, current = next ) { |
118 | 1466 | next = current.nextNode; |
119 | |
|
120 | 1466 | if ( areEqual( key, current.key() ) ) { |
121 | 1318 | --numberOfElements; |
122 | |
|
123 | 1318 | if ( current == hashed ) |
124 | 1183 | buckets[ hashIndex ] = next; |
125 | |
else |
126 | 135 | hashed.nextNode = next; |
127 | |
|
128 | 1318 | return current.value(); |
129 | |
} |
130 | |
} |
131 | |
|
132 | 85 | return null; |
133 | |
} |
134 | |
|
135 | |
|
136 | |
|
137 | |
|
138 | |
|
139 | |
|
140 | |
|
141 | |
public boolean hasKey( K key ) { |
142 | 2827 | int hashIndex = hash( key ); |
143 | |
|
144 | 2827 | for ( Node<K, V> hashed = cast( buckets[ hashIndex ] ); |
145 | 3063 | hashed != null; |
146 | 236 | hashed = hashed.nextNode ) { |
147 | |
|
148 | 2426 | if ( areEqual( key, hashed.key() ) ) |
149 | 2190 | return true; |
150 | |
} |
151 | |
|
152 | 637 | return false; |
153 | |
} |
154 | |
|
155 | |
|
156 | |
|
157 | |
|
158 | |
|
159 | |
|
160 | |
public int size() { |
161 | 12116 | return numberOfElements; |
162 | |
} |
163 | |
|
164 | |
|
165 | |
|
166 | |
|
167 | |
|
168 | |
|
169 | |
public int capacity() { |
170 | 6 | return buckets.length; |
171 | |
} |
172 | |
|
173 | |
|
174 | |
|
175 | |
|
176 | |
|
177 | |
|
178 | |
public void forEachDo( UnaryFunctor<? super Pair<K, V>, ?> operation ) { |
179 | 43588 | for ( Object each : buckets ) |
180 | 41155 | doForBucket( operation, each ); |
181 | 2433 | } |
182 | |
|
183 | |
private void doForBucket( UnaryFunctor<? super Pair<K, V>, ?> operation, |
184 | |
Object bucket ) { |
185 | |
|
186 | 41155 | for ( Node<K, V> node = cast( bucket ); |
187 | 49043 | node != null; |
188 | 7888 | node = node.nextNode ) { |
189 | |
|
190 | 8175 | operation.evaluate( node.pair ); |
191 | |
} |
192 | 40868 | } |
193 | |
|
194 | |
|
195 | |
|
196 | |
|
197 | |
|
198 | |
|
199 | |
|
200 | |
|
201 | |
|
202 | |
public boolean areEqual( Object first, Object second ) { |
203 | 12981 | return equivalenceTester.areEqual( first, second ); |
204 | |
} |
205 | |
|
206 | |
|
207 | |
|
208 | |
|
209 | |
public void rehash() { |
210 | 8544 | if ( size() >= (int) ( buckets.length * DEFAULT_LOAD_FACTOR ) ) { |
211 | 24 | Object[] oldTable = buckets; |
212 | 24 | buckets = new Object[ 2 * buckets.length ]; |
213 | 24 | numberOfElements = 0; |
214 | |
|
215 | 1464 | for ( Object each : oldTable ) |
216 | 1440 | repopulateBucket( each ); |
217 | |
} |
218 | 8544 | } |
219 | |
|
220 | |
private void repopulateBucket( Object bucket ) { |
221 | 2520 | for ( Node<K, V> node = cast( bucket ); node != null; node = node.nextNode ) |
222 | 1080 | put( node.key(), node.value() ); |
223 | 1440 | } |
224 | |
|
225 | |
|
226 | |
|
227 | |
|
228 | |
|
229 | |
private int hash( K key ) { |
230 | 19953 | int[] perturbations = { 15, 10, 3, 6, 11, 16 }; |
231 | |
|
232 | 19953 | int hashValue = equivalenceTester.hashCode( key ); |
233 | 19953 | int index = 0; |
234 | 19953 | hashValue += ~( hashValue << perturbations[ index ] ); |
235 | 19953 | ++index; |
236 | 19953 | hashValue ^= hashValue >>> perturbations[ index ]; |
237 | 19953 | ++index; |
238 | 19953 | hashValue += hashValue << perturbations[ index ]; |
239 | 19953 | ++index; |
240 | 19953 | hashValue ^= hashValue >>> perturbations[ index ]; |
241 | 19953 | ++index; |
242 | 19953 | hashValue += ~( hashValue << perturbations[ index ] ); |
243 | 19953 | ++index; |
244 | 19953 | hashValue ^= hashValue >>> perturbations[ index ]; |
245 | |
|
246 | 19953 | return hashValue & ( buckets.length - 1 ); |
247 | |
} |
248 | |
|
249 | |
|
250 | |
|
251 | |
|
252 | |
|
253 | |
public static class Node<K, V> { |
254 | |
public final MutablePair<K, V> pair; |
255 | |
public Node<K, V> nextNode; |
256 | |
|
257 | 8533 | Node( K key, V value, Node<K, V> nextNode ) { |
258 | 8533 | this.nextNode = nextNode; |
259 | 8533 | pair = new MutablePair<K, V>( key, value ); |
260 | 8533 | } |
261 | |
|
262 | |
K key() { |
263 | 11605 | return pair.key(); |
264 | |
} |
265 | |
|
266 | |
V value() { |
267 | 7455 | return pair.value(); |
268 | |
} |
269 | |
} |
270 | |
} |