]>
Commit | Line | Data |
---|---|---|
f911ba98 TT |
1 | /* HashMap.java -- a class providing a basic hashtable data structure, |
2 | mapping Object --> Object | |
3 | Copyright (C) 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc. | |
4 | ||
5 | This file is part of GNU Classpath. | |
6 | ||
7 | GNU Classpath is free software; you can redistribute it and/or modify | |
8 | it under the terms of the GNU General Public License as published by | |
9 | the Free Software Foundation; either version 2, or (at your option) | |
10 | any later version. | |
11 | ||
12 | GNU Classpath is distributed in the hope that it will be useful, but | |
13 | WITHOUT ANY WARRANTY; without even the implied warranty of | |
14 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
15 | General Public License for more details. | |
16 | ||
17 | You should have received a copy of the GNU General Public License | |
18 | along with GNU Classpath; see the file COPYING. If not, write to the | |
19 | Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA | |
20 | 02110-1301 USA. | |
21 | ||
22 | Linking this library statically or dynamically with other modules is | |
23 | making a combined work based on this library. Thus, the terms and | |
24 | conditions of the GNU General Public License cover the whole | |
25 | combination. | |
26 | ||
27 | As a special exception, the copyright holders of this library give you | |
28 | permission to link this library with independent modules to produce an | |
29 | executable, regardless of the license terms of these independent | |
30 | modules, and to copy and distribute the resulting executable under | |
31 | terms of your choice, provided that you also meet, for each linked | |
32 | independent module, the terms and conditions of the license of that | |
33 | module. An independent module is a module which is not derived from | |
34 | or based on this library. If you modify this library, you may extend | |
35 | this exception to your version of the library, but you are not | |
36 | obligated to do so. If you do not wish to do so, delete this | |
37 | exception statement from your version. */ | |
38 | ||
39 | ||
40 | package java.util; | |
41 | ||
42 | import java.io.IOException; | |
43 | import java.io.ObjectInputStream; | |
44 | import java.io.ObjectOutputStream; | |
45 | import java.io.Serializable; | |
46 | ||
47 | // NOTE: This implementation is very similar to that of Hashtable. If you fix | |
48 | // a bug in here, chances are you should make a similar change to the Hashtable | |
49 | // code. | |
50 | ||
51 | // NOTE: This implementation has some nasty coding style in order to | |
52 | // support LinkedHashMap, which extends this. | |
53 | ||
54 | /** | |
55 | * This class provides a hashtable-backed implementation of the | |
56 | * Map interface. | |
57 | * <p> | |
58 | * | |
59 | * It uses a hash-bucket approach; that is, hash collisions are handled | |
60 | * by linking the new node off of the pre-existing node (or list of | |
61 | * nodes). In this manner, techniques such as linear probing (which | |
62 | * can cause primary clustering) and rehashing (which does not fit very | |
63 | * well with Java's method of precomputing hash codes) are avoided. | |
64 | * <p> | |
65 | * | |
66 | * Under ideal circumstances (no collisions), HashMap offers O(1) | |
67 | * performance on most operations (<code>containsValue()</code> is, | |
68 | * of course, O(n)). In the worst case (all keys map to the same | |
69 | * hash code -- very unlikely), most operations are O(n). | |
70 | * <p> | |
71 | * | |
72 | * HashMap is part of the JDK1.2 Collections API. It differs from | |
73 | * Hashtable in that it accepts the null key and null values, and it | |
74 | * does not support "Enumeration views." Also, it is not synchronized; | |
75 | * if you plan to use it in multiple threads, consider using:<br> | |
76 | * <code>Map m = Collections.synchronizedMap(new HashMap(...));</code> | |
77 | * <p> | |
78 | * | |
79 | * The iterators are <i>fail-fast</i>, meaning that any structural | |
80 | * modification, except for <code>remove()</code> called on the iterator | |
81 | * itself, cause the iterator to throw a | |
82 | * <code>ConcurrentModificationException</code> rather than exhibit | |
83 | * non-deterministic behavior. | |
84 | * | |
85 | * @author Jon Zeppieri | |
86 | * @author Jochen Hoenicke | |
87 | * @author Bryce McKinlay | |
88 | * @author Eric Blake (ebb9@email.byu.edu) | |
89 | * @see Object#hashCode() | |
90 | * @see Collection | |
91 | * @see Map | |
92 | * @see TreeMap | |
93 | * @see LinkedHashMap | |
94 | * @see IdentityHashMap | |
95 | * @see Hashtable | |
96 | * @since 1.2 | |
97 | * @status updated to 1.4 | |
98 | */ | |
99 | public class HashMap extends AbstractMap | |
100 | implements Map, Cloneable, Serializable | |
101 | { | |
102 | /** | |
103 | * Default number of buckets. This is the value the JDK 1.3 uses. Some | |
104 | * early documentation specified this value as 101. That is incorrect. | |
105 | * Package visible for use by HashSet. | |
106 | */ | |
107 | static final int DEFAULT_CAPACITY = 11; | |
108 | ||
109 | /** | |
110 | * The default load factor; this is explicitly specified by the spec. | |
111 | * Package visible for use by HashSet. | |
112 | */ | |
113 | static final float DEFAULT_LOAD_FACTOR = 0.75f; | |
114 | ||
115 | /** | |
116 | * Compatible with JDK 1.2. | |
117 | */ | |
118 | private static final long serialVersionUID = 362498820763181265L; | |
119 | ||
120 | /** | |
121 | * The rounded product of the capacity and the load factor; when the number | |
122 | * of elements exceeds the threshold, the HashMap calls | |
123 | * <code>rehash()</code>. | |
124 | * @serial the threshold for rehashing | |
125 | */ | |
126 | private int threshold; | |
127 | ||
128 | /** | |
129 | * Load factor of this HashMap: used in computing the threshold. | |
130 | * Package visible for use by HashSet. | |
131 | * @serial the load factor | |
132 | */ | |
133 | final float loadFactor; | |
134 | ||
135 | /** | |
136 | * Array containing the actual key-value mappings. | |
137 | * Package visible for use by nested and subclasses. | |
138 | */ | |
139 | transient HashEntry[] buckets; | |
140 | ||
141 | /** | |
142 | * Counts the number of modifications this HashMap has undergone, used | |
143 | * by Iterators to know when to throw ConcurrentModificationExceptions. | |
144 | * Package visible for use by nested and subclasses. | |
145 | */ | |
146 | transient int modCount; | |
147 | ||
148 | /** | |
149 | * The size of this HashMap: denotes the number of key-value pairs. | |
150 | * Package visible for use by nested and subclasses. | |
151 | */ | |
152 | transient int size; | |
153 | ||
154 | /** | |
155 | * The cache for {@link #entrySet()}. | |
156 | */ | |
157 | private transient Set entries; | |
158 | ||
159 | /** | |
160 | * Class to represent an entry in the hash table. Holds a single key-value | |
161 | * pair. Package visible for use by subclass. | |
162 | * | |
163 | * @author Eric Blake (ebb9@email.byu.edu) | |
164 | */ | |
165 | static class HashEntry extends AbstractMap.BasicMapEntry | |
166 | { | |
167 | /** | |
168 | * The next entry in the linked list. Package visible for use by subclass. | |
169 | */ | |
170 | HashEntry next; | |
171 | ||
172 | /** | |
173 | * Simple constructor. | |
174 | * @param key the key | |
175 | * @param value the value | |
176 | */ | |
177 | HashEntry(Object key, Object value) | |
178 | { | |
179 | super(key, value); | |
180 | } | |
181 | ||
182 | /** | |
183 | * Called when this entry is accessed via {@link #put(Object, Object)}. | |
184 | * This version does nothing, but in LinkedHashMap, it must do some | |
185 | * bookkeeping for access-traversal mode. | |
186 | */ | |
187 | void access() | |
188 | { | |
189 | } | |
190 | ||
191 | /** | |
192 | * Called when this entry is removed from the map. This version simply | |
193 | * returns the value, but in LinkedHashMap, it must also do bookkeeping. | |
194 | * | |
195 | * @return the value of this key as it is removed | |
196 | */ | |
197 | Object cleanup() | |
198 | { | |
199 | return value; | |
200 | } | |
201 | } | |
202 | ||
203 | /** | |
204 | * Construct a new HashMap with the default capacity (11) and the default | |
205 | * load factor (0.75). | |
206 | */ | |
207 | public HashMap() | |
208 | { | |
209 | this(DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR); | |
210 | } | |
211 | ||
212 | /** | |
213 | * Construct a new HashMap from the given Map, with initial capacity | |
214 | * the greater of the size of <code>m</code> or the default of 11. | |
215 | * <p> | |
216 | * | |
217 | * Every element in Map m will be put into this new HashMap. | |
218 | * | |
219 | * @param m a Map whose key / value pairs will be put into the new HashMap. | |
220 | * <b>NOTE: key / value pairs are not cloned in this constructor.</b> | |
221 | * @throws NullPointerException if m is null | |
222 | */ | |
223 | public HashMap(Map m) | |
224 | { | |
225 | this(Math.max(m.size() * 2, DEFAULT_CAPACITY), DEFAULT_LOAD_FACTOR); | |
226 | putAll(m); | |
227 | } | |
228 | ||
229 | /** | |
230 | * Construct a new HashMap with a specific inital capacity and | |
231 | * default load factor of 0.75. | |
232 | * | |
233 | * @param initialCapacity the initial capacity of this HashMap (>=0) | |
234 | * @throws IllegalArgumentException if (initialCapacity < 0) | |
235 | */ | |
236 | public HashMap(int initialCapacity) | |
237 | { | |
238 | this(initialCapacity, DEFAULT_LOAD_FACTOR); | |
239 | } | |
240 | ||
241 | /** | |
242 | * Construct a new HashMap with a specific inital capacity and load factor. | |
243 | * | |
244 | * @param initialCapacity the initial capacity (>=0) | |
245 | * @param loadFactor the load factor (> 0, not NaN) | |
246 | * @throws IllegalArgumentException if (initialCapacity < 0) || | |
247 | * ! (loadFactor > 0.0) | |
248 | */ | |
249 | public HashMap(int initialCapacity, float loadFactor) | |
250 | { | |
251 | if (initialCapacity < 0) | |
252 | throw new IllegalArgumentException("Illegal Capacity: " | |
253 | + initialCapacity); | |
254 | if (! (loadFactor > 0)) // check for NaN too | |
255 | throw new IllegalArgumentException("Illegal Load: " + loadFactor); | |
256 | ||
257 | if (initialCapacity == 0) | |
258 | initialCapacity = 1; | |
259 | buckets = new HashEntry[initialCapacity]; | |
260 | this.loadFactor = loadFactor; | |
261 | threshold = (int) (initialCapacity * loadFactor); | |
262 | } | |
263 | ||
264 | /** | |
265 | * Returns the number of kay-value mappings currently in this Map. | |
266 | * | |
267 | * @return the size | |
268 | */ | |
269 | public int size() | |
270 | { | |
271 | return size; | |
272 | } | |
273 | ||
274 | /** | |
275 | * Returns true if there are no key-value mappings currently in this Map. | |
276 | * | |
277 | * @return <code>size() == 0</code> | |
278 | */ | |
279 | public boolean isEmpty() | |
280 | { | |
281 | return size == 0; | |
282 | } | |
283 | ||
284 | /** | |
285 | * Return the value in this HashMap associated with the supplied key, | |
286 | * or <code>null</code> if the key maps to nothing. NOTE: Since the value | |
287 | * could also be null, you must use containsKey to see if this key | |
288 | * actually maps to something. | |
289 | * | |
290 | * @param key the key for which to fetch an associated value | |
291 | * @return what the key maps to, if present | |
292 | * @see #put(Object, Object) | |
293 | * @see #containsKey(Object) | |
294 | */ | |
295 | public Object get(Object key) | |
296 | { | |
297 | int idx = hash(key); | |
298 | HashEntry e = buckets[idx]; | |
299 | while (e != null) | |
300 | { | |
301 | if (equals(key, e.key)) | |
302 | return e.value; | |
303 | e = e.next; | |
304 | } | |
305 | return null; | |
306 | } | |
307 | ||
308 | /** | |
309 | * Returns true if the supplied object <code>equals()</code> a key | |
310 | * in this HashMap. | |
311 | * | |
312 | * @param key the key to search for in this HashMap | |
313 | * @return true if the key is in the table | |
314 | * @see #containsValue(Object) | |
315 | */ | |
316 | public boolean containsKey(Object key) | |
317 | { | |
318 | int idx = hash(key); | |
319 | HashEntry e = buckets[idx]; | |
320 | while (e != null) | |
321 | { | |
322 | if (equals(key, e.key)) | |
323 | return true; | |
324 | e = e.next; | |
325 | } | |
326 | return false; | |
327 | } | |
328 | ||
329 | /** | |
330 | * Puts the supplied value into the Map, mapped by the supplied key. | |
331 | * The value may be retrieved by any object which <code>equals()</code> | |
332 | * this key. NOTE: Since the prior value could also be null, you must | |
333 | * first use containsKey if you want to see if you are replacing the | |
334 | * key's mapping. | |
335 | * | |
336 | * @param key the key used to locate the value | |
337 | * @param value the value to be stored in the HashMap | |
338 | * @return the prior mapping of the key, or null if there was none | |
339 | * @see #get(Object) | |
340 | * @see Object#equals(Object) | |
341 | */ | |
342 | public Object put(Object key, Object value) | |
343 | { | |
344 | int idx = hash(key); | |
345 | HashEntry e = buckets[idx]; | |
346 | ||
347 | while (e != null) | |
348 | { | |
349 | if (equals(key, e.key)) | |
350 | { | |
351 | e.access(); // Must call this for bookkeeping in LinkedHashMap. | |
352 | Object r = e.value; | |
353 | e.value = value; | |
354 | return r; | |
355 | } | |
356 | else | |
357 | e = e.next; | |
358 | } | |
359 | ||
360 | // At this point, we know we need to add a new entry. | |
361 | modCount++; | |
362 | if (++size > threshold) | |
363 | { | |
364 | rehash(); | |
365 | // Need a new hash value to suit the bigger table. | |
366 | idx = hash(key); | |
367 | } | |
368 | ||
369 | // LinkedHashMap cannot override put(), hence this call. | |
370 | addEntry(key, value, idx, true); | |
371 | return null; | |
372 | } | |
373 | ||
374 | /** | |
375 | * Copies all elements of the given map into this hashtable. If this table | |
376 | * already has a mapping for a key, the new mapping replaces the current | |
377 | * one. | |
378 | * | |
379 | * @param m the map to be hashed into this | |
380 | */ | |
381 | public void putAll(Map m) | |
382 | { | |
383 | Iterator itr = m.entrySet().iterator(); | |
384 | while (itr.hasNext()) | |
385 | { | |
386 | Map.Entry e = (Map.Entry) itr.next(); | |
387 | // Optimize in case the Entry is one of our own. | |
388 | if (e instanceof AbstractMap.BasicMapEntry) | |
389 | { | |
390 | AbstractMap.BasicMapEntry entry = (AbstractMap.BasicMapEntry) e; | |
391 | put(entry.key, entry.value); | |
392 | } | |
393 | else | |
394 | put(e.getKey(), e.getValue()); | |
395 | } | |
396 | } | |
397 | ||
398 | /** | |
399 | * Removes from the HashMap and returns the value which is mapped by the | |
400 | * supplied key. If the key maps to nothing, then the HashMap remains | |
401 | * unchanged, and <code>null</code> is returned. NOTE: Since the value | |
402 | * could also be null, you must use containsKey to see if you are | |
403 | * actually removing a mapping. | |
404 | * | |
405 | * @param key the key used to locate the value to remove | |
406 | * @return whatever the key mapped to, if present | |
407 | */ | |
408 | public Object remove(Object key) | |
409 | { | |
410 | int idx = hash(key); | |
411 | HashEntry e = buckets[idx]; | |
412 | HashEntry last = null; | |
413 | ||
414 | while (e != null) | |
415 | { | |
416 | if (equals(key, e.key)) | |
417 | { | |
418 | modCount++; | |
419 | if (last == null) | |
420 | buckets[idx] = e.next; | |
421 | else | |
422 | last.next = e.next; | |
423 | size--; | |
424 | // Method call necessary for LinkedHashMap to work correctly. | |
425 | return e.cleanup(); | |
426 | } | |
427 | last = e; | |
428 | e = e.next; | |
429 | } | |
430 | return null; | |
431 | } | |
432 | ||
433 | /** | |
434 | * Clears the Map so it has no keys. This is O(1). | |
435 | */ | |
436 | public void clear() | |
437 | { | |
438 | if (size != 0) | |
439 | { | |
440 | modCount++; | |
441 | Arrays.fill(buckets, null); | |
442 | size = 0; | |
443 | } | |
444 | } | |
445 | ||
446 | /** | |
447 | * Returns true if this HashMap contains a value <code>o</code>, such that | |
448 | * <code>o.equals(value)</code>. | |
449 | * | |
450 | * @param value the value to search for in this HashMap | |
451 | * @return true if at least one key maps to the value | |
8f523f3a | 452 | * @see #containsKey(Object) |
f911ba98 TT |
453 | */ |
454 | public boolean containsValue(Object value) | |
455 | { | |
456 | for (int i = buckets.length - 1; i >= 0; i--) | |
457 | { | |
458 | HashEntry e = buckets[i]; | |
459 | while (e != null) | |
460 | { | |
461 | if (equals(value, e.value)) | |
462 | return true; | |
463 | e = e.next; | |
464 | } | |
465 | } | |
466 | return false; | |
467 | } | |
468 | ||
469 | /** | |
470 | * Returns a shallow clone of this HashMap. The Map itself is cloned, | |
471 | * but its contents are not. This is O(n). | |
472 | * | |
473 | * @return the clone | |
474 | */ | |
475 | public Object clone() | |
476 | { | |
477 | HashMap copy = null; | |
478 | try | |
479 | { | |
480 | copy = (HashMap) super.clone(); | |
481 | } | |
482 | catch (CloneNotSupportedException x) | |
483 | { | |
484 | // This is impossible. | |
485 | } | |
486 | copy.buckets = new HashEntry[buckets.length]; | |
487 | copy.putAllInternal(this); | |
488 | // Clear the entry cache. AbstractMap.clone() does the others. | |
489 | copy.entries = null; | |
490 | return copy; | |
491 | } | |
492 | ||
493 | /** | |
494 | * Returns a "set view" of this HashMap's keys. The set is backed by the | |
495 | * HashMap, so changes in one show up in the other. The set supports | |
496 | * element removal, but not element addition. | |
497 | * | |
498 | * @return a set view of the keys | |
499 | * @see #values() | |
500 | * @see #entrySet() | |
501 | */ | |
502 | public Set keySet() | |
503 | { | |
504 | if (keys == null) | |
505 | // Create an AbstractSet with custom implementations of those methods | |
506 | // that can be overridden easily and efficiently. | |
507 | keys = new AbstractSet() | |
508 | { | |
509 | public int size() | |
510 | { | |
511 | return size; | |
512 | } | |
513 | ||
514 | public Iterator iterator() | |
515 | { | |
516 | // Cannot create the iterator directly, because of LinkedHashMap. | |
517 | return HashMap.this.iterator(KEYS); | |
518 | } | |
519 | ||
520 | public void clear() | |
521 | { | |
522 | HashMap.this.clear(); | |
523 | } | |
524 | ||
525 | public boolean contains(Object o) | |
526 | { | |
527 | return containsKey(o); | |
528 | } | |
529 | ||
530 | public boolean remove(Object o) | |
531 | { | |
532 | // Test against the size of the HashMap to determine if anything | |
533 | // really got removed. This is necessary because the return value | |
534 | // of HashMap.remove() is ambiguous in the null case. | |
535 | int oldsize = size; | |
536 | HashMap.this.remove(o); | |
537 | return oldsize != size; | |
538 | } | |
539 | }; | |
540 | return keys; | |
541 | } | |
542 | ||
543 | /** | |
544 | * Returns a "collection view" (or "bag view") of this HashMap's values. | |
545 | * The collection is backed by the HashMap, so changes in one show up | |
546 | * in the other. The collection supports element removal, but not element | |
547 | * addition. | |
548 | * | |
549 | * @return a bag view of the values | |
550 | * @see #keySet() | |
551 | * @see #entrySet() | |
552 | */ | |
553 | public Collection values() | |
554 | { | |
555 | if (values == null) | |
556 | // We don't bother overriding many of the optional methods, as doing so | |
557 | // wouldn't provide any significant performance advantage. | |
558 | values = new AbstractCollection() | |
559 | { | |
560 | public int size() | |
561 | { | |
562 | return size; | |
563 | } | |
564 | ||
565 | public Iterator iterator() | |
566 | { | |
567 | // Cannot create the iterator directly, because of LinkedHashMap. | |
568 | return HashMap.this.iterator(VALUES); | |
569 | } | |
570 | ||
571 | public void clear() | |
572 | { | |
573 | HashMap.this.clear(); | |
574 | } | |
575 | }; | |
576 | return values; | |
577 | } | |
578 | ||
579 | /** | |
580 | * Returns a "set view" of this HashMap's entries. The set is backed by | |
581 | * the HashMap, so changes in one show up in the other. The set supports | |
582 | * element removal, but not element addition.<p> | |
583 | * | |
584 | * Note that the iterators for all three views, from keySet(), entrySet(), | |
585 | * and values(), traverse the HashMap in the same sequence. | |
586 | * | |
587 | * @return a set view of the entries | |
588 | * @see #keySet() | |
589 | * @see #values() | |
590 | * @see Map.Entry | |
591 | */ | |
592 | public Set entrySet() | |
593 | { | |
594 | if (entries == null) | |
595 | // Create an AbstractSet with custom implementations of those methods | |
596 | // that can be overridden easily and efficiently. | |
597 | entries = new AbstractSet() | |
598 | { | |
599 | public int size() | |
600 | { | |
601 | return size; | |
602 | } | |
603 | ||
604 | public Iterator iterator() | |
605 | { | |
606 | // Cannot create the iterator directly, because of LinkedHashMap. | |
607 | return HashMap.this.iterator(ENTRIES); | |
608 | } | |
609 | ||
610 | public void clear() | |
611 | { | |
612 | HashMap.this.clear(); | |
613 | } | |
614 | ||
615 | public boolean contains(Object o) | |
616 | { | |
617 | return getEntry(o) != null; | |
618 | } | |
619 | ||
620 | public boolean remove(Object o) | |
621 | { | |
622 | HashEntry e = getEntry(o); | |
623 | if (e != null) | |
624 | { | |
625 | HashMap.this.remove(e.key); | |
626 | return true; | |
627 | } | |
628 | return false; | |
629 | } | |
630 | }; | |
631 | return entries; | |
632 | } | |
633 | ||
634 | /** | |
635 | * Helper method for put, that creates and adds a new Entry. This is | |
636 | * overridden in LinkedHashMap for bookkeeping purposes. | |
637 | * | |
638 | * @param key the key of the new Entry | |
639 | * @param value the value | |
640 | * @param idx the index in buckets where the new Entry belongs | |
641 | * @param callRemove whether to call the removeEldestEntry method | |
642 | * @see #put(Object, Object) | |
643 | */ | |
644 | void addEntry(Object key, Object value, int idx, boolean callRemove) | |
645 | { | |
646 | HashEntry e = new HashEntry(key, value); | |
647 | e.next = buckets[idx]; | |
648 | buckets[idx] = e; | |
649 | } | |
650 | ||
651 | /** | |
652 | * Helper method for entrySet(), which matches both key and value | |
653 | * simultaneously. | |
654 | * | |
655 | * @param o the entry to match | |
656 | * @return the matching entry, if found, or null | |
657 | * @see #entrySet() | |
658 | */ | |
659 | // Package visible, for use in nested classes. | |
660 | final HashEntry getEntry(Object o) | |
661 | { | |
662 | if (! (o instanceof Map.Entry)) | |
663 | return null; | |
664 | Map.Entry me = (Map.Entry) o; | |
665 | Object key = me.getKey(); | |
666 | int idx = hash(key); | |
667 | HashEntry e = buckets[idx]; | |
668 | while (e != null) | |
669 | { | |
670 | if (equals(e.key, key)) | |
671 | return equals(e.value, me.getValue()) ? e : null; | |
672 | e = e.next; | |
673 | } | |
674 | return null; | |
675 | } | |
676 | ||
677 | /** | |
678 | * Helper method that returns an index in the buckets array for `key' | |
679 | * based on its hashCode(). Package visible for use by subclasses. | |
680 | * | |
681 | * @param key the key | |
682 | * @return the bucket number | |
683 | */ | |
684 | final int hash(Object key) | |
685 | { | |
686 | return key == null ? 0 : Math.abs(key.hashCode() % buckets.length); | |
687 | } | |
688 | ||
689 | /** | |
690 | * Generates a parameterized iterator. Must be overrideable, since | |
691 | * LinkedHashMap iterates in a different order. | |
692 | * | |
693 | * @param type {@link #KEYS}, {@link #VALUES}, or {@link #ENTRIES} | |
694 | * @return the appropriate iterator | |
695 | */ | |
696 | Iterator iterator(int type) | |
697 | { | |
698 | return new HashIterator(type); | |
699 | } | |
700 | ||
701 | /** | |
702 | * A simplified, more efficient internal implementation of putAll(). clone() | |
703 | * should not call putAll or put, in order to be compatible with the JDK | |
704 | * implementation with respect to subclasses. | |
705 | * | |
706 | * @param m the map to initialize this from | |
707 | */ | |
708 | void putAllInternal(Map m) | |
709 | { | |
710 | Iterator itr = m.entrySet().iterator(); | |
711 | size = 0; | |
712 | while (itr.hasNext()) | |
713 | { | |
714 | size++; | |
715 | Map.Entry e = (Map.Entry) itr.next(); | |
716 | Object key = e.getKey(); | |
717 | int idx = hash(key); | |
718 | addEntry(key, e.getValue(), idx, false); | |
719 | } | |
720 | } | |
721 | ||
722 | /** | |
723 | * Increases the size of the HashMap and rehashes all keys to new | |
724 | * array indices; this is called when the addition of a new value | |
725 | * would cause size() > threshold. Note that the existing Entry | |
726 | * objects are reused in the new hash table. | |
727 | * | |
728 | * <p>This is not specified, but the new size is twice the current size | |
729 | * plus one; this number is not always prime, unfortunately. | |
730 | */ | |
731 | private void rehash() | |
732 | { | |
733 | HashEntry[] oldBuckets = buckets; | |
734 | ||
735 | int newcapacity = (buckets.length * 2) + 1; | |
736 | threshold = (int) (newcapacity * loadFactor); | |
737 | buckets = new HashEntry[newcapacity]; | |
738 | ||
739 | for (int i = oldBuckets.length - 1; i >= 0; i--) | |
740 | { | |
741 | HashEntry e = oldBuckets[i]; | |
742 | while (e != null) | |
743 | { | |
744 | int idx = hash(e.key); | |
745 | HashEntry dest = buckets[idx]; | |
746 | HashEntry next = e.next; | |
747 | e.next = buckets[idx]; | |
748 | buckets[idx] = e; | |
749 | e = next; | |
750 | } | |
751 | } | |
752 | } | |
753 | ||
754 | /** | |
755 | * Serializes this object to the given stream. | |
756 | * | |
757 | * @param s the stream to write to | |
758 | * @throws IOException if the underlying stream fails | |
759 | * @serialData the <i>capacity</i>(int) that is the length of the | |
760 | * bucket array, the <i>size</i>(int) of the hash map | |
761 | * are emitted first. They are followed by size entries, | |
762 | * each consisting of a key (Object) and a value (Object). | |
763 | */ | |
764 | private void writeObject(ObjectOutputStream s) throws IOException | |
765 | { | |
766 | // Write the threshold and loadFactor fields. | |
767 | s.defaultWriteObject(); | |
768 | ||
769 | s.writeInt(buckets.length); | |
770 | s.writeInt(size); | |
771 | // Avoid creating a wasted Set by creating the iterator directly. | |
772 | Iterator it = iterator(ENTRIES); | |
773 | while (it.hasNext()) | |
774 | { | |
775 | HashEntry entry = (HashEntry) it.next(); | |
776 | s.writeObject(entry.key); | |
777 | s.writeObject(entry.value); | |
778 | } | |
779 | } | |
780 | ||
781 | /** | |
782 | * Deserializes this object from the given stream. | |
783 | * | |
784 | * @param s the stream to read from | |
785 | * @throws ClassNotFoundException if the underlying stream fails | |
786 | * @throws IOException if the underlying stream fails | |
787 | * @serialData the <i>capacity</i>(int) that is the length of the | |
788 | * bucket array, the <i>size</i>(int) of the hash map | |
789 | * are emitted first. They are followed by size entries, | |
790 | * each consisting of a key (Object) and a value (Object). | |
791 | */ | |
792 | private void readObject(ObjectInputStream s) | |
793 | throws IOException, ClassNotFoundException | |
794 | { | |
795 | // Read the threshold and loadFactor fields. | |
796 | s.defaultReadObject(); | |
797 | ||
798 | // Read and use capacity, followed by key/value pairs. | |
799 | buckets = new HashEntry[s.readInt()]; | |
800 | int len = s.readInt(); | |
801 | size = len; | |
802 | while (len-- > 0) | |
803 | { | |
804 | Object key = s.readObject(); | |
805 | addEntry(key, s.readObject(), hash(key), false); | |
806 | } | |
807 | } | |
808 | ||
809 | /** | |
810 | * Iterate over HashMap's entries. | |
811 | * This implementation is parameterized to give a sequential view of | |
812 | * keys, values, or entries. | |
813 | * | |
814 | * @author Jon Zeppieri | |
815 | */ | |
816 | private final class HashIterator implements Iterator | |
817 | { | |
818 | /** | |
819 | * The type of this Iterator: {@link #KEYS}, {@link #VALUES}, | |
820 | * or {@link #ENTRIES}. | |
821 | */ | |
822 | private final int type; | |
823 | /** | |
824 | * The number of modifications to the backing HashMap that we know about. | |
825 | */ | |
826 | private int knownMod = modCount; | |
827 | /** The number of elements remaining to be returned by next(). */ | |
828 | private int count = size; | |
829 | /** Current index in the physical hash table. */ | |
830 | private int idx = buckets.length; | |
831 | /** The last Entry returned by a next() call. */ | |
832 | private HashEntry last; | |
833 | /** | |
834 | * The next entry that should be returned by next(). It is set to something | |
835 | * if we're iterating through a bucket that contains multiple linked | |
836 | * entries. It is null if next() needs to find a new bucket. | |
837 | */ | |
838 | private HashEntry next; | |
839 | ||
840 | /** | |
841 | * Construct a new HashIterator with the supplied type. | |
842 | * @param type {@link #KEYS}, {@link #VALUES}, or {@link #ENTRIES} | |
843 | */ | |
844 | HashIterator(int type) | |
845 | { | |
846 | this.type = type; | |
847 | } | |
848 | ||
849 | /** | |
850 | * Returns true if the Iterator has more elements. | |
851 | * @return true if there are more elements | |
f911ba98 TT |
852 | */ |
853 | public boolean hasNext() | |
854 | { | |
f911ba98 TT |
855 | return count > 0; |
856 | } | |
857 | ||
858 | /** | |
859 | * Returns the next element in the Iterator's sequential view. | |
860 | * @return the next element | |
861 | * @throws ConcurrentModificationException if the HashMap was modified | |
862 | * @throws NoSuchElementException if there is none | |
863 | */ | |
864 | public Object next() | |
865 | { | |
866 | if (knownMod != modCount) | |
867 | throw new ConcurrentModificationException(); | |
868 | if (count == 0) | |
869 | throw new NoSuchElementException(); | |
870 | count--; | |
871 | HashEntry e = next; | |
872 | ||
873 | while (e == null) | |
874 | e = buckets[--idx]; | |
875 | ||
876 | next = e.next; | |
877 | last = e; | |
878 | if (type == VALUES) | |
879 | return e.value; | |
880 | if (type == KEYS) | |
881 | return e.key; | |
882 | return e; | |
883 | } | |
884 | ||
885 | /** | |
886 | * Removes from the backing HashMap the last element which was fetched | |
887 | * with the <code>next()</code> method. | |
888 | * @throws ConcurrentModificationException if the HashMap was modified | |
889 | * @throws IllegalStateException if called when there is no last element | |
890 | */ | |
891 | public void remove() | |
892 | { | |
893 | if (knownMod != modCount) | |
894 | throw new ConcurrentModificationException(); | |
895 | if (last == null) | |
896 | throw new IllegalStateException(); | |
897 | ||
898 | HashMap.this.remove(last.key); | |
899 | last = null; | |
900 | knownMod++; | |
901 | } | |
902 | } | |
903 | } |