1 | /* |
2 | * #! |
3 | * Ontopia Engine |
4 | * #- |
5 | * Copyright (C) 2001 - 2013 The Ontopia Project |
6 | * #- |
7 | * Licensed under the Apache License, Version 2.0 (the "License"); |
8 | * you may not use this file except in compliance with the License. |
9 | * You may obtain a copy of the License at |
10 | * |
11 | * http://www.apache.org/licenses/LICENSE-2.0 |
12 | * |
13 | * Unless required by applicable law or agreed to in writing, software |
14 | * distributed under the License is distributed on an "AS IS" BASIS, |
15 | * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
16 | * See the License for the specific language governing permissions and |
17 | * limitations under the License. |
18 | * !# |
19 | */ |
20 | |
21 | sclass CompactHashMap<K, V> extends AbstractMap<K, V> { |
22 | final static int INITIAL_SIZE = 0; |
23 | final static double LOAD_FACTOR = 0.6; |
24 | |
25 | // This object is used to represent null, should clients use that as |
26 | final static Object nullObject = new Object(); |
27 | |
28 | /** |
29 | * When a key is deleted this object is put into the hashtable in |
30 | * its place, so that other entries with the same key (collisions) |
31 | * further down the hashtable are not lost after we delete an object |
32 | * in the collision chain. |
33 | */ |
34 | final static Object deletedObject = new Object(); |
35 | int elements; |
36 | int freecells; |
37 | O[] table; // key, value, key, value, ... |
38 | //int modCount; |
39 | |
40 | *() { |
41 | this(INITIAL_SIZE); |
42 | } |
43 | |
44 | *(int size) { |
45 | table = size == 0 ? null : new O[size*2]; |
46 | elements = 0; |
47 | freecells = tableSize(); |
48 | //modCount = 0; |
49 | } |
50 | |
51 | // ===== MAP IMPLEMENTATION ============================================= |
52 | |
53 | /** |
54 | * Returns the number of key/value mappings in this map. |
55 | */ |
56 | public synchronized int size() { |
57 | return elements; |
58 | } |
59 | |
60 | /** |
61 | * Returns <tt>true</tt> if this map contains no mappings. |
62 | */ |
63 | public synchronized boolean isEmpty() { |
64 | return elements == 0; |
65 | } |
66 | |
67 | /** |
68 | * Removes all key/value mappings in the map. |
69 | */ |
70 | public synchronized void clear() { |
71 | elements = 0; |
72 | for (int ix = 0; ix < tableSize(); ix++) { |
73 | key(ix, null); |
74 | value(ix, null); |
75 | } |
76 | freecells = tableSize(); |
77 | //modCount++; |
78 | } |
79 | |
80 | /** |
81 | * Returns <tt>true</tt> if this map contains the specified key. |
82 | */ |
83 | public synchronized boolean containsKey(Object k) { |
84 | return key(findKeyIndex(k)) != null; |
85 | } |
86 | |
87 | /** |
88 | * Returns <tt>true</tt> if this map contains the specified value. |
89 | */ |
90 | public synchronized boolean containsValue(Object v) { |
91 | if (v == null) |
92 | v = (V)nullObject; |
93 | |
94 | for (int ix = 0; ix < tableSize(); ix++) |
95 | if (value(ix) != null && value(ix).equals(v)) |
96 | return true; |
97 | |
98 | return false; |
99 | } |
100 | |
101 | /** |
102 | * Returns a read-only set view of the map's keys. |
103 | */ |
104 | public synchronized Set<Entry<K, V>> entrySet() { |
105 | throw new UnsupportedOperationException(); |
106 | } |
107 | |
108 | /** |
109 | * Removes the mapping with key k, if there is one, and returns its |
110 | * value, if there is one, and null if there is none. |
111 | */ |
112 | public synchronized V remove(Object k) { |
113 | int index = findKeyIndex(k); |
114 | |
115 | // we found the right position, now do the removal |
116 | if (key(index) != null) { |
117 | // we found the object |
118 | |
119 | // same problem here as with put |
120 | V v = value(index); |
121 | key(index, deletedObject); |
122 | value(index, deletedObject); |
123 | //modCount++; |
124 | elements--; |
125 | return v; |
126 | } else |
127 | // we did not find the key |
128 | return null; |
129 | } |
130 | |
131 | /** |
132 | * Adds the specified mapping to this map, returning the old value for |
133 | * the mapping, if there was one. |
134 | */ |
135 | public synchronized V put(K k, V v) { |
136 | if (k == null) |
137 | k = (K)nullObject; |
138 | |
139 | int hash = k.hashCode(); |
140 | int index = 0; |
141 | int deletedix = -1; |
142 | |
143 | if (table != null) { |
144 | index = (hash & 0x7FFFFFFF) % tableSize(); |
145 | int offset = 1; |
146 | |
147 | // search for the key (continue while !null and !this key) |
148 | while (key(index) != null && |
149 | !(key(index).hashCode() == hash && |
150 | key(index).equals(k))) { |
151 | |
152 | // if there's a deleted mapping here we can put this mapping here, |
153 | // provided it's not in here somewhere else already |
154 | if (key(index) == deletedObject) |
155 | deletedix = index; |
156 | |
157 | index = ((index + offset) & 0x7FFFFFFF) % tableSize(); |
158 | offset = offset*2 + 1; |
159 | |
160 | if (offset == -1) |
161 | offset = 2; |
162 | } |
163 | } |
164 | |
165 | if (key(index) == null) { // wasn't present already |
166 | elements++; |
167 | //modCount++; |
168 | |
169 | if (table == null) { |
170 | table = new O[2]; |
171 | key(0, k); |
172 | value(0, v); |
173 | null; |
174 | } |
175 | |
176 | if (deletedix != -1) // reusing a deleted cell |
177 | index = deletedix; |
178 | else |
179 | freecells--; |
180 | |
181 | key(index, k); |
182 | value(index, v); |
183 | |
184 | // rehash with increased capacity |
185 | if (1 - (freecells / (double) tableSize()) > LOAD_FACTOR) |
186 | rehash(tableSize()*2 + 1); |
187 | return null; |
188 | } else { // was there already |
189 | //modCount++; |
190 | V oldv = value(index); |
191 | value(index, v); |
192 | return oldv; |
193 | } |
194 | } |
195 | |
196 | /** |
197 | * INTERNAL: Rehashes the hashmap to a bigger size. |
198 | */ |
199 | void rehash(int newCapacity) { |
200 | int oldCapacity = tableSize(); |
201 | O[] newTable = newCapacity == 0 ? null : new O[newCapacity*2]; |
202 | |
203 | for (int ix = 0; ix < oldCapacity; ix++) { |
204 | Object k = key(ix); |
205 | if (k == null || k == deletedObject) |
206 | continue; |
207 | |
208 | int hash = k.hashCode(); |
209 | int index = (hash & 0x7FFFFFFF) % newCapacity; |
210 | int offset = 1; |
211 | |
212 | // search for the key |
213 | while(newTable[index*2] != null) { // no need to test for duplicates |
214 | index = ((index + offset) & 0x7FFFFFFF) % newCapacity; |
215 | offset = offset*2 + 1; |
216 | |
217 | if (offset == -1) |
218 | offset = 2; |
219 | } |
220 | |
221 | newTable[index*2] = k; |
222 | newTable[index*2+1] = value(ix); |
223 | } |
224 | |
225 | table = newTable; |
226 | freecells = tableSize() - elements; |
227 | } |
228 | |
229 | /** |
230 | * Returns the value for the key k, if there is one, and null if |
231 | * there is none. |
232 | */ |
233 | public synchronized V get(O k) { |
234 | return value(findKeyIndex(k)); |
235 | } |
236 | |
237 | /** |
238 | * Returns a virtual read-only collection containing all the values |
239 | * in the map. |
240 | */ |
241 | public synchronized Collection<V> values() { |
242 | return new ValueCollection(); |
243 | } |
244 | |
245 | /** |
246 | * Returns a virtual read-only set of all the keys in the map. |
247 | */ |
248 | public synchronized Set<K> keySet() { |
249 | return new KeySet(); |
250 | } |
251 | |
252 | // --- Internal utilities |
253 | |
254 | final int findKeyIndex(O k) { |
255 | if (k == null) |
256 | k = nullObject; |
257 | |
258 | if (table == null) ret 0; |
259 | int hash = k.hashCode(); |
260 | int index = (hash & 0x7FFFFFFF) % tableSize(); |
261 | int offset = 1; |
262 | |
263 | // search for the key (continue while !null and !this key) |
264 | while(key(index) != null && |
265 | !(key(index).hashCode() == hash && |
266 | key(index).equals(k))) { |
267 | index = ((index + offset) & 0x7FFFFFFF) % tableSize(); |
268 | offset = offset*2 + 1; |
269 | |
270 | if (offset == -1) |
271 | offset = 2; |
272 | } |
273 | return index; |
274 | } |
275 | |
276 | // --- Key set |
277 | |
278 | class KeySet<K> extends AbstractSet<K> { |
279 | public synchronized int size() { |
280 | return elements; |
281 | } |
282 | |
283 | public synchronized boolean contains(Object k) { |
284 | return containsKey(k); |
285 | } |
286 | |
287 | public synchronized Iterator<K> iterator() { |
288 | return new KeyIterator(); |
289 | } |
290 | } |
291 | |
292 | class KeyIterator<K> implements Iterator<K> { |
293 | private int ix; |
294 | |
295 | private KeyIterator() { |
296 | // walk up to first value, so that hasNext() and next() return |
297 | // correct results |
298 | for (; ix < tableSize(); ix++) |
299 | if (value(ix) != null && key(ix) != deletedObject) |
300 | break; |
301 | } |
302 | |
303 | public synchronized boolean hasNext() { |
304 | return ix < tableSize(); |
305 | } |
306 | |
307 | public synchronized void remove() { |
308 | throw new UnsupportedOperationException("Collection is read-only"); |
309 | } |
310 | |
311 | public synchronized K next() { |
312 | if (ix >= tableSize()) |
313 | throw new NoSuchElementException(); |
314 | K key = (K) key(ix++); |
315 | |
316 | // walk up to next value |
317 | for (; ix < tableSize(); ix++) |
318 | if (key(ix) != null && key(ix) != deletedObject) |
319 | break; |
320 | |
321 | // ix now either points to next key, or outside array (if no next) |
322 | return key; |
323 | } |
324 | } |
325 | |
326 | // --- Value collection |
327 | |
328 | class ValueCollection<V> extends AbstractCollection<V> { |
329 | public synchronized int size() { |
330 | return elements; |
331 | } |
332 | |
333 | public synchronized Iterator<V> iterator() { |
334 | return new ValueIterator(); |
335 | } |
336 | |
337 | public synchronized boolean contains(Object v) { |
338 | return containsValue(v); |
339 | } |
340 | } |
341 | |
342 | class ValueIterator<V> implements Iterator<V> { |
343 | private int ix; |
344 | |
345 | private ValueIterator() { |
346 | // walk up to first value, so that hasNext() and next() return |
347 | // correct results |
348 | for (; ix < tableSize(); ix++) |
349 | if (value(ix) != null && value(ix) != deletedObject) |
350 | break; |
351 | } |
352 | |
353 | public synchronized boolean hasNext() { |
354 | return ix < tableSize(); |
355 | } |
356 | |
357 | public synchronized void remove() { |
358 | throw new UnsupportedOperationException("Collection is read-only"); |
359 | } |
360 | |
361 | public synchronized V next() { |
362 | if (ix >= tableSize()) |
363 | throw new NoSuchElementException(); |
364 | V value = (V) value(ix++); |
365 | |
366 | // walk up to next value |
367 | for (; ix < tableSize(); ix++) |
368 | if (value(ix) != null && value(ix) != deletedObject) |
369 | break; |
370 | |
371 | // ix now either points to next value, or outside array (if no next) |
372 | return value; |
373 | } |
374 | } |
375 | |
376 | K key(int i) { ret table == null ?: (K) table[i*2]; } |
377 | void key(int i, O key) { table[i*2] = key; } |
378 | V value(int i) { ret table == null ?: (V) table[i*2+1]; } |
379 | void value(int i, O value) { table[i*2+1] = value; } |
380 | |
381 | int tableSize() { ret table == null ? 0 : table.length/2; } |
382 | } |
Began life as a copy of #1031040
download show line numbers debug dex old transpilations
Travelled to 3 computer(s): bhatertpkbcr, mowyntqkapby, mqqgnosmbjvj
No comments. add comment
Snippet ID: | #1034066 |
Snippet name: | CompactHashMap v2 [using 0, 1, 3, ... cells, dev.] |
Eternal ID of this version: | #1034066/4 |
Text MD5: | bbba27e142c727f06ea212c03b2d5b26 |
Author: | stefan |
Category: | javax / collections |
Type: | JavaX fragment (include) |
Public (visible to everyone): | Yes |
Archived (hidden from active list): | No |
Created/modified: | 2022-01-20 02:07:07 |
Source code size: | 10077 bytes / 382 lines |
Pitched / IR pitched: | No / No |
Views / Downloads: | 59 / 72 |
Version history: | 3 change(s) |
Referenced in: | [show references] |