1 /*
2 * Copyright (c) 1997, 2010, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation. Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
25
26 package java.util;
27 import java.io.*;
28
29 /**
30 * Hash table based implementation of the <tt>Map</tt> interface. This
31 * implementation provides all of the optional map operations, and permits
32 * <tt>null</tt> values and the <tt>null</tt> key. (The <tt>HashMap</tt>
33 * class is roughly equivalent to <tt>Hashtable</tt>, except that it is
34 * unsynchronized and permits nulls.) This class makes no guarantees as to
35 * the order of the map; in particular, it does not guarantee that the order
36 * will remain constant over time.
37 *
38 * <p>This implementation provides constant-time performance for the basic
39 * operations (<tt>get</tt> and <tt>put</tt>), assuming the hash function
40 * disperses the elements properly among the buckets. Iteration over
41 * collection views requires time proportional to the "capacity" of the
42 * <tt>HashMap</tt> instance (the number of buckets) plus its size (the number
43 * of key-value mappings). Thus, it's very important not to set the initial
44 * capacity too high (or the load factor too low) if iteration performance is
45 * important.
46 *
47 * <p>An instance of <tt>HashMap</tt> has two parameters that affect its
48 * performance: <i>initial capacity</i> and <i>load factor</i>. The
49 * <i>capacity</i> is the number of buckets in the hash table, and the initial
50 * capacity is simply the capacity at the time the hash table is created. The
51 * <i>load factor</i> is a measure of how full the hash table is allowed to
52 * get before its capacity is automatically increased. When the number of
53 * entries in the hash table exceeds the product of the load factor and the
54 * current capacity, the hash table is <i>rehashed</i> (that is, internal data
55 * structures are rebuilt) so that the hash table has approximately twice the
56 * number of buckets.
57 *
58 * <p>As a general rule, the default load factor (.75) offers a good tradeoff
59 * between time and space costs. Higher values decrease the space overhead
60 * but increase the lookup cost (reflected in most of the operations of the
61 * <tt>HashMap</tt> class, including <tt>get</tt> and <tt>put</tt>). The
62 * expected number of entries in the map and its load factor should be taken
63 * into account when setting its initial capacity, so as to minimize the
64 * number of rehash operations. If the initial capacity is greater
65 * than the maximum number of entries divided by the load factor, no
66 * rehash operations will ever occur.
67 *
68 * <p>If many mappings are to be stored in a <tt>HashMap</tt> instance,
69 * creating it with a sufficiently large capacity will allow the mappings to
70 * be stored more efficiently than letting it perform automatic rehashing as
71 * needed to grow the table.
72 *
73 * <p><strong>Note that this implementation is not synchronized.</strong>
74 * If multiple threads access a hash map concurrently, and at least one of
75 * the threads modifies the map structurally, it <i>must</i> be
76 * synchronized externally. (A structural modification is any operation
77 * that adds or deletes one or more mappings; merely changing the value
78 * associated with a key that an instance already contains is not a
79 * structural modification.) This is typically accomplished by
80 * synchronizing on some object that naturally encapsulates the map.
81 *
82 * If no such object exists, the map should be "wrapped" using the
83 * {@link Collections#synchronizedMap Collections.synchronizedMap}
84 * method. This is best done at creation time, to prevent accidental
85 * unsynchronized access to the map:<pre>
86 * Map m = Collections.synchronizedMap(new HashMap(...));</pre>
87 *
88 * <p>The iterators returned by all of this class's "collection view methods"
89 * are <i>fail-fast</i>: if the map is structurally modified at any time after
90 * the iterator is created, in any way except through the iterator's own
91 * <tt>remove</tt> method, the iterator will throw a
92 * {@link ConcurrentModificationException}. Thus, in the face of concurrent
93 * modification, the iterator fails quickly and cleanly, rather than risking
94 * arbitrary, non-deterministic behavior at an undetermined time in the
95 * future.
96 *
97 * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
98 * as it is, generally speaking, impossible to make any hard guarantees in the
99 * presence of unsynchronized concurrent modification. Fail-fast iterators
100 * throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
101 * Therefore, it would be wrong to write a program that depended on this
102 * exception for its correctness: <i>the fail-fast behavior of iterators
103 * should be used only to detect bugs.</i>
104 *
105 * <p>This class is a member of the
106 * <a href="{@docRoot}/../technotes/guides/collections/index.html">
107 * Java Collections Framework</a>.
108 *
109 * @param <K> the type of keys maintained by this map
110 * @param <V> the type of mapped values
111 *
112 * @author Doug Lea
113 * @author Josh Bloch
114 * @author Arthur van Hoff
115 * @author Neal Gafter
116 * @see Object#hashCode()
117 * @see Collection
118 * @see Map
119 * @see TreeMap
120 * @see Hashtable
121 * @since 1.2
122 */
123
124 public class HashMap<K,V>
125 extends AbstractMap<K,V>
126 implements Map<K,V>, Cloneable, Serializable
127 {
128
129 /**
130 * The default initial capacity - MUST be a power of two.
131 */
132 static final int DEFAULT_INITIAL_CAPACITY = 16;
133
134 /**
135 * The maximum capacity, used if a higher value is implicitly specified
136 * by either of the constructors with arguments.
137 * MUST be a power of two <= 1<<30.
138 */
139 static final int MAXIMUM_CAPACITY = 1 << 30;
140
141 /**
142 * The load factor used when none specified in constructor.
143 */
144 static final float DEFAULT_LOAD_FACTOR = 0.75f;
145
146 /**
147 * The table, resized as necessary. Length MUST Always be a power of two.
148 */
149 transient Entry<K,V>[] table;
150
151 /**
152 * The number of key-value mappings contained in this map.
153 */
154 transient int size;
155
156 /**
157 * The next size value at which to resize (capacity * load factor).
158 * @serial
159 */
160 int threshold;
161
162 /**
163 * The load factor for the hash table.
164 *
165 * @serial
166 */
167 final float loadFactor;
168
169 /**
170 * The number of times this HashMap has been structurally modified
171 * Structural modifications are those that change the number of mappings in
172 * the HashMap or otherwise modify its internal structure (e.g.,
173 * rehash). This field is used to make iterators on Collection-views of
174 * the HashMap fail-fast. (See ConcurrentModificationException).
175 */
176 transient int modCount;
177
178 /**
179 * The default threshold of map capacity above which alternative hashing is
180 * used for String keys. Alternative hashing reduces the incidence of
181 * collisions due to weak hash code calculation for String keys.
182 * <p/>
183 * This value may be overridden by defining the system property
184 * {@code jdk.map.althashing.threshold}. A property value of {@code 1}
185 * forces alternative hashing to be used at all times whereas
186 * {@code -1} value ensures that alternative hashing is never used.
187 */
188 static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;
189
190 /**
191 * holds values which can't be initialized until after VM is booted.
192 */
193 private static class Holder {
194
195 /**
196 * Table capacity above which to switch to use alternative hashing.
197 */
198 static final int ALTERNATIVE_HASHING_THRESHOLD;
199
200 static {
201 String altThreshold = java.security.AccessController.doPrivileged(
202 new sun.security.action.GetPropertyAction(
203 "jdk.map.althashing.threshold"));
204
205 int threshold;
206 try {
207 threshold = (null != altThreshold)
208 ? Integer.parseInt(altThreshold)
209 : ALTERNATIVE_HASHING_THRESHOLD_DEFAULT;
210
211 // disable alternative hashing if -1
212 if (threshold == -1) {
213 threshold = Integer.MAX_VALUE;
214 }
215
216 if (threshold < 0) {
217 throw new IllegalArgumentException("value must be positive integer.");
218 }
219 } catch(IllegalArgumentException failed) {
220 throw new Error("Illegal value for 'jdk.map.althashing.threshold'", failed);
221 }
222
223 ALTERNATIVE_HASHING_THRESHOLD = threshold;
224 }
225 }
226
227 /**
228 * A randomizing value associated with this instance that is applied to
229 * hash code of keys to make hash collisions harder to find. If 0 then
230 * alternative hashing is disabled.
231 */
232 transient int hashSeed = 0;
233
234 /**
235 * Constructs an empty <tt>HashMap</tt> with the specified initial
236 * capacity and load factor.
237 *
238 * @param initialCapacity the initial capacity
239 * @param loadFactor the load factor
240 * @throws IllegalArgumentException if the initial capacity is negative
241 * or the load factor is nonpositive
242 */
243 public HashMap(int initialCapacity, float loadFactor) {
244 if (initialCapacity < 0)
245 throw new IllegalArgumentException("Illegal initial capacity: " +
246 initialCapacity);
247 if (initialCapacity > MAXIMUM_CAPACITY)
248 initialCapacity = MAXIMUM_CAPACITY;
249 if (loadFactor <= 0 || Float.isNaN(loadFactor))
250 throw new IllegalArgumentException("Illegal load factor: " +
251 loadFactor);
252
253 // Find a power of 2 >= initialCapacity
254 int capacity = (capacity = Integer.highestOneBit(initialCapacity)) != 0
255 ? capacity
256 : 1;
257 capacity <<= (Integer.bitCount(initialCapacity) > 1) ? 1 : 0;
258
259 this.loadFactor = loadFactor;
260 threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
261 table = new Entry[capacity];
262 initHashSeedAsNeeded(capacity);
263 init();
264 }
265
266 /**
267 * Constructs an empty <tt>HashMap</tt> with the specified initial
268 * capacity and the default load factor (0.75).
269 *
270 * @param initialCapacity the initial capacity.
271 * @throws IllegalArgumentException if the initial capacity is negative.
272 */
273 public HashMap(int initialCapacity) {
274 this(initialCapacity, DEFAULT_LOAD_FACTOR);
275 }
276
277 /**
278 * Constructs an empty <tt>HashMap</tt> with the default initial capacity
279 * (16) and the default load factor (0.75).
280 */
281 public HashMap() {
282 this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
283 }
284
285 /**
286 * Constructs a new <tt>HashMap</tt> with the same mappings as the
287 * specified <tt>Map</tt>. The <tt>HashMap</tt> is created with
288 * default load factor (0.75) and an initial capacity sufficient to
289 * hold the mappings in the specified <tt>Map</tt>.
290 *
291 * @param m the map whose mappings are to be placed in this map
292 * @throws NullPointerException if the specified map is null
293 */
294 public HashMap(Map<? extends K, ? extends V> m) {
295 this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
296 DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
297 putAllForCreate(m);
298 }
299
300 // internal utilities
301
302 /**
303 * Initialization hook for subclasses. This method is called
304 * in all constructors and pseudo-constructors (clone, readObject)
305 * after HashMap has been initialized but before any entries have
306 * been inserted. (In the absence of this method, readObject would
307 * require explicit knowledge of subclasses.)
308 */
309 void init() {
310 }
311
312 /**
313 * Initialize the hashing mask value. We defer initialization until we
314 * really need it.
315 */
316 final boolean initHashSeedAsNeeded(int capacity) {
317 boolean currentAltHashing = hashSeed != 0;
318 boolean useAltHashing = sun.misc.VM.isBooted() &&
319 (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
320 boolean switching = currentAltHashing ^ useAltHashing;
321 if (switching) {
322 hashSeed = useAltHashing
323 ? sun.misc.Hashing.randomHashSeed(this)
324 : 0;
325 }
326 return switching;
327 }
328
329 /**
330 * Retrieve object hash code and applies a supplemental hash function to the
331 * result hash, which defends against poor quality hash functions. This is
332 * critical because HashMap uses power-of-two length hash tables, that
333 * otherwise encounter collisions for hashCodes that do not differ
334 * in lower bits. Note: Null keys always map to hash 0, thus index 0.
335 */
336 final int hash(Object k) {
337 int h = hashSeed;
338 if (0 != h && k instanceof String) {
339 return sun.misc.Hashing.stringHash32((String) k);
340 }
341
342 h ^= k.hashCode();
343
344 // This function ensures that hashCodes that differ only by
345 // constant multiples at each bit position have a bounded
346 // number of collisions (approximately 8 at default load factor).
347 h ^= (h >>> 20) ^ (h >>> 12);
348 return h ^ (h >>> 7) ^ (h >>> 4);
349 }
350
351 /**
352 * Returns index for hash code h.
353 */
354 static int indexFor(int h, int length) {
355 return h & (length-1);
356 }
357
358 /**
359 * Returns the number of key-value mappings in this map.
360 *
361 * @return the number of key-value mappings in this map
362 */
363 public int size() {
364 return size;
365 }
366
367 /**
368 * Returns <tt>true</tt> if this map contains no key-value mappings.
369 *
370 * @return <tt>true</tt> if this map contains no key-value mappings
371 */
372 public boolean isEmpty() {
373 return size == 0;
374 }
375
376 /**
377 * Returns the value to which the specified key is mapped,
378 * or {@code null} if this map contains no mapping for the key.
379 *
380 * <p>More formally, if this map contains a mapping from a key
381 * {@code k} to a value {@code v} such that {@code (key==null ? k==null :
382 * key.equals(k))}, then this method returns {@code v}; otherwise
383 * it returns {@code null}. (There can be at most one such mapping.)
384 *
385 * <p>A return value of {@code null} does not <i>necessarily</i>
386 * indicate that the map contains no mapping for the key; it's also
387 * possible that the map explicitly maps the key to {@code null}.
388 * The {@link #containsKey containsKey} operation may be used to
389 * distinguish these two cases.
390 *
391 * @see #put(Object, Object)
392 */
393 public V get(Object key) {
394 if (key == null)
395 return getForNullKey();
396 Entry<K,V> entry = getEntry(key);
397
398 return null == entry ? null : entry.getValue();
399 }
400
401 /**
402 * Offloaded version of get() to look up null keys. Null keys map
403 * to index 0. This null case is split out into separate methods
404 * for the sake of performance in the two most commonly used
405 * operations (get and put), but incorporated with conditionals in
406 * others.
407 */
408 private V getForNullKey() {
409 for (Entry<K,V> e = table[0]; e != null; e = e.next) {
410 if (e.key == null)
411 return e.value;
412 }
413 return null;
414 }
415
416 /**
417 * Returns <tt>true</tt> if this map contains a mapping for the
418 * specified key.
419 *
420 * @param key The key whose presence in this map is to be tested
421 * @return <tt>true</tt> if this map contains a mapping for the specified
422 * key.
423 */
424 public boolean containsKey(Object key) {
425 return getEntry(key) != null;
426 }
427
428 /**
429 * Returns the entry associated with the specified key in the
430 * HashMap. Returns null if the HashMap contains no mapping
431 * for the key.
432 */
433 final Entry<K,V> getEntry(Object key) {
434 int hash = (key == null) ? 0 : hash(key);
435 for (Entry<K,V> e = table[indexFor(hash, table.length)];
436 e != null;
437 e = e.next) {
438 Object k;
439 if (e.hash == hash &&
440 ((k = e.key) == key || (key != null && key.equals(k))))
441 return e;
442 }
443 return null;
444 }
445
446
447 /**
448 * Associates the specified value with the specified key in this map.
449 * If the map previously contained a mapping for the key, the old
450 * value is replaced.
451 *
452 * @param key key with which the specified value is to be associated
453 * @param value value to be associated with the specified key
454 * @return the previous value associated with <tt>key</tt>, or
455 * <tt>null</tt> if there was no mapping for <tt>key</tt>.
456 * (A <tt>null</tt> return can also indicate that the map
457 * previously associated <tt>null</tt> with <tt>key</tt>.)
458 */
459 public V put(K key, V value) {
460 if (key == null)
461 return putForNullKey(value);
462 int hash = hash(key);
463 int i = indexFor(hash, table.length);
464 for (Entry<K,V> e = table[i]; e != null; e = e.next) {
465 Object k;
466 if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
467 V oldValue = e.value;
468 e.value = value;
469 e.recordAccess(this);
470 return oldValue;
471 }
472 }
473
474 modCount++;
475 addEntry(hash, key, value, i);
476 return null;
477 }
478
479 /**
480 * Offloaded version of put for null keys
481 */
482 private V putForNullKey(V value) {
483 for (Entry<K,V> e = table[0]; e != null; e = e.next) {
484 if (e.key == null) {
485 V oldValue = e.value;
486 e.value = value;
487 e.recordAccess(this);
488 return oldValue;
489 }
490 }
491 modCount++;
492 addEntry(0, null, value, 0);
493 return null;
494 }
495
496 /**
497 * This method is used instead of put by constructors and
498 * pseudoconstructors (clone, readObject). It does not resize the table,
499 * check for comodification, etc. It calls createEntry rather than
500 * addEntry.
501 */
502 private void putForCreate(K key, V value) {
503 int hash = null == key ? 0 : hash(key);
504 int i = indexFor(hash, table.length);
505
506 /**
507 * Look for preexisting entry for key. This will never happen for
508 * clone or deserialize. It will only happen for construction if the
509 * input Map is a sorted map whose ordering is inconsistent w/ equals.
510 */
511 for (Entry<K,V> e = table[i]; e != null; e = e.next) {
512 Object k;
513 if (e.hash == hash &&
514 ((k = e.key) == key || (key != null && key.equals(k)))) {
515 e.value = value;
516 return;
517 }
518 }
519
520 createEntry(hash, key, value, i);
521 }
522
523 private void putAllForCreate(Map<? extends K, ? extends V> m) {
524 for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
525 putForCreate(e.getKey(), e.getValue());
526 }
527
528 /**
529 * Rehashes the contents of this map into a new array with a
530 * larger capacity. This method is called automatically when the
531 * number of keys in this map reaches its threshold.
532 *
533 * If current capacity is MAXIMUM_CAPACITY, this method does not
534 * resize the map, but sets threshold to Integer.MAX_VALUE.
535 * This has the effect of preventing future calls.
536 *
537 * @param newCapacity the new capacity, MUST be a power of two;
538 * must be greater than current capacity unless current
539 * capacity is MAXIMUM_CAPACITY (in which case value
540 * is irrelevant).
541 */
542 void resize(int newCapacity) {
543 Entry[] oldTable = table;
544 int oldCapacity = oldTable.length;
545 if (oldCapacity == MAXIMUM_CAPACITY) {
546 threshold = Integer.MAX_VALUE;
547 return;
548 }
549
550 Entry[] newTable = new Entry[newCapacity];
551 transfer(newTable, initHashSeedAsNeeded(newCapacity));
552 table = newTable;
553 threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
554 }
555
556 /**
557 * Transfers all entries from current table to newTable.
558 */
559 void transfer(Entry[] newTable, boolean rehash) {
560 int newCapacity = newTable.length;
561 for (Entry<K,V> e : table) {
562 while(null != e) {
563 Entry<K,V> next = e.next;
564 if (rehash) {
565 e.hash = null == e.key ? 0 : hash(e.key);
566 }
567 int i = indexFor(e.hash, newCapacity);
568 e.next = newTable[i];
569 newTable[i] = e;
570 e = next;
571 }
572 }
573 }
574
575 /**
576 * Copies all of the mappings from the specified map to this map.
577 * These mappings will replace any mappings that this map had for
578 * any of the keys currently in the specified map.
579 *
580 * @param m mappings to be stored in this map
581 * @throws NullPointerException if the specified map is null
582 */
583 public void putAll(Map<? extends K, ? extends V> m) {
584 int numKeysToBeAdded = m.size();
585 if (numKeysToBeAdded == 0)
586 return;
587
588 /*
589 * Expand the map if the map if the number of mappings to be added
590 * is greater than or equal to threshold. This is conservative; the
591 * obvious condition is (m.size() + size) >= threshold, but this
592 * condition could result in a map with twice the appropriate capacity,
593 * if the keys to be added overlap with the keys already in this map.
594 * By using the conservative calculation, we subject ourself
595 * to at most one extra resize.
596 */
597 if (numKeysToBeAdded > threshold) {
598 int targetCapacity = (int)(numKeysToBeAdded / loadFactor + 1);
599 if (targetCapacity > MAXIMUM_CAPACITY)
600 targetCapacity = MAXIMUM_CAPACITY;
601 int newCapacity = table.length;
602 while (newCapacity < targetCapacity)
603 newCapacity <<= 1;
604 if (newCapacity > table.length)
605 resize(newCapacity);
606 }
607
608 for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
609 put(e.getKey(), e.getValue());
610 }
611
612 /**
613 * Removes the mapping for the specified key from this map if present.
614 *
615 * @param key key whose mapping is to be removed from the map
616 * @return the previous value associated with <tt>key</tt>, or
617 * <tt>null</tt> if there was no mapping for <tt>key</tt>.
618 * (A <tt>null</tt> return can also indicate that the map
619 * previously associated <tt>null</tt> with <tt>key</tt>.)
620 */
621 public V remove(Object key) {
622 Entry<K,V> e = removeEntryForKey(key);
623 return (e == null ? null : e.value);
624 }
625
626 /**
627 * Removes and returns the entry associated with the specified key
628 * in the HashMap. Returns null if the HashMap contains no mapping
629 * for this key.
630 */
631 final Entry<K,V> removeEntryForKey(Object key) {
632 int hash = (key == null) ? 0 : hash(key);
633 int i = indexFor(hash, table.length);
634 Entry<K,V> prev = table[i];
635 Entry<K,V> e = prev;
636
637 while (e != null) {
638 Entry<K,V> next = e.next;
639 Object k;
640 if (e.hash == hash &&
641 ((k = e.key) == key || (key != null && key.equals(k)))) {
642 modCount++;
643 size--;
644 if (prev == e)
645 table[i] = next;
646 else
647 prev.next = next;
648 e.recordRemoval(this);
649 return e;
650 }
651 prev = e;
652 e = next;
653 }
654
655 return e;
656 }
657
658 /**
659 * Special version of remove for EntrySet using {@code Map.Entry.equals()}
660 * for matching.
661 */
662 final Entry<K,V> removeMapping(Object o) {
663 if (!(o instanceof Map.Entry))
664 return null;
665
666 Map.Entry<K,V> entry = (Map.Entry<K,V>) o;
667 Object key = entry.getKey();
668 int hash = (key == null) ? 0 : hash(key);
669 int i = indexFor(hash, table.length);
670 Entry<K,V> prev = table[i];
671 Entry<K,V> e = prev;
672
673 while (e != null) {
674 Entry<K,V> next = e.next;
675 if (e.hash == hash && e.equals(entry)) {
676 modCount++;
677 size--;
678 if (prev == e)
679 table[i] = next;
680 else
681 prev.next = next;
682 e.recordRemoval(this);
683 return e;
684 }
685 prev = e;
686 e = next;
687 }
688
689 return e;
690 }
691
692 /**
693 * Removes all of the mappings from this map.
694 * The map will be empty after this call returns.
695 */
696 public void clear() {
697 modCount++;
698 Entry[] tab = table;
699 for (int i = 0; i < tab.length; i++)
700 tab[i] = null;
701 size = 0;
702 }
703
704 /**
705 * Returns <tt>true</tt> if this map maps one or more keys to the
706 * specified value.
707 *
708 * @param value value whose presence in this map is to be tested
709 * @return <tt>true</tt> if this map maps one or more keys to the
710 * specified value
711 */
712 public boolean containsValue(Object value) {
713 if (value == null)
714 return containsNullValue();
715
716 Entry[] tab = table;
717 for (int i = 0; i < tab.length ; i++)
718 for (Entry e = tab[i] ; e != null ; e = e.next)
719 if (value.equals(e.value))
720 return true;
721 return false;
722 }
723
724 /**
725 * Special-case code for containsValue with null argument
726 */
727 private boolean containsNullValue() {
728 Entry[] tab = table;
729 for (int i = 0; i < tab.length ; i++)
730 for (Entry e = tab[i] ; e != null ; e = e.next)
731 if (e.value == null)
732 return true;
733 return false;
734 }
735
736 /**
737 * Returns a shallow copy of this <tt>HashMap</tt> instance: the keys and
738 * values themselves are not cloned.
739 *
740 * @return a shallow copy of this map
741 */
742 public Object clone() {
743 HashMap<K,V> result = null;
744 try {
745 result = (HashMap<K,V>)super.clone();
746 } catch (CloneNotSupportedException e) {
747 // assert false;
748 }
749 result.table = new Entry[table.length];
750 result.entrySet = null;
751 result.modCount = 0;
752 result.size = 0;
753 result.init();
754 result.putAllForCreate(this);
755
756 return result;
757 }
758
759 static class Entry<K,V> implements Map.Entry<K,V> {
760 final K key;
761 V value;
762 Entry<K,V> next;
763 int hash;
764
765 /**
766 * Creates new entry.
767 */
768 Entry(int h, K k, V v, Entry<K,V> n) {
769 value = v;
770 next = n;
771 key = k;
772 hash = h;
773 }
774
775 public final K getKey() {
776 return key;
777 }
778
779 public final V getValue() {
780 return value;
781 }
782
783 public final V setValue(V newValue) {
784 V oldValue = value;
785 value = newValue;
786 return oldValue;
787 }
788
789 public final boolean equals(Object o) {
790 if (!(o instanceof Map.Entry))
791 return false;
792 Map.Entry e = (Map.Entry)o;
793 Object k1 = getKey();
794 Object k2 = e.getKey();
795 if (k1 == k2 || (k1 != null && k1.equals(k2))) {
796 Object v1 = getValue();
797 Object v2 = e.getValue();
798 if (v1 == v2 || (v1 != null && v1.equals(v2)))
799 return true;
800 }
801 return false;
802 }
803
804 public final int hashCode() {
805 return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());
806 }
807
808 public final String toString() {
809 return getKey() + "=" + getValue();
810 }
811
812 /**
813 * This method is invoked whenever the value in an entry is
814 * overwritten by an invocation of put(k,v) for a key k that's already
815 * in the HashMap.
816 */
817 void recordAccess(HashMap<K,V> m) {
818 }
819
820 /**
821 * This method is invoked whenever the entry is
822 * removed from the table.
823 */
824 void recordRemoval(HashMap<K,V> m) {
825 }
826 }
827
828 /**
829 * Adds a new entry with the specified key, value and hash code to
830 * the specified bucket. It is the responsibility of this
831 * method to resize the table if appropriate.
832 *
833 * Subclass overrides this to alter the behavior of put method.
834 */
835 void addEntry(int hash, K key, V value, int bucketIndex) {
836 if ((size >= threshold) && (null != table[bucketIndex])) {
837 resize(2 * table.length);
838 hash = (null != key) ? hash(key) : 0;
839 bucketIndex = indexFor(hash, table.length);
840 }
841
842 createEntry(hash, key, value, bucketIndex);
843 }
844
845 /**
846 * Like addEntry except that this version is used when creating entries
847 * as part of Map construction or "pseudo-construction" (cloning,
848 * deserialization). This version needn't worry about resizing the table.
849 *
850 * Subclass overrides this to alter the behavior of HashMap(Map),
851 * clone, and readObject.
852 */
853 void createEntry(int hash, K key, V value, int bucketIndex) {
854 Entry<K,V> e = table[bucketIndex];
855 table[bucketIndex] = new Entry<>(hash, key, value, e);
856 size++;
857 }
858
859 private abstract class HashIterator<E> implements Iterator<E> {
860 Entry<K,V> next; // next entry to return
861 int expectedModCount; // For fast-fail
862 int index; // current slot
863 Entry<K,V> current; // current entry
864
865 HashIterator() {
866 expectedModCount = modCount;
867 if (size > 0) { // advance to first entry
868 Entry[] t = table;
869 while (index < t.length && (next = t[index++]) == null)
870 ;
871 }
872 }
873
874 public final boolean hasNext() {
875 return next != null;
876 }
877
878 final Entry<K,V> nextEntry() {
879 if (modCount != expectedModCount)
880 throw new ConcurrentModificationException();
881 Entry<K,V> e = next;
882 if (e == null)
883 throw new NoSuchElementException();
884
885 if ((next = e.next) == null) {
886 Entry[] t = table;
887 while (index < t.length && (next = t[index++]) == null)
888 ;
889 }
890 current = e;
891 return e;
892 }
893
894 public void remove() {
895 if (current == null)
896 throw new IllegalStateException();
897 if (modCount != expectedModCount)
898 throw new ConcurrentModificationException();
899 Object k = current.key;
900 current = null;
901 HashMap.this.removeEntryForKey(k);
902 expectedModCount = modCount;
903 }
904 }
905
906 private final class ValueIterator extends HashIterator<V> {
907 public V next() {
908 return nextEntry().value;
909 }
910 }
911
912 private final class KeyIterator extends HashIterator<K> {
913 public K next() {
914 return nextEntry().getKey();
915 }
916 }
917
918 private final class EntryIterator extends HashIterator<Map.Entry<K,V>> {
919 public Map.Entry<K,V> next() {
920 return nextEntry();
921 }
922 }
923
924 // Subclass overrides these to alter behavior of views' iterator() method
925 Iterator<K> newKeyIterator() {
926 return new KeyIterator();
927 }
928 Iterator<V> newValueIterator() {
929 return new ValueIterator();
930 }
931 Iterator<Map.Entry<K,V>> newEntryIterator() {
932 return new EntryIterator();
933 }
934
935
936 // Views
937
938 private transient Set<Map.Entry<K,V>> entrySet = null;
939
940 /**
941 * Returns a {@link Set} view of the keys contained in this map.
942 * The set is backed by the map, so changes to the map are
943 * reflected in the set, and vice-versa. If the map is modified
944 * while an iteration over the set is in progress (except through
945 * the iterator's own <tt>remove</tt> operation), the results of
946 * the iteration are undefined. The set supports element removal,
947 * which removes the corresponding mapping from the map, via the
948 * <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
949 * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>
950 * operations. It does not support the <tt>add</tt> or <tt>addAll</tt>
951 * operations.
952 */
953 public Set<K> keySet() {
954 Set<K> ks = keySet;
955 return (ks != null ? ks : (keySet = new KeySet()));
956 }
957
958 private final class KeySet extends AbstractSet<K> {
959 public Iterator<K> iterator() {
960 return newKeyIterator();
961 }
962 public int size() {
963 return size;
964 }
965 public boolean contains(Object o) {
966 return containsKey(o);
967 }
968 public boolean remove(Object o) {
969 return HashMap.this.removeEntryForKey(o) != null;
970 }
971 public void clear() {
972 HashMap.this.clear();
973 }
974 }
975
976 /**
977 * Returns a {@link Collection} view of the values contained in this map.
978 * The collection is backed by the map, so changes to the map are
979 * reflected in the collection, and vice-versa. If the map is
980 * modified while an iteration over the collection is in progress
981 * (except through the iterator's own <tt>remove</tt> operation),
982 * the results of the iteration are undefined. The collection
983 * supports element removal, which removes the corresponding
984 * mapping from the map, via the <tt>Iterator.remove</tt>,
985 * <tt>Collection.remove</tt>, <tt>removeAll</tt>,
986 * <tt>retainAll</tt> and <tt>clear</tt> operations. It does not
987 * support the <tt>add</tt> or <tt>addAll</tt> operations.
988 */
989 public Collection<V> values() {
990 Collection<V> vs = values;
991 return (vs != null ? vs : (values = new Values()));
992 }
993
994 private final class Values extends AbstractCollection<V> {
995 public Iterator<V> iterator() {
996 return newValueIterator();
997 }
998 public int size() {
999 return size;
1000 }
1001 public boolean contains(Object o) {
1002 return containsValue(o);
1003 }
1004 public void clear() {
1005 HashMap.this.clear();
1006 }
1007 }
1008
1009 /**
1010 * Returns a {@link Set} view of the mappings contained in this map.
1011 * The set is backed by the map, so changes to the map are
1012 * reflected in the set, and vice-versa. If the map is modified
1013 * while an iteration over the set is in progress (except through
1014 * the iterator's own <tt>remove</tt> operation, or through the
1015 * <tt>setValue</tt> operation on a map entry returned by the
1016 * iterator) the results of the iteration are undefined. The set
1017 * supports element removal, which removes the corresponding
1018 * mapping from the map, via the <tt>Iterator.remove</tt>,
1019 * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt> and
1020 * <tt>clear</tt> operations. It does not support the
1021 * <tt>add</tt> or <tt>addAll</tt> operations.
1022 *
1023 * @return a set view of the mappings contained in this map
1024 */
1025 public Set<Map.Entry<K,V>> entrySet() {
1026 return entrySet0();
1027 }
1028
1029 private Set<Map.Entry<K,V>> entrySet0() {
1030 Set<Map.Entry<K,V>> es = entrySet;
1031 return es != null ? es : (entrySet = new EntrySet());
1032 }
1033
1034 private final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
1035 public Iterator<Map.Entry<K,V>> iterator() {
1036 return newEntryIterator();
1037 }
1038 public boolean contains(Object o) {
1039 if (!(o instanceof Map.Entry))
1040 return false;
1041 Map.Entry<K,V> e = (Map.Entry<K,V>) o;
1042 Entry<K,V> candidate = getEntry(e.getKey());
1043 return candidate != null && candidate.equals(e);
1044 }
1045 public boolean remove(Object o) {
1046 return removeMapping(o) != null;
1047 }
1048 public int size() {
1049 return size;
1050 }
1051 public void clear() {
1052 HashMap.this.clear();
1053 }
1054 }
1055
1056 /**
1057 * Save the state of the <tt>HashMap</tt> instance to a stream (i.e.,
1058 * serialize it).
1059 *
1060 * @serialData The <i>capacity</i> of the HashMap (the length of the
1061 * bucket array) is emitted (int), followed by the
1062 * <i>size</i> (an int, the number of key-value
1063 * mappings), followed by the key (Object) and value (Object)
1064 * for each key-value mapping. The key-value mappings are
1065 * emitted in no particular order.
1066 */
1067 private void writeObject(java.io.ObjectOutputStream s)
1068 throws IOException
1069 {
1070 Iterator<Map.Entry<K,V>> i =
1071 (size > 0) ? entrySet0().iterator() : null;
1072
1073 // Write out the threshold, loadfactor, and any hidden stuff
1074 s.defaultWriteObject();
1075
1076 // Write out number of buckets
1077 s.writeInt(table.length);
1078
1079 // Write out size (number of Mappings)
1080 s.writeInt(size);
1081
1082 // Write out keys and values (alternating)
1083 if (size > 0) {
1084 for(Map.Entry<K,V> e : entrySet0()) {
1085 s.writeObject(e.getKey());
1086 s.writeObject(e.getValue());
1087 }
1088 }
1089 }
1090
1091 private static final long serialVersionUID = 362498820763181265L;
1092
1093 /**
1094 * Reconstitute the {@code HashMap} instance from a stream (i.e.,
1095 * deserialize it).
1096 */
1097 private void readObject(java.io.ObjectInputStream s)
1098 throws IOException, ClassNotFoundException
1099 {
1100 // Read in the threshold (ignored), loadfactor, and any hidden stuff
1101 s.defaultReadObject();
1102 if (loadFactor <= 0 || Float.isNaN(loadFactor))
1103 throw new InvalidObjectException("Illegal load factor: " +
1104 loadFactor);
1105
1106 // Read in number of buckets and allocate the bucket array;
1107 s.readInt(); // ignored
1108
1109 // Read number of mappings
1110 int mappings = s.readInt();
1111 if (mappings < 0)
1112 throw new InvalidObjectException("Illegal mappings count: " +
1113 mappings);
1114
1115 int initialCapacity = (int) Math.min(
1116 // capacity chosen by number of mappings
1117 // and desired load (if >= 0.25)
1118 mappings * Math.min(1 / loadFactor, 4.0f),
1119 // we have limits...
1120 HashMap.MAXIMUM_CAPACITY);
1121 // find smallest power of two which holds all mappings
1122 int capacity = (capacity = Integer.highestOneBit(initialCapacity)) != 0
1123 ? capacity
1124 : 1;
1125 capacity <<= (Integer.bitCount(initialCapacity) > 1) ? 1 : 0;
1126
1127 table = new Entry[capacity];
1128 threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
1129 initHashSeedAsNeeded(capacity);
1130
1131 init(); // Give subclass a chance to do its thing.
1132
1133 // Read the keys and values, and put the mappings in the HashMap
1134 for (int i=0; i<mappings; i++) {
1135 K key = (K) s.readObject();
1136 V value = (V) s.readObject();
1137 putForCreate(key, value);
1138 }
1139 }
1140
1141 // These methods are used when serializing HashSets
1142 int capacity() { return table.length; }
1143 float loadFactor() { return loadFactor; }
1144 }