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