1 /*
2 * Copyright (c) 1997, 2013, 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
28 import java.io.*;
29 import java.util.function.Consumer;
30 import java.util.function.BiFunction;
31 import java.util.function.Function;
32
33 /**
34 * Hash table based implementation of the <tt>Map</tt> interface. This
35 * implementation provides all of the optional map operations, and permits
36 * <tt>null</tt> values and the <tt>null</tt> key. (The <tt>HashMap</tt>
37 * class is roughly equivalent to <tt>Hashtable</tt>, except that it is
38 * unsynchronized and permits nulls.) This class makes no guarantees as to
39 * the order of the map; in particular, it does not guarantee that the order
40 * will remain constant over time.
41 *
42 * <p>This implementation provides constant-time performance for the basic
43 * operations (<tt>get</tt> and <tt>put</tt>), assuming the hash function
44 * disperses the elements properly among the buckets. Iteration over
45 * collection views requires time proportional to the "capacity" of the
46 * <tt>HashMap</tt> instance (the number of buckets) plus its size (the number
47 * of key-value mappings). Thus, it's very important not to set the initial
48 * capacity too high (or the load factor too low) if iteration performance is
49 * important.
50 *
51 * <p>An instance of <tt>HashMap</tt> has two parameters that affect its
52 * performance: <i>initial capacity</i> and <i>load factor</i>. The
53 * <i>capacity</i> is the number of buckets in the hash table, and the initial
54 * capacity is simply the capacity at the time the hash table is created. The
55 * <i>load factor</i> is a measure of how full the hash table is allowed to
56 * get before its capacity is automatically increased. When the number of
57 * entries in the hash table exceeds the product of the load factor and the
58 * current capacity, the hash table is <i>rehashed</i> (that is, internal data
59 * structures are rebuilt) so that the hash table has approximately twice the
60 * number of buckets.
61 *
62 * <p>As a general rule, the default load factor (.75) offers a good tradeoff
63 * between time and space costs. Higher values decrease the space overhead
64 * but increase the lookup cost (reflected in most of the operations of the
65 * <tt>HashMap</tt> class, including <tt>get</tt> and <tt>put</tt>). The
66 * expected number of entries in the map and its load factor should be taken
67 * into account when setting its initial capacity, so as to minimize the
68 * number of rehash operations. If the initial capacity is greater
69 * than the maximum number of entries divided by the load factor, no
70 * rehash operations will ever occur.
71 *
72 * <p>If many mappings are to be stored in a <tt>HashMap</tt> instance,
73 * creating it with a sufficiently large capacity will allow the mappings to
74 * be stored more efficiently than letting it perform automatic rehashing as
75 * needed to grow the table.
76 *
77 * <p><strong>Note that this implementation is not synchronized.</strong>
78 * If multiple threads access a hash map concurrently, and at least one of
79 * the threads modifies the map structurally, it <i>must</i> be
80 * synchronized externally. (A structural modification is any operation
81 * that adds or deletes one or more mappings; merely changing the value
82 * associated with a key that an instance already contains is not a
83 * structural modification.) This is typically accomplished by
84 * synchronizing on some object that naturally encapsulates the map.
85 *
86 * If no such object exists, the map should be "wrapped" using the
87 * {@link Collections#synchronizedMap Collections.synchronizedMap}
88 * method. This is best done at creation time, to prevent accidental
89 * unsynchronized access to the map:<pre>
90 * Map m = Collections.synchronizedMap(new HashMap(...));</pre>
91 *
92 * <p>The iterators returned by all of this class's "collection view methods"
93 * are <i>fail-fast</i>: if the map is structurally modified at any time after
94 * the iterator is created, in any way except through the iterator's own
95 * <tt>remove</tt> method, the iterator will throw a
96 * {@link ConcurrentModificationException}. Thus, in the face of concurrent
97 * modification, the iterator fails quickly and cleanly, rather than risking
98 * arbitrary, non-deterministic behavior at an undetermined time in the
99 * future.
100 *
101 * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
102 * as it is, generally speaking, impossible to make any hard guarantees in the
103 * presence of unsynchronized concurrent modification. Fail-fast iterators
104 * throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
105 * Therefore, it would be wrong to write a program that depended on this
106 * exception for its correctness: <i>the fail-fast behavior of iterators
107 * should be used only to detect bugs.</i>
108 *
109 * <p>This class is a member of the
110 * <a href="{@docRoot}/../technotes/guides/collections/index.html">
111 * Java Collections Framework</a>.
112 *
113 * @param <K> the type of keys maintained by this map
114 * @param <V> the type of mapped values
115 *
116 * @author Doug Lea
117 * @author Josh Bloch
118 * @author Arthur van Hoff
119 * @author Neal Gafter
120 * @see Object#hashCode()
121 * @see Collection
122 * @see Map
123 * @see TreeMap
124 * @see Hashtable
125 * @since 1.2
126 */
127
128 public class HashMap<K,V>
129 extends AbstractMap<K,V>
130 implements Map<K,V>, Cloneable, Serializable
131 {
132
133 /**
134 * The default initial capacity - MUST be a power of two.
135 */
136 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
137
138 /**
139 * The maximum capacity, used if a higher value is implicitly specified
140 * by either of the constructors with arguments.
141 * MUST be a power of two <= 1<<30.
142 */
143 static final int MAXIMUM_CAPACITY = 1 << 30;
144
145 /**
146 * The load factor used when none specified in constructor.
147 */
148 static final float DEFAULT_LOAD_FACTOR = 0.75f;
149
150 /**
151 * An empty table instance to share when the table is not inflated.
152 */
153 static final Entry<?,?>[] EMPTY_TABLE = {};
154
155 /**
156 * The table, resized as necessary. Length MUST Always be a power of two.
157 */
158 transient Entry<?,?>[] table = EMPTY_TABLE;
159
160 /**
161 * The number of key-value mappings contained in this map.
162 */
163 transient int size;
164
165 /**
166 * The next size value at which to resize (capacity * load factor).
167 * @serial
168 */
169 // If table == EMPTY_TABLE then this is the initial capacity at which the
170 // table will be created when inflated.
171 int threshold;
172
173 /**
174 * The load factor for the hash table.
175 *
176 * @serial
177 */
178 final float loadFactor;
179
180 /**
181 * The number of times this HashMap has been structurally modified
182 * Structural modifications are those that change the number of mappings in
183 * the HashMap or otherwise modify its internal structure (e.g.,
184 * rehash). This field is used to make iterators on Collection-views of
185 * the HashMap fail-fast. (See ConcurrentModificationException).
186 */
187 transient int modCount;
188
189 private static class Holder {
190 /**
191 *
192 */
193 static final sun.misc.Unsafe UNSAFE;
194
195 /**
196 * Offset of "final" hashSeed field we must set in
197 * readObject() method.
198 */
199 static final long HASHSEED_OFFSET;
200
201 static {
202 try {
203 UNSAFE = sun.misc.Unsafe.getUnsafe();
204 HASHSEED_OFFSET = UNSAFE.objectFieldOffset(
205 HashMap.class.getDeclaredField("hashSeed"));
206 } catch (NoSuchFieldException | SecurityException e) {
207 throw new InternalError("Failed to record hashSeed offset", e);
208 }
209 }
210 }
211
212 /**
213 * A randomizing value associated with this instance that is applied to
214 * hash code of keys to make hash collisions harder to find.
215 */
216 transient final int hashSeed = sun.misc.Hashing.randomHashSeed(this);
217
218 /**
219 * Constructs an empty <tt>HashMap</tt> with the specified initial
220 * capacity and load factor.
221 *
222 * @param initialCapacity the initial capacity
223 * @param loadFactor the load factor
224 * @throws IllegalArgumentException if the initial capacity is negative
225 * or the load factor is nonpositive
226 */
227 public HashMap(int initialCapacity, float loadFactor) {
228 if (initialCapacity < 0)
229 throw new IllegalArgumentException("Illegal initial capacity: " +
230 initialCapacity);
231 if (initialCapacity > MAXIMUM_CAPACITY)
232 initialCapacity = MAXIMUM_CAPACITY;
233 if (loadFactor <= 0 || Float.isNaN(loadFactor))
234 throw new IllegalArgumentException("Illegal load factor: " +
235 loadFactor);
236
237 this.loadFactor = loadFactor;
238 threshold = initialCapacity;
239 init();
240 }
241
242 /**
243 * Constructs an empty <tt>HashMap</tt> with the specified initial
244 * capacity and the default load factor (0.75).
245 *
246 * @param initialCapacity the initial capacity.
247 * @throws IllegalArgumentException if the initial capacity is negative.
248 */
249 public HashMap(int initialCapacity) {
250 this(initialCapacity, DEFAULT_LOAD_FACTOR);
251 }
252
253 /**
254 * Constructs an empty <tt>HashMap</tt> with the default initial capacity
255 * (16) and the default load factor (0.75).
256 */
257 public HashMap() {
258 this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
259 }
260
261 /**
262 * Constructs a new <tt>HashMap</tt> with the same mappings as the
263 * specified <tt>Map</tt>. The <tt>HashMap</tt> is created with
264 * default load factor (0.75) and an initial capacity sufficient to
265 * hold the mappings in the specified <tt>Map</tt>.
266 *
267 * @param m the map whose mappings are to be placed in this map
268 * @throws NullPointerException if the specified map is null
269 */
270 public HashMap(Map<? extends K, ? extends V> m) {
271 this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
272 DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
273 inflateTable(threshold);
274
275 putAllForCreate(m);
276 }
277
278 private static int roundUpToPowerOf2(int number) {
279 // assert number >= 0 : "number must be non-negative";
280 int rounded = number >= MAXIMUM_CAPACITY
281 ? MAXIMUM_CAPACITY
282 : (rounded = Integer.highestOneBit(number)) != 0
283 ? (Integer.bitCount(number) > 1) ? rounded << 1 : rounded
284 : 1;
285
286 return rounded;
287 }
288
289 /**
290 * Inflates the table.
291 */
292 private void inflateTable(int toSize) {
293 // Find a power of 2 >= toSize
294 int capacity = roundUpToPowerOf2(toSize);
295
296 threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
297 table = new Entry[capacity];
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 * Retrieve object hash code and applies a supplemental hash function to the
314 * result hash, which defends against poor quality hash functions. This is
315 * critical because HashMap uses power-of-two length hash tables, that
316 * otherwise encounter collisions for hashCodes that do not differ
317 * in lower bits.
318 */
319 final int hash(Object k) {
320 if (k instanceof String) {
321 return ((String) k).hash32();
322 }
323
324 int h = hashSeed ^ k.hashCode();
325
326 // This function ensures that hashCodes that differ only by
327 // constant multiples at each bit position have a bounded
328 // number of collisions (approximately 8 at default load factor).
329 h ^= (h >>> 20) ^ (h >>> 12);
330 return h ^ (h >>> 7) ^ (h >>> 4);
331 }
332
333 /**
334 * Returns index for hash code h.
335 */
336 static int indexFor(int h, int length) {
337 // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
338 return h & (length-1);
339 }
340
341 /**
342 * Returns the number of key-value mappings in this map.
343 *
344 * @return the number of key-value mappings in this map
345 */
346 public int size() {
347 return size;
348 }
349
350 /**
351 * Returns <tt>true</tt> if this map contains no key-value mappings.
352 *
353 * @return <tt>true</tt> if this map contains no key-value mappings
354 */
355 public boolean isEmpty() {
356 return size == 0;
357 }
358
359 /**
360 * Returns the value to which the specified key is mapped,
361 * or {@code null} if this map contains no mapping for the key.
362 *
363 * <p>More formally, if this map contains a mapping from a key
364 * {@code k} to a value {@code v} such that {@code (key==null ? k==null :
365 * key.equals(k))}, then this method returns {@code v}; otherwise
366 * it returns {@code null}. (There can be at most one such mapping.)
367 *
368 * <p>A return value of {@code null} does not <i>necessarily</i>
369 * indicate that the map contains no mapping for the key; it's also
370 * possible that the map explicitly maps the key to {@code null}.
371 * The {@link #containsKey containsKey} operation may be used to
372 * distinguish these two cases.
373 *
374 * @see #put(Object, Object)
375 */
376 @SuppressWarnings("unchecked")
377 public V get(Object key) {
378 Entry<K,V> entry = getEntry(key);
379
380 return null == entry ? null : entry.getValue();
381 }
382
383 @Override
384 public V getOrDefault(Object key, V defaultValue) {
385 Entry<K,V> entry = getEntry(key);
386
387 return (entry == null) ? defaultValue : entry.getValue();
388 }
389
390 /**
391 * Returns <tt>true</tt> if this map contains a mapping for the
392 * specified key.
393 *
394 * @param key The key whose presence in this map is to be tested
395 * @return <tt>true</tt> if this map contains a mapping for the specified
396 * key.
397 */
398 public boolean containsKey(Object key) {
399 return getEntry(key) != null;
400 }
401
402 /**
403 * Returns the entry associated with the specified key in the
404 * HashMap. Returns null if the HashMap contains no mapping
405 * for the key.
406 */
407 @SuppressWarnings("unchecked")
408 final Entry<K,V> getEntry(Object key) {
409 if (isEmpty()) {
410 return null;
411 }
412
413 int hash = (key == null) ? 0 : hash(key);
414 for (Entry<?,?> e = table[indexFor(hash, table.length)];
415 e != null;
416 e = e.next) {
417 Object k;
418 if (e.hash == hash &&
419 ((k = e.key) == key || (key != null && key.equals(k))))
420 return (Entry<K,V>)e;
421 }
422 return null;
423 }
424
425 /**
426 * Associates the specified value with the specified key in this map.
427 * If the map previously contained a mapping for the key, the old
428 * value is replaced.
429 *
430 * @param key key with which the specified value is to be associated
431 * @param value value to be associated with the specified key
432 * @return the previous value associated with <tt>key</tt>, or
433 * <tt>null</tt> if there was no mapping for <tt>key</tt>.
434 * (A <tt>null</tt> return can also indicate that the map
435 * previously associated <tt>null</tt> with <tt>key</tt>.)
436 */
437 public V put(K key, V value) {
438 if (table == EMPTY_TABLE) {
439 inflateTable(threshold);
440 }
441 if (key == null)
442 return putForNullKey(value);
443 int hash = hash(key);
444 int i = indexFor(hash, table.length);
445 @SuppressWarnings("unchecked")
446 Entry<K,V> e = (Entry<K,V>)table[i];
447 for(; e != null; e = e.next) {
448 Object k;
449 if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
450 V oldValue = e.value;
451 e.value = value;
452 e.recordAccess(this);
453 return oldValue;
454 }
455 }
456
457 modCount++;
458 addEntry(hash, key, value, i);
459 return null;
460 }
461
462 /**
463 * Offloaded version of put for null keys
464 */
465 private V putForNullKey(V value) {
466 @SuppressWarnings("unchecked")
467 Entry<K,V> e = (Entry<K,V>)table[0];
468 for(; e != null; e = e.next) {
469 if (e.key == null) {
470 V oldValue = e.value;
471 e.value = value;
472 e.recordAccess(this);
473 return oldValue;
474 }
475 }
476 modCount++;
477 addEntry(0, null, value, 0);
478 return null;
479 }
480
481 /**
482 * This method is used instead of put by constructors and
483 * pseudoconstructors (clone, readObject). It does not resize the table,
484 * check for comodification, etc. It calls createEntry rather than
485 * addEntry.
486 */
487 private void putForCreate(K key, V value) {
488 int hash = null == key ? 0 : hash(key);
489 int i = indexFor(hash, table.length);
490
491 /**
492 * Look for preexisting entry for key. This will never happen for
493 * clone or deserialize. It will only happen for construction if the
494 * input Map is a sorted map whose ordering is inconsistent w/ equals.
495 */
496 for (@SuppressWarnings("unchecked")
497 Entry<?,V> e = (Entry<?,V>)table[i]; e != null; e = e.next) {
498 Object k;
499 if (e.hash == hash &&
500 ((k = e.key) == key || (key != null && key.equals(k)))) {
501 e.value = value;
502 return;
503 }
504 }
505
506 createEntry(hash, key, value, i);
507 }
508
509 private void putAllForCreate(Map<? extends K, ? extends V> m) {
510 for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
511 putForCreate(e.getKey(), e.getValue());
512 }
513
514 /**
515 * Rehashes the contents of this map into a new array with a
516 * larger capacity. This method is called automatically when the
517 * number of keys in this map reaches its threshold.
518 *
519 * If current capacity is MAXIMUM_CAPACITY, this method does not
520 * resize the map, but sets threshold to Integer.MAX_VALUE.
521 * This has the effect of preventing future calls.
522 *
523 * @param newCapacity the new capacity, MUST be a power of two;
524 * must be greater than current capacity unless current
525 * capacity is MAXIMUM_CAPACITY (in which case value
526 * is irrelevant).
527 */
528 void resize(int newCapacity) {
529 Entry<?,?>[] oldTable = table;
530 int oldCapacity = oldTable.length;
531 if (oldCapacity == MAXIMUM_CAPACITY) {
532 threshold = Integer.MAX_VALUE;
533 return;
534 }
535
536 Entry<?,?>[] newTable = new Entry<?,?>[newCapacity];
537 transfer(newTable);
538 table = newTable;
539 threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
540 }
541
542 /**
543 * Transfers all entries from current table to newTable.
544 */
545 @SuppressWarnings("unchecked")
546 void transfer(Entry<?,?>[] newTable) {
547 Entry<?,?>[] src = table;
548 int newCapacity = newTable.length;
549 for (int j = 0; j < src.length; j++ ) {
550 Entry<K,V> e = (Entry<K,V>) src[j];
551 while(null != e) {
552 Entry<K,V> next = e.next;
553 int i = indexFor(e.hash, newCapacity);
554 e.next = (Entry<K,V>) newTable[i];
555 newTable[i] = e;
556 e = next;
557 }
558 }
559 Arrays.fill(table, null);
560 }
561
562 /**
563 * Copies all of the mappings from the specified map to this map.
564 * These mappings will replace any mappings that this map had for
565 * any of the keys currently in the specified map.
566 *
567 * @param m mappings to be stored in this map
568 * @throws NullPointerException if the specified map is null
569 */
570 public void putAll(Map<? extends K, ? extends V> m) {
571 int numKeysToBeAdded = m.size();
572 if (numKeysToBeAdded == 0)
573 return;
574
575 if (table == EMPTY_TABLE) {
576 inflateTable((int) Math.max(numKeysToBeAdded * loadFactor, threshold));
577 }
578
579 /*
580 * Expand the map if the map if the number of mappings to be added
581 * is greater than or equal to threshold. This is conservative; the
582 * obvious condition is (m.size() + size) >= threshold, but this
583 * condition could result in a map with twice the appropriate capacity,
584 * if the keys to be added overlap with the keys already in this map.
585 * By using the conservative calculation, we subject ourself
586 * to at most one extra resize.
587 */
588 if (numKeysToBeAdded > threshold) {
589 int targetCapacity = (int)(numKeysToBeAdded / loadFactor + 1);
590 if (targetCapacity > MAXIMUM_CAPACITY)
591 targetCapacity = MAXIMUM_CAPACITY;
592 int newCapacity = table.length;
593 while (newCapacity < targetCapacity)
594 newCapacity <<= 1;
595 if (newCapacity > table.length)
596 resize(newCapacity);
597 }
598
599 for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
600 put(e.getKey(), e.getValue());
601 }
602
603 /**
604 * Removes the mapping for the specified key from this map if present.
605 *
606 * @param key key whose mapping is to be removed from the map
607 * @return the previous value associated with <tt>key</tt>, or
608 * <tt>null</tt> if there was no mapping for <tt>key</tt>.
609 * (A <tt>null</tt> return can also indicate that the map
610 * previously associated <tt>null</tt> with <tt>key</tt>.)
611 */
612 public V remove(Object key) {
613 Entry<K,V> e = removeEntryForKey(key);
614 return (e == null ? null : e.value);
615 }
616
617 // optimized implementations of default methods in Map
618
619 @Override
620 public V putIfAbsent(K key, V value) {
621 if (table == EMPTY_TABLE) {
622 inflateTable(threshold);
623 }
624 int hash = (key == null) ? 0 : hash(key);
625 int i = indexFor(hash, table.length);
626 @SuppressWarnings("unchecked")
627 Entry<K,V> e = (Entry<K,V>)table[i];
628 for(; e != null; e = e.next) {
629 if (e.hash == hash && Objects.equals(e.key, key)) {
630 if(e.value != null) {
631 return e.value;
632 }
633 e.value = value;
634 modCount++;
635 e.recordAccess(this);
636 return null;
637 }
638 }
639
640 modCount++;
641 addEntry(hash, key, value, i);
642 return null;
643 }
644
645 @Override
646 public boolean remove(Object key, Object value) {
647 if (isEmpty()) {
648 return false;
649 }
650 int hash = (key == null) ? 0 : hash(key);
651 int i = indexFor(hash, table.length);
652 @SuppressWarnings("unchecked")
653 Entry<K,V> prev = (Entry<K,V>)table[i];
654 Entry<K,V> e = prev;
655
656 while (e != null) {
657 Entry<K,V> next = e.next;
658 if (e.hash == hash && Objects.equals(e.key, key)) {
659 if (!Objects.equals(e.value, value)) {
660 return false;
661 }
662 modCount++;
663 size--;
664 if (prev == e)
665 table[i] = next;
666 else
667 prev.next = next;
668 e.recordRemoval(this);
669 return true;
670 }
671 prev = e;
672 e = next;
673 }
674
675 return false;
676 }
677
678 @Override
679 public boolean replace(K key, V oldValue, V newValue) {
680 if (isEmpty()) {
681 return false;
682 }
683 int hash = (key == null) ? 0 : hash(key);
684 int i = indexFor(hash, table.length);
685 @SuppressWarnings("unchecked")
686 Entry<K,V> e = (Entry<K,V>)table[i];
687 for (; e != null; e = e.next) {
688 if (e.hash == hash && Objects.equals(e.key, key) && Objects.equals(e.value, oldValue)) {
689 e.value = newValue;
690 e.recordAccess(this);
691 return true;
692 }
693 }
694
695 return false;
696 }
697
698 @Override
699 public V replace(K key, V value) {
700 if (isEmpty()) {
701 return null;
702 }
703 int hash = (key == null) ? 0 : hash(key);
704 int i = indexFor(hash, table.length);
705 @SuppressWarnings("unchecked")
706 Entry<K,V> e = (Entry<K,V>)table[i];
707 for (; e != null; e = e.next) {
708 if (e.hash == hash && Objects.equals(e.key, key)) {
709 V oldValue = e.value;
710 e.value = value;
711 e.recordAccess(this);
712 return oldValue;
713 }
714 }
715
716 return null;
717 }
718
719 @Override
720 public V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction) {
721 if (table == EMPTY_TABLE) {
722 inflateTable(threshold);
723 }
724 int hash = (key == null) ? 0 : hash(key);
725 int i = indexFor(hash, table.length);
726 @SuppressWarnings("unchecked")
727 Entry<K,V> e = (Entry<K,V>)table[i];
728 for (; e != null; e = e.next) {
729 if (e.hash == hash && Objects.equals(e.key, key)) {
730 V oldValue = e.value;
731 return oldValue == null ? (e.value = mappingFunction.apply(key)) : oldValue;
732 }
733 }
734
735 V newValue = mappingFunction.apply(key);
736 if (newValue != null) {
737 modCount++;
738 addEntry(hash, key, newValue, i);
739 }
740
741 return newValue;
742 }
743
744 @Override
745 public V computeIfPresent(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
746 if (isEmpty()) {
747 return null;
748 }
749 int hash = (key == null) ? 0 : hash(key);
750 int i = indexFor(hash, table.length);
751 @SuppressWarnings("unchecked")
752 Entry<K,V> prev = (Entry<K,V>)table[i];
753 Entry<K,V> e = prev;
754
755 while (e != null) {
756 Entry<K,V> next = e.next;
757 if (e.hash == hash && Objects.equals(e.key, key)) {
758 V oldValue = e.value;
759 if (oldValue == null)
760 break;
761 V newValue = remappingFunction.apply(key, oldValue);
762 modCount++;
763 if (newValue == null) {
764 size--;
765 if (prev == e)
766 table[i] = next;
767 else
768 prev.next = next;
769 e.recordRemoval(this);
770 } else {
771 e.value = newValue;
772 e.recordAccess(this);
773 }
774 return newValue;
775 }
776 prev = e;
777 e = next;
778 }
779
780 return null;
781 }
782
783 @Override
784 public V compute(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
785 if (table == EMPTY_TABLE) {
786 inflateTable(threshold);
787 }
788 int hash = (key == null) ? 0 : hash(key);
789 int i = indexFor(hash, table.length);
790 @SuppressWarnings("unchecked")
791 Entry<K,V> prev = (Entry<K,V>)table[i];
792 Entry<K,V> e = prev;
793
794 while (e != null) {
795 Entry<K,V> next = e.next;
796 if (e.hash == hash && Objects.equals(e.key, key)) {
797 V oldValue = e.value;
798 V newValue = remappingFunction.apply(key, oldValue);
799 if (newValue != oldValue) {
800 modCount++;
801 if (newValue == null) {
802 size--;
803 if (prev == e)
804 table[i] = next;
805 else
806 prev.next = next;
807 e.recordRemoval(this);
808 } else {
809 e.value = newValue;
810 e.recordAccess(this);
811 }
812 }
813 return newValue;
814 }
815 prev = e;
816 e = next;
817 }
818
819 V newValue = remappingFunction.apply(key, null);
820 if (newValue != null) {
821 modCount++;
822 addEntry(hash, key, newValue, i);
823 }
824
825 return newValue;
826 }
827
828 @Override
829 public V merge(K key, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
830 if (table == EMPTY_TABLE) {
831 inflateTable(threshold);
832 }
833 int hash = (key == null) ? 0 : hash(key);
834 int i = indexFor(hash, table.length);
835 @SuppressWarnings("unchecked")
836 Entry<K,V> prev = (Entry<K,V>)table[i];
837 Entry<K,V> e = prev;
838
839 while (e != null) {
840 Entry<K,V> next = e.next;
841 if (e.hash == hash && Objects.equals(e.key, key)) {
842 V oldValue = e.value;
843 V newValue = remappingFunction.apply(oldValue, value);
844 modCount++;
845 if (newValue == null) {
846 size--;
847 if (prev == e)
848 table[i] = next;
849 else
850 prev.next = next;
851 e.recordRemoval(this);
852 } else {
853 e.value = newValue;
854 e.recordAccess(this);
855 }
856 return newValue;
857 }
858 prev = e;
859 e = next;
860 }
861
862 if (value != null) {
863 modCount++;
864 addEntry(hash, key, value, i);
865 }
866
867 return value;
868 }
869
870 // end of optimized implementations of default methods in Map
871
872 /**
873 * Removes and returns the entry associated with the specified key
874 * in the HashMap. Returns null if the HashMap contains no mapping
875 * for this key.
876 */
877 final Entry<K,V> removeEntryForKey(Object key) {
878 if (isEmpty()) {
879 return null;
880 }
881 int hash = (key == null) ? 0 : hash(key);
882 int i = indexFor(hash, table.length);
883 @SuppressWarnings("unchecked")
884 Entry<K,V> prev = (Entry<K,V>)table[i];
885 Entry<K,V> e = prev;
886
887 while (e != null) {
888 Entry<K,V> next = e.next;
889 Object k;
890 if (e.hash == hash &&
891 ((k = e.key) == key || (key != null && key.equals(k)))) {
892 modCount++;
893 size--;
894 if (prev == e)
895 table[i] = next;
896 else
897 prev.next = next;
898 e.recordRemoval(this);
899 return e;
900 }
901 prev = e;
902 e = next;
903 }
904
905 return e;
906 }
907
908 /**
909 * Special version of remove for EntrySet using {@code Map.Entry.equals()}
910 * for matching.
911 */
912 final Entry<K,V> removeMapping(Object o) {
913 if (isEmpty() || !(o instanceof Map.Entry))
914 return null;
915
916 Map.Entry<?,?> entry = (Map.Entry<?,?>) o;
917 Object key = entry.getKey();
918 int hash = (key == null) ? 0 : hash(key);
919 int i = indexFor(hash, table.length);
920 @SuppressWarnings("unchecked")
921 Entry<K,V> prev = (Entry<K,V>)table[i];
922 Entry<K,V> e = prev;
923
924 while (e != null) {
925 Entry<K,V> next = e.next;
926 if (e.hash == hash && e.equals(entry)) {
927 modCount++;
928 size--;
929 if (prev == e)
930 table[i] = next;
931 else
932 prev.next = next;
933 e.recordRemoval(this);
934 return e;
935 }
936 prev = e;
937 e = next;
938 }
939
940 return e;
941 }
942
943 /**
944 * Removes all of the mappings from this map.
945 * The map will be empty after this call returns.
946 */
947 public void clear() {
948 modCount++;
949 Arrays.fill(table, null);
950 size = 0;
951 }
952
953 /**
954 * Returns <tt>true</tt> if this map maps one or more keys to the
955 * specified value.
956 *
957 * @param value value whose presence in this map is to be tested
958 * @return <tt>true</tt> if this map maps one or more keys to the
959 * specified value
960 */
961 public boolean containsValue(Object value) {
962 if (value == null)
963 return containsNullValue();
964
965 Entry<?,?>[] tab = table;
966 for (int i = 0; i < tab.length; i++)
967 for (Entry<?,?> e = tab[i]; e != null; e = e.next)
968 if (value.equals(e.value))
969 return true;
970 return false;
971 }
972
973 /**
974 * Special-case code for containsValue with null argument
975 */
976 private boolean containsNullValue() {
977 Entry<?,?>[] tab = table;
978 for (int i = 0; i < tab.length; i++)
979 for (Entry<?,?> e = tab[i]; e != null; e = e.next)
980 if (e.value == null)
981 return true;
982 return false;
983 }
984
985 /**
986 * Returns a shallow copy of this <tt>HashMap</tt> instance: the keys and
987 * values themselves are not cloned.
988 *
989 * @return a shallow copy of this map
990 */
991 @SuppressWarnings("unchecked")
992 public Object clone() {
993 HashMap<K,V> result = null;
994 try {
995 result = (HashMap<K,V>)super.clone();
996 } catch (CloneNotSupportedException e) {
997 // assert false;
998 }
999 if (result.table != EMPTY_TABLE) {
1000 result.inflateTable(Math.min(
1001 (int) Math.min(
1002 size * Math.min(1 / loadFactor, 4.0f),
1003 // we have limits...
1004 HashMap.MAXIMUM_CAPACITY),
1005 table.length));
1006 }
1007 result.entrySet = null;
1008 result.modCount = 0;
1009 result.size = 0;
1010 result.init();
1011 result.putAllForCreate(this);
1012
1013 return result;
1014 }
1015
1016 static class Entry<K,V> implements Map.Entry<K,V> {
1017 final K key;
1018 V value;
1019 Entry<K,V> next;
1020 final int hash;
1021
1022 /**
1023 * Creates new entry.
1024 */
1025 Entry(int h, K k, V v, Entry<K,V> n) {
1026 value = v;
1027 next = n;
1028 key = k;
1029 hash = h;
1030 }
1031
1032 public final K getKey() {
1033 return key;
1034 }
1035
1036 public final V getValue() {
1037 return value;
1038 }
1039
1040 public final V setValue(V newValue) {
1041 V oldValue = value;
1042 value = newValue;
1043 return oldValue;
1044 }
1045
1046 public final boolean equals(Object o) {
1047 if (!(o instanceof Map.Entry))
1048 return false;
1049 Map.Entry<?,?> e = (Map.Entry<?,?>)o;
1050 Object k1 = getKey();
1051 Object k2 = e.getKey();
1052 if (k1 == k2 || (k1 != null && k1.equals(k2))) {
1053 Object v1 = getValue();
1054 Object v2 = e.getValue();
1055 if (v1 == v2 || (v1 != null && v1.equals(v2)))
1056 return true;
1057 }
1058 return false;
1059 }
1060
1061 public final int hashCode() {
1062 return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());
1063 }
1064
1065 public final String toString() {
1066 return getKey() + "=" + getValue();
1067 }
1068
1069 /**
1070 * This method is invoked whenever the value in an entry is
1071 * overwritten by an invocation of put(k,v) for a key k that's already
1072 * in the HashMap.
1073 */
1074 void recordAccess(HashMap<K,V> m) {
1075 }
1076
1077 /**
1078 * This method is invoked whenever the entry is
1079 * removed from the table.
1080 */
1081 void recordRemoval(HashMap<K,V> m) {
1082 }
1083 }
1084
1085 /**
1086 * Adds a new entry with the specified key, value and hash code to
1087 * the specified bucket. It is the responsibility of this
1088 * method to resize the table if appropriate.
1089 *
1090 * Subclass overrides this to alter the behavior of put method.
1091 */
1092 void addEntry(int hash, K key, V value, int bucketIndex) {
1093 if ((size >= threshold) && (null != table[bucketIndex])) {
1094 resize(2 * table.length);
1095 hash = (null != key) ? hash(key) : 0;
1096 bucketIndex = indexFor(hash, table.length);
1097 }
1098
1099 createEntry(hash, key, value, bucketIndex);
1100 }
1101
1102 /**
1103 * Like addEntry except that this version is used when creating entries
1104 * as part of Map construction or "pseudo-construction" (cloning,
1105 * deserialization). This version needn't worry about resizing the table.
1106 *
1107 * Subclass overrides this to alter the behavior of HashMap(Map),
1108 * clone, and readObject.
1109 */
1110 void createEntry(int hash, K key, V value, int bucketIndex) {
1111 @SuppressWarnings("unchecked")
1112 Entry<K,V> e = (Entry<K,V>)table[bucketIndex];
1113 table[bucketIndex] = new Entry<>(hash, key, value, e);
1114 size++;
1115 }
1116
1117 private abstract class HashIterator<E> implements Iterator<E> {
1118 Entry<?,?> next; // next entry to return
1119 int expectedModCount; // For fast-fail
1120 int index; // current slot
1121 Entry<?,?> current; // current entry
1122
1123 HashIterator() {
1124 expectedModCount = modCount;
1125 if (size > 0) { // advance to first entry
1126 Entry<?,?>[] t = table;
1127 while (index < t.length && (next = t[index++]) == null)
1128 ;
1129 }
1130 }
1131
1132 public final boolean hasNext() {
1133 return next != null;
1134 }
1135
1136 @SuppressWarnings("unchecked")
1137 final Entry<K,V> nextEntry() {
1138 if (modCount != expectedModCount)
1139 throw new ConcurrentModificationException();
1140 Entry<?,?> e = next;
1141 if (e == null)
1142 throw new NoSuchElementException();
1143
1144 if ((next = e.next) == null) {
1145 Entry<?,?>[] t = table;
1146 while (index < t.length && (next = t[index++]) == null)
1147 ;
1148 }
1149 current = e;
1150 return (Entry<K,V>)e;
1151 }
1152
1153 public void remove() {
1154 if (current == null)
1155 throw new IllegalStateException();
1156 if (modCount != expectedModCount)
1157 throw new ConcurrentModificationException();
1158 Object k = current.key;
1159 current = null;
1160 HashMap.this.removeEntryForKey(k);
1161 expectedModCount = modCount;
1162 }
1163 }
1164
1165 private final class ValueIterator extends HashIterator<V> {
1166 public V next() {
1167 return nextEntry().value;
1168 }
1169 }
1170
1171 private final class KeyIterator extends HashIterator<K> {
1172 public K next() {
1173 return nextEntry().getKey();
1174 }
1175 }
1176
1177 private final class EntryIterator extends HashIterator<Map.Entry<K,V>> {
1178 public Map.Entry<K,V> next() {
1179 return nextEntry();
1180 }
1181 }
1182
1183 // Subclass overrides these to alter behavior of views' iterator() method
1184 Iterator<K> newKeyIterator() {
1185 return new KeyIterator();
1186 }
1187 Iterator<V> newValueIterator() {
1188 return new ValueIterator();
1189 }
1190 Iterator<Map.Entry<K,V>> newEntryIterator() {
1191 return new EntryIterator();
1192 }
1193
1194
1195 // Views
1196
1197 private transient Set<Map.Entry<K,V>> entrySet = null;
1198
1199 /**
1200 * Returns a {@link Set} view of the keys contained in this map.
1201 * The set is backed by the map, so changes to the map are
1202 * reflected in the set, and vice-versa. If the map is modified
1203 * while an iteration over the set is in progress (except through
1204 * the iterator's own <tt>remove</tt> operation), the results of
1205 * the iteration are undefined. The set supports element removal,
1206 * which removes the corresponding mapping from the map, via the
1207 * <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
1208 * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>
1209 * operations. It does not support the <tt>add</tt> or <tt>addAll</tt>
1210 * operations.
1211 */
1212 public Set<K> keySet() {
1213 Set<K> ks = keySet;
1214 return (ks != null ? ks : (keySet = new KeySet()));
1215 }
1216
1217 private final class KeySet extends AbstractSet<K> {
1218 public Iterator<K> iterator() {
1219 return newKeyIterator();
1220 }
1221 public int size() {
1222 return size;
1223 }
1224 public boolean contains(Object o) {
1225 return containsKey(o);
1226 }
1227 public boolean remove(Object o) {
1228 return HashMap.this.removeEntryForKey(o) != null;
1229 }
1230 public void clear() {
1231 HashMap.this.clear();
1232 }
1233 }
1234
1235 /**
1236 * Returns a {@link Collection} view of the values contained in this map.
1237 * The collection is backed by the map, so changes to the map are
1238 * reflected in the collection, and vice-versa. If the map is
1239 * modified while an iteration over the collection is in progress
1240 * (except through the iterator's own <tt>remove</tt> operation),
1241 * the results of the iteration are undefined. The collection
1242 * supports element removal, which removes the corresponding
1243 * mapping from the map, via the <tt>Iterator.remove</tt>,
1244 * <tt>Collection.remove</tt>, <tt>removeAll</tt>,
1245 * <tt>retainAll</tt> and <tt>clear</tt> operations. It does not
1246 * support the <tt>add</tt> or <tt>addAll</tt> operations.
1247 */
1248 public Collection<V> values() {
1249 Collection<V> vs = values;
1250 return (vs != null ? vs : (values = new Values()));
1251 }
1252
1253 private final class Values extends AbstractCollection<V> {
1254 public Iterator<V> iterator() {
1255 return newValueIterator();
1256 }
1257 public int size() {
1258 return size;
1259 }
1260 public boolean contains(Object o) {
1261 return containsValue(o);
1262 }
1263 public void clear() {
1264 HashMap.this.clear();
1265 }
1266 }
1267
1268 /**
1269 * Returns a {@link Set} view of the mappings contained in this map.
1270 * The set is backed by the map, so changes to the map are
1271 * reflected in the set, and vice-versa. If the map is modified
1272 * while an iteration over the set is in progress (except through
1273 * the iterator's own <tt>remove</tt> operation, or through the
1274 * <tt>setValue</tt> operation on a map entry returned by the
1275 * iterator) the results of the iteration are undefined. The set
1276 * supports element removal, which removes the corresponding
1277 * mapping from the map, via the <tt>Iterator.remove</tt>,
1278 * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt> and
1279 * <tt>clear</tt> operations. It does not support the
1280 * <tt>add</tt> or <tt>addAll</tt> operations.
1281 *
1282 * @return a set view of the mappings contained in this map
1283 */
1284 public Set<Map.Entry<K,V>> entrySet() {
1285 return entrySet0();
1286 }
1287
1288 private Set<Map.Entry<K,V>> entrySet0() {
1289 Set<Map.Entry<K,V>> es = entrySet;
1290 return es != null ? es : (entrySet = new EntrySet());
1291 }
1292
1293 private final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
1294 public Iterator<Map.Entry<K,V>> iterator() {
1295 return newEntryIterator();
1296 }
1297 public boolean contains(Object o) {
1298 if (!(o instanceof Map.Entry))
1299 return false;
1300 Map.Entry<?,?> e = (Map.Entry<?,?>) o;
1301 Entry<K,V> candidate = getEntry(e.getKey());
1302 return candidate != null && candidate.equals(e);
1303 }
1304 public boolean remove(Object o) {
1305 return removeMapping(o) != null;
1306 }
1307 public int size() {
1308 return size;
1309 }
1310 public void clear() {
1311 HashMap.this.clear();
1312 }
1313 }
1314
1315 /**
1316 * Save the state of the <tt>HashMap</tt> instance to a stream (i.e.,
1317 * serialize it).
1318 *
1319 * @serialData The <i>capacity</i> of the HashMap (the length of the
1320 * bucket array) is emitted (int), followed by the
1321 * <i>size</i> (an int, the number of key-value
1322 * mappings), followed by the key (Object) and value (Object)
1323 * for each key-value mapping. The key-value mappings are
1324 * emitted in no particular order.
1325 */
1326 private void writeObject(java.io.ObjectOutputStream s)
1327 throws IOException
1328 {
1329 // Write out the threshold, loadfactor, and any hidden stuff
1330 s.defaultWriteObject();
1331
1332 // Write out number of buckets
1333 if (table==EMPTY_TABLE) {
1334 s.writeInt(roundUpToPowerOf2(threshold));
1335 } else {
1336 s.writeInt(table.length);
1337 }
1338
1339 // Write out size (number of Mappings)
1340 s.writeInt(size);
1341
1342 // Write out keys and values (alternating)
1343 if (size > 0) {
1344 for(Map.Entry<K,V> e : entrySet0()) {
1345 s.writeObject(e.getKey());
1346 s.writeObject(e.getValue());
1347 }
1348 }
1349 }
1350
1351 private static final long serialVersionUID = 362498820763181265L;
1352
1353 /**
1354 * Reconstitute the {@code HashMap} instance from a stream (i.e.,
1355 * deserialize it).
1356 */
1357 private void readObject(java.io.ObjectInputStream s)
1358 throws IOException, ClassNotFoundException
1359 {
1360 // Read in the threshold (ignored), loadfactor, and any hidden stuff
1361 s.defaultReadObject();
1362 if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
1363 throw new InvalidObjectException("Illegal load factor: " +
1364 loadFactor);
1365 }
1366
1367 // set other fields that need values
1368 Holder.UNSAFE.putIntVolatile(this, Holder.HASHSEED_OFFSET,
1369 sun.misc.Hashing.randomHashSeed(this));
1370 table = EMPTY_TABLE;
1371
1372 // Read in number of buckets
1373 s.readInt(); // ignored.
1374
1375 // Read number of mappings
1376 int mappings = s.readInt();
1377 if (mappings < 0)
1378 throw new InvalidObjectException("Illegal mappings count: " +
1379 mappings);
1380
1381 // capacity chosen by number of mappings and desired load (if >= 0.25)
1382 int capacity = (int) Math.min(
1383 mappings * Math.min(1 / loadFactor, 4.0f),
1384 // we have limits...
1385 HashMap.MAXIMUM_CAPACITY);
1386
1387 // allocate the bucket array;
1388 if (mappings > 0) {
1389 inflateTable(capacity);
1390 } else {
1391 threshold = capacity;
1392 }
1393
1394 init(); // Give subclass a chance to do its thing.
1395
1396 // Read the keys and values, and put the mappings in the HashMap
1397 for (int i=0; i<mappings; i++) {
1398 @SuppressWarnings("unchecked")
1399 K key = (K) s.readObject();
1400 @SuppressWarnings("unchecked")
1401 V value = (V) s.readObject();
1402 putForCreate(key, value);
1403 }
1404 }
1405
1406 // These methods are used when serializing HashSets
1407 int capacity() { return table.length; }
1408 float loadFactor() { return loadFactor; }
1409 }