1 /*
2 * Copyright (c) 1997, 2018, 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.IOException;
29 import java.io.InvalidObjectException;
30 import java.io.Serializable;
31 import java.lang.reflect.ParameterizedType;
32 import java.lang.reflect.Type;
33 import java.util.function.BiConsumer;
34 import java.util.function.BiFunction;
35 import java.util.function.Consumer;
36 import java.util.function.Function;
37 import jdk.internal.misc.SharedSecrets;
38
39 /**
40 * Hash table based implementation of the {@code Map} interface. This
41 * implementation provides all of the optional map operations, and permits
42 * {@code null} values and the {@code null} key. (The {@code HashMap}
43 * class is roughly equivalent to {@code Hashtable}, except that it is
44 * unsynchronized and permits nulls.) This class makes no guarantees as to
45 * the order of the map; in particular, it does not guarantee that the order
46 * will remain constant over time.
47 *
48 * <p>This implementation provides constant-time performance for the basic
49 * operations ({@code get} and {@code put}), assuming the hash function
50 * disperses the elements properly among the buckets. Iteration over
51 * collection views requires time proportional to the "capacity" of the
52 * {@code HashMap} instance (the number of buckets) plus its size (the number
53 * of key-value mappings). Thus, it's very important not to set the initial
54 * capacity too high (or the load factor too low) if iteration performance is
55 * important.
56 *
57 * <p>An instance of {@code HashMap} has two parameters that affect its
58 * performance: <i>initial capacity</i> and <i>load factor</i>. The
59 * <i>capacity</i> is the number of buckets in the hash table, and the initial
60 * capacity is simply the capacity at the time the hash table is created. The
61 * <i>load factor</i> is a measure of how full the hash table is allowed to
62 * get before its capacity is automatically increased. When the number of
63 * entries in the hash table exceeds the product of the load factor and the
64 * current capacity, the hash table is <i>rehashed</i> (that is, internal data
65 * structures are rebuilt) so that the hash table has approximately twice the
66 * number of buckets.
67 *
68 * <p>As a general rule, the default load factor (.75) offers a good
69 * tradeoff between time and space costs. Higher values decrease the
70 * space overhead but increase the lookup cost (reflected in most of
71 * the operations of the {@code HashMap} class, including
72 * {@code get} and {@code put}). The expected number of entries in
73 * the map and its load factor should be taken into account when
74 * setting its initial capacity, so as to minimize the number of
75 * rehash operations. If the initial capacity is greater than the
76 * maximum number of entries divided by the load factor, no rehash
77 * operations will ever occur.
78 *
79 * <p>If many mappings are to be stored in a {@code HashMap}
80 * instance, creating it with a sufficiently large capacity will allow
81 * the mappings to be stored more efficiently than letting it perform
82 * automatic rehashing as needed to grow the table. Note that using
83 * many keys with the same {@code hashCode()} is a sure way to slow
84 * down performance of any hash table. To ameliorate impact, when keys
85 * are {@link Comparable}, this class may use comparison order among
86 * keys to help break ties.
87 *
88 * <p><strong>Note that this implementation is not synchronized.</strong>
89 * If multiple threads access a hash map concurrently, and at least one of
90 * the threads modifies the map structurally, it <i>must</i> be
91 * synchronized externally. (A structural modification is any operation
92 * that adds or deletes one or more mappings; merely changing the value
93 * associated with a key that an instance already contains is not a
94 * structural modification.) This is typically accomplished by
95 * synchronizing on some object that naturally encapsulates the map.
96 *
97 * If no such object exists, the map should be "wrapped" using the
98 * {@link Collections#synchronizedMap Collections.synchronizedMap}
99 * method. This is best done at creation time, to prevent accidental
100 * unsynchronized access to the map:<pre>
101 * Map m = Collections.synchronizedMap(new HashMap(...));</pre>
102 *
103 * <p>The iterators returned by all of this class's "collection view methods"
104 * are <i>fail-fast</i>: if the map is structurally modified at any time after
105 * the iterator is created, in any way except through the iterator's own
106 * {@code remove} method, the iterator will throw a
107 * {@link ConcurrentModificationException}. Thus, in the face of concurrent
108 * modification, the iterator fails quickly and cleanly, rather than risking
109 * arbitrary, non-deterministic behavior at an undetermined time in the
110 * future.
111 *
112 * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
113 * as it is, generally speaking, impossible to make any hard guarantees in the
114 * presence of unsynchronized concurrent modification. Fail-fast iterators
115 * throw {@code ConcurrentModificationException} on a best-effort basis.
116 * Therefore, it would be wrong to write a program that depended on this
117 * exception for its correctness: <i>the fail-fast behavior of iterators
118 * should be used only to detect bugs.</i>
119 *
120 * <p>This class is a member of the
121 * <a href="{@docRoot}/java.base/java/util/package-summary.html#CollectionsFramework">
122 * Java Collections Framework</a>.
123 *
124 * @param <K> the type of keys maintained by this map
125 * @param <V> the type of mapped values
126 *
127 * @author Doug Lea
128 * @author Josh Bloch
129 * @author Arthur van Hoff
130 * @author Neal Gafter
131 * @see Object#hashCode()
132 * @see Collection
133 * @see Map
134 * @see TreeMap
135 * @see Hashtable
136 * @since 1.2
137 */
138 public class HashMap<K,V> extends AbstractMap<K,V>
139 implements Map<K,V>, Cloneable, Serializable {
140
141 private static final long serialVersionUID = 362498820763181265L;
142
143 /*
144 * Implementation notes.
145 *
146 * This map usually acts as a binned (bucketed) hash table, but
147 * when bins get too large, they are transformed into bins of
148 * TreeNodes, each structured similarly to those in
149 * java.util.TreeMap. Most methods try to use normal bins, but
150 * relay to TreeNode methods when applicable (simply by checking
151 * instanceof a node). Bins of TreeNodes may be traversed and
152 * used like any others, but additionally support faster lookup
153 * when overpopulated. However, since the vast majority of bins in
154 * normal use are not overpopulated, checking for existence of
155 * tree bins may be delayed in the course of table methods.
156 *
157 * Tree bins (i.e., bins whose elements are all TreeNodes) are
158 * ordered primarily by hashCode, but in the case of ties, if two
159 * elements are of the same "class C implements Comparable<C>",
160 * type then their compareTo method is used for ordering. (We
161 * conservatively check generic types via reflection to validate
162 * this -- see method comparableClassFor). The added complexity
163 * of tree bins is worthwhile in providing worst-case O(log n)
164 * operations when keys either have distinct hashes or are
165 * orderable, Thus, performance degrades gracefully under
166 * accidental or malicious usages in which hashCode() methods
167 * return values that are poorly distributed, as well as those in
168 * which many keys share a hashCode, so long as they are also
169 * Comparable. (If neither of these apply, we may waste about a
170 * factor of two in time and space compared to taking no
171 * precautions. But the only known cases stem from poor user
172 * programming practices that are already so slow that this makes
173 * little difference.)
174 *
175 * Because TreeNodes are about twice the size of regular nodes, we
176 * use them only when bins contain enough nodes to warrant use
177 * (see TREEIFY_THRESHOLD). And when they become too small (due to
178 * removal or resizing) they are converted back to plain bins. In
179 * usages with well-distributed user hashCodes, tree bins are
180 * rarely used. Ideally, under random hashCodes, the frequency of
181 * nodes in bins follows a Poisson distribution
182 * (http://en.wikipedia.org/wiki/Poisson_distribution) with a
183 * parameter of about 0.5 on average for the default resizing
184 * threshold of 0.75, although with a large variance because of
185 * resizing granularity. Ignoring variance, the expected
186 * occurrences of list size k are (exp(-0.5) * pow(0.5, k) /
187 * factorial(k)). The first values are:
188 *
189 * 0: 0.60653066
190 * 1: 0.30326533
191 * 2: 0.07581633
192 * 3: 0.01263606
193 * 4: 0.00157952
194 * 5: 0.00015795
195 * 6: 0.00001316
196 * 7: 0.00000094
197 * 8: 0.00000006
198 * more: less than 1 in ten million
199 *
200 * The root of a tree bin is normally its first node. However,
201 * sometimes (currently only upon Iterator.remove), the root might
202 * be elsewhere, but can be recovered following parent links
203 * (method TreeNode.root()).
204 *
205 * All applicable internal methods accept a hash code as an
206 * argument (as normally supplied from a public method), allowing
207 * them to call each other without recomputing user hashCodes.
208 * Most internal methods also accept a "tab" argument, that is
209 * normally the current table, but may be a new or old one when
210 * resizing or converting.
211 *
212 * When bin lists are treeified, split, or untreeified, we keep
213 * them in the same relative access/traversal order (i.e., field
214 * Node.next) to better preserve locality, and to slightly
215 * simplify handling of splits and traversals that invoke
216 * iterator.remove. When using comparators on insertion, to keep a
217 * total ordering (or as close as is required here) across
218 * rebalancings, we compare classes and identityHashCodes as
219 * tie-breakers.
220 *
221 * The use and transitions among plain vs tree modes is
222 * complicated by the existence of subclass LinkedHashMap. See
223 * below for hook methods defined to be invoked upon insertion,
224 * removal and access that allow LinkedHashMap internals to
225 * otherwise remain independent of these mechanics. (This also
226 * requires that a map instance be passed to some utility methods
227 * that may create new nodes.)
228 *
229 * The concurrent-programming-like SSA-based coding style helps
230 * avoid aliasing errors amid all of the twisty pointer operations.
231 */
232
233 /**
234 * The default initial capacity - MUST be a power of two.
235 */
236 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
237
238 /**
239 * The maximum capacity, used if a higher value is implicitly specified
240 * by either of the constructors with arguments.
241 * MUST be a power of two <= 1<<30.
242 */
243 static final int MAXIMUM_CAPACITY = 1 << 30;
244
245 /**
246 * The load factor used when none specified in constructor.
247 */
248 static final float DEFAULT_LOAD_FACTOR = 0.75f;
249
250 /**
251 * The bin count threshold for using a tree rather than list for a
252 * bin. Bins are converted to trees when adding an element to a
253 * bin with at least this many nodes. The value must be greater
254 * than 2 and should be at least 8 to mesh with assumptions in
255 * tree removal about conversion back to plain bins upon
256 * shrinkage.
257 */
258 static final int TREEIFY_THRESHOLD = 8;
259
260 /**
261 * The bin count threshold for untreeifying a (split) bin during a
262 * resize operation. Should be less than TREEIFY_THRESHOLD, and at
263 * most 6 to mesh with shrinkage detection under removal.
264 */
265 static final int UNTREEIFY_THRESHOLD = 6;
266
267 /**
268 * The smallest table capacity for which bins may be treeified.
269 * (Otherwise the table is resized if too many nodes in a bin.)
270 * Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
271 * between resizing and treeification thresholds.
272 */
273 static final int MIN_TREEIFY_CAPACITY = 64;
274
275 /**
276 * Basic hash bin node, used for most entries. (See below for
277 * TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
278 */
279 static class Node<K,V> implements Map.Entry<K,V> {
280 final int hash;
281 final K key;
282 V value;
283 Node<K,V> next;
284
285 Node(int hash, K key, V value, Node<K,V> next) {
286 this.hash = hash;
287 this.key = key;
288 this.value = value;
289 this.next = next;
290 }
291
292 public final K getKey() { return key; }
293 public final V getValue() { return value; }
294 public final String toString() { return key + "=" + value; }
295
296 public final int hashCode() {
297 return Objects.hashCode(key) ^ Objects.hashCode(value);
298 }
299
300 public final V setValue(V newValue) {
301 V oldValue = value;
302 value = newValue;
303 return oldValue;
304 }
305
306 public final boolean equals(Object o) {
307 if (o == this)
308 return true;
309 if (o instanceof Map.Entry) {
310 Map.Entry<?,?> e = (Map.Entry<?,?>)o;
311 if (Objects.equals(key, e.getKey()) &&
312 Objects.equals(value, e.getValue()))
313 return true;
314 }
315 return false;
316 }
317 }
318
319 /* ---------------- Static utilities -------------- */
320
321 /**
322 * Computes key.hashCode() and spreads (XORs) higher bits of hash
323 * to lower. Because the table uses power-of-two masking, sets of
324 * hashes that vary only in bits above the current mask will
325 * always collide. (Among known examples are sets of Float keys
326 * holding consecutive whole numbers in small tables.) So we
327 * apply a transform that spreads the impact of higher bits
328 * downward. There is a tradeoff between speed, utility, and
329 * quality of bit-spreading. Because many common sets of hashes
330 * are already reasonably distributed (so don't benefit from
331 * spreading), and because we use trees to handle large sets of
332 * collisions in bins, we just XOR some shifted bits in the
333 * cheapest possible way to reduce systematic lossage, as well as
334 * to incorporate impact of the highest bits that would otherwise
335 * never be used in index calculations because of table bounds.
336 */
337 static final int hash(Object key) {
338 int h;
339 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
340 }
341
342 /**
343 * Returns x's Class if it is of the form "class C implements
344 * Comparable<C>", else null.
345 */
346 static Class<?> comparableClassFor(Object x) {
347 if (x instanceof Comparable) {
348 Class<?> c; Type[] ts, as; ParameterizedType p;
349 if ((c = x.getClass()) == String.class) // bypass checks
350 return c;
351 if ((ts = c.getGenericInterfaces()) != null) {
352 for (Type t : ts) {
353 if ((t instanceof ParameterizedType) &&
354 ((p = (ParameterizedType) t).getRawType() ==
355 Comparable.class) &&
356 (as = p.getActualTypeArguments()) != null &&
357 as.length == 1 && as[0] == c) // type arg is c
358 return c;
359 }
360 }
361 }
362 return null;
363 }
364
365 /**
366 * Returns k.compareTo(x) if x matches kc (k's screened comparable
367 * class), else 0.
368 */
369 @SuppressWarnings({"rawtypes","unchecked"}) // for cast to Comparable
370 static int compareComparables(Class<?> kc, Object k, Object x) {
371 return (x == null || x.getClass() != kc ? 0 :
372 ((Comparable)k).compareTo(x));
373 }
374
375 /**
376 * Returns a power of two size for the given target capacity.
377 */
378 static final int tableSizeFor(int cap) {
379 int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);
380 return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
381 }
382
383 /* ---------------- Fields -------------- */
384
385 /**
386 * The table, initialized on first use, and resized as
387 * necessary. When allocated, length is always a power of two.
388 * (We also tolerate length zero in some operations to allow
389 * bootstrapping mechanics that are currently not needed.)
390 */
391 transient Node<K,V>[] table;
392
393 /**
394 * Holds cached entrySet(). Note that AbstractMap fields are used
395 * for keySet() and values().
396 */
397 transient Set<Map.Entry<K,V>> entrySet;
398
399 /**
400 * The number of key-value mappings contained in this map.
401 */
402 transient int size;
403
404 /**
405 * The number of times this HashMap has been structurally modified
406 * Structural modifications are those that change the number of mappings in
407 * the HashMap or otherwise modify its internal structure (e.g.,
408 * rehash). This field is used to make iterators on Collection-views of
409 * the HashMap fail-fast. (See ConcurrentModificationException).
410 */
411 transient int modCount;
412
413 /**
414 * The next size value at which to resize (capacity * load factor).
415 *
416 * @serial
417 */
418 // (The javadoc description is true upon serialization.
419 // Additionally, if the table array has not been allocated, this
420 // field holds the initial array capacity, or zero signifying
421 // DEFAULT_INITIAL_CAPACITY.)
422 int threshold;
423
424 /**
425 * The load factor for the hash table.
426 *
427 * @serial
428 */
429 final float loadFactor;
430
431 /* ---------------- Public operations -------------- */
432
433 /**
434 * Constructs an empty {@code HashMap} with the specified initial
435 * capacity and load factor.
436 *
437 * @param initialCapacity the initial capacity
438 * @param loadFactor the load factor
439 * @throws IllegalArgumentException if the initial capacity is negative
440 * or the load factor is nonpositive
441 */
442 public HashMap(int initialCapacity, float loadFactor) {
443 if (initialCapacity < 0)
444 throw new IllegalArgumentException("Illegal initial capacity: " +
445 initialCapacity);
446 if (initialCapacity > MAXIMUM_CAPACITY)
447 initialCapacity = MAXIMUM_CAPACITY;
448 if (loadFactor <= 0 || Float.isNaN(loadFactor))
449 throw new IllegalArgumentException("Illegal load factor: " +
450 loadFactor);
451 this.loadFactor = loadFactor;
452 this.threshold = tableSizeFor(initialCapacity);
453 }
454
455 /**
456 * Constructs an empty {@code HashMap} with the specified initial
457 * capacity and the default load factor (0.75).
458 *
459 * @param initialCapacity the initial capacity.
460 * @throws IllegalArgumentException if the initial capacity is negative.
461 */
462 public HashMap(int initialCapacity) {
463 this(initialCapacity, DEFAULT_LOAD_FACTOR);
464 }
465
466 /**
467 * Constructs an empty {@code HashMap} with the default initial capacity
468 * (16) and the default load factor (0.75).
469 */
470 public HashMap() {
471 this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
472 }
473
474 /**
475 * Constructs a new {@code HashMap} with the same mappings as the
476 * specified {@code Map}. The {@code HashMap} is created with
477 * default load factor (0.75) and an initial capacity sufficient to
478 * hold the mappings in the specified {@code Map}.
479 *
480 * @param m the map whose mappings are to be placed in this map
481 * @throws NullPointerException if the specified map is null
482 */
483 public HashMap(Map<? extends K, ? extends V> m) {
484 this.loadFactor = DEFAULT_LOAD_FACTOR;
485 putMapEntries(m, false);
486 }
487
488 /**
489 * Implements Map.putAll and Map constructor.
490 *
491 * @param m the map
492 * @param evict false when initially constructing this map, else
493 * true (relayed to method afterNodeInsertion).
494 */
495 final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
496 int s = m.size();
497 if (s > 0) {
498 if (table == null) { // pre-size
499 float ft = ((float)s / loadFactor) + 1.0F;
500 int t = ((ft < (float)MAXIMUM_CAPACITY) ?
501 (int)ft : MAXIMUM_CAPACITY);
502 if (t > threshold)
503 threshold = tableSizeFor(t);
504 }
505 else if (s > threshold)
506 resize();
507 for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
508 K key = e.getKey();
509 V value = e.getValue();
510 putVal(hash(key), key, value, false, evict);
511 }
512 }
513 }
514
515 /**
516 * Returns the number of key-value mappings in this map.
517 *
518 * @return the number of key-value mappings in this map
519 */
520 public int size() {
521 return size;
522 }
523
524 /**
525 * Returns {@code true} if this map contains no key-value mappings.
526 *
527 * @return {@code true} if this map contains no key-value mappings
528 */
529 public boolean isEmpty() {
530 return size == 0;
531 }
532
533 /**
534 * Returns the value to which the specified key is mapped,
535 * or {@code null} if this map contains no mapping for the key.
536 *
537 * <p>More formally, if this map contains a mapping from a key
538 * {@code k} to a value {@code v} such that {@code (key==null ? k==null :
539 * key.equals(k))}, then this method returns {@code v}; otherwise
540 * it returns {@code null}. (There can be at most one such mapping.)
541 *
542 * <p>A return value of {@code null} does not <i>necessarily</i>
543 * indicate that the map contains no mapping for the key; it's also
544 * possible that the map explicitly maps the key to {@code null}.
545 * The {@link #containsKey containsKey} operation may be used to
546 * distinguish these two cases.
547 *
548 * @see #put(Object, Object)
549 */
550 public V get(Object key) {
551 Node<K,V> e;
552 return (e = getNode(hash(key), key)) == null ? null : e.value;
553 }
554
555 /**
556 * Implements Map.get and related methods.
557 *
558 * @param hash hash for key
559 * @param key the key
560 * @return the node, or null if none
561 */
562 final Node<K,V> getNode(int hash, Object key) {
563 Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
564 if ((tab = table) != null && (n = tab.length) > 0 &&
565 (first = tab[(n - 1) & hash]) != null) {
566 if (first.hash == hash && // always check first node
567 ((k = first.key) == key || (key != null && key.equals(k))))
568 return first;
569 if ((e = first.next) != null) {
570 if (first instanceof TreeNode)
571 return ((TreeNode<K,V>)first).getTreeNode(hash, key);
572 do {
573 if (e.hash == hash &&
574 ((k = e.key) == key || (key != null && key.equals(k))))
575 return e;
576 } while ((e = e.next) != null);
577 }
578 }
579 return null;
580 }
581
582 /**
583 * Returns {@code true} if this map contains a mapping for the
584 * specified key.
585 *
586 * @param key The key whose presence in this map is to be tested
587 * @return {@code true} if this map contains a mapping for the specified
588 * key.
589 */
590 public boolean containsKey(Object key) {
591 return getNode(hash(key), key) != null;
592 }
593
594 /**
595 * Associates the specified value with the specified key in this map.
596 * If the map previously contained a mapping for the key, the old
597 * value is replaced.
598 *
599 * @param key key with which the specified value is to be associated
600 * @param value value to be associated with the specified key
601 * @return the previous value associated with {@code key}, or
602 * {@code null} if there was no mapping for {@code key}.
603 * (A {@code null} return can also indicate that the map
604 * previously associated {@code null} with {@code key}.)
605 */
606 public V put(K key, V value) {
607 return putVal(hash(key), key, value, false, true);
608 }
609
610 /**
611 * Implements Map.put and related methods.
612 *
613 * @param hash hash for key
614 * @param key the key
615 * @param value the value to put
616 * @param onlyIfAbsent if true, don't change existing value
617 * @param evict if false, the table is in creation mode.
618 * @return previous value, or null if none
619 */
620 final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
621 boolean evict) {
622 Node<K,V>[] tab; Node<K,V> p; int n, i;
623 if ((tab = table) == null || (n = tab.length) == 0)
624 n = (tab = resize()).length;
625 if ((p = tab[i = (n - 1) & hash]) == null)
626 tab[i] = newNode(hash, key, value, null);
627 else {
628 Node<K,V> e; K k;
629 if (p.hash == hash &&
630 ((k = p.key) == key || (key != null && key.equals(k))))
631 e = p;
632 else if (p instanceof TreeNode)
633 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
634 else {
635 for (int binCount = 0; ; ++binCount) {
636 if ((e = p.next) == null) {
637 p.next = newNode(hash, key, value, null);
638 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
639 treeifyBin(tab, hash);
640 break;
641 }
642 if (e.hash == hash &&
643 ((k = e.key) == key || (key != null && key.equals(k))))
644 break;
645 p = e;
646 }
647 }
648 if (e != null) { // existing mapping for key
649 V oldValue = e.value;
650 if (!onlyIfAbsent || oldValue == null)
651 e.value = value;
652 afterNodeAccess(e);
653 return oldValue;
654 }
655 }
656 ++modCount;
657 if (++size > threshold)
658 resize();
659 afterNodeInsertion(evict);
660 return null;
661 }
662
663 /**
664 * Initializes or doubles table size. If null, allocates in
665 * accord with initial capacity target held in field threshold.
666 * Otherwise, because we are using power-of-two expansion, the
667 * elements from each bin must either stay at same index, or move
668 * with a power of two offset in the new table.
669 *
670 * @return the table
671 */
672 final Node<K,V>[] resize() {
673 Node<K,V>[] oldTab = table;
674 int oldCap = (oldTab == null) ? 0 : oldTab.length;
675 int oldThr = threshold;
676 int newCap, newThr = 0;
677 if (oldCap > 0) {
678 if (oldCap >= MAXIMUM_CAPACITY) {
679 threshold = Integer.MAX_VALUE;
680 return oldTab;
681 }
682 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
683 oldCap >= DEFAULT_INITIAL_CAPACITY)
684 newThr = oldThr << 1; // double threshold
685 }
686 else if (oldThr > 0) // initial capacity was placed in threshold
687 newCap = oldThr;
688 else { // zero initial threshold signifies using defaults
689 newCap = DEFAULT_INITIAL_CAPACITY;
690 newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
691 }
692 if (newThr == 0) {
693 float ft = (float)newCap * loadFactor;
694 newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
695 (int)ft : Integer.MAX_VALUE);
696 }
697 threshold = newThr;
698 @SuppressWarnings({"rawtypes","unchecked"})
699 Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
700 table = newTab;
701 if (oldTab != null) {
702 for (int j = 0; j < oldCap; ++j) {
703 Node<K,V> e;
704 if ((e = oldTab[j]) != null) {
705 oldTab[j] = null;
706 if (e.next == null)
707 newTab[e.hash & (newCap - 1)] = e;
708 else if (e instanceof TreeNode)
709 ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
710 else { // preserve order
711 Node<K,V> loHead = null, loTail = null;
712 Node<K,V> hiHead = null, hiTail = null;
713 Node<K,V> next;
714 do {
715 next = e.next;
716 if ((e.hash & oldCap) == 0) {
717 if (loTail == null)
718 loHead = e;
719 else
720 loTail.next = e;
721 loTail = e;
722 }
723 else {
724 if (hiTail == null)
725 hiHead = e;
726 else
727 hiTail.next = e;
728 hiTail = e;
729 }
730 } while ((e = next) != null);
731 if (loTail != null) {
732 loTail.next = null;
733 newTab[j] = loHead;
734 }
735 if (hiTail != null) {
736 hiTail.next = null;
737 newTab[j + oldCap] = hiHead;
738 }
739 }
740 }
741 }
742 }
743 return newTab;
744 }
745
746 /**
747 * Replaces all linked nodes in bin at index for given hash unless
748 * table is too small, in which case resizes instead.
749 */
750 final void treeifyBin(Node<K,V>[] tab, int hash) {
751 int n, index; Node<K,V> e;
752 if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
753 resize();
754 else if ((e = tab[index = (n - 1) & hash]) != null) {
755 TreeNode<K,V> hd = null, tl = null;
756 do {
757 TreeNode<K,V> p = replacementTreeNode(e, null);
758 if (tl == null)
759 hd = p;
760 else {
761 p.prev = tl;
762 tl.next = p;
763 }
764 tl = p;
765 } while ((e = e.next) != null);
766 if ((tab[index] = hd) != null)
767 hd.treeify(tab);
768 }
769 }
770
771 /**
772 * Copies all of the mappings from the specified map to this map.
773 * These mappings will replace any mappings that this map had for
774 * any of the keys currently in the specified map.
775 *
776 * @param m mappings to be stored in this map
777 * @throws NullPointerException if the specified map is null
778 */
779 public void putAll(Map<? extends K, ? extends V> m) {
780 putMapEntries(m, true);
781 }
782
783 /**
784 * Removes the mapping for the specified key from this map if present.
785 *
786 * @param key key whose mapping is to be removed from the map
787 * @return the previous value associated with {@code key}, or
788 * {@code null} if there was no mapping for {@code key}.
789 * (A {@code null} return can also indicate that the map
790 * previously associated {@code null} with {@code key}.)
791 */
792 public V remove(Object key) {
793 Node<K,V> e;
794 return (e = removeNode(hash(key), key, null, false, true)) == null ?
795 null : e.value;
796 }
797
798 /**
799 * Implements Map.remove and related methods.
800 *
801 * @param hash hash for key
802 * @param key the key
803 * @param value the value to match if matchValue, else ignored
804 * @param matchValue if true only remove if value is equal
805 * @param movable if false do not move other nodes while removing
806 * @return the node, or null if none
807 */
808 final Node<K,V> removeNode(int hash, Object key, Object value,
809 boolean matchValue, boolean movable) {
810 Node<K,V>[] tab; Node<K,V> p; int n, index;
811 if ((tab = table) != null && (n = tab.length) > 0 &&
812 (p = tab[index = (n - 1) & hash]) != null) {
813 Node<K,V> node = null, e; K k; V v;
814 if (p.hash == hash &&
815 ((k = p.key) == key || (key != null && key.equals(k))))
816 node = p;
817 else if ((e = p.next) != null) {
818 if (p instanceof TreeNode)
819 node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
820 else {
821 do {
822 if (e.hash == hash &&
823 ((k = e.key) == key ||
824 (key != null && key.equals(k)))) {
825 node = e;
826 break;
827 }
828 p = e;
829 } while ((e = e.next) != null);
830 }
831 }
832 if (node != null && (!matchValue || (v = node.value) == value ||
833 (value != null && value.equals(v)))) {
834 if (node instanceof TreeNode)
835 ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
836 else if (node == p)
837 tab[index] = node.next;
838 else
839 p.next = node.next;
840 ++modCount;
841 --size;
842 afterNodeRemoval(node);
843 return node;
844 }
845 }
846 return null;
847 }
848
849 /**
850 * Removes all of the mappings from this map.
851 * The map will be empty after this call returns.
852 */
853 public void clear() {
854 Node<K,V>[] tab;
855 modCount++;
856 if ((tab = table) != null && size > 0) {
857 size = 0;
858 for (int i = 0; i < tab.length; ++i)
859 tab[i] = null;
860 }
861 }
862
863 /**
864 * Returns {@code true} if this map maps one or more keys to the
865 * specified value.
866 *
867 * @param value value whose presence in this map is to be tested
868 * @return {@code true} if this map maps one or more keys to the
869 * specified value
870 */
871 public boolean containsValue(Object value) {
872 Node<K,V>[] tab; V v;
873 if ((tab = table) != null && size > 0) {
874 for (Node<K,V> e : tab) {
875 for (; e != null; e = e.next) {
876 if ((v = e.value) == value ||
877 (value != null && value.equals(v)))
878 return true;
879 }
880 }
881 }
882 return false;
883 }
884
885 /**
886 * Returns a {@link Set} view of the keys contained in this map.
887 * The set is backed by the map, so changes to the map are
888 * reflected in the set, and vice-versa. If the map is modified
889 * while an iteration over the set is in progress (except through
890 * the iterator's own {@code remove} operation), the results of
891 * the iteration are undefined. The set supports element removal,
892 * which removes the corresponding mapping from the map, via the
893 * {@code Iterator.remove}, {@code Set.remove},
894 * {@code removeAll}, {@code retainAll}, and {@code clear}
895 * operations. It does not support the {@code add} or {@code addAll}
896 * operations.
897 *
898 * @return a set view of the keys contained in this map
899 */
900 public Set<K> keySet() {
901 Set<K> ks = keySet;
902 if (ks == null) {
903 ks = new KeySet();
904 keySet = ks;
905 }
906 return ks;
907 }
908
909 final class KeySet extends AbstractSet<K> {
910 public final int size() { return size; }
911 public final void clear() { HashMap.this.clear(); }
912 public final Iterator<K> iterator() { return new KeyIterator(); }
913 public final boolean contains(Object o) { return containsKey(o); }
914 public final boolean remove(Object key) {
915 return removeNode(hash(key), key, null, false, true) != null;
916 }
917 public final Spliterator<K> spliterator() {
918 return new KeySpliterator<>(HashMap.this, 0, -1, 0, 0);
919 }
920 public final void forEach(Consumer<? super K> action) {
921 Node<K,V>[] tab;
922 if (action == null)
923 throw new NullPointerException();
924 if (size > 0 && (tab = table) != null) {
925 int mc = modCount;
926 for (Node<K,V> e : tab) {
927 for (; e != null; e = e.next)
928 action.accept(e.key);
929 }
930 if (modCount != mc)
931 throw new ConcurrentModificationException();
932 }
933 }
934 }
935
936 /**
937 * Returns a {@link Collection} view of the values contained in this map.
938 * The collection is backed by the map, so changes to the map are
939 * reflected in the collection, and vice-versa. If the map is
940 * modified while an iteration over the collection is in progress
941 * (except through the iterator's own {@code remove} operation),
942 * the results of the iteration are undefined. The collection
943 * supports element removal, which removes the corresponding
944 * mapping from the map, via the {@code Iterator.remove},
945 * {@code Collection.remove}, {@code removeAll},
946 * {@code retainAll} and {@code clear} operations. It does not
947 * support the {@code add} or {@code addAll} operations.
948 *
949 * @return a view of the values contained in this map
950 */
951 public Collection<V> values() {
952 Collection<V> vs = values;
953 if (vs == null) {
954 vs = new Values();
955 values = vs;
956 }
957 return vs;
958 }
959
960 final class Values extends AbstractCollection<V> {
961 public final int size() { return size; }
962 public final void clear() { HashMap.this.clear(); }
963 public final Iterator<V> iterator() { return new ValueIterator(); }
964 public final boolean contains(Object o) { return containsValue(o); }
965 public final Spliterator<V> spliterator() {
966 return new ValueSpliterator<>(HashMap.this, 0, -1, 0, 0);
967 }
968 public final void forEach(Consumer<? super V> action) {
969 Node<K,V>[] tab;
970 if (action == null)
971 throw new NullPointerException();
972 if (size > 0 && (tab = table) != null) {
973 int mc = modCount;
974 for (Node<K,V> e : tab) {
975 for (; e != null; e = e.next)
976 action.accept(e.value);
977 }
978 if (modCount != mc)
979 throw new ConcurrentModificationException();
980 }
981 }
982 }
983
984 /**
985 * Returns a {@link Set} view of the mappings contained in this map.
986 * The set is backed by the map, so changes to the map are
987 * reflected in the set, and vice-versa. If the map is modified
988 * while an iteration over the set is in progress (except through
989 * the iterator's own {@code remove} operation, or through the
990 * {@code setValue} operation on a map entry returned by the
991 * iterator) the results of the iteration are undefined. The set
992 * supports element removal, which removes the corresponding
993 * mapping from the map, via the {@code Iterator.remove},
994 * {@code Set.remove}, {@code removeAll}, {@code retainAll} and
995 * {@code clear} operations. It does not support the
996 * {@code add} or {@code addAll} operations.
997 *
998 * @return a set view of the mappings contained in this map
999 */
1000 public Set<Map.Entry<K,V>> entrySet() {
1001 Set<Map.Entry<K,V>> es;
1002 return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;
1003 }
1004
1005 final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
1006 public final int size() { return size; }
1007 public final void clear() { HashMap.this.clear(); }
1008 public final Iterator<Map.Entry<K,V>> iterator() {
1009 return new EntryIterator();
1010 }
1011 public final boolean contains(Object o) {
1012 if (!(o instanceof Map.Entry))
1013 return false;
1014 Map.Entry<?,?> e = (Map.Entry<?,?>) o;
1015 Object key = e.getKey();
1016 Node<K,V> candidate = getNode(hash(key), key);
1017 return candidate != null && candidate.equals(e);
1018 }
1019 public final boolean remove(Object o) {
1020 if (o instanceof Map.Entry) {
1021 Map.Entry<?,?> e = (Map.Entry<?,?>) o;
1022 Object key = e.getKey();
1023 Object value = e.getValue();
1024 return removeNode(hash(key), key, value, true, true) != null;
1025 }
1026 return false;
1027 }
1028 public final Spliterator<Map.Entry<K,V>> spliterator() {
1029 return new EntrySpliterator<>(HashMap.this, 0, -1, 0, 0);
1030 }
1031 public final void forEach(Consumer<? super Map.Entry<K,V>> action) {
1032 Node<K,V>[] tab;
1033 if (action == null)
1034 throw new NullPointerException();
1035 if (size > 0 && (tab = table) != null) {
1036 int mc = modCount;
1037 for (Node<K,V> e : tab) {
1038 for (; e != null; e = e.next)
1039 action.accept(e);
1040 }
1041 if (modCount != mc)
1042 throw new ConcurrentModificationException();
1043 }
1044 }
1045 }
1046
1047 // Overrides of JDK8 Map extension methods
1048
1049 @Override
1050 public V getOrDefault(Object key, V defaultValue) {
1051 Node<K,V> e;
1052 return (e = getNode(hash(key), key)) == null ? defaultValue : e.value;
1053 }
1054
1055 @Override
1056 public V putIfAbsent(K key, V value) {
1057 return putVal(hash(key), key, value, true, true);
1058 }
1059
1060 @Override
1061 public boolean remove(Object key, Object value) {
1062 return removeNode(hash(key), key, value, true, true) != null;
1063 }
1064
1065 @Override
1066 public boolean replace(K key, V oldValue, V newValue) {
1067 Node<K,V> e; V v;
1068 if ((e = getNode(hash(key), key)) != null &&
1069 ((v = e.value) == oldValue || (v != null && v.equals(oldValue)))) {
1070 e.value = newValue;
1071 afterNodeAccess(e);
1072 return true;
1073 }
1074 return false;
1075 }
1076
1077 @Override
1078 public V replace(K key, V value) {
1079 Node<K,V> e;
1080 if ((e = getNode(hash(key), key)) != null) {
1081 V oldValue = e.value;
1082 e.value = value;
1083 afterNodeAccess(e);
1084 return oldValue;
1085 }
1086 return null;
1087 }
1088
1089 /**
1090 * {@inheritDoc}
1091 *
1092 * <p>This method will, on a best-effort basis, throw a
1093 * {@link ConcurrentModificationException} if it is detected that the
1094 * mapping function modifies this map during computation.
1095 *
1096 * @throws ConcurrentModificationException if it is detected that the
1097 * mapping function modified this map
1098 */
1099 @Override
1100 public V computeIfAbsent(K key,
1101 Function<? super K, ? extends V> mappingFunction) {
1102 if (mappingFunction == null)
1103 throw new NullPointerException();
1104 int hash = hash(key);
1105 Node<K,V>[] tab; Node<K,V> first; int n, i;
1106 int binCount = 0;
1107 TreeNode<K,V> t = null;
1108 Node<K,V> old = null;
1109 if (size > threshold || (tab = table) == null ||
1110 (n = tab.length) == 0)
1111 n = (tab = resize()).length;
1112 if ((first = tab[i = (n - 1) & hash]) != null) {
1113 if (first instanceof TreeNode)
1114 old = (t = (TreeNode<K,V>)first).getTreeNode(hash, key);
1115 else {
1116 Node<K,V> e = first; K k;
1117 do {
1118 if (e.hash == hash &&
1119 ((k = e.key) == key || (key != null && key.equals(k)))) {
1120 old = e;
1121 break;
1122 }
1123 ++binCount;
1124 } while ((e = e.next) != null);
1125 }
1126 V oldValue;
1127 if (old != null && (oldValue = old.value) != null) {
1128 afterNodeAccess(old);
1129 return oldValue;
1130 }
1131 }
1132 int mc = modCount;
1133 V v = mappingFunction.apply(key);
1134 if (mc != modCount) { throw new ConcurrentModificationException(); }
1135 if (v == null) {
1136 return null;
1137 } else if (old != null) {
1138 old.value = v;
1139 afterNodeAccess(old);
1140 return v;
1141 }
1142 else if (t != null)
1143 t.putTreeVal(this, tab, hash, key, v);
1144 else {
1145 tab[i] = newNode(hash, key, v, first);
1146 if (binCount >= TREEIFY_THRESHOLD - 1)
1147 treeifyBin(tab, hash);
1148 }
1149 modCount = mc + 1;
1150 ++size;
1151 afterNodeInsertion(true);
1152 return v;
1153 }
1154
1155 /**
1156 * {@inheritDoc}
1157 *
1158 * <p>This method will, on a best-effort basis, throw a
1159 * {@link ConcurrentModificationException} if it is detected that the
1160 * remapping function modifies this map during computation.
1161 *
1162 * @throws ConcurrentModificationException if it is detected that the
1163 * remapping function modified this map
1164 */
1165 @Override
1166 public V computeIfPresent(K key,
1167 BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
1168 if (remappingFunction == null)
1169 throw new NullPointerException();
1170 Node<K,V> e; V oldValue;
1171 int hash = hash(key);
1172 if ((e = getNode(hash, key)) != null &&
1173 (oldValue = e.value) != null) {
1174 int mc = modCount;
1175 V v = remappingFunction.apply(key, oldValue);
1176 if (mc != modCount) { throw new ConcurrentModificationException(); }
1177 if (v != null) {
1178 e.value = v;
1179 afterNodeAccess(e);
1180 return v;
1181 }
1182 else
1183 removeNode(hash, key, null, false, true);
1184 }
1185 return null;
1186 }
1187
1188 /**
1189 * {@inheritDoc}
1190 *
1191 * <p>This method will, on a best-effort basis, throw a
1192 * {@link ConcurrentModificationException} if it is detected that the
1193 * remapping function modifies this map during computation.
1194 *
1195 * @throws ConcurrentModificationException if it is detected that the
1196 * remapping function modified this map
1197 */
1198 @Override
1199 public V compute(K key,
1200 BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
1201 if (remappingFunction == null)
1202 throw new NullPointerException();
1203 int hash = hash(key);
1204 Node<K,V>[] tab; Node<K,V> first; int n, i;
1205 int binCount = 0;
1206 TreeNode<K,V> t = null;
1207 Node<K,V> old = null;
1208 if (size > threshold || (tab = table) == null ||
1209 (n = tab.length) == 0)
1210 n = (tab = resize()).length;
1211 if ((first = tab[i = (n - 1) & hash]) != null) {
1212 if (first instanceof TreeNode)
1213 old = (t = (TreeNode<K,V>)first).getTreeNode(hash, key);
1214 else {
1215 Node<K,V> e = first; K k;
1216 do {
1217 if (e.hash == hash &&
1218 ((k = e.key) == key || (key != null && key.equals(k)))) {
1219 old = e;
1220 break;
1221 }
1222 ++binCount;
1223 } while ((e = e.next) != null);
1224 }
1225 }
1226 V oldValue = (old == null) ? null : old.value;
1227 int mc = modCount;
1228 V v = remappingFunction.apply(key, oldValue);
1229 if (mc != modCount) { throw new ConcurrentModificationException(); }
1230 if (old != null) {
1231 if (v != null) {
1232 old.value = v;
1233 afterNodeAccess(old);
1234 }
1235 else
1236 removeNode(hash, key, null, false, true);
1237 }
1238 else if (v != null) {
1239 if (t != null)
1240 t.putTreeVal(this, tab, hash, key, v);
1241 else {
1242 tab[i] = newNode(hash, key, v, first);
1243 if (binCount >= TREEIFY_THRESHOLD - 1)
1244 treeifyBin(tab, hash);
1245 }
1246 modCount = mc + 1;
1247 ++size;
1248 afterNodeInsertion(true);
1249 }
1250 return v;
1251 }
1252
1253 /**
1254 * {@inheritDoc}
1255 *
1256 * <p>This method will, on a best-effort basis, throw a
1257 * {@link ConcurrentModificationException} if it is detected that the
1258 * remapping function modifies this map during computation.
1259 *
1260 * @throws ConcurrentModificationException if it is detected that the
1261 * remapping function modified this map
1262 */
1263 @Override
1264 public V merge(K key, V value,
1265 BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
1266 if (value == null)
1267 throw new NullPointerException();
1268 if (remappingFunction == null)
1269 throw new NullPointerException();
1270 int hash = hash(key);
1271 Node<K,V>[] tab; Node<K,V> first; int n, i;
1272 int binCount = 0;
1273 TreeNode<K,V> t = null;
1274 Node<K,V> old = null;
1275 if (size > threshold || (tab = table) == null ||
1276 (n = tab.length) == 0)
1277 n = (tab = resize()).length;
1278 if ((first = tab[i = (n - 1) & hash]) != null) {
1279 if (first instanceof TreeNode)
1280 old = (t = (TreeNode<K,V>)first).getTreeNode(hash, key);
1281 else {
1282 Node<K,V> e = first; K k;
1283 do {
1284 if (e.hash == hash &&
1285 ((k = e.key) == key || (key != null && key.equals(k)))) {
1286 old = e;
1287 break;
1288 }
1289 ++binCount;
1290 } while ((e = e.next) != null);
1291 }
1292 }
1293 if (old != null) {
1294 V v;
1295 if (old.value != null) {
1296 int mc = modCount;
1297 v = remappingFunction.apply(old.value, value);
1298 if (mc != modCount) {
1299 throw new ConcurrentModificationException();
1300 }
1301 } else {
1302 v = value;
1303 }
1304 if (v != null) {
1305 old.value = v;
1306 afterNodeAccess(old);
1307 }
1308 else
1309 removeNode(hash, key, null, false, true);
1310 return v;
1311 }
1312 if (value != null) {
1313 if (t != null)
1314 t.putTreeVal(this, tab, hash, key, value);
1315 else {
1316 tab[i] = newNode(hash, key, value, first);
1317 if (binCount >= TREEIFY_THRESHOLD - 1)
1318 treeifyBin(tab, hash);
1319 }
1320 ++modCount;
1321 ++size;
1322 afterNodeInsertion(true);
1323 }
1324 return value;
1325 }
1326
1327 @Override
1328 public void forEach(BiConsumer<? super K, ? super V> action) {
1329 Node<K,V>[] tab;
1330 if (action == null)
1331 throw new NullPointerException();
1332 if (size > 0 && (tab = table) != null) {
1333 int mc = modCount;
1334 for (Node<K,V> e : tab) {
1335 for (; e != null; e = e.next)
1336 action.accept(e.key, e.value);
1337 }
1338 if (modCount != mc)
1339 throw new ConcurrentModificationException();
1340 }
1341 }
1342
1343 @Override
1344 public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
1345 Node<K,V>[] tab;
1346 if (function == null)
1347 throw new NullPointerException();
1348 if (size > 0 && (tab = table) != null) {
1349 int mc = modCount;
1350 for (Node<K,V> e : tab) {
1351 for (; e != null; e = e.next) {
1352 e.value = function.apply(e.key, e.value);
1353 }
1354 }
1355 if (modCount != mc)
1356 throw new ConcurrentModificationException();
1357 }
1358 }
1359
1360 /* ------------------------------------------------------------ */
1361 // Cloning and serialization
1362
1363 /**
1364 * Returns a shallow copy of this {@code HashMap} instance: the keys and
1365 * values themselves are not cloned.
1366 *
1367 * @return a shallow copy of this map
1368 */
1369 @SuppressWarnings("unchecked")
1370 @Override
1371 public Object clone() {
1372 HashMap<K,V> result;
1373 try {
1374 result = (HashMap<K,V>)super.clone();
1375 } catch (CloneNotSupportedException e) {
1376 // this shouldn't happen, since we are Cloneable
1377 throw new InternalError(e);
1378 }
1379 result.reinitialize();
1380 result.putMapEntries(this, false);
1381 return result;
1382 }
1383
1384 // These methods are also used when serializing HashSets
1385 final float loadFactor() { return loadFactor; }
1386 final int capacity() {
1387 return (table != null) ? table.length :
1388 (threshold > 0) ? threshold :
1389 DEFAULT_INITIAL_CAPACITY;
1390 }
1391
1392 /**
1393 * Saves this map to a stream (that is, serializes it).
1394 *
1395 * @param s the stream
1396 * @throws IOException if an I/O error occurs
1397 * @serialData The <i>capacity</i> of the HashMap (the length of the
1398 * bucket array) is emitted (int), followed by the
1399 * <i>size</i> (an int, the number of key-value
1400 * mappings), followed by the key (Object) and value (Object)
1401 * for each key-value mapping. The key-value mappings are
1402 * emitted in no particular order.
1403 */
1404 private void writeObject(java.io.ObjectOutputStream s)
1405 throws IOException {
1406 int buckets = capacity();
1407 // Write out the threshold, loadfactor, and any hidden stuff
1408 s.defaultWriteObject();
1409 s.writeInt(buckets);
1410 s.writeInt(size);
1411 internalWriteEntries(s);
1412 }
1413
1414 /**
1415 * Reconstitutes this map from a stream (that is, deserializes it).
1416 * @param s the stream
1417 * @throws ClassNotFoundException if the class of a serialized object
1418 * could not be found
1419 * @throws IOException if an I/O error occurs
1420 */
1421 private void readObject(java.io.ObjectInputStream s)
1422 throws IOException, ClassNotFoundException {
1423 // Read in the threshold (ignored), loadfactor, and any hidden stuff
1424 s.defaultReadObject();
1425 reinitialize();
1426 if (loadFactor <= 0 || Float.isNaN(loadFactor))
1427 throw new InvalidObjectException("Illegal load factor: " +
1428 loadFactor);
1429 s.readInt(); // Read and ignore number of buckets
1430 int mappings = s.readInt(); // Read number of mappings (size)
1431 if (mappings < 0)
1432 throw new InvalidObjectException("Illegal mappings count: " +
1433 mappings);
1434 else if (mappings > 0) { // (if zero, use defaults)
1435 // Size the table using given load factor only if within
1436 // range of 0.25...4.0
1437 float lf = Math.min(Math.max(0.25f, loadFactor), 4.0f);
1438 float fc = (float)mappings / lf + 1.0f;
1439 int cap = ((fc < DEFAULT_INITIAL_CAPACITY) ?
1440 DEFAULT_INITIAL_CAPACITY :
1441 (fc >= MAXIMUM_CAPACITY) ?
1442 MAXIMUM_CAPACITY :
1443 tableSizeFor((int)fc));
1444 float ft = (float)cap * lf;
1445 threshold = ((cap < MAXIMUM_CAPACITY && ft < MAXIMUM_CAPACITY) ?
1446 (int)ft : Integer.MAX_VALUE);
1447
1448 // Check Map.Entry[].class since it's the nearest public type to
1449 // what we're actually creating.
1450 SharedSecrets.getJavaObjectInputStreamAccess().checkArray(s, Map.Entry[].class, cap);
1451 @SuppressWarnings({"rawtypes","unchecked"})
1452 Node<K,V>[] tab = (Node<K,V>[])new Node[cap];
1453 table = tab;
1454
1455 // Read the keys and values, and put the mappings in the HashMap
1456 for (int i = 0; i < mappings; i++) {
1457 @SuppressWarnings("unchecked")
1458 K key = (K) s.readObject();
1459 @SuppressWarnings("unchecked")
1460 V value = (V) s.readObject();
1461 putVal(hash(key), key, value, false, false);
1462 }
1463 }
1464 }
1465
1466 /* ------------------------------------------------------------ */
1467 // iterators
1468
1469 abstract class HashIterator {
1470 Node<K,V> next; // next entry to return
1471 Node<K,V> current; // current entry
1472 int expectedModCount; // for fast-fail
1473 int index; // current slot
1474
1475 HashIterator() {
1476 expectedModCount = modCount;
1477 Node<K,V>[] t = table;
1478 current = next = null;
1479 index = 0;
1480 if (t != null && size > 0) { // advance to first entry
1481 do {} while (index < t.length && (next = t[index++]) == null);
1482 }
1483 }
1484
1485 public final boolean hasNext() {
1486 return next != null;
1487 }
1488
1489 final Node<K,V> nextNode() {
1490 Node<K,V>[] t;
1491 Node<K,V> e = next;
1492 if (modCount != expectedModCount)
1493 throw new ConcurrentModificationException();
1494 if (e == null)
1495 throw new NoSuchElementException();
1496 if ((next = (current = e).next) == null && (t = table) != null) {
1497 do {} while (index < t.length && (next = t[index++]) == null);
1498 }
1499 return e;
1500 }
1501
1502 public final void remove() {
1503 Node<K,V> p = current;
1504 if (p == null)
1505 throw new IllegalStateException();
1506 if (modCount != expectedModCount)
1507 throw new ConcurrentModificationException();
1508 current = null;
1509 removeNode(p.hash, p.key, null, false, false);
1510 expectedModCount = modCount;
1511 }
1512 }
1513
1514 final class KeyIterator extends HashIterator
1515 implements Iterator<K> {
1516 public final K next() { return nextNode().key; }
1517 }
1518
1519 final class ValueIterator extends HashIterator
1520 implements Iterator<V> {
1521 public final V next() { return nextNode().value; }
1522 }
1523
1524 final class EntryIterator extends HashIterator
1525 implements Iterator<Map.Entry<K,V>> {
1526 public final Map.Entry<K,V> next() { return nextNode(); }
1527 }
1528
1529 /* ------------------------------------------------------------ */
1530 // spliterators
1531
1532 static class HashMapSpliterator<K,V> {
1533 final HashMap<K,V> map;
1534 Node<K,V> current; // current node
1535 int index; // current index, modified on advance/split
1536 int fence; // one past last index
1537 int est; // size estimate
1538 int expectedModCount; // for comodification checks
1539
1540 HashMapSpliterator(HashMap<K,V> m, int origin,
1541 int fence, int est,
1542 int expectedModCount) {
1543 this.map = m;
1544 this.index = origin;
1545 this.fence = fence;
1546 this.est = est;
1547 this.expectedModCount = expectedModCount;
1548 }
1549
1550 final int getFence() { // initialize fence and size on first use
1551 int hi;
1552 if ((hi = fence) < 0) {
1553 HashMap<K,V> m = map;
1554 est = m.size;
1555 expectedModCount = m.modCount;
1556 Node<K,V>[] tab = m.table;
1557 hi = fence = (tab == null) ? 0 : tab.length;
1558 }
1559 return hi;
1560 }
1561
1562 public final long estimateSize() {
1563 getFence(); // force init
1564 return (long) est;
1565 }
1566 }
1567
1568 static final class KeySpliterator<K,V>
1569 extends HashMapSpliterator<K,V>
1570 implements Spliterator<K> {
1571 KeySpliterator(HashMap<K,V> m, int origin, int fence, int est,
1572 int expectedModCount) {
1573 super(m, origin, fence, est, expectedModCount);
1574 }
1575
1576 public KeySpliterator<K,V> trySplit() {
1577 int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
1578 return (lo >= mid || current != null) ? null :
1579 new KeySpliterator<>(map, lo, index = mid, est >>>= 1,
1580 expectedModCount);
1581 }
1582
1583 public void forEachRemaining(Consumer<? super K> action) {
1584 int i, hi, mc;
1585 if (action == null)
1586 throw new NullPointerException();
1587 HashMap<K,V> m = map;
1588 Node<K,V>[] tab = m.table;
1589 if ((hi = fence) < 0) {
1590 mc = expectedModCount = m.modCount;
1591 hi = fence = (tab == null) ? 0 : tab.length;
1592 }
1593 else
1594 mc = expectedModCount;
1595 if (tab != null && tab.length >= hi &&
1596 (i = index) >= 0 && (i < (index = hi) || current != null)) {
1597 Node<K,V> p = current;
1598 current = null;
1599 do {
1600 if (p == null)
1601 p = tab[i++];
1602 else {
1603 action.accept(p.key);
1604 p = p.next;
1605 }
1606 } while (p != null || i < hi);
1607 if (m.modCount != mc)
1608 throw new ConcurrentModificationException();
1609 }
1610 }
1611
1612 public boolean tryAdvance(Consumer<? super K> action) {
1613 int hi;
1614 if (action == null)
1615 throw new NullPointerException();
1616 Node<K,V>[] tab = map.table;
1617 if (tab != null && tab.length >= (hi = getFence()) && index >= 0) {
1618 while (current != null || index < hi) {
1619 if (current == null)
1620 current = tab[index++];
1621 else {
1622 K k = current.key;
1623 current = current.next;
1624 action.accept(k);
1625 if (map.modCount != expectedModCount)
1626 throw new ConcurrentModificationException();
1627 return true;
1628 }
1629 }
1630 }
1631 return false;
1632 }
1633
1634 public int characteristics() {
1635 return (fence < 0 || est == map.size ? Spliterator.SIZED : 0) |
1636 Spliterator.DISTINCT;
1637 }
1638 }
1639
1640 static final class ValueSpliterator<K,V>
1641 extends HashMapSpliterator<K,V>
1642 implements Spliterator<V> {
1643 ValueSpliterator(HashMap<K,V> m, int origin, int fence, int est,
1644 int expectedModCount) {
1645 super(m, origin, fence, est, expectedModCount);
1646 }
1647
1648 public ValueSpliterator<K,V> trySplit() {
1649 int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
1650 return (lo >= mid || current != null) ? null :
1651 new ValueSpliterator<>(map, lo, index = mid, est >>>= 1,
1652 expectedModCount);
1653 }
1654
1655 public void forEachRemaining(Consumer<? super V> action) {
1656 int i, hi, mc;
1657 if (action == null)
1658 throw new NullPointerException();
1659 HashMap<K,V> m = map;
1660 Node<K,V>[] tab = m.table;
1661 if ((hi = fence) < 0) {
1662 mc = expectedModCount = m.modCount;
1663 hi = fence = (tab == null) ? 0 : tab.length;
1664 }
1665 else
1666 mc = expectedModCount;
1667 if (tab != null && tab.length >= hi &&
1668 (i = index) >= 0 && (i < (index = hi) || current != null)) {
1669 Node<K,V> p = current;
1670 current = null;
1671 do {
1672 if (p == null)
1673 p = tab[i++];
1674 else {
1675 action.accept(p.value);
1676 p = p.next;
1677 }
1678 } while (p != null || i < hi);
1679 if (m.modCount != mc)
1680 throw new ConcurrentModificationException();
1681 }
1682 }
1683
1684 public boolean tryAdvance(Consumer<? super V> action) {
1685 int hi;
1686 if (action == null)
1687 throw new NullPointerException();
1688 Node<K,V>[] tab = map.table;
1689 if (tab != null && tab.length >= (hi = getFence()) && index >= 0) {
1690 while (current != null || index < hi) {
1691 if (current == null)
1692 current = tab[index++];
1693 else {
1694 V v = current.value;
1695 current = current.next;
1696 action.accept(v);
1697 if (map.modCount != expectedModCount)
1698 throw new ConcurrentModificationException();
1699 return true;
1700 }
1701 }
1702 }
1703 return false;
1704 }
1705
1706 public int characteristics() {
1707 return (fence < 0 || est == map.size ? Spliterator.SIZED : 0);
1708 }
1709 }
1710
1711 static final class EntrySpliterator<K,V>
1712 extends HashMapSpliterator<K,V>
1713 implements Spliterator<Map.Entry<K,V>> {
1714 EntrySpliterator(HashMap<K,V> m, int origin, int fence, int est,
1715 int expectedModCount) {
1716 super(m, origin, fence, est, expectedModCount);
1717 }
1718
1719 public EntrySpliterator<K,V> trySplit() {
1720 int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
1721 return (lo >= mid || current != null) ? null :
1722 new EntrySpliterator<>(map, lo, index = mid, est >>>= 1,
1723 expectedModCount);
1724 }
1725
1726 public void forEachRemaining(Consumer<? super Map.Entry<K,V>> action) {
1727 int i, hi, mc;
1728 if (action == null)
1729 throw new NullPointerException();
1730 HashMap<K,V> m = map;
1731 Node<K,V>[] tab = m.table;
1732 if ((hi = fence) < 0) {
1733 mc = expectedModCount = m.modCount;
1734 hi = fence = (tab == null) ? 0 : tab.length;
1735 }
1736 else
1737 mc = expectedModCount;
1738 if (tab != null && tab.length >= hi &&
1739 (i = index) >= 0 && (i < (index = hi) || current != null)) {
1740 Node<K,V> p = current;
1741 current = null;
1742 do {
1743 if (p == null)
1744 p = tab[i++];
1745 else {
1746 action.accept(p);
1747 p = p.next;
1748 }
1749 } while (p != null || i < hi);
1750 if (m.modCount != mc)
1751 throw new ConcurrentModificationException();
1752 }
1753 }
1754
1755 public boolean tryAdvance(Consumer<? super Map.Entry<K,V>> action) {
1756 int hi;
1757 if (action == null)
1758 throw new NullPointerException();
1759 Node<K,V>[] tab = map.table;
1760 if (tab != null && tab.length >= (hi = getFence()) && index >= 0) {
1761 while (current != null || index < hi) {
1762 if (current == null)
1763 current = tab[index++];
1764 else {
1765 Node<K,V> e = current;
1766 current = current.next;
1767 action.accept(e);
1768 if (map.modCount != expectedModCount)
1769 throw new ConcurrentModificationException();
1770 return true;
1771 }
1772 }
1773 }
1774 return false;
1775 }
1776
1777 public int characteristics() {
1778 return (fence < 0 || est == map.size ? Spliterator.SIZED : 0) |
1779 Spliterator.DISTINCT;
1780 }
1781 }
1782
1783 /* ------------------------------------------------------------ */
1784 // LinkedHashMap support
1785
1786
1787 /*
1788 * The following package-protected methods are designed to be
1789 * overridden by LinkedHashMap, but not by any other subclass.
1790 * Nearly all other internal methods are also package-protected
1791 * but are declared final, so can be used by LinkedHashMap, view
1792 * classes, and HashSet.
1793 */
1794
1795 // Create a regular (non-tree) node
1796 Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
1797 return new Node<>(hash, key, value, next);
1798 }
1799
1800 // For conversion from TreeNodes to plain nodes
1801 Node<K,V> replacementNode(Node<K,V> p, Node<K,V> next) {
1802 return new Node<>(p.hash, p.key, p.value, next);
1803 }
1804
1805 // Create a tree bin node
1806 TreeNode<K,V> newTreeNode(int hash, K key, V value, Node<K,V> next) {
1807 return new TreeNode<>(hash, key, value, next);
1808 }
1809
1810 // For treeifyBin
1811 TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
1812 return new TreeNode<>(p.hash, p.key, p.value, next);
1813 }
1814
1815 /**
1816 * Reset to initial default state. Called by clone and readObject.
1817 */
1818 void reinitialize() {
1819 table = null;
1820 entrySet = null;
1821 keySet = null;
1822 values = null;
1823 modCount = 0;
1824 threshold = 0;
1825 size = 0;
1826 }
1827
1828 // Callbacks to allow LinkedHashMap post-actions
1829 void afterNodeAccess(Node<K,V> p) { }
1830 void afterNodeInsertion(boolean evict) { }
1831 void afterNodeRemoval(Node<K,V> p) { }
1832
1833 // Called only from writeObject, to ensure compatible ordering.
1834 void internalWriteEntries(java.io.ObjectOutputStream s) throws IOException {
1835 Node<K,V>[] tab;
1836 if (size > 0 && (tab = table) != null) {
1837 for (Node<K,V> e : tab) {
1838 for (; e != null; e = e.next) {
1839 s.writeObject(e.key);
1840 s.writeObject(e.value);
1841 }
1842 }
1843 }
1844 }
1845
1846 /* ------------------------------------------------------------ */
1847 // Tree bins
1848
1849 /**
1850 * Entry for Tree bins. Extends LinkedHashMap.Entry (which in turn
1851 * extends Node) so can be used as extension of either regular or
1852 * linked node.
1853 */
1854 static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
1855 TreeNode<K,V> parent; // red-black tree links
1856 TreeNode<K,V> left;
1857 TreeNode<K,V> right;
1858 TreeNode<K,V> prev; // needed to unlink next upon deletion
1859 boolean red;
1860 TreeNode(int hash, K key, V val, Node<K,V> next) {
1861 super(hash, key, val, next);
1862 }
1863
1864 /**
1865 * Returns root of tree containing this node.
1866 */
1867 final TreeNode<K,V> root() {
1868 for (TreeNode<K,V> r = this, p;;) {
1869 if ((p = r.parent) == null)
1870 return r;
1871 r = p;
1872 }
1873 }
1874
1875 /**
1876 * Ensures that the given root is the first node of its bin.
1877 */
1878 static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {
1879 int n;
1880 if (root != null && tab != null && (n = tab.length) > 0) {
1881 int index = (n - 1) & root.hash;
1882 TreeNode<K,V> first = (TreeNode<K,V>)tab[index];
1883 if (root != first) {
1884 Node<K,V> rn;
1885 tab[index] = root;
1886 TreeNode<K,V> rp = root.prev;
1887 if ((rn = root.next) != null)
1888 ((TreeNode<K,V>)rn).prev = rp;
1889 if (rp != null)
1890 rp.next = rn;
1891 if (first != null)
1892 first.prev = root;
1893 root.next = first;
1894 root.prev = null;
1895 }
1896 assert checkInvariants(root);
1897 }
1898 }
1899
1900 /**
1901 * Finds the node starting at root p with the given hash and key.
1902 * The kc argument caches comparableClassFor(key) upon first use
1903 * comparing keys.
1904 */
1905 final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
1906 TreeNode<K,V> p = this;
1907 do {
1908 int ph, dir; K pk;
1909 TreeNode<K,V> pl = p.left, pr = p.right, q;
1910 if ((ph = p.hash) > h)
1911 p = pl;
1912 else if (ph < h)
1913 p = pr;
1914 else if ((pk = p.key) == k || (k != null && k.equals(pk)))
1915 return p;
1916 else if (pl == null)
1917 p = pr;
1918 else if (pr == null)
1919 p = pl;
1920 else if ((kc != null ||
1921 (kc = comparableClassFor(k)) != null) &&
1922 (dir = compareComparables(kc, k, pk)) != 0)
1923 p = (dir < 0) ? pl : pr;
1924 else if ((q = pr.find(h, k, kc)) != null)
1925 return q;
1926 else
1927 p = pl;
1928 } while (p != null);
1929 return null;
1930 }
1931
1932 /**
1933 * Calls find for root node.
1934 */
1935 final TreeNode<K,V> getTreeNode(int h, Object k) {
1936 return ((parent != null) ? root() : this).find(h, k, null);
1937 }
1938
1939 /**
1940 * Tie-breaking utility for ordering insertions when equal
1941 * hashCodes and non-comparable. We don't require a total
1942 * order, just a consistent insertion rule to maintain
1943 * equivalence across rebalancings. Tie-breaking further than
1944 * necessary simplifies testing a bit.
1945 */
1946 static int tieBreakOrder(Object a, Object b) {
1947 int d;
1948 if (a == null || b == null ||
1949 (d = a.getClass().getName().
1950 compareTo(b.getClass().getName())) == 0)
1951 d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
1952 -1 : 1);
1953 return d;
1954 }
1955
1956 /**
1957 * Forms tree of the nodes linked from this node.
1958 */
1959 final void treeify(Node<K,V>[] tab) {
1960 TreeNode<K,V> root = null;
1961 for (TreeNode<K,V> x = this, next; x != null; x = next) {
1962 next = (TreeNode<K,V>)x.next;
1963 x.left = x.right = null;
1964 if (root == null) {
1965 x.parent = null;
1966 x.red = false;
1967 root = x;
1968 }
1969 else {
1970 K k = x.key;
1971 int h = x.hash;
1972 Class<?> kc = null;
1973 for (TreeNode<K,V> p = root;;) {
1974 int dir, ph;
1975 K pk = p.key;
1976 if ((ph = p.hash) > h)
1977 dir = -1;
1978 else if (ph < h)
1979 dir = 1;
1980 else if ((kc == null &&
1981 (kc = comparableClassFor(k)) == null) ||
1982 (dir = compareComparables(kc, k, pk)) == 0)
1983 dir = tieBreakOrder(k, pk);
1984
1985 TreeNode<K,V> xp = p;
1986 if ((p = (dir <= 0) ? p.left : p.right) == null) {
1987 x.parent = xp;
1988 if (dir <= 0)
1989 xp.left = x;
1990 else
1991 xp.right = x;
1992 root = balanceInsertion(root, x);
1993 break;
1994 }
1995 }
1996 }
1997 }
1998 moveRootToFront(tab, root);
1999 }
2000
2001 /**
2002 * Returns a list of non-TreeNodes replacing those linked from
2003 * this node.
2004 */
2005 final Node<K,V> untreeify(HashMap<K,V> map) {
2006 Node<K,V> hd = null, tl = null;
2007 for (Node<K,V> q = this; q != null; q = q.next) {
2008 Node<K,V> p = map.replacementNode(q, null);
2009 if (tl == null)
2010 hd = p;
2011 else
2012 tl.next = p;
2013 tl = p;
2014 }
2015 return hd;
2016 }
2017
2018 /**
2019 * Tree version of putVal.
2020 */
2021 final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
2022 int h, K k, V v) {
2023 Class<?> kc = null;
2024 boolean searched = false;
2025 TreeNode<K,V> root = (parent != null) ? root() : this;
2026 for (TreeNode<K,V> p = root;;) {
2027 int dir, ph; K pk;
2028 if ((ph = p.hash) > h)
2029 dir = -1;
2030 else if (ph < h)
2031 dir = 1;
2032 else if ((pk = p.key) == k || (k != null && k.equals(pk)))
2033 return p;
2034 else if ((kc == null &&
2035 (kc = comparableClassFor(k)) == null) ||
2036 (dir = compareComparables(kc, k, pk)) == 0) {
2037 if (!searched) {
2038 TreeNode<K,V> q, ch;
2039 searched = true;
2040 if (((ch = p.left) != null &&
2041 (q = ch.find(h, k, kc)) != null) ||
2042 ((ch = p.right) != null &&
2043 (q = ch.find(h, k, kc)) != null))
2044 return q;
2045 }
2046 dir = tieBreakOrder(k, pk);
2047 }
2048
2049 TreeNode<K,V> xp = p;
2050 if ((p = (dir <= 0) ? p.left : p.right) == null) {
2051 Node<K,V> xpn = xp.next;
2052 TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
2053 if (dir <= 0)
2054 xp.left = x;
2055 else
2056 xp.right = x;
2057 xp.next = x;
2058 x.parent = x.prev = xp;
2059 if (xpn != null)
2060 ((TreeNode<K,V>)xpn).prev = x;
2061 moveRootToFront(tab, balanceInsertion(root, x));
2062 return null;
2063 }
2064 }
2065 }
2066
2067 /**
2068 * Removes the given node, that must be present before this call.
2069 * This is messier than typical red-black deletion code because we
2070 * cannot swap the contents of an interior node with a leaf
2071 * successor that is pinned by "next" pointers that are accessible
2072 * independently during traversal. So instead we swap the tree
2073 * linkages. If the current tree appears to have too few nodes,
2074 * the bin is converted back to a plain bin. (The test triggers
2075 * somewhere between 2 and 6 nodes, depending on tree structure).
2076 */
2077 final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab,
2078 boolean movable) {
2079 int n;
2080 if (tab == null || (n = tab.length) == 0)
2081 return;
2082 int index = (n - 1) & hash;
2083 TreeNode<K,V> first = (TreeNode<K,V>)tab[index], root = first, rl;
2084 TreeNode<K,V> succ = (TreeNode<K,V>)next, pred = prev;
2085 if (pred == null)
2086 tab[index] = first = succ;
2087 else
2088 pred.next = succ;
2089 if (succ != null)
2090 succ.prev = pred;
2091 if (first == null)
2092 return;
2093 if (root.parent != null)
2094 root = root.root();
2095 if (root == null
2096 || (movable
2097 && (root.right == null
2098 || (rl = root.left) == null
2099 || rl.left == null))) {
2100 tab[index] = first.untreeify(map); // too small
2101 return;
2102 }
2103 TreeNode<K,V> p = this, pl = left, pr = right, replacement;
2104 if (pl != null && pr != null) {
2105 TreeNode<K,V> s = pr, sl;
2106 while ((sl = s.left) != null) // find successor
2107 s = sl;
2108 boolean c = s.red; s.red = p.red; p.red = c; // swap colors
2109 TreeNode<K,V> sr = s.right;
2110 TreeNode<K,V> pp = p.parent;
2111 if (s == pr) { // p was s's direct parent
2112 p.parent = s;
2113 s.right = p;
2114 }
2115 else {
2116 TreeNode<K,V> sp = s.parent;
2117 if ((p.parent = sp) != null) {
2118 if (s == sp.left)
2119 sp.left = p;
2120 else
2121 sp.right = p;
2122 }
2123 if ((s.right = pr) != null)
2124 pr.parent = s;
2125 }
2126 p.left = null;
2127 if ((p.right = sr) != null)
2128 sr.parent = p;
2129 if ((s.left = pl) != null)
2130 pl.parent = s;
2131 if ((s.parent = pp) == null)
2132 root = s;
2133 else if (p == pp.left)
2134 pp.left = s;
2135 else
2136 pp.right = s;
2137 if (sr != null)
2138 replacement = sr;
2139 else
2140 replacement = p;
2141 }
2142 else if (pl != null)
2143 replacement = pl;
2144 else if (pr != null)
2145 replacement = pr;
2146 else
2147 replacement = p;
2148 if (replacement != p) {
2149 TreeNode<K,V> pp = replacement.parent = p.parent;
2150 if (pp == null)
2151 root = replacement;
2152 else if (p == pp.left)
2153 pp.left = replacement;
2154 else
2155 pp.right = replacement;
2156 p.left = p.right = p.parent = null;
2157 }
2158
2159 TreeNode<K,V> r = p.red ? root : balanceDeletion(root, replacement);
2160
2161 if (replacement == p) { // detach
2162 TreeNode<K,V> pp = p.parent;
2163 p.parent = null;
2164 if (pp != null) {
2165 if (p == pp.left)
2166 pp.left = null;
2167 else if (p == pp.right)
2168 pp.right = null;
2169 }
2170 }
2171 if (movable)
2172 moveRootToFront(tab, r);
2173 }
2174
2175 /**
2176 * Splits nodes in a tree bin into lower and upper tree bins,
2177 * or untreeifies if now too small. Called only from resize;
2178 * see above discussion about split bits and indices.
2179 *
2180 * @param map the map
2181 * @param tab the table for recording bin heads
2182 * @param index the index of the table being split
2183 * @param bit the bit of hash to split on
2184 */
2185 final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
2186 TreeNode<K,V> b = this;
2187 // Relink into lo and hi lists, preserving order
2188 TreeNode<K,V> loHead = null, loTail = null;
2189 TreeNode<K,V> hiHead = null, hiTail = null;
2190 int lc = 0, hc = 0;
2191 for (TreeNode<K,V> e = b, next; e != null; e = next) {
2192 next = (TreeNode<K,V>)e.next;
2193 e.next = null;
2194 if ((e.hash & bit) == 0) {
2195 if ((e.prev = loTail) == null)
2196 loHead = e;
2197 else
2198 loTail.next = e;
2199 loTail = e;
2200 ++lc;
2201 }
2202 else {
2203 if ((e.prev = hiTail) == null)
2204 hiHead = e;
2205 else
2206 hiTail.next = e;
2207 hiTail = e;
2208 ++hc;
2209 }
2210 }
2211
2212 if (loHead != null) {
2213 if (lc <= UNTREEIFY_THRESHOLD)
2214 tab[index] = loHead.untreeify(map);
2215 else {
2216 tab[index] = loHead;
2217 if (hiHead != null) // (else is already treeified)
2218 loHead.treeify(tab);
2219 }
2220 }
2221 if (hiHead != null) {
2222 if (hc <= UNTREEIFY_THRESHOLD)
2223 tab[index + bit] = hiHead.untreeify(map);
2224 else {
2225 tab[index + bit] = hiHead;
2226 if (loHead != null)
2227 hiHead.treeify(tab);
2228 }
2229 }
2230 }
2231
2232 /* ------------------------------------------------------------ */
2233 // Red-black tree methods, all adapted from CLR
2234
2235 static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,
2236 TreeNode<K,V> p) {
2237 TreeNode<K,V> r, pp, rl;
2238 if (p != null && (r = p.right) != null) {
2239 if ((rl = p.right = r.left) != null)
2240 rl.parent = p;
2241 if ((pp = r.parent = p.parent) == null)
2242 (root = r).red = false;
2243 else if (pp.left == p)
2244 pp.left = r;
2245 else
2246 pp.right = r;
2247 r.left = p;
2248 p.parent = r;
2249 }
2250 return root;
2251 }
2252
2253 static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root,
2254 TreeNode<K,V> p) {
2255 TreeNode<K,V> l, pp, lr;
2256 if (p != null && (l = p.left) != null) {
2257 if ((lr = p.left = l.right) != null)
2258 lr.parent = p;
2259 if ((pp = l.parent = p.parent) == null)
2260 (root = l).red = false;
2261 else if (pp.right == p)
2262 pp.right = l;
2263 else
2264 pp.left = l;
2265 l.right = p;
2266 p.parent = l;
2267 }
2268 return root;
2269 }
2270
2271 static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
2272 TreeNode<K,V> x) {
2273 x.red = true;
2274 for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
2275 if ((xp = x.parent) == null) {
2276 x.red = false;
2277 return x;
2278 }
2279 else if (!xp.red || (xpp = xp.parent) == null)
2280 return root;
2281 if (xp == (xppl = xpp.left)) {
2282 if ((xppr = xpp.right) != null && xppr.red) {
2283 xppr.red = false;
2284 xp.red = false;
2285 xpp.red = true;
2286 x = xpp;
2287 }
2288 else {
2289 if (x == xp.right) {
2290 root = rotateLeft(root, x = xp);
2291 xpp = (xp = x.parent) == null ? null : xp.parent;
2292 }
2293 if (xp != null) {
2294 xp.red = false;
2295 if (xpp != null) {
2296 xpp.red = true;
2297 root = rotateRight(root, xpp);
2298 }
2299 }
2300 }
2301 }
2302 else {
2303 if (xppl != null && xppl.red) {
2304 xppl.red = false;
2305 xp.red = false;
2306 xpp.red = true;
2307 x = xpp;
2308 }
2309 else {
2310 if (x == xp.left) {
2311 root = rotateRight(root, x = xp);
2312 xpp = (xp = x.parent) == null ? null : xp.parent;
2313 }
2314 if (xp != null) {
2315 xp.red = false;
2316 if (xpp != null) {
2317 xpp.red = true;
2318 root = rotateLeft(root, xpp);
2319 }
2320 }
2321 }
2322 }
2323 }
2324 }
2325
2326 static <K,V> TreeNode<K,V> balanceDeletion(TreeNode<K,V> root,
2327 TreeNode<K,V> x) {
2328 for (TreeNode<K,V> xp, xpl, xpr;;) {
2329 if (x == null || x == root)
2330 return root;
2331 else if ((xp = x.parent) == null) {
2332 x.red = false;
2333 return x;
2334 }
2335 else if (x.red) {
2336 x.red = false;
2337 return root;
2338 }
2339 else if ((xpl = xp.left) == x) {
2340 if ((xpr = xp.right) != null && xpr.red) {
2341 xpr.red = false;
2342 xp.red = true;
2343 root = rotateLeft(root, xp);
2344 xpr = (xp = x.parent) == null ? null : xp.right;
2345 }
2346 if (xpr == null)
2347 x = xp;
2348 else {
2349 TreeNode<K,V> sl = xpr.left, sr = xpr.right;
2350 if ((sr == null || !sr.red) &&
2351 (sl == null || !sl.red)) {
2352 xpr.red = true;
2353 x = xp;
2354 }
2355 else {
2356 if (sr == null || !sr.red) {
2357 if (sl != null)
2358 sl.red = false;
2359 xpr.red = true;
2360 root = rotateRight(root, xpr);
2361 xpr = (xp = x.parent) == null ?
2362 null : xp.right;
2363 }
2364 if (xpr != null) {
2365 xpr.red = (xp == null) ? false : xp.red;
2366 if ((sr = xpr.right) != null)
2367 sr.red = false;
2368 }
2369 if (xp != null) {
2370 xp.red = false;
2371 root = rotateLeft(root, xp);
2372 }
2373 x = root;
2374 }
2375 }
2376 }
2377 else { // symmetric
2378 if (xpl != null && xpl.red) {
2379 xpl.red = false;
2380 xp.red = true;
2381 root = rotateRight(root, xp);
2382 xpl = (xp = x.parent) == null ? null : xp.left;
2383 }
2384 if (xpl == null)
2385 x = xp;
2386 else {
2387 TreeNode<K,V> sl = xpl.left, sr = xpl.right;
2388 if ((sl == null || !sl.red) &&
2389 (sr == null || !sr.red)) {
2390 xpl.red = true;
2391 x = xp;
2392 }
2393 else {
2394 if (sl == null || !sl.red) {
2395 if (sr != null)
2396 sr.red = false;
2397 xpl.red = true;
2398 root = rotateLeft(root, xpl);
2399 xpl = (xp = x.parent) == null ?
2400 null : xp.left;
2401 }
2402 if (xpl != null) {
2403 xpl.red = (xp == null) ? false : xp.red;
2404 if ((sl = xpl.left) != null)
2405 sl.red = false;
2406 }
2407 if (xp != null) {
2408 xp.red = false;
2409 root = rotateRight(root, xp);
2410 }
2411 x = root;
2412 }
2413 }
2414 }
2415 }
2416 }
2417
2418 /**
2419 * Recursive invariant check
2420 */
2421 static <K,V> boolean checkInvariants(TreeNode<K,V> t) {
2422 TreeNode<K,V> tp = t.parent, tl = t.left, tr = t.right,
2423 tb = t.prev, tn = (TreeNode<K,V>)t.next;
2424 if (tb != null && tb.next != t)
2425 return false;
2426 if (tn != null && tn.prev != t)
2427 return false;
2428 if (tp != null && t != tp.left && t != tp.right)
2429 return false;
2430 if (tl != null && (tl.parent != t || tl.hash > t.hash))
2431 return false;
2432 if (tr != null && (tr.parent != t || tr.hash < t.hash))
2433 return false;
2434 if (t.red && tl != null && tl.red && tr != null && tr.red)
2435 return false;
2436 if (tl != null && !checkInvariants(tl))
2437 return false;
2438 if (tr != null && !checkInvariants(tr))
2439 return false;
2440 return true;
2441 }
2442 }
2443
2444 }
2445