1 /*
   2  * Copyright (c) 1997, 2013, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.  Oracle designates this
   8  * particular file as subject to the "Classpath" exception as provided
   9  * by Oracle in the LICENSE file that accompanied this code.
  10  *
  11  * This code is distributed in the hope that it will be useful, but WITHOUT
  12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14  * version 2 for more details (a copy is included in the LICENSE file that
  15  * accompanied this code).
  16  *
  17  * You should have received a copy of the GNU General Public License version
  18  * 2 along with this work; if not, write to the Free Software Foundation,
  19  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  20  *
  21  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  22  * or visit www.oracle.com if you need additional information or have any
  23  * questions.
  24  */
  25 
  26 package java.util;
  27 
  28 import java.io.*;
  29 import java.lang.reflect.ParameterizedType;
  30 import java.lang.reflect.Type;
  31 import java.util.concurrent.ThreadLocalRandom;
  32 import java.util.function.BiConsumer;
  33 import java.util.function.Consumer;
  34 import java.util.function.BiFunction;
  35 import java.util.function.Function;
  36 
  37 /**
  38  * Hash table based implementation of the <tt>Map</tt> interface.  This
  39  * implementation provides all of the optional map operations, and permits
  40  * <tt>null</tt> values and the <tt>null</tt> key.  (The <tt>HashMap</tt>
  41  * class is roughly equivalent to <tt>Hashtable</tt>, except that it is
  42  * unsynchronized and permits nulls.)  This class makes no guarantees as to
  43  * the order of the map; in particular, it does not guarantee that the order
  44  * will remain constant over time.
  45  *
  46  * <p>This implementation provides constant-time performance for the basic
  47  * operations (<tt>get</tt> and <tt>put</tt>), assuming the hash function
  48  * disperses the elements properly among the buckets.  Iteration over
  49  * collection views requires time proportional to the "capacity" of the
  50  * <tt>HashMap</tt> instance (the number of buckets) plus its size (the number
  51  * of key-value mappings).  Thus, it's very important not to set the initial
  52  * capacity too high (or the load factor too low) if iteration performance is
  53  * important.
  54  *
  55  * <p>An instance of <tt>HashMap</tt> has two parameters that affect its
  56  * performance: <i>initial capacity</i> and <i>load factor</i>.  The
  57  * <i>capacity</i> is the number of buckets in the hash table, and the initial
  58  * capacity is simply the capacity at the time the hash table is created.  The
  59  * <i>load factor</i> is a measure of how full the hash table is allowed to
  60  * get before its capacity is automatically increased.  When the number of
  61  * entries in the hash table exceeds the product of the load factor and the
  62  * current capacity, the hash table is <i>rehashed</i> (that is, internal data
  63  * structures are rebuilt) so that the hash table has approximately twice the
  64  * number of buckets.
  65  *
  66  * <p>As a general rule, the default load factor (.75) offers a good tradeoff
  67  * between time and space costs.  Higher values decrease the space overhead
  68  * but increase the lookup cost (reflected in most of the operations of the
  69  * <tt>HashMap</tt> class, including <tt>get</tt> and <tt>put</tt>).  The
  70  * expected number of entries in the map and its load factor should be taken
  71  * into account when setting its initial capacity, so as to minimize the
  72  * number of rehash operations.  If the initial capacity is greater
  73  * than the maximum number of entries divided by the load factor, no
  74  * rehash operations will ever occur.
  75  *
  76  * <p>If many mappings are to be stored in a <tt>HashMap</tt> instance,
  77  * creating it with a sufficiently large capacity will allow the mappings to
  78  * be stored more efficiently than letting it perform automatic rehashing as
  79  * needed to grow the table.
  80  *
  81  * <p><strong>Note that this implementation is not synchronized.</strong>
  82  * If multiple threads access a hash map concurrently, and at least one of
  83  * the threads modifies the map structurally, it <i>must</i> be
  84  * synchronized externally.  (A structural modification is any operation
  85  * that adds or deletes one or more mappings; merely changing the value
  86  * associated with a key that an instance already contains is not a
  87  * structural modification.)  This is typically accomplished by
  88  * synchronizing on some object that naturally encapsulates the map.
  89  *
  90  * If no such object exists, the map should be "wrapped" using the
  91  * {@link Collections#synchronizedMap Collections.synchronizedMap}
  92  * method.  This is best done at creation time, to prevent accidental
  93  * unsynchronized access to the map:<pre>
  94  *   Map m = Collections.synchronizedMap(new HashMap(...));</pre>
  95  *
  96  * <p>The iterators returned by all of this class's "collection view methods"
  97  * are <i>fail-fast</i>: if the map is structurally modified at any time after
  98  * the iterator is created, in any way except through the iterator's own
  99  * <tt>remove</tt> method, the iterator will throw a
 100  * {@link ConcurrentModificationException}.  Thus, in the face of concurrent
 101  * modification, the iterator fails quickly and cleanly, rather than risking
 102  * arbitrary, non-deterministic behavior at an undetermined time in the
 103  * future.
 104  *
 105  * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
 106  * as it is, generally speaking, impossible to make any hard guarantees in the
 107  * presence of unsynchronized concurrent modification.  Fail-fast iterators
 108  * throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
 109  * Therefore, it would be wrong to write a program that depended on this
 110  * exception for its correctness: <i>the fail-fast behavior of iterators
 111  * should be used only to detect bugs.</i>
 112  *
 113  * <p>This class is a member of the
 114  * <a href="{@docRoot}/../technotes/guides/collections/index.html">
 115  * Java Collections Framework</a>.
 116  *
 117  * @param <K> the type of keys maintained by this map
 118  * @param <V> the type of mapped values
 119  *
 120  * @author  Doug Lea
 121  * @author  Josh Bloch
 122  * @author  Arthur van Hoff
 123  * @author  Neal Gafter
 124  * @see     Object#hashCode()
 125  * @see     Collection
 126  * @see     Map
 127  * @see     TreeMap
 128  * @see     Hashtable
 129  * @since   1.2
 130  */
 131 
 132 public class HashMap<K,V>
 133         extends AbstractMap<K,V>
 134     implements Map<K,V>, Cloneable, Serializable
 135 {
 136 
 137     /**
 138      * The default initial capacity - MUST be a power of two.
 139      */
 140     static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
 141 
 142     /**
 143      * The maximum capacity, used if a higher value is implicitly specified
 144      * by either of the constructors with arguments.
 145      * MUST be a power of two <= 1<<30.
 146      */
 147     static final int MAXIMUM_CAPACITY = 1 << 30;
 148 
 149     /**
 150      * The load factor used when none specified in constructor.
 151      */
 152     static final float DEFAULT_LOAD_FACTOR = 0.75f;
 153 
 154     /**
 155      * An empty table instance to share when the table is not inflated.
 156      */
 157     static final Object[] EMPTY_TABLE = {};
 158 
 159     /**
 160      * The table, resized as necessary. Length MUST Always be a power of two.
 161      */
 162     transient Object[] table = EMPTY_TABLE;
 163 
 164     /**
 165      * The number of key-value mappings contained in this map.
 166      */
 167     transient int size;
 168 
 169     /**
 170      * The next size value at which to resize (capacity * load factor).
 171      * @serial
 172      */
 173     // If table == EMPTY_TABLE then this is the initial capacity at which the
 174     // table will be created when inflated.
 175     int threshold;
 176 
 177     /**
 178      * The load factor for the hash table.
 179      *
 180      * @serial
 181      */
 182     final float loadFactor;
 183 
 184     /**
 185      * The number of times this HashMap has been structurally modified
 186      * Structural modifications are those that change the number of mappings in
 187      * the HashMap or otherwise modify its internal structure (e.g.,
 188      * rehash).  This field is used to make iterators on Collection-views of
 189      * the HashMap fail-fast.  (See ConcurrentModificationException).
 190      */
 191     transient int modCount;
 192 
 193     /**
 194      * Holds values which can't be initialized until after VM is booted.
 195      */
 196     private static class Holder {
 197         static final sun.misc.Unsafe UNSAFE;
 198 
 199         /**
 200          * Offset of "final" hashSeed field we must set in
 201          * readObject() method.
 202          */
 203         static final long HASHSEED_OFFSET;
 204 
 205         static final boolean USE_HASHSEED;
 206 
 207         static {
 208             String hashSeedProp = java.security.AccessController.doPrivileged(
 209                     new sun.security.action.GetPropertyAction(
 210                         "jdk.map.useRandomSeed"));
 211             boolean localBool = (null != hashSeedProp)
 212                     ? Boolean.parseBoolean(hashSeedProp) : false;
 213             USE_HASHSEED = localBool;
 214 
 215             if (USE_HASHSEED) {
 216                 try {
 217                     UNSAFE = sun.misc.Unsafe.getUnsafe();
 218                     HASHSEED_OFFSET = UNSAFE.objectFieldOffset(
 219                         HashMap.class.getDeclaredField("hashSeed"));
 220                 } catch (NoSuchFieldException | SecurityException e) {
 221                     throw new InternalError("Failed to record hashSeed offset", e);
 222                 }
 223             } else {
 224                 UNSAFE = null;
 225                 HASHSEED_OFFSET = 0;
 226             }
 227         }
 228     }
 229 
 230     /*
 231      * A randomizing value associated with this instance that is applied to
 232      * hash code of keys to make hash collisions harder to find.
 233      *
 234      * Non-final so it can be set lazily, but be sure not to set more than once.
 235      */
 236     transient final int hashSeed;
 237 
 238     /*
 239      * TreeBin/TreeNode code from CHM doesn't handle the null key.  Store the
 240      * null key entry here.
 241      */
 242     transient Entry<K,V> nullKeyEntry = null;
 243 
 244     /*
 245      * In order to improve performance under high hash-collision conditions,
 246      * HashMap will switch to storing a bin's entries in a balanced tree
 247      * (TreeBin) instead of a linked-list once the number of entries in the bin
 248      * passes a certain threshold (TreeBin.TREE_THRESHOLD), if at least one of
 249      * the keys in the bin implements Comparable.  This technique is borrowed
 250      * from ConcurrentHashMap.
 251      */
 252 
 253     /*
 254      * Code based on CHMv8
 255      *
 256      * Node type for TreeBin
 257      */
 258     final static class TreeNode<K,V> {
 259         TreeNode parent;  // red-black tree links
 260         TreeNode left;
 261         TreeNode right;
 262         TreeNode prev;    // needed to unlink next upon deletion
 263         boolean red;
 264         final HashMap.Entry<K,V> entry;
 265 
 266         TreeNode(HashMap.Entry<K,V> entry, Object next, TreeNode parent) {
 267             this.entry = entry;
 268             this.entry.next = next;
 269             this.parent = parent;
 270         }
 271     }
 272 
 273     /**
 274      * Returns a Class for the given object of the form "class C
 275      * implements Comparable<C>", if one exists, else null.  See the TreeBin
 276      * docs, below, for explanation.
 277      */
 278     static Class<?> comparableClassFor(Object x) {
 279         Class<?> c, s, cmpc; Type[] ts, as; Type t; ParameterizedType p;
 280         if ((c = x.getClass()) == String.class) // bypass checks
 281             return c;
 282         if ((cmpc = Comparable.class).isAssignableFrom(c)) {
 283             while (cmpc.isAssignableFrom(s = c.getSuperclass()))
 284                 c = s; // find topmost comparable class
 285             if ((ts  = c.getGenericInterfaces()) != null) {
 286                 for (int i = 0; i < ts.length; ++i) {
 287                     if (((t = ts[i]) instanceof ParameterizedType) &&
 288                         ((p = (ParameterizedType)t).getRawType() == cmpc) &&
 289                         (as = p.getActualTypeArguments()) != null &&
 290                         as.length == 1 && as[0] == c) // type arg is c
 291                         return c;
 292                 }
 293             }
 294         }
 295         return null;
 296     }
 297 
 298     /*
 299      * Code based on CHMv8
 300      *
 301      * A specialized form of red-black tree for use in bins
 302      * whose size exceeds a threshold.
 303      *
 304      * TreeBins use a special form of comparison for search and
 305      * related operations (which is the main reason we cannot use
 306      * existing collections such as TreeMaps). TreeBins contain
 307      * Comparable elements, but may contain others, as well as
 308      * elements that are Comparable but not necessarily Comparable<T>
 309      * for the same T, so we cannot invoke compareTo among them. To
 310      * handle this, the tree is ordered primarily by hash value, then
 311      * by Comparable.compareTo order if applicable.  On lookup at a
 312      * node, if elements are not comparable or compare as 0 then both
 313      * left and right children may need to be searched in the case of
 314      * tied hash values. (This corresponds to the full list search
 315      * that would be necessary if all elements were non-Comparable and
 316      * had tied hashes.)  The red-black balancing code is updated from
 317      * pre-jdk-collections
 318      * (http://gee.cs.oswego.edu/dl/classes/collections/RBCell.java)
 319      * based in turn on Cormen, Leiserson, and Rivest "Introduction to
 320      * Algorithms" (CLR).
 321      */
 322     final class TreeBin {
 323         /*
 324          * The bin count threshold for using a tree rather than list for a bin. The
 325          * value reflects the approximate break-even point for using tree-based
 326          * operations.
 327          */
 328         static final int TREE_THRESHOLD = 16;
 329 
 330         TreeNode<K,V> root;  // root of tree
 331         TreeNode<K,V> first; // head of next-pointer list
 332 
 333         /*
 334          * Split a TreeBin into lo and hi parts and install in given table.
 335          *
 336          * Existing Entrys are re-used, which maintains the before/after links for
 337          * LinkedHashMap.Entry.
 338          *
 339          * No check for Comparable, though this is the same as CHM.
 340          */
 341         final void splitTreeBin(Object[] newTable, int i, TreeBin loTree, TreeBin hiTree) {
 342             TreeBin oldTree = this;
 343             int bit = newTable.length >>> 1;
 344             int loCount = 0, hiCount = 0;
 345             TreeNode<K,V> e = oldTree.first;
 346             TreeNode<K,V> next;
 347 
 348             // This method is called when the table has just increased capacity,
 349             // so indexFor() is now taking one additional bit of hash into
 350             // account ("bit").  Entries in this TreeBin now belong in one of
 351             // two bins, "i" or "i+bit", depending on if the new top bit of the
 352             // hash is set.  The trees for the two bins are loTree and hiTree.
 353             // If either tree ends up containing fewer than TREE_THRESHOLD
 354             // entries, it is converted back to a linked list.
 355             while (e != null) {
 356                 // Save entry.next - it will get overwritten in putTreeNode()
 357                 next = (TreeNode<K,V>)e.entry.next;
 358 
 359                 int h = e.entry.hash;
 360                 K k = (K) e.entry.key;
 361                 V v = e.entry.value;
 362                 if ((h & bit) == 0) {
 363                     ++loCount;
 364                     // Re-using e.entry
 365                     loTree.putTreeNode(h, k, v, e.entry);
 366                 } else {
 367                     ++hiCount;
 368                     hiTree.putTreeNode(h, k, v, e.entry);
 369                 }
 370                 // Iterate using the saved 'next'
 371                 e = next;
 372             }
 373             if (loCount < TREE_THRESHOLD) { // too small, convert back to list
 374                 HashMap.Entry loEntry = null;
 375                 TreeNode<K,V> p = loTree.first;
 376                 while (p != null) {
 377                     @SuppressWarnings("unchecked")
 378                     TreeNode<K,V> savedNext = (TreeNode<K,V>) p.entry.next;
 379                     p.entry.next = loEntry;
 380                     loEntry = p.entry;
 381                     p = savedNext;
 382                 }
 383                 // assert newTable[i] == null;
 384                 newTable[i] = loEntry;
 385             } else {
 386                 // assert newTable[i] == null;
 387                 newTable[i] = loTree;
 388             }
 389             if (hiCount < TREE_THRESHOLD) { // too small, convert back to list
 390                 HashMap.Entry hiEntry = null;
 391                 TreeNode<K,V> p = hiTree.first;
 392                 while (p != null) {
 393                     @SuppressWarnings("unchecked")
 394                     TreeNode<K,V> savedNext = (TreeNode<K,V>) p.entry.next;
 395                     p.entry.next = hiEntry;
 396                     hiEntry = p.entry;
 397                     p = savedNext;
 398                 }
 399                 // assert newTable[i + bit] == null;
 400                 newTable[i + bit] = hiEntry;
 401             } else {
 402                 // assert newTable[i + bit] == null;
 403                 newTable[i + bit] = hiTree;
 404             }
 405         }
 406 
 407         /*
 408          * Popuplate the TreeBin with entries from the linked list e
 409          *
 410          * Assumes 'this' is a new/empty TreeBin
 411          *
 412          * Note: no check for Comparable
 413          * Note: I believe this changes iteration order
 414          */
 415         @SuppressWarnings("unchecked")
 416         void populate(HashMap.Entry e) {
 417             // assert root == null;
 418             // assert first == null;
 419             HashMap.Entry next;
 420             while (e != null) {
 421                 // Save entry.next - it will get overwritten in putTreeNode()
 422                 next = (HashMap.Entry)e.next;
 423                 // Re-using Entry e will maintain before/after in LinkedHM
 424                 putTreeNode(e.hash, (K)e.key, (V)e.value, e);
 425                 // Iterate using the saved 'next'
 426                 e = next;
 427             }
 428         }
 429 
 430         /**
 431          * Copied from CHMv8
 432          * From CLR
 433          */
 434         private void rotateLeft(TreeNode p) {
 435             if (p != null) {
 436                 TreeNode r = p.right, pp, rl;
 437                 if ((rl = p.right = r.left) != null) {
 438                     rl.parent = p;
 439                 }
 440                 if ((pp = r.parent = p.parent) == null) {
 441                     root = r;
 442                 } else if (pp.left == p) {
 443                     pp.left = r;
 444                 } else {
 445                     pp.right = r;
 446                 }
 447                 r.left = p;
 448                 p.parent = r;
 449             }
 450         }
 451 
 452         /**
 453          * Copied from CHMv8
 454          * From CLR
 455          */
 456         private void rotateRight(TreeNode p) {
 457             if (p != null) {
 458                 TreeNode l = p.left, pp, lr;
 459                 if ((lr = p.left = l.right) != null) {
 460                     lr.parent = p;
 461                 }
 462                 if ((pp = l.parent = p.parent) == null) {
 463                     root = l;
 464                 } else if (pp.right == p) {
 465                     pp.right = l;
 466                 } else {
 467                     pp.left = l;
 468                 }
 469                 l.right = p;
 470                 p.parent = l;
 471             }
 472         }
 473 
 474         /**
 475          * Returns the TreeNode (or null if not found) for the given
 476          * key.  A front-end for recursive version.
 477          */
 478         final TreeNode getTreeNode(int h, K k) {
 479             return getTreeNode(h, k, root, comparableClassFor(k));
 480         }
 481 
 482         /**
 483          * Returns the TreeNode (or null if not found) for the given key
 484          * starting at given root.
 485          */
 486         @SuppressWarnings("unchecked")
 487         final TreeNode getTreeNode (int h, K k, TreeNode p, Class<?> cc) {
 488             // assert k != null;
 489             while (p != null) {
 490                 int dir, ph;  Object pk;
 491                 if ((ph = p.entry.hash) != h)
 492                     dir = (h < ph) ? -1 : 1;
 493                 else if ((pk = p.entry.key) == k || k.equals(pk))
 494                     return p;
 495                 else if (cc == null || comparableClassFor(pk) != cc ||
 496                          (dir = ((Comparable<Object>)k).compareTo(pk)) == 0) {
 497                     // assert pk != null;
 498                     TreeNode r, pl, pr; // check both sides
 499                     if ((pr = p.right) != null &&
 500                         (r = getTreeNode(h, k, pr, cc)) != null)
 501                         return r;
 502                     else if ((pl = p.left) != null)
 503                         dir = -1;
 504                     else // nothing there
 505                         break;
 506                 }
 507                 p = (dir > 0) ? p.right : p.left;
 508             }
 509             return null;
 510         }
 511 
 512         /*
 513          * Finds or adds a node.
 514          *
 515          * 'entry' should be used to recycle an existing Entry (e.g. in the case
 516          * of converting a linked-list bin to a TreeBin).
 517          * If entry is null, a new Entry will be created for the new TreeNode
 518          *
 519          * @return the TreeNode containing the mapping, or null if a new
 520          * TreeNode was added
 521          */
 522         @SuppressWarnings("unchecked")
 523         TreeNode putTreeNode(int h, K k, V v, HashMap.Entry<K,V> entry) {
 524             // assert k != null;
 525             //if (entry != null) {
 526                 // assert h == entry.hash;
 527                 // assert k == entry.key;
 528                 // assert v == entry.value;
 529             // }
 530             Class<?> cc = comparableClassFor(k);
 531             TreeNode pp = root, p = null;
 532             int dir = 0;
 533             while (pp != null) { // find existing node or leaf to insert at
 534                 int ph;  Object pk;
 535                 p = pp;
 536                 if ((ph = p.entry.hash) != h)
 537                     dir = (h < ph) ? -1 : 1;
 538                 else if ((pk = p.entry.key) == k || k.equals(pk))
 539                     return p;
 540                 else if (cc == null || comparableClassFor(pk) != cc ||
 541                          (dir = ((Comparable<Object>)k).compareTo(pk)) == 0) {
 542                     TreeNode r, pr;
 543                     if ((pr = p.right) != null &&
 544                         (r = getTreeNode(h, k, pr, cc)) != null)
 545                         return r;
 546                     else // continue left
 547                         dir = -1;
 548                 }
 549                 pp = (dir > 0) ? p.right : p.left;
 550             }
 551 
 552             // Didn't find the mapping in the tree, so add it
 553             TreeNode f = first;
 554             TreeNode x;
 555             if (entry != null) {
 556                 x = new TreeNode(entry, f, p);
 557             } else {
 558                 x = new TreeNode(newEntry(h, k, v, null), f, p);
 559             }
 560             first = x;
 561 
 562             if (p == null) {
 563                 root = x;
 564             } else { // attach and rebalance; adapted from CLR
 565                 TreeNode xp, xpp;
 566                 if (f != null) {
 567                     f.prev = x;
 568                 }
 569                 if (dir <= 0) {
 570                     p.left = x;
 571                 } else {
 572                     p.right = x;
 573                 }
 574                 x.red = true;
 575                 while (x != null && (xp = x.parent) != null && xp.red
 576                         && (xpp = xp.parent) != null) {
 577                     TreeNode xppl = xpp.left;
 578                     if (xp == xppl) {
 579                         TreeNode y = xpp.right;
 580                         if (y != null && y.red) {
 581                             y.red = false;
 582                             xp.red = false;
 583                             xpp.red = true;
 584                             x = xpp;
 585                         } else {
 586                             if (x == xp.right) {
 587                                 rotateLeft(x = xp);
 588                                 xpp = (xp = x.parent) == null ? null : xp.parent;
 589                             }
 590                             if (xp != null) {
 591                                 xp.red = false;
 592                                 if (xpp != null) {
 593                                     xpp.red = true;
 594                                     rotateRight(xpp);
 595                                 }
 596                             }
 597                         }
 598                     } else {
 599                         TreeNode y = xppl;
 600                         if (y != null && y.red) {
 601                             y.red = false;
 602                             xp.red = false;
 603                             xpp.red = true;
 604                             x = xpp;
 605                         } else {
 606                             if (x == xp.left) {
 607                                 rotateRight(x = xp);
 608                                 xpp = (xp = x.parent) == null ? null : xp.parent;
 609                             }
 610                             if (xp != null) {
 611                                 xp.red = false;
 612                                 if (xpp != null) {
 613                                     xpp.red = true;
 614                                     rotateLeft(xpp);
 615                                 }
 616                             }
 617                         }
 618                     }
 619                 }
 620                 TreeNode r = root;
 621                 if (r != null && r.red) {
 622                     r.red = false;
 623                 }
 624             }
 625             return null;
 626         }
 627 
 628         /*
 629          * From CHMv8
 630          *
 631          * Removes the given node, that must be present before this
 632          * call.  This is messier than typical red-black deletion code
 633          * because we cannot swap the contents of an interior node
 634          * with a leaf successor that is pinned by "next" pointers
 635          * that are accessible independently of lock. So instead we
 636          * swap the tree linkages.
 637          */
 638         final void deleteTreeNode(TreeNode p) {
 639             TreeNode next = (TreeNode) p.entry.next; // unlink traversal pointers
 640             TreeNode pred = p.prev;
 641             if (pred == null) {
 642                 first = next;
 643             } else {
 644                 pred.entry.next = next;
 645             }
 646             if (next != null) {
 647                 next.prev = pred;
 648             }
 649             TreeNode replacement;
 650             TreeNode pl = p.left;
 651             TreeNode pr = p.right;
 652             if (pl != null && pr != null) {
 653                 TreeNode s = pr, sl;
 654                 while ((sl = s.left) != null) // find successor
 655                 {
 656                     s = sl;
 657                 }
 658                 boolean c = s.red;
 659                 s.red = p.red;
 660                 p.red = c; // swap colors
 661                 TreeNode sr = s.right;
 662                 TreeNode pp = p.parent;
 663                 if (s == pr) { // p was s's direct parent
 664                     p.parent = s;
 665                     s.right = p;
 666                 } else {
 667                     TreeNode sp = s.parent;
 668                     if ((p.parent = sp) != null) {
 669                         if (s == sp.left) {
 670                             sp.left = p;
 671                         } else {
 672                             sp.right = p;
 673                         }
 674                     }
 675                     if ((s.right = pr) != null) {
 676                         pr.parent = s;
 677                     }
 678                 }
 679                 p.left = null;
 680                 if ((p.right = sr) != null) {
 681                     sr.parent = p;
 682                 }
 683                 if ((s.left = pl) != null) {
 684                     pl.parent = s;
 685                 }
 686                 if ((s.parent = pp) == null) {
 687                     root = s;
 688                 } else if (p == pp.left) {
 689                     pp.left = s;
 690                 } else {
 691                     pp.right = s;
 692                 }
 693                 replacement = sr;
 694             } else {
 695                 replacement = (pl != null) ? pl : pr;
 696             }
 697             TreeNode pp = p.parent;
 698             if (replacement == null) {
 699                 if (pp == null) {
 700                     root = null;
 701                     return;
 702                 }
 703                 replacement = p;
 704             } else {
 705                 replacement.parent = pp;
 706                 if (pp == null) {
 707                     root = replacement;
 708                 } else if (p == pp.left) {
 709                     pp.left = replacement;
 710                 } else {
 711                     pp.right = replacement;
 712                 }
 713                 p.left = p.right = p.parent = null;
 714             }
 715             if (!p.red) { // rebalance, from CLR
 716                 TreeNode x = replacement;
 717                 while (x != null) {
 718                     TreeNode xp, xpl;
 719                     if (x.red || (xp = x.parent) == null) {
 720                         x.red = false;
 721                         break;
 722                     }
 723                     if (x == (xpl = xp.left)) {
 724                         TreeNode sib = xp.right;
 725                         if (sib != null && sib.red) {
 726                             sib.red = false;
 727                             xp.red = true;
 728                             rotateLeft(xp);
 729                             sib = (xp = x.parent) == null ? null : xp.right;
 730                         }
 731                         if (sib == null) {
 732                             x = xp;
 733                         } else {
 734                             TreeNode sl = sib.left, sr = sib.right;
 735                             if ((sr == null || !sr.red)
 736                                     && (sl == null || !sl.red)) {
 737                                 sib.red = true;
 738                                 x = xp;
 739                             } else {
 740                                 if (sr == null || !sr.red) {
 741                                     if (sl != null) {
 742                                         sl.red = false;
 743                                     }
 744                                     sib.red = true;
 745                                     rotateRight(sib);
 746                                     sib = (xp = x.parent) == null ?
 747                                         null : xp.right;
 748                                 }
 749                                 if (sib != null) {
 750                                     sib.red = (xp == null) ? false : xp.red;
 751                                     if ((sr = sib.right) != null) {
 752                                         sr.red = false;
 753                                     }
 754                                 }
 755                                 if (xp != null) {
 756                                     xp.red = false;
 757                                     rotateLeft(xp);
 758                                 }
 759                                 x = root;
 760                             }
 761                         }
 762                     } else { // symmetric
 763                         TreeNode sib = xpl;
 764                         if (sib != null && sib.red) {
 765                             sib.red = false;
 766                             xp.red = true;
 767                             rotateRight(xp);
 768                             sib = (xp = x.parent) == null ? null : xp.left;
 769                         }
 770                         if (sib == null) {
 771                             x = xp;
 772                         } else {
 773                             TreeNode sl = sib.left, sr = sib.right;
 774                             if ((sl == null || !sl.red)
 775                                     && (sr == null || !sr.red)) {
 776                                 sib.red = true;
 777                                 x = xp;
 778                             } else {
 779                                 if (sl == null || !sl.red) {
 780                                     if (sr != null) {
 781                                         sr.red = false;
 782                                     }
 783                                     sib.red = true;
 784                                     rotateLeft(sib);
 785                                     sib = (xp = x.parent) == null ?
 786                                         null : xp.left;
 787                                 }
 788                                 if (sib != null) {
 789                                     sib.red = (xp == null) ? false : xp.red;
 790                                     if ((sl = sib.left) != null) {
 791                                         sl.red = false;
 792                                     }
 793                                 }
 794                                 if (xp != null) {
 795                                     xp.red = false;
 796                                     rotateRight(xp);
 797                                 }
 798                                 x = root;
 799                             }
 800                         }
 801                     }
 802                 }
 803             }
 804             if (p == replacement && (pp = p.parent) != null) {
 805                 if (p == pp.left) // detach pointers
 806                 {
 807                     pp.left = null;
 808                 } else if (p == pp.right) {
 809                     pp.right = null;
 810                 }
 811                 p.parent = null;
 812             }
 813         }
 814     }
 815 
 816     /**
 817      * Constructs an empty <tt>HashMap</tt> with the specified initial
 818      * capacity and load factor.
 819      *
 820      * @param  initialCapacity the initial capacity
 821      * @param  loadFactor      the load factor
 822      * @throws IllegalArgumentException if the initial capacity is negative
 823      *         or the load factor is nonpositive
 824      */
 825     public HashMap(int initialCapacity, float loadFactor) {
 826         if (initialCapacity < 0)
 827             throw new IllegalArgumentException("Illegal initial capacity: " +
 828                                                initialCapacity);
 829         if (initialCapacity > MAXIMUM_CAPACITY)
 830             initialCapacity = MAXIMUM_CAPACITY;
 831         if (loadFactor <= 0 || Float.isNaN(loadFactor))
 832             throw new IllegalArgumentException("Illegal load factor: " +
 833                                                loadFactor);
 834         this.loadFactor = loadFactor;
 835         threshold = initialCapacity;
 836         hashSeed = initHashSeed();
 837         init();
 838     }
 839 
 840     /**
 841      * Constructs an empty <tt>HashMap</tt> with the specified initial
 842      * capacity and the default load factor (0.75).
 843      *
 844      * @param  initialCapacity the initial capacity.
 845      * @throws IllegalArgumentException if the initial capacity is negative.
 846      */
 847     public HashMap(int initialCapacity) {
 848         this(initialCapacity, DEFAULT_LOAD_FACTOR);
 849     }
 850 
 851     /**
 852      * Constructs an empty <tt>HashMap</tt> with the default initial capacity
 853      * (16) and the default load factor (0.75).
 854      */
 855     public HashMap() {
 856         this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
 857     }
 858 
 859     /**
 860      * Constructs a new <tt>HashMap</tt> with the same mappings as the
 861      * specified <tt>Map</tt>.  The <tt>HashMap</tt> is created with
 862      * default load factor (0.75) and an initial capacity sufficient to
 863      * hold the mappings in the specified <tt>Map</tt>.
 864      *
 865      * @param   m the map whose mappings are to be placed in this map
 866      * @throws  NullPointerException if the specified map is null
 867      */
 868     public HashMap(Map<? extends K, ? extends V> m) {
 869         this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
 870                 DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
 871         inflateTable(threshold);
 872 
 873         putAllForCreate(m);
 874         // assert size == m.size();
 875     }
 876 
 877     private static int roundUpToPowerOf2(int number) {
 878         // assert number >= 0 : "number must be non-negative";
 879         int rounded = number >= MAXIMUM_CAPACITY
 880                 ? MAXIMUM_CAPACITY
 881                 : (rounded = Integer.highestOneBit(number)) != 0
 882                     ? (Integer.bitCount(number) > 1) ? rounded << 1 : rounded
 883                     : 1;
 884 
 885         return rounded;
 886     }
 887 
 888     /**
 889      * Inflates the table.
 890      */
 891     private void inflateTable(int toSize) {
 892         // Find a power of 2 >= toSize
 893         int capacity = roundUpToPowerOf2(toSize);
 894 
 895         threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
 896         table = new Object[capacity];
 897     }
 898 
 899     // internal utilities
 900 
 901     /**
 902      * Initialization hook for subclasses. This method is called
 903      * in all constructors and pseudo-constructors (clone, readObject)
 904      * after HashMap has been initialized but before any entries have
 905      * been inserted.  (In the absence of this method, readObject would
 906      * require explicit knowledge of subclasses.)
 907      */
 908     void init() {
 909     }
 910 
 911     /**
 912      * Return an initial value for the hashSeed, or 0 if the random seed is not
 913      * enabled.
 914      */
 915     final int initHashSeed() {
 916         if (sun.misc.VM.isBooted() && Holder.USE_HASHSEED) {
 917             int seed = ThreadLocalRandom.current().nextInt();
 918             return (seed != 0) ? seed : 1;
 919         }
 920         return 0;
 921     }
 922 
 923     /**
 924      * Retrieve object hash code and applies a supplemental hash function to the
 925      * result hash, which defends against poor quality hash functions. This is
 926      * critical because HashMap uses power-of-two length hash tables, that
 927      * otherwise encounter collisions for hashCodes that do not differ
 928      * in lower bits.
 929      */
 930     final int hash(Object k) {
 931         int  h = hashSeed ^ k.hashCode();
 932 
 933         // This function ensures that hashCodes that differ only by
 934         // constant multiples at each bit position have a bounded
 935         // number of collisions (approximately 8 at default load factor).
 936         h ^= (h >>> 20) ^ (h >>> 12);
 937         return h ^ (h >>> 7) ^ (h >>> 4);
 938     }
 939 
 940     /**
 941      * Returns index for hash code h.
 942      */
 943     static int indexFor(int h, int length) {
 944         // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
 945         return h & (length-1);
 946     }
 947 
 948     /**
 949      * Returns the number of key-value mappings in this map.
 950      *
 951      * @return the number of key-value mappings in this map
 952      */
 953     public int size() {
 954         return size;
 955     }
 956 
 957     /**
 958      * Returns <tt>true</tt> if this map contains no key-value mappings.
 959      *
 960      * @return <tt>true</tt> if this map contains no key-value mappings
 961      */
 962     public boolean isEmpty() {
 963         return size == 0;
 964     }
 965 
 966     /**
 967      * Returns the value to which the specified key is mapped,
 968      * or {@code null} if this map contains no mapping for the key.
 969      *
 970      * <p>More formally, if this map contains a mapping from a key
 971      * {@code k} to a value {@code v} such that {@code (key==null ? k==null :
 972      * key.equals(k))}, then this method returns {@code v}; otherwise
 973      * it returns {@code null}.  (There can be at most one such mapping.)
 974      *
 975      * <p>A return value of {@code null} does not <i>necessarily</i>
 976      * indicate that the map contains no mapping for the key; it's also
 977      * possible that the map explicitly maps the key to {@code null}.
 978      * The {@link #containsKey containsKey} operation may be used to
 979      * distinguish these two cases.
 980      *
 981      * @see #put(Object, Object)
 982      */
 983     @SuppressWarnings("unchecked")
 984     public V get(Object key) {
 985         Entry<K,V> entry = getEntry(key);
 986 
 987         return null == entry ? null : entry.getValue();
 988     }
 989 
 990     @Override
 991     public V getOrDefault(Object key, V defaultValue) {
 992         Entry<K,V> entry = getEntry(key);
 993 
 994         return (entry == null) ? defaultValue : entry.getValue();
 995     }
 996 
 997     /**
 998      * Returns <tt>true</tt> if this map contains a mapping for the
 999      * specified key.
1000      *
1001      * @param   key   The key whose presence in this map is to be tested
1002      * @return <tt>true</tt> if this map contains a mapping for the specified
1003      * key.
1004      */
1005     public boolean containsKey(Object key) {
1006         return getEntry(key) != null;
1007     }
1008 
1009     /**
1010      * Returns the entry associated with the specified key in the
1011      * HashMap.  Returns null if the HashMap contains no mapping
1012      * for the key.
1013      */
1014     @SuppressWarnings("unchecked")
1015     final Entry<K,V> getEntry(Object key) {
1016         if (isEmpty()) {
1017             return null;
1018         }
1019         if (key == null) {
1020             return nullKeyEntry;
1021         }
1022         int hash = hash(key);
1023         int bin = indexFor(hash, table.length);
1024 
1025         if (table[bin] instanceof Entry) {
1026             Entry<K,V> e = (Entry<K,V>) table[bin];
1027             for (; e != null; e = (Entry<K,V>)e.next) {
1028                 Object k;
1029                 if (e.hash == hash &&
1030                     ((k = e.key) == key || key.equals(k))) {
1031                     return e;
1032                 }
1033             }
1034         } else if (table[bin] != null) {
1035             TreeBin e = (TreeBin)table[bin];
1036             TreeNode p = e.getTreeNode(hash, (K)key);
1037             if (p != null) {
1038                 // assert p.entry.hash == hash && p.entry.key.equals(key);
1039                 return (Entry<K,V>)p.entry;
1040             } else {
1041                 return null;
1042             }
1043         }
1044         return null;
1045     }
1046 
1047 
1048     /**
1049      * Associates the specified value with the specified key in this map.
1050      * If the map previously contained a mapping for the key, the old
1051      * value is replaced.
1052      *
1053      * @param key key with which the specified value is to be associated
1054      * @param value value to be associated with the specified key
1055      * @return the previous value associated with <tt>key</tt>, or
1056      *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
1057      *         (A <tt>null</tt> return can also indicate that the map
1058      *         previously associated <tt>null</tt> with <tt>key</tt>.)
1059      */
1060     @SuppressWarnings("unchecked")
1061     public V put(K key, V value) {
1062         if (table == EMPTY_TABLE) {
1063             inflateTable(threshold);
1064         }
1065        if (key == null)
1066             return putForNullKey(value);
1067         int hash = hash(key);
1068         int i = indexFor(hash, table.length);
1069         boolean checkIfNeedTree = false; // Might we convert bin to a TreeBin?
1070 
1071         if (table[i] instanceof Entry) {
1072             // Bin contains ordinary Entries.  Search for key in the linked list
1073             // of entries, counting the number of entries.  Only check for
1074             // TreeBin conversion if the list size is >= TREE_THRESHOLD.
1075             // (The conversion still may not happen if the table gets resized.)
1076             int listSize = 0;
1077             Entry<K,V> e = (Entry<K,V>) table[i];
1078             for (; e != null; e = (Entry<K,V>)e.next) {
1079                 Object k;
1080                 if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
1081                     V oldValue = e.value;
1082                     e.value = value;
1083                     e.recordAccess(this);
1084                     return oldValue;
1085                 }
1086                 listSize++;
1087             }
1088             // Didn't find, so fall through and call addEntry() to add the
1089             // Entry and check for TreeBin conversion.
1090             checkIfNeedTree = listSize >= TreeBin.TREE_THRESHOLD;
1091         } else if (table[i] != null) {
1092             TreeBin e = (TreeBin)table[i];
1093             TreeNode p = e.putTreeNode(hash, key, value, null);
1094             if (p == null) { // putTreeNode() added a new node
1095                 modCount++;
1096                 size++;
1097                 if (size >= threshold) {
1098                     resize(2 * table.length);
1099                 }
1100                 return null;
1101             } else { // putTreeNode() found an existing node
1102                 Entry<K,V> pEntry = (Entry<K,V>)p.entry;
1103                 V oldVal = pEntry.value;
1104                 pEntry.value = value;
1105                 pEntry.recordAccess(this);
1106                 return oldVal;
1107             }
1108         }
1109         modCount++;
1110         addEntry(hash, key, value, i, checkIfNeedTree);
1111         return null;
1112     }
1113 
1114     /**
1115      * Offloaded version of put for null keys
1116      */
1117     private V putForNullKey(V value) {
1118         if (nullKeyEntry != null) {
1119             V oldValue = nullKeyEntry.value;
1120             nullKeyEntry.value = value;
1121             nullKeyEntry.recordAccess(this);
1122             return oldValue;
1123         }
1124         modCount++;
1125         size++; // newEntry() skips size++
1126         nullKeyEntry = newEntry(0, null, value, null);
1127         return null;
1128     }
1129 
1130     private void putForCreateNullKey(V value) {
1131         // Look for preexisting entry for key.  This will never happen for
1132         // clone or deserialize.  It will only happen for construction if the
1133         // input Map is a sorted map whose ordering is inconsistent w/ equals.
1134         if (nullKeyEntry != null) {
1135             nullKeyEntry.value = value;
1136         } else {
1137             nullKeyEntry = newEntry(0, null, value, null);
1138             size++;
1139         }
1140     }
1141 
1142 
1143     /**
1144      * This method is used instead of put by constructors and
1145      * pseudoconstructors (clone, readObject).  It does not resize the table,
1146      * check for comodification, etc, though it will convert bins to TreeBins
1147      * as needed.  It calls createEntry rather than addEntry.
1148      */
1149     @SuppressWarnings("unchecked")
1150     private void putForCreate(K key, V value) {
1151         if (null == key) {
1152             putForCreateNullKey(value);
1153             return;
1154         }
1155         int hash = hash(key);
1156         int i = indexFor(hash, table.length);
1157         boolean checkIfNeedTree = false; // Might we convert bin to a TreeBin?
1158 
1159         /**
1160          * Look for preexisting entry for key.  This will never happen for
1161          * clone or deserialize.  It will only happen for construction if the
1162          * input Map is a sorted map whose ordering is inconsistent w/ equals.
1163          */
1164         if (table[i] instanceof Entry) {
1165             int listSize = 0;
1166             Entry<K,V> e = (Entry<K,V>) table[i];
1167             for (; e != null; e = (Entry<K,V>)e.next) {
1168                 Object k;
1169                 if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
1170                     e.value = value;
1171                     return;
1172                 }
1173                 listSize++;
1174             }
1175             // Didn't find, fall through to createEntry().
1176             // Check for conversion to TreeBin done via createEntry().
1177             checkIfNeedTree = listSize >= TreeBin.TREE_THRESHOLD;
1178         } else if (table[i] != null) {
1179             TreeBin e = (TreeBin)table[i];
1180             TreeNode p = e.putTreeNode(hash, key, value, null);
1181             if (p != null) {
1182                 p.entry.setValue(value); // Found an existing node, set value
1183             } else {
1184                 size++; // Added a new TreeNode, so update size
1185             }
1186             // don't need modCount++/check for resize - just return
1187             return;
1188         }
1189 
1190         createEntry(hash, key, value, i, checkIfNeedTree);
1191     }
1192 
1193     private void putAllForCreate(Map<? extends K, ? extends V> m) {
1194         for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
1195             putForCreate(e.getKey(), e.getValue());
1196     }
1197 
1198     /**
1199      * Rehashes the contents of this map into a new array with a
1200      * larger capacity.  This method is called automatically when the
1201      * number of keys in this map reaches its threshold.
1202      *
1203      * If current capacity is MAXIMUM_CAPACITY, this method does not
1204      * resize the map, but sets threshold to Integer.MAX_VALUE.
1205      * This has the effect of preventing future calls.
1206      *
1207      * @param newCapacity the new capacity, MUST be a power of two;
1208      *        must be greater than current capacity unless current
1209      *        capacity is MAXIMUM_CAPACITY (in which case value
1210      *        is irrelevant).
1211      */
1212     void resize(int newCapacity) {
1213         Object[] oldTable = table;
1214         int oldCapacity = oldTable.length;
1215         if (oldCapacity == MAXIMUM_CAPACITY) {
1216             threshold = Integer.MAX_VALUE;
1217             return;
1218         }
1219 
1220         Object[] newTable = new Object[newCapacity];
1221         transfer(newTable);
1222         table = newTable;
1223         threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
1224     }
1225 
1226     /**
1227      * Transfers all entries from current table to newTable.
1228      *
1229      * Assumes newTable is larger than table
1230      */
1231     @SuppressWarnings("unchecked")
1232     void transfer(Object[] newTable) {
1233         Object[] src = table;
1234         // assert newTable.length > src.length : "newTable.length(" +
1235         //   newTable.length + ") expected to be > src.length("+src.length+")";
1236         int newCapacity = newTable.length;
1237         for (int j = 0; j < src.length; j++) {
1238              if (src[j] instanceof Entry) {
1239                 // Assume: since wasn't TreeBin before, won't need TreeBin now
1240                 Entry<K,V> e = (Entry<K,V>) src[j];
1241                 while (null != e) {
1242                     Entry<K,V> next = (Entry<K,V>)e.next;
1243                     int i = indexFor(e.hash, newCapacity);
1244                     e.next = (Entry<K,V>) newTable[i];
1245                     newTable[i] = e;
1246                     e = next;
1247                 }
1248             } else if (src[j] != null) {
1249                 TreeBin e = (TreeBin) src[j];
1250                 TreeBin loTree = new TreeBin();
1251                 TreeBin hiTree = new TreeBin();
1252                 e.splitTreeBin(newTable, j, loTree, hiTree);
1253             }
1254         }
1255         Arrays.fill(table, null);
1256     }
1257 
1258     /**
1259      * Copies all of the mappings from the specified map to this map.
1260      * These mappings will replace any mappings that this map had for
1261      * any of the keys currently in the specified map.
1262      *
1263      * @param m mappings to be stored in this map
1264      * @throws NullPointerException if the specified map is null
1265      */
1266     public void putAll(Map<? extends K, ? extends V> m) {
1267         int numKeysToBeAdded = m.size();
1268         if (numKeysToBeAdded == 0)
1269             return;
1270 
1271         if (table == EMPTY_TABLE) {
1272             inflateTable((int) Math.max(numKeysToBeAdded * loadFactor, threshold));
1273         }
1274 
1275         /*
1276          * Expand the map if the map if the number of mappings to be added
1277          * is greater than or equal to threshold.  This is conservative; the
1278          * obvious condition is (m.size() + size) >= threshold, but this
1279          * condition could result in a map with twice the appropriate capacity,
1280          * if the keys to be added overlap with the keys already in this map.
1281          * By using the conservative calculation, we subject ourself
1282          * to at most one extra resize.
1283          */
1284         if (numKeysToBeAdded > threshold && table.length < MAXIMUM_CAPACITY) {
1285             resize(table.length * 2);
1286         }
1287 
1288         for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
1289             put(e.getKey(), e.getValue());
1290         }
1291 
1292     /**
1293      * Removes the mapping for the specified key from this map if present.
1294      *
1295      * @param  key key whose mapping is to be removed from the map
1296      * @return the previous value associated with <tt>key</tt>, or
1297      *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
1298      *         (A <tt>null</tt> return can also indicate that the map
1299      *         previously associated <tt>null</tt> with <tt>key</tt>.)
1300      */
1301     public V remove(Object key) {
1302         Entry<K,V> e = removeEntryForKey(key);
1303        return (e == null ? null : e.value);
1304    }
1305    // optimized implementations of default methods in Map
1306 
1307    @Override
1308    public void forEach(BiConsumer<? super K, ? super V> action) {
1309         Objects.requireNonNull(action);
1310         final int expectedModCount = modCount;
1311         if (nullKeyEntry != null) {
1312             forEachNullKey(expectedModCount, action);
1313         }
1314         Object[] tab = this.table;
1315         for(int index = 0; index < tab.length; index++) {
1316             Object item = tab[index];
1317             if (item == null) {
1318                 continue;
1319             }
1320             if (item instanceof HashMap.TreeBin) {
1321                 eachTreeNode(expectedModCount, ((TreeBin)item).first, action);
1322                 continue;
1323             }
1324             @SuppressWarnings("unchecked")
1325             Entry<K,V> entry = (Entry<K,V>)item;
1326             while (entry != null) {
1327                 action.accept(entry.key, entry.value);
1328                 entry = (Entry<K,V>)entry.next;
1329 
1330                 if (expectedModCount != modCount) {
1331                     throw new ConcurrentModificationException();
1332                 }
1333             }
1334         }
1335     }
1336 
1337     private void eachTreeNode(int expectedModCount, TreeNode<K,V> node, BiConsumer<? super K, ? super V> action) {
1338         while (node != null) {
1339             @SuppressWarnings("unchecked")
1340             Entry<K,V> entry = (Entry<K,V>)node.entry;
1341             action.accept(entry.key, entry.value);
1342             node = (TreeNode<K,V>)entry.next;
1343 
1344             if (expectedModCount != modCount) {
1345                 throw new ConcurrentModificationException();
1346             }
1347         }
1348     }
1349 
1350     private void forEachNullKey(int expectedModCount, BiConsumer<? super K, ? super V> action) {
1351         action.accept(null, nullKeyEntry.value);
1352 
1353         if (expectedModCount != modCount) {
1354             throw new ConcurrentModificationException();
1355         }
1356     }
1357 
1358   @Override
1359   public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
1360         Objects.requireNonNull(function);
1361         final int expectedModCount = modCount;
1362         if (nullKeyEntry != null) {
1363             replaceforNullKey(expectedModCount, function);
1364         }
1365         Object[] tab = this.table;
1366         for(int index = 0; index < tab.length; index++) {
1367             Object item = tab[index];
1368             if (item == null) {
1369                 continue;
1370             }
1371             if (item instanceof HashMap.TreeBin) {
1372                 replaceEachTreeNode(expectedModCount, ((TreeBin)item).first, function);
1373                 continue;
1374             }
1375             @SuppressWarnings("unchecked")
1376             Entry<K,V> entry = (Entry<K,V>)item;
1377             while (entry != null) {
1378                 function.apply(entry.key, entry.value);
1379                 entry = (Entry<K,V>)entry.next;
1380 
1381                 if (expectedModCount != modCount) {
1382                     throw new ConcurrentModificationException();
1383                 }
1384             }
1385         }
1386     }
1387 
1388     private void replaceEachTreeNode(int expectedModCount, TreeNode<K,V> node, BiFunction<? super K, ? super V, ? extends V> function) {
1389         while (node != null) {
1390             @SuppressWarnings("unchecked")
1391             Entry<K,V> entry = (Entry<K,V>)node.entry;
1392             entry.value = function.apply(entry.key, entry.value);
1393             node = (TreeNode<K,V>)entry.next;
1394 
1395             if (expectedModCount != modCount) {
1396                 throw new ConcurrentModificationException();
1397             }
1398         }
1399     }
1400 
1401     private void replaceforNullKey(int expectedModCount, BiFunction<? super K, ? super V, ? extends V> function) {
1402         nullKeyEntry.value = function.apply(null, nullKeyEntry.value);
1403 
1404         if (expectedModCount != modCount) {
1405             throw new ConcurrentModificationException();
1406         }
1407     }
1408 
1409     @Override
1410     public V putIfAbsent(K key, V value) {
1411         if (table == EMPTY_TABLE) {
1412             inflateTable(threshold);
1413         }
1414         if (key == null) {
1415             if (nullKeyEntry == null || nullKeyEntry.value == null) {
1416                 putForNullKey(value);
1417                 return null;
1418             } else {
1419                 return nullKeyEntry.value;
1420             }
1421         }
1422         int hash = hash(key);
1423         int i = indexFor(hash, table.length);
1424         boolean checkIfNeedTree = false; // Might we convert bin to a TreeBin?
1425 
1426         if (table[i] instanceof Entry) {
1427             int listSize = 0;
1428             Entry<K,V> e = (Entry<K,V>) table[i];
1429             for (; e != null; e = (Entry<K,V>)e.next) {
1430                 if (e.hash == hash && Objects.equals(e.key, key)) {
1431                     if (e.value != null) {
1432                         return e.value;
1433                     }
1434                     e.value = value;
1435                     e.recordAccess(this);
1436                     return null;
1437                 }
1438                 listSize++;
1439             }
1440             // Didn't find, so fall through and call addEntry() to add the
1441             // Entry and check for TreeBin conversion.
1442             checkIfNeedTree = listSize >= TreeBin.TREE_THRESHOLD;
1443         } else if (table[i] != null) {
1444             TreeBin e = (TreeBin)table[i];
1445             TreeNode p = e.putTreeNode(hash, key, value, null);
1446             if (p == null) { // not found, putTreeNode() added a new node
1447                 modCount++;
1448                 size++;
1449                 if (size >= threshold) {
1450                     resize(2 * table.length);
1451                 }
1452                 return null;
1453             } else { // putTreeNode() found an existing node
1454                 Entry<K,V> pEntry = (Entry<K,V>)p.entry;
1455                 V oldVal = pEntry.value;
1456                 if (oldVal == null) { // only replace if maps to null
1457                     pEntry.value = value;
1458                     pEntry.recordAccess(this);
1459                 }
1460                 return oldVal;
1461             }
1462         }
1463         modCount++;
1464         addEntry(hash, key, value, i, checkIfNeedTree);
1465         return null;
1466     }
1467 
1468     @Override
1469     public boolean remove(Object key, Object value) {
1470         if (isEmpty()) {
1471             return false;
1472         }
1473         if (key == null) {
1474             if (nullKeyEntry != null &&
1475                  Objects.equals(nullKeyEntry.value, value)) {
1476                 removeNullKey();
1477                 return true;
1478             }
1479             return false;
1480         }
1481         int hash = hash(key);
1482         int i = indexFor(hash, table.length);
1483 
1484         if (table[i] instanceof Entry) {
1485             @SuppressWarnings("unchecked")
1486             Entry<K,V> prev = (Entry<K,V>) table[i];
1487             Entry<K,V> e = prev;
1488             while (e != null) {
1489                 @SuppressWarnings("unchecked")
1490                 Entry<K,V> next = (Entry<K,V>) e.next;
1491                 if (e.hash == hash && Objects.equals(e.key, key)) {
1492                     if (!Objects.equals(e.value, value)) {
1493                         return false;
1494                     }
1495                     modCount++;
1496                     size--;
1497                     if (prev == e)
1498                         table[i] = next;
1499                     else
1500                         prev.next = next;
1501                     e.recordRemoval(this);
1502                     return true;
1503                 }
1504                 prev = e;
1505                 e = next;
1506             }
1507         } else if (table[i] != null) {
1508             TreeBin tb = ((TreeBin) table[i]);
1509             TreeNode p = tb.getTreeNode(hash, (K)key);
1510             if (p != null) {
1511                 Entry<K,V> pEntry = (Entry<K,V>)p.entry;
1512                 // assert pEntry.key.equals(key);
1513                 if (Objects.equals(pEntry.value, value)) {
1514                     modCount++;
1515                     size--;
1516                     tb.deleteTreeNode(p);
1517                     pEntry.recordRemoval(this);
1518                     if (tb.root == null || tb.first == null) {
1519                         // assert tb.root == null && tb.first == null :
1520                         //         "TreeBin.first and root should both be null";
1521                         // TreeBin is now empty, we should blank this bin
1522                         table[i] = null;
1523                     }
1524                     return true;
1525                 }
1526             }
1527         }
1528         return false;
1529     }
1530 
1531     @Override
1532     public boolean replace(K key, V oldValue, V newValue) {
1533         if (isEmpty()) {
1534             return false;
1535         }
1536         if (key == null) {
1537             if (nullKeyEntry != null &&
1538                  Objects.equals(nullKeyEntry.value, oldValue)) {
1539                 putForNullKey(newValue);
1540                 return true;
1541             }
1542             return false;
1543         }
1544         int hash = hash(key);
1545         int i = indexFor(hash, table.length);
1546 
1547         if (table[i] instanceof Entry) {
1548             @SuppressWarnings("unchecked")
1549             Entry<K,V> e = (Entry<K,V>) table[i];
1550             for (; e != null; e = (Entry<K,V>)e.next) {
1551                 if (e.hash == hash && Objects.equals(e.key, key) && Objects.equals(e.value, oldValue)) {
1552                     e.value = newValue;
1553                     e.recordAccess(this);
1554                     return true;
1555                 }
1556             }
1557             return false;
1558         } else if (table[i] != null) {
1559             TreeBin tb = ((TreeBin) table[i]);
1560             TreeNode p = tb.getTreeNode(hash, key);
1561             if (p != null) {
1562                 Entry<K,V> pEntry = (Entry<K,V>)p.entry;
1563                 // assert pEntry.key.equals(key);
1564                 if (Objects.equals(pEntry.value, oldValue)) {
1565                     pEntry.value = newValue;
1566                     pEntry.recordAccess(this);
1567                     return true;
1568                 }
1569             }
1570         }
1571         return false;
1572     }
1573 
1574    @Override
1575     public V replace(K key, V value) {
1576         if (isEmpty()) {
1577             return null;
1578         }
1579         if (key == null) {
1580             if (nullKeyEntry != null) {
1581                 return putForNullKey(value);
1582             }
1583             return null;
1584         }
1585         int hash = hash(key);
1586         int i = indexFor(hash, table.length);
1587         if (table[i] instanceof Entry) {
1588             @SuppressWarnings("unchecked")
1589             Entry<K,V> e = (Entry<K,V>)table[i];
1590             for (; e != null; e = (Entry<K,V>)e.next) {
1591                 if (e.hash == hash && Objects.equals(e.key, key)) {
1592                     V oldValue = e.value;
1593                     e.value = value;
1594                     e.recordAccess(this);
1595                     return oldValue;
1596                 }
1597             }
1598 
1599             return null;
1600         } else if (table[i] != null) {
1601             TreeBin tb = ((TreeBin) table[i]);
1602             TreeNode p = tb.getTreeNode(hash, key);
1603             if (p != null) {
1604                 Entry<K,V> pEntry = (Entry<K,V>)p.entry;
1605                 // assert pEntry.key.equals(key);
1606                 V oldValue = pEntry.value;
1607                 pEntry.value = value;
1608                 pEntry.recordAccess(this);
1609                 return oldValue;
1610             }
1611         }
1612         return null;
1613     }
1614 
1615     @Override
1616     public V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction) {
1617         if (table == EMPTY_TABLE) {
1618             inflateTable(threshold);
1619         }
1620         if (key == null) {
1621             if (nullKeyEntry == null || nullKeyEntry.value == null) {
1622                 V newValue = mappingFunction.apply(key);
1623                 if (newValue != null) {
1624                     putForNullKey(newValue);
1625                 }
1626                 return newValue;
1627             }
1628             return nullKeyEntry.value;
1629         }
1630         int hash = hash(key);
1631         int i = indexFor(hash, table.length);
1632         boolean checkIfNeedTree = false; // Might we convert bin to a TreeBin?
1633 
1634         if (table[i] instanceof Entry) {
1635             int listSize = 0;
1636             @SuppressWarnings("unchecked")
1637             Entry<K,V> e = (Entry<K,V>)table[i];
1638             for (; e != null; e = (Entry<K,V>)e.next) {
1639                 if (e.hash == hash && Objects.equals(e.key, key)) {
1640                     V oldValue = e.value;
1641                     if (oldValue == null) {
1642                         V newValue = mappingFunction.apply(key);
1643                         if (newValue != null) {
1644                             e.value = newValue;
1645                             e.recordAccess(this);
1646                         }
1647                         return newValue;
1648                     }
1649                     return oldValue;
1650                 }
1651                 listSize++;
1652             }
1653             // Didn't find, fall through to call the mapping function
1654             checkIfNeedTree = listSize >= TreeBin.TREE_THRESHOLD;
1655         } else if (table[i] != null) {
1656             TreeBin e = (TreeBin)table[i];
1657             V value = mappingFunction.apply(key);
1658             if (value == null) { // Return the existing value, if any
1659                 TreeNode p = e.getTreeNode(hash, key);
1660                 if (p != null) {
1661                     return (V) p.entry.value;
1662                 }
1663                 return null;
1664             } else { // Put the new value into the Tree, if absent
1665                 TreeNode p = e.putTreeNode(hash, key, value, null);
1666                 if (p == null) { // not found, new node was added
1667                     modCount++;
1668                     size++;
1669                     if (size >= threshold) {
1670                         resize(2 * table.length);
1671                     }
1672                     return value;
1673                 } else { // putTreeNode() found an existing node
1674                     Entry<K,V> pEntry = (Entry<K,V>)p.entry;
1675                     V oldVal = pEntry.value;
1676                     if (oldVal == null) { // only replace if maps to null
1677                         pEntry.value = value;
1678                         pEntry.recordAccess(this);
1679                         return value;
1680                     }
1681                     return oldVal;
1682                 }
1683             }
1684         }
1685         V newValue = mappingFunction.apply(key);
1686         if (newValue != null) { // add Entry and check for TreeBin conversion
1687             modCount++;
1688             addEntry(hash, key, newValue, i, checkIfNeedTree);
1689         }
1690 
1691         return newValue;
1692     }
1693 
1694     @Override
1695     public V computeIfPresent(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
1696         if (isEmpty()) {
1697             return null;
1698         }
1699         if (key == null) {
1700             V oldValue;
1701             if (nullKeyEntry != null && (oldValue = nullKeyEntry.value) != null) {
1702                 V newValue = remappingFunction.apply(key, oldValue);
1703                 if (newValue != null ) {
1704                     putForNullKey(newValue);
1705                     return newValue;
1706                 } else {
1707                     removeNullKey();
1708                 }
1709             }
1710             return null;
1711         }
1712         int hash = hash(key);
1713         int i = indexFor(hash, table.length);
1714         if (table[i] instanceof Entry) {
1715             @SuppressWarnings("unchecked")
1716             Entry<K,V> prev = (Entry<K,V>)table[i];
1717             Entry<K,V> e = prev;
1718             while (e != null) {
1719                 Entry<K,V> next = (Entry<K,V>)e.next;
1720                 if (e.hash == hash && Objects.equals(e.key, key)) {
1721                     V oldValue = e.value;
1722                     if (oldValue == null)
1723                         break;
1724                     V newValue = remappingFunction.apply(key, oldValue);
1725                     if (newValue == null) {
1726                         modCount++;
1727                         size--;
1728                         if (prev == e)
1729                             table[i] = next;
1730                         else
1731                             prev.next = next;
1732                         e.recordRemoval(this);
1733                     } else {
1734                         e.value = newValue;
1735                         e.recordAccess(this);
1736                     }
1737                     return newValue;
1738                 }
1739                 prev = e;
1740                 e = next;
1741             }
1742         } else if (table[i] != null) {
1743             TreeBin tb = (TreeBin)table[i];
1744             TreeNode p = tb.getTreeNode(hash, key);
1745             if (p != null) {
1746                 Entry<K,V> pEntry = (Entry<K,V>)p.entry;
1747                 // assert pEntry.key.equals(key);
1748                 V oldValue = pEntry.value;
1749                 if (oldValue != null) {
1750                     V newValue = remappingFunction.apply(key, oldValue);
1751                     if (newValue == null) { // remove mapping
1752                         modCount++;
1753                         size--;
1754                         tb.deleteTreeNode(p);
1755                         pEntry.recordRemoval(this);
1756                         if (tb.root == null || tb.first == null) {
1757                             // assert tb.root == null && tb.first == null :
1758                             //     "TreeBin.first and root should both be null";
1759                             // TreeBin is now empty, we should blank this bin
1760                             table[i] = null;
1761                         }
1762                     } else {
1763                         pEntry.value = newValue;
1764                         pEntry.recordAccess(this);
1765                     }
1766                     return newValue;
1767                 }
1768             }
1769         }
1770         return null;
1771     }
1772 
1773     @Override
1774     public V compute(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
1775         if (table == EMPTY_TABLE) {
1776             inflateTable(threshold);
1777         }
1778         if (key == null) {
1779             V oldValue = nullKeyEntry == null ? null : nullKeyEntry.value;
1780             V newValue = remappingFunction.apply(key, oldValue);
1781             if (newValue != oldValue) {
1782                 if (newValue == null) {
1783                     removeNullKey();
1784                 } else {
1785                     putForNullKey(newValue);
1786                 }
1787             }
1788             return newValue;
1789         }
1790         int hash = hash(key);
1791         int i = indexFor(hash, table.length);
1792         boolean checkIfNeedTree = false; // Might we convert bin to a TreeBin?
1793 
1794         if (table[i] instanceof Entry) {
1795             int listSize = 0;
1796             @SuppressWarnings("unchecked")
1797             Entry<K,V> prev = (Entry<K,V>)table[i];
1798             Entry<K,V> e = prev;
1799 
1800             while (e != null) {
1801                 Entry<K,V> next = (Entry<K,V>)e.next;
1802                 if (e.hash == hash && Objects.equals(e.key, key)) {
1803                     V oldValue = e.value;
1804                     V newValue = remappingFunction.apply(key, oldValue);
1805                     if (newValue != oldValue) {
1806                         if (newValue == null) {
1807                             modCount++;
1808                             size--;
1809                             if (prev == e)
1810                                 table[i] = next;
1811                             else
1812                                 prev.next = next;
1813                             e.recordRemoval(this);
1814                         } else {
1815                             e.value = newValue;
1816                             e.recordAccess(this);
1817                         }
1818                     }
1819                     return newValue;
1820                 }
1821                 prev = e;
1822                 e = next;
1823                 listSize++;
1824             }
1825             checkIfNeedTree = listSize >= TreeBin.TREE_THRESHOLD;
1826         } else if (table[i] != null) {
1827             TreeBin tb = (TreeBin)table[i];
1828             TreeNode p = tb.getTreeNode(hash, key);
1829             V oldValue = p == null ? null : (V)p.entry.value;
1830             V newValue = remappingFunction.apply(key, oldValue);
1831             if (newValue != oldValue) {
1832                 if (newValue == null) {
1833                     Entry<K,V> pEntry = (Entry<K,V>)p.entry;
1834                     modCount++;
1835                     size--;
1836                     tb.deleteTreeNode(p);
1837                     pEntry.recordRemoval(this);
1838                     if (tb.root == null || tb.first == null) {
1839                         // assert tb.root == null && tb.first == null :
1840                         //         "TreeBin.first and root should both be null";
1841                         // TreeBin is now empty, we should blank this bin
1842                         table[i] = null;
1843                     }
1844                 } else {
1845                     if (p != null) { // just update the value
1846                         Entry<K,V> pEntry = (Entry<K,V>)p.entry;
1847                         pEntry.value = newValue;
1848                         pEntry.recordAccess(this);
1849                     } else { // need to put new node
1850                         p = tb.putTreeNode(hash, key, newValue, null);
1851                         // assert p == null; // should have added a new node
1852                         modCount++;
1853                         size++;
1854                         if (size >= threshold) {
1855                             resize(2 * table.length);
1856                         }
1857                     }
1858                 }
1859             }
1860             return newValue;
1861         }
1862 
1863         V newValue = remappingFunction.apply(key, null);
1864         if (newValue != null) {
1865             modCount++;
1866             addEntry(hash, key, newValue, i, checkIfNeedTree);
1867         }
1868 
1869         return newValue;
1870     }
1871 
1872     @Override
1873     public V merge(K key, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
1874         if (table == EMPTY_TABLE) {
1875             inflateTable(threshold);
1876         }
1877         if (key == null) {
1878             V oldValue = nullKeyEntry == null ? null : nullKeyEntry.value;
1879             V newValue = oldValue == null ? value : remappingFunction.apply(oldValue, value);
1880             if (newValue != null) {
1881                 putForNullKey(newValue);
1882             } else if (nullKeyEntry != null) {
1883                 removeNullKey();
1884             }
1885             return newValue;
1886         }
1887         int hash = hash(key);
1888         int i = indexFor(hash, table.length);
1889         boolean checkIfNeedTree = false; // Might we convert bin to a TreeBin?
1890 
1891         if (table[i] instanceof Entry) {
1892             int listSize = 0;
1893             @SuppressWarnings("unchecked")
1894             Entry<K,V> prev = (Entry<K,V>)table[i];
1895             Entry<K,V> e = prev;
1896 
1897             while (e != null) {
1898                 Entry<K,V> next = (Entry<K,V>)e.next;
1899                 if (e.hash == hash && Objects.equals(e.key, key)) {
1900                     V oldValue = e.value;
1901                     V newValue = (oldValue == null) ? value :
1902                                  remappingFunction.apply(oldValue, value);
1903                     if (newValue == null) {
1904                         modCount++;
1905                         size--;
1906                         if (prev == e)
1907                             table[i] = next;
1908                         else
1909                             prev.next = next;
1910                         e.recordRemoval(this);
1911                     } else {
1912                         e.value = newValue;
1913                         e.recordAccess(this);
1914                     }
1915                     return newValue;
1916                 }
1917                 prev = e;
1918                 e = next;
1919                 listSize++;
1920             }
1921             // Didn't find, so fall through and (maybe) call addEntry() to add
1922             // the Entry and check for TreeBin conversion.
1923             checkIfNeedTree = listSize >= TreeBin.TREE_THRESHOLD;
1924         } else if (table[i] != null) {
1925             TreeBin tb = (TreeBin)table[i];
1926             TreeNode p = tb.getTreeNode(hash, key);
1927             V oldValue = p == null ? null : (V)p.entry.value;
1928             V newValue = (oldValue == null) ? value :
1929                          remappingFunction.apply(oldValue, value);
1930             if (newValue == null) {
1931                 if (p != null) {
1932                     Entry<K,V> pEntry = (Entry<K,V>)p.entry;
1933                     modCount++;
1934                     size--;
1935                     tb.deleteTreeNode(p);
1936                     pEntry.recordRemoval(this);
1937 
1938                     if (tb.root == null || tb.first == null) {
1939                         // assert tb.root == null && tb.first == null :
1940                         //         "TreeBin.first and root should both be null";
1941                         // TreeBin is now empty, we should blank this bin
1942                         table[i] = null;
1943                     }
1944                 }
1945                 return null;
1946             } else if (newValue != oldValue) {
1947                 if (p != null) { // just update the value
1948                     Entry<K,V> pEntry = (Entry<K,V>)p.entry;
1949                     pEntry.value = newValue;
1950                     pEntry.recordAccess(this);
1951                 } else { // need to put new node
1952                     p = tb.putTreeNode(hash, key, newValue, null);
1953                     // assert p == null; // should have added a new node
1954                     modCount++;
1955                     size++;
1956                     if (size >= threshold) {
1957                         resize(2 * table.length);
1958                     }
1959                 }
1960             }
1961             return newValue;
1962         }
1963         if (value != null) {
1964             modCount++;
1965             addEntry(hash, key, value, i, checkIfNeedTree);
1966         }
1967         return value;
1968     }
1969 
1970     // end of optimized implementations of default methods in Map
1971 
1972     /**
1973      * Removes and returns the entry associated with the specified key
1974      * in the HashMap.  Returns null if the HashMap contains no mapping
1975      * for this key.
1976      *
1977      * We don't bother converting TreeBins back to Entry lists if the bin falls
1978      * back below TREE_THRESHOLD, but we do clear bins when removing the last
1979      * TreeNode in a TreeBin.
1980      */
1981     final Entry<K,V> removeEntryForKey(Object key) {
1982         if (isEmpty()) {
1983             return null;
1984         }
1985         if (key == null) {
1986             if (nullKeyEntry != null) {
1987                 return removeNullKey();
1988             }
1989             return null;
1990         }
1991         int hash = hash(key);
1992         int i = indexFor(hash, table.length);
1993 
1994         if (table[i] instanceof Entry) {
1995             @SuppressWarnings("unchecked")
1996             Entry<K,V> prev = (Entry<K,V>)table[i];
1997             Entry<K,V> e = prev;
1998 
1999             while (e != null) {
2000                 @SuppressWarnings("unchecked")
2001                 Entry<K,V> next = (Entry<K,V>) e.next;
2002                 if (e.hash == hash && Objects.equals(e.key, key)) {
2003                     modCount++;
2004                     size--;
2005                     if (prev == e)
2006                         table[i] = next;
2007                     else
2008                         prev.next = next;
2009                     e.recordRemoval(this);
2010                     return e;
2011                 }
2012                 prev = e;
2013                 e = next;
2014             }
2015         } else if (table[i] != null) {
2016             TreeBin tb = ((TreeBin) table[i]);
2017             TreeNode p = tb.getTreeNode(hash, (K)key);
2018             if (p != null) {
2019                 Entry<K,V> pEntry = (Entry<K,V>)p.entry;
2020                 // assert pEntry.key.equals(key);
2021                 modCount++;
2022                 size--;
2023                 tb.deleteTreeNode(p);
2024                 pEntry.recordRemoval(this);
2025                 if (tb.root == null || tb.first == null) {
2026                     // assert tb.root == null && tb.first == null :
2027                     //             "TreeBin.first and root should both be null";
2028                     // TreeBin is now empty, we should blank this bin
2029                     table[i] = null;
2030                 }
2031                 return pEntry;
2032             }
2033         }
2034         return null;
2035     }
2036 
2037     /**
2038      * Special version of remove for EntrySet using {@code Map.Entry.equals()}
2039      * for matching.
2040      */
2041     final Entry<K,V> removeMapping(Object o) {
2042         if (isEmpty() || !(o instanceof Map.Entry))
2043             return null;
2044 
2045         Map.Entry<?,?> entry = (Map.Entry<?,?>) o;
2046         Object key = entry.getKey();
2047 
2048         if (key == null) {
2049             if (entry.equals(nullKeyEntry)) {
2050                 return removeNullKey();
2051             }
2052             return null;
2053         }
2054 
2055         int hash = hash(key);
2056         int i = indexFor(hash, table.length);
2057 
2058         if (table[i] instanceof Entry) {
2059             @SuppressWarnings("unchecked")
2060                 Entry<K,V> prev = (Entry<K,V>)table[i];
2061             Entry<K,V> e = prev;
2062 
2063             while (e != null) {
2064                 @SuppressWarnings("unchecked")
2065                 Entry<K,V> next = (Entry<K,V>)e.next;
2066                 if (e.hash == hash && e.equals(entry)) {
2067                     modCount++;
2068                     size--;
2069                     if (prev == e)
2070                         table[i] = next;
2071                     else
2072                         prev.next = next;
2073                     e.recordRemoval(this);
2074                     return e;
2075                 }
2076                 prev = e;
2077                 e = next;
2078             }
2079         } else if (table[i] != null) {
2080             TreeBin tb = ((TreeBin) table[i]);
2081             TreeNode p = tb.getTreeNode(hash, (K)key);
2082             if (p != null && p.entry.equals(entry)) {
2083                 @SuppressWarnings("unchecked")
2084                 Entry<K,V> pEntry = (Entry<K,V>)p.entry;
2085                 // assert pEntry.key.equals(key);
2086                 modCount++;
2087                 size--;
2088                 tb.deleteTreeNode(p);
2089                 pEntry.recordRemoval(this);
2090                 if (tb.root == null || tb.first == null) {
2091                     // assert tb.root == null && tb.first == null :
2092                     //             "TreeBin.first and root should both be null";
2093                     // TreeBin is now empty, we should blank this bin
2094                     table[i] = null;
2095                 }
2096                 return pEntry;
2097             }
2098         }
2099         return null;
2100     }
2101 
2102     /*
2103      * Remove the mapping for the null key, and update internal accounting
2104      * (size, modcount, recordRemoval, etc).
2105      *
2106      * Assumes nullKeyEntry is non-null.
2107      */
2108     private Entry<K,V> removeNullKey() {
2109         // assert nullKeyEntry != null;
2110         Entry<K,V> retVal = nullKeyEntry;
2111         modCount++;
2112         size--;
2113         retVal.recordRemoval(this);
2114         nullKeyEntry = null;
2115         return retVal;
2116     }
2117 
2118     /**
2119      * Removes all of the mappings from this map.
2120      * The map will be empty after this call returns.
2121      */
2122     public void clear() {
2123         modCount++;
2124         if (nullKeyEntry != null) {
2125             nullKeyEntry = null;
2126         }
2127         Arrays.fill(table, null);
2128         size = 0;
2129     }
2130 
2131     /**
2132      * Returns <tt>true</tt> if this map maps one or more keys to the
2133      * specified value.
2134      *
2135      * @param value value whose presence in this map is to be tested
2136      * @return <tt>true</tt> if this map maps one or more keys to the
2137      *         specified value
2138      */
2139     public boolean containsValue(Object value) {
2140         if (value == null) {
2141             return containsNullValue();
2142         }
2143         Object[] tab = table;
2144         for (int i = 0; i < tab.length; i++) {
2145             if (tab[i] instanceof Entry) {
2146                 Entry<?,?> e = (Entry<?,?>)tab[i];
2147                 for (; e != null; e = (Entry<?,?>)e.next) {
2148                     if (value.equals(e.value)) {
2149                         return true;
2150                     }
2151                 }
2152             } else if (tab[i] != null) {
2153                 TreeBin e = (TreeBin)tab[i];
2154                 TreeNode p = e.first;
2155                 for (; p != null; p = (TreeNode) p.entry.next) {
2156                     if (value == p.entry.value || value.equals(p.entry.value)) {
2157                         return true;
2158                     }
2159                 }
2160             }
2161         }
2162         // Didn't find value in table - could be in nullKeyEntry
2163         return (nullKeyEntry != null && (value == nullKeyEntry.value ||
2164                                          value.equals(nullKeyEntry.value)));
2165     }
2166 
2167     /**
2168      * Special-case code for containsValue with null argument
2169      */
2170     private boolean containsNullValue() {
2171         Object[] tab = table;
2172         for (int i = 0; i < tab.length; i++) {
2173             if (tab[i] instanceof Entry) {
2174                 Entry<K,V> e = (Entry<K,V>)tab[i];
2175                 for (; e != null; e = (Entry<K,V>)e.next) {
2176                     if (e.value == null) {
2177                         return true;
2178                     }
2179                 }
2180             } else if (tab[i] != null) {
2181                 TreeBin e = (TreeBin)tab[i];
2182                 TreeNode p = e.first;
2183                 for (; p != null; p = (TreeNode) p.entry.next) {
2184                     if (p.entry.value == null) {
2185                         return true;
2186                     }
2187                 }
2188             }
2189         }
2190         // Didn't find value in table - could be in nullKeyEntry
2191         return (nullKeyEntry != null && nullKeyEntry.value == null);
2192     }
2193 
2194     /**
2195      * Returns a shallow copy of this <tt>HashMap</tt> instance: the keys and
2196      * values themselves are not cloned.
2197      *
2198      * @return a shallow copy of this map
2199      */
2200     @SuppressWarnings("unchecked")
2201     public Object clone() {
2202         HashMap<K,V> result = null;
2203         try {
2204             result = (HashMap<K,V>)super.clone();
2205         } catch (CloneNotSupportedException e) {
2206             // assert false;
2207         }
2208         if (result.table != EMPTY_TABLE) {
2209             result.inflateTable(Math.min(
2210                 (int) Math.min(
2211                     size * Math.min(1 / loadFactor, 4.0f),
2212                     // we have limits...
2213                     HashMap.MAXIMUM_CAPACITY),
2214                 table.length));
2215         }
2216         result.entrySet = null;
2217         result.modCount = 0;
2218         result.size = 0;
2219         result.nullKeyEntry = null;
2220         result.init();
2221         result.putAllForCreate(this);
2222 
2223         return result;
2224     }
2225 
2226     static class Entry<K,V> implements Map.Entry<K,V> {
2227         final K key;
2228         V value;
2229         Object next; // an Entry, or a TreeNode
2230         final int hash;
2231 
2232         /**
2233          * Creates new entry.
2234          */
2235         Entry(int h, K k, V v, Object n) {
2236             value = v;
2237             next = n;
2238             key = k;
2239             hash = h;
2240         }
2241 
2242         public final K getKey() {
2243             return key;
2244         }
2245 
2246         public final V getValue() {
2247             return value;
2248         }
2249 
2250         public final V setValue(V newValue) {
2251             V oldValue = value;
2252             value = newValue;
2253             return oldValue;
2254         }
2255 
2256         public final boolean equals(Object o) {
2257             if (!(o instanceof Map.Entry))
2258                 return false;
2259             Map.Entry<?,?> e = (Map.Entry<?,?>)o;
2260             Object k1 = getKey();
2261             Object k2 = e.getKey();
2262             if (k1 == k2 || (k1 != null && k1.equals(k2))) {
2263                 Object v1 = getValue();
2264                 Object v2 = e.getValue();
2265                 if (v1 == v2 || (v1 != null && v1.equals(v2)))
2266                     return true;
2267                 }
2268             return false;
2269         }
2270 
2271         public final int hashCode() {
2272             return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());
2273         }
2274 
2275         public final String toString() {
2276             return getKey() + "=" + getValue();
2277         }
2278 
2279         /**
2280          * This method is invoked whenever the value in an entry is
2281          * overwritten for a key that's already in the HashMap.
2282          */
2283         void recordAccess(HashMap<K,V> m) {
2284         }
2285 
2286         /**
2287          * This method is invoked whenever the entry is
2288          * removed from the table.
2289          */
2290         void recordRemoval(HashMap<K,V> m) {
2291         }
2292     }
2293 
2294     void addEntry(int hash, K key, V value, int bucketIndex) {
2295         addEntry(hash, key, value, bucketIndex, true);
2296     }
2297 
2298     /**
2299      * Adds a new entry with the specified key, value and hash code to
2300      * the specified bucket.  It is the responsibility of this
2301      * method to resize the table if appropriate.  The new entry is then
2302      * created by calling createEntry().
2303      *
2304      * Subclass overrides this to alter the behavior of put method.
2305      *
2306      * If checkIfNeedTree is false, it is known that this bucket will not need
2307      * to be converted to a TreeBin, so don't bothering checking.
2308      *
2309      * Assumes key is not null.
2310      */
2311     void addEntry(int hash, K key, V value, int bucketIndex, boolean checkIfNeedTree) {
2312         // assert key != null;
2313         if ((size >= threshold) && (null != table[bucketIndex])) {
2314             resize(2 * table.length);
2315             hash = hash(key);
2316             bucketIndex = indexFor(hash, table.length);
2317         }
2318         createEntry(hash, key, value, bucketIndex, checkIfNeedTree);
2319     }
2320 
2321     /**
2322      * Called by addEntry(), and also used when creating entries
2323      * as part of Map construction or "pseudo-construction" (cloning,
2324      * deserialization).  This version does not check for resizing of the table.
2325      *
2326      * This method is responsible for converting a bucket to a TreeBin once
2327      * TREE_THRESHOLD is reached. However if checkIfNeedTree is false, it is known
2328      * that this bucket will not need to be converted to a TreeBin, so don't
2329      * bother checking.  The new entry is constructed by calling newEntry().
2330      *
2331      * Assumes key is not null.
2332      *
2333      * Note: buckets already converted to a TreeBin don't call this method, but
2334      * instead call TreeBin.putTreeNode() to create new entries.
2335      */
2336     void createEntry(int hash, K key, V value, int bucketIndex, boolean checkIfNeedTree) {
2337         // assert key != null;
2338         @SuppressWarnings("unchecked")
2339             Entry<K,V> e = (Entry<K,V>)table[bucketIndex];
2340         table[bucketIndex] = newEntry(hash, key, value, e);
2341         size++;
2342 
2343         if (checkIfNeedTree) {
2344             int listSize = 0;
2345             for (e = (Entry<K,V>) table[bucketIndex]; e != null; e = (Entry<K,V>)e.next) {
2346                 listSize++;
2347                 if (listSize >= TreeBin.TREE_THRESHOLD) { // Convert to TreeBin
2348                     if (comparableClassFor(key) != null) {
2349                         TreeBin t = new TreeBin();
2350                         t.populate((Entry)table[bucketIndex]);
2351                         table[bucketIndex] = t;
2352                     }
2353                     break;
2354                 }
2355             }
2356         }
2357     }
2358 
2359     /*
2360      * Factory method to create a new Entry object.
2361      */
2362     Entry<K,V> newEntry(int hash, K key, V value, Object next) {
2363         return new HashMap.Entry<>(hash, key, value, next);
2364     }
2365 
2366 
2367     private abstract class HashIterator<E> implements Iterator<E> {
2368         Object next;            // next entry to return, an Entry or a TreeNode
2369         int expectedModCount;   // For fast-fail
2370         int index;              // current slot
2371         Object current;         // current entry, an Entry or a TreeNode
2372 
2373         HashIterator() {
2374             expectedModCount = modCount;
2375             if (size > 0) { // advance to first entry
2376                 if (nullKeyEntry != null) {
2377                     // assert nullKeyEntry.next == null;
2378                     // This works with nextEntry(): nullKeyEntry isa Entry, and
2379                     // e.next will be null, so we'll hit the findNextBin() call.
2380                     next = nullKeyEntry;
2381                 } else {
2382                     findNextBin();
2383                 }
2384             }
2385         }
2386 
2387         public final boolean hasNext() {
2388             return next != null;
2389         }
2390 
2391         @SuppressWarnings("unchecked")
2392         final Entry<K,V> nextEntry() {
2393             if (modCount != expectedModCount) {
2394                 throw new ConcurrentModificationException();
2395             }
2396             Object e = next;
2397             Entry<K,V> retVal;
2398 
2399             if (e == null)
2400                 throw new NoSuchElementException();
2401 
2402             if (e instanceof TreeNode) { // TreeBin
2403                 retVal = (Entry<K,V>)((TreeNode)e).entry;
2404                 next = retVal.next;
2405             } else {
2406                 retVal = (Entry<K,V>)e;
2407                 next = ((Entry<K,V>)e).next;
2408             }
2409 
2410             if (next == null) { // Move to next bin
2411                 findNextBin();
2412             }
2413             current = e;
2414             return retVal;
2415         }
2416 
2417         public void remove() {
2418             if (current == null)
2419                 throw new IllegalStateException();
2420             if (modCount != expectedModCount)
2421                 throw new ConcurrentModificationException();
2422             K k;
2423 
2424             if (current instanceof Entry) {
2425                 k = ((Entry<K,V>)current).key;
2426             } else {
2427                 k = ((Entry<K,V>)((TreeNode)current).entry).key;
2428 
2429             }
2430             current = null;
2431             HashMap.this.removeEntryForKey(k);
2432             expectedModCount = modCount;
2433         }
2434 
2435         /*
2436          * Set 'next' to the first entry of the next non-empty bin in the table
2437          */
2438         private void findNextBin() {
2439             // assert next == null;
2440             Object[] t = table;
2441 
2442             while (index < t.length && (next = t[index++]) == null)
2443                 ;
2444             if (next instanceof HashMap.TreeBin) { // Point to the first TreeNode
2445                 next = ((TreeBin) next).first;
2446                 // assert next != null; // There should be no empty TreeBins
2447             }
2448         }
2449     }
2450 
2451     private final class ValueIterator extends HashIterator<V> {
2452         public V next() {
2453             return nextEntry().value;
2454         }
2455     }
2456 
2457     private final class KeyIterator extends HashIterator<K> {
2458         public K next() {
2459             return nextEntry().getKey();
2460         }
2461     }
2462 
2463     private final class EntryIterator extends HashIterator<Map.Entry<K,V>> {
2464         public Map.Entry<K,V> next() {
2465             return nextEntry();
2466         }
2467     }
2468 
2469     // Subclass overrides these to alter behavior of views' iterator() method
2470     Iterator<K> newKeyIterator()   {
2471         return new KeyIterator();
2472     }
2473     Iterator<V> newValueIterator()   {
2474         return new ValueIterator();
2475     }
2476     Iterator<Map.Entry<K,V>> newEntryIterator()   {
2477         return new EntryIterator();
2478     }
2479 
2480 
2481     // Views
2482 
2483     private transient Set<Map.Entry<K,V>> entrySet = null;
2484 
2485     /**
2486      * Returns a {@link Set} view of the keys contained in this map.
2487      * The set is backed by the map, so changes to the map are
2488      * reflected in the set, and vice-versa.  If the map is modified
2489      * while an iteration over the set is in progress (except through
2490      * the iterator's own <tt>remove</tt> operation), the results of
2491      * the iteration are undefined.  The set supports element removal,
2492      * which removes the corresponding mapping from the map, via the
2493      * <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
2494      * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>
2495      * operations.  It does not support the <tt>add</tt> or <tt>addAll</tt>
2496      * operations.
2497      */
2498     public Set<K> keySet() {
2499         Set<K> ks = keySet;
2500         return (ks != null ? ks : (keySet = new KeySet()));
2501     }
2502 
2503     private final class KeySet extends AbstractSet<K> {
2504         public Iterator<K> iterator() {
2505             return newKeyIterator();
2506         }
2507         public int size() {
2508             return size;
2509         }
2510         public boolean contains(Object o) {
2511             return containsKey(o);
2512         }
2513         public boolean remove(Object o) {
2514             return HashMap.this.removeEntryForKey(o) != null;
2515         }
2516         public void clear() {
2517             HashMap.this.clear();
2518         }
2519 
2520         public Spliterator<K> spliterator() {
2521             if (HashMap.this.getClass() == HashMap.class)
2522                 return new KeySpliterator<K,V>(HashMap.this, 0, -1, 0, 0);
2523             else
2524                 return Spliterators.spliterator
2525                         (this, Spliterator.SIZED | Spliterator.DISTINCT);
2526         }
2527     }
2528 
2529     /**
2530      * Returns a {@link Collection} view of the values contained in this map.
2531      * The collection is backed by the map, so changes to the map are
2532      * reflected in the collection, and vice-versa.  If the map is
2533      * modified while an iteration over the collection is in progress
2534      * (except through the iterator's own <tt>remove</tt> operation),
2535      * the results of the iteration are undefined.  The collection
2536      * supports element removal, which removes the corresponding
2537      * mapping from the map, via the <tt>Iterator.remove</tt>,
2538      * <tt>Collection.remove</tt>, <tt>removeAll</tt>,
2539      * <tt>retainAll</tt> and <tt>clear</tt> operations.  It does not
2540      * support the <tt>add</tt> or <tt>addAll</tt> operations.
2541      */
2542     public Collection<V> values() {
2543         Collection<V> vs = values;
2544         return (vs != null ? vs : (values = new Values()));
2545     }
2546 
2547     private final class Values extends AbstractCollection<V> {
2548         public Iterator<V> iterator() {
2549             return newValueIterator();
2550         }
2551         public int size() {
2552             return size;
2553         }
2554         public boolean contains(Object o) {
2555             return containsValue(o);
2556         }
2557         public void clear() {
2558             HashMap.this.clear();
2559         }
2560 
2561         public Spliterator<V> spliterator() {
2562             if (HashMap.this.getClass() == HashMap.class)
2563                 return new ValueSpliterator<K,V>(HashMap.this, 0, -1, 0, 0);
2564             else
2565                 return Spliterators.spliterator
2566                         (this, Spliterator.SIZED);
2567         }
2568     }
2569 
2570     /**
2571      * Returns a {@link Set} view of the mappings contained in this map.
2572      * The set is backed by the map, so changes to the map are
2573      * reflected in the set, and vice-versa.  If the map is modified
2574      * while an iteration over the set is in progress (except through
2575      * the iterator's own <tt>remove</tt> operation, or through the
2576      * <tt>setValue</tt> operation on a map entry returned by the
2577      * iterator) the results of the iteration are undefined.  The set
2578      * supports element removal, which removes the corresponding
2579      * mapping from the map, via the <tt>Iterator.remove</tt>,
2580      * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt> and
2581      * <tt>clear</tt> operations.  It does not support the
2582      * <tt>add</tt> or <tt>addAll</tt> operations.
2583      *
2584      * @return a set view of the mappings contained in this map
2585      */
2586     public Set<Map.Entry<K,V>> entrySet() {
2587         return entrySet0();
2588     }
2589 
2590     private Set<Map.Entry<K,V>> entrySet0() {
2591         Set<Map.Entry<K,V>> es = entrySet;
2592         return es != null ? es : (entrySet = new EntrySet());
2593     }
2594 
2595     private final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
2596         public Iterator<Map.Entry<K,V>> iterator() {
2597             return newEntryIterator();
2598         }
2599         public boolean contains(Object o) {
2600             if (!(o instanceof Map.Entry))
2601                 return false;
2602             Map.Entry<?,?> e = (Map.Entry<?,?>) o;
2603             Entry<K,V> candidate = getEntry(e.getKey());
2604             return candidate != null && candidate.equals(e);
2605         }
2606         public boolean remove(Object o) {
2607             return removeMapping(o) != null;
2608         }
2609         public int size() {
2610             return size;
2611         }
2612         public void clear() {
2613             HashMap.this.clear();
2614         }
2615 
2616         public Spliterator<Map.Entry<K,V>> spliterator() {
2617             if (HashMap.this.getClass() == HashMap.class)
2618                 return new EntrySpliterator<K,V>(HashMap.this, 0, -1, 0, 0);
2619             else
2620                 return Spliterators.spliterator
2621                         (this, Spliterator.SIZED | Spliterator.DISTINCT);
2622         }
2623     }
2624 
2625     /**
2626      * Save the state of the <tt>HashMap</tt> instance to a stream (i.e.,
2627      * serialize it).
2628      *
2629      * @serialData The <i>capacity</i> of the HashMap (the length of the
2630      *             bucket array) is emitted (int), followed by the
2631      *             <i>size</i> (an int, the number of key-value
2632      *             mappings), followed by the key (Object) and value (Object)
2633      *             for each key-value mapping.  The key-value mappings are
2634      *             emitted in no particular order.
2635      */
2636     private void writeObject(java.io.ObjectOutputStream s)
2637         throws IOException
2638     {
2639         // Write out the threshold, loadfactor, and any hidden stuff
2640         s.defaultWriteObject();
2641 
2642         // Write out number of buckets
2643         if (table==EMPTY_TABLE) {
2644             s.writeInt(roundUpToPowerOf2(threshold));
2645         } else {
2646             s.writeInt(table.length);
2647         }
2648 
2649         // Write out size (number of Mappings)
2650         s.writeInt(size);
2651 
2652         // Write out keys and values (alternating)
2653         if (size > 0) {
2654             for(Map.Entry<K,V> e : entrySet0()) {
2655                 s.writeObject(e.getKey());
2656                 s.writeObject(e.getValue());
2657             }
2658         }
2659     }
2660 
2661     private static final long serialVersionUID = 362498820763181265L;
2662 
2663     /**
2664      * Reconstitute the {@code HashMap} instance from a stream (i.e.,
2665      * deserialize it).
2666      */
2667     private void readObject(java.io.ObjectInputStream s)
2668          throws IOException, ClassNotFoundException
2669     {
2670         // Read in the threshold (ignored), loadfactor, and any hidden stuff
2671         s.defaultReadObject();
2672         if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
2673             throw new InvalidObjectException("Illegal load factor: " +
2674                                                loadFactor);
2675         }
2676 
2677         // set other fields that need values
2678         if (Holder.USE_HASHSEED) {
2679             int seed = ThreadLocalRandom.current().nextInt();
2680             Holder.UNSAFE.putIntVolatile(this, Holder.HASHSEED_OFFSET,
2681                                          (seed != 0) ? seed : 1);
2682         }
2683         table = EMPTY_TABLE;
2684 
2685         // Read in number of buckets
2686         s.readInt(); // ignored.
2687 
2688         // Read number of mappings
2689         int mappings = s.readInt();
2690         if (mappings < 0)
2691             throw new InvalidObjectException("Illegal mappings count: " +
2692                                                mappings);
2693 
2694         // capacity chosen by number of mappings and desired load (if >= 0.25)
2695         int capacity = (int) Math.min(
2696                 mappings * Math.min(1 / loadFactor, 4.0f),
2697                 // we have limits...
2698                 HashMap.MAXIMUM_CAPACITY);
2699 
2700         // allocate the bucket array;
2701         if (mappings > 0) {
2702             inflateTable(capacity);
2703         } else {
2704             threshold = capacity;
2705         }
2706 
2707         init();  // Give subclass a chance to do its thing.
2708 
2709         // Read the keys and values, and put the mappings in the HashMap
2710         for (int i=0; i<mappings; i++) {
2711             @SuppressWarnings("unchecked")
2712             K key = (K) s.readObject();
2713             @SuppressWarnings("unchecked")
2714             V value = (V) s.readObject();
2715             putForCreate(key, value);
2716         }
2717     }
2718 
2719     // These methods are used when serializing HashSets
2720     int   capacity()     { return table.length; }
2721     float loadFactor()   { return loadFactor;   }
2722 
2723     /**
2724      * Standin until HM overhaul; based loosely on Weak and Identity HM.
2725      */
2726     static class HashMapSpliterator<K,V> {
2727         final HashMap<K,V> map;
2728         Object current;             // current node, can be Entry or TreeNode
2729         int index;                  // current index, modified on advance/split
2730         int fence;                  // one past last index
2731         int est;                    // size estimate
2732         int expectedModCount;       // for comodification checks
2733         boolean acceptedNull;       // Have we accepted the null key?
2734                                     // Without this, we can't distinguish
2735                                     // between being at the very beginning (and
2736                                     // needing to accept null), or being at the
2737                                     // end of the list in bin 0.  In both cases,
2738                                     // current == null && index == 0.
2739 
2740         HashMapSpliterator(HashMap<K,V> m, int origin,
2741                                int fence, int est,
2742                                int expectedModCount) {
2743             this.map = m;
2744             this.index = origin;
2745             this.fence = fence;
2746             this.est = est;
2747             this.expectedModCount = expectedModCount;
2748             this.acceptedNull = false;
2749         }
2750 
2751         final int getFence() { // initialize fence and size on first use
2752             int hi;
2753             if ((hi = fence) < 0) {
2754                 HashMap<K,V> m = map;
2755                 est = m.size;
2756                 expectedModCount = m.modCount;
2757                 hi = fence = m.table.length;
2758             }
2759             return hi;
2760         }
2761 
2762         public final long estimateSize() {
2763             getFence(); // force init
2764             return (long) est;
2765         }
2766     }
2767 
2768     static final class KeySpliterator<K,V>
2769         extends HashMapSpliterator<K,V>
2770         implements Spliterator<K> {
2771         KeySpliterator(HashMap<K,V> m, int origin, int fence, int est,
2772                        int expectedModCount) {
2773             super(m, origin, fence, est, expectedModCount);
2774         }
2775 
2776         public KeySpliterator<K,V> trySplit() {
2777             int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
2778             if (lo >= mid || current != null) {
2779                 return null;
2780             } else {
2781                 KeySpliterator<K,V> retVal = new KeySpliterator<K,V>(map, lo,
2782                                      index = mid, est >>>= 1, expectedModCount);
2783                 // Only 'this' Spliterator chould check for null.
2784                 retVal.acceptedNull = true;
2785                 return retVal;
2786             }
2787         }
2788 
2789         @SuppressWarnings("unchecked")
2790         public void forEachRemaining(Consumer<? super K> action) {
2791             int i, hi, mc;
2792             if (action == null)
2793                 throw new NullPointerException();
2794             HashMap<K,V> m = map;
2795             Object[] tab = m.table;
2796             if ((hi = fence) < 0) {
2797                 mc = expectedModCount = m.modCount;
2798                 hi = fence = tab.length;
2799             }
2800             else
2801                 mc = expectedModCount;
2802 
2803             if (!acceptedNull) {
2804                 acceptedNull = true;
2805                 if (m.nullKeyEntry != null) {
2806                     action.accept(m.nullKeyEntry.key);
2807                 }
2808             }
2809             if (tab.length >= hi && (i = index) >= 0 &&
2810                 (i < (index = hi) || current != null)) {
2811                 Object p = current;
2812                 current = null;
2813                 do {
2814                     if (p == null) {
2815                         p = tab[i++];
2816                         if (p instanceof HashMap.TreeBin) {
2817                             p = ((HashMap.TreeBin)p).first;
2818                         }
2819                     } else {
2820                         HashMap.Entry<K,V> entry;
2821                         if (p instanceof HashMap.Entry) {
2822                             entry = (HashMap.Entry<K,V>)p;
2823                         } else {
2824                             entry = (HashMap.Entry<K,V>)((TreeNode)p).entry;
2825                         }
2826                         action.accept(entry.key);
2827                         p = entry.next;
2828                     }
2829                 } while (p != null || i < hi);
2830                 if (m.modCount != mc)
2831                     throw new ConcurrentModificationException();
2832             }
2833         }
2834 
2835         @SuppressWarnings("unchecked")
2836         public boolean tryAdvance(Consumer<? super K> action) {
2837             int hi;
2838             if (action == null)
2839                 throw new NullPointerException();
2840             Object[] tab = map.table;
2841             hi = getFence();
2842 
2843             if (!acceptedNull) {
2844                 acceptedNull = true;
2845                 if (map.nullKeyEntry != null) {
2846                     action.accept(map.nullKeyEntry.key);
2847                     if (map.modCount != expectedModCount)
2848                         throw new ConcurrentModificationException();
2849                     return true;
2850                 }
2851             }
2852             if (tab.length >= hi && index >= 0) {
2853                 while (current != null || index < hi) {
2854                     if (current == null) {
2855                         current = tab[index++];
2856                         if (current instanceof HashMap.TreeBin) {
2857                             current = ((HashMap.TreeBin)current).first;
2858                         }
2859                     } else {
2860                         HashMap.Entry<K,V> entry;
2861                         if (current instanceof HashMap.Entry) {
2862                             entry = (HashMap.Entry<K,V>)current;
2863                         } else {
2864                             entry = (HashMap.Entry<K,V>)((TreeNode)current).entry;
2865                         }
2866                         K k = entry.key;
2867                         current = entry.next;
2868                         action.accept(k);
2869                         if (map.modCount != expectedModCount)
2870                             throw new ConcurrentModificationException();
2871                         return true;
2872                     }
2873                 }
2874             }
2875             return false;
2876         }
2877 
2878         public int characteristics() {
2879             return (fence < 0 || est == map.size ? Spliterator.SIZED : 0) |
2880                 Spliterator.DISTINCT;
2881         }
2882     }
2883 
2884     static final class ValueSpliterator<K,V>
2885         extends HashMapSpliterator<K,V>
2886         implements Spliterator<V> {
2887         ValueSpliterator(HashMap<K,V> m, int origin, int fence, int est,
2888                          int expectedModCount) {
2889             super(m, origin, fence, est, expectedModCount);
2890         }
2891 
2892         public ValueSpliterator<K,V> trySplit() {
2893             int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
2894             if (lo >= mid || current != null) {
2895                 return null;
2896             } else {
2897                 ValueSpliterator<K,V> retVal = new ValueSpliterator<K,V>(map,
2898                                  lo, index = mid, est >>>= 1, expectedModCount);
2899                 // Only 'this' Spliterator chould check for null.
2900                 retVal.acceptedNull = true;
2901                 return retVal;
2902             }
2903         }
2904 
2905         @SuppressWarnings("unchecked")
2906         public void forEachRemaining(Consumer<? super V> action) {
2907             int i, hi, mc;
2908             if (action == null)
2909                 throw new NullPointerException();
2910             HashMap<K,V> m = map;
2911             Object[] tab = m.table;
2912             if ((hi = fence) < 0) {
2913                 mc = expectedModCount = m.modCount;
2914                 hi = fence = tab.length;
2915             }
2916             else
2917                 mc = expectedModCount;
2918 
2919             if (!acceptedNull) {
2920                 acceptedNull = true;
2921                 if (m.nullKeyEntry != null) {
2922                     action.accept(m.nullKeyEntry.value);
2923                 }
2924             }
2925             if (tab.length >= hi && (i = index) >= 0 &&
2926                 (i < (index = hi) || current != null)) {
2927                 Object p = current;
2928                 current = null;
2929                 do {
2930                     if (p == null) {
2931                         p = tab[i++];
2932                         if (p instanceof HashMap.TreeBin) {
2933                             p = ((HashMap.TreeBin)p).first;
2934                         }
2935                     } else {
2936                         HashMap.Entry<K,V> entry;
2937                         if (p instanceof HashMap.Entry) {
2938                             entry = (HashMap.Entry<K,V>)p;
2939                         } else {
2940                             entry = (HashMap.Entry<K,V>)((TreeNode)p).entry;
2941                         }
2942                         action.accept(entry.value);
2943                         p = entry.next;
2944                     }
2945                 } while (p != null || i < hi);
2946                 if (m.modCount != mc)
2947                     throw new ConcurrentModificationException();
2948             }
2949         }
2950 
2951         @SuppressWarnings("unchecked")
2952         public boolean tryAdvance(Consumer<? super V> action) {
2953             int hi;
2954             if (action == null)
2955                 throw new NullPointerException();
2956             Object[] tab = map.table;
2957             hi = getFence();
2958 
2959             if (!acceptedNull) {
2960                 acceptedNull = true;
2961                 if (map.nullKeyEntry != null) {
2962                     action.accept(map.nullKeyEntry.value);
2963                     if (map.modCount != expectedModCount)
2964                         throw new ConcurrentModificationException();
2965                     return true;
2966                 }
2967             }
2968             if (tab.length >= hi && index >= 0) {
2969                 while (current != null || index < hi) {
2970                     if (current == null) {
2971                         current = tab[index++];
2972                         if (current instanceof HashMap.TreeBin) {
2973                             current = ((HashMap.TreeBin)current).first;
2974                         }
2975                     } else {
2976                         HashMap.Entry<K,V> entry;
2977                         if (current instanceof HashMap.Entry) {
2978                             entry = (Entry<K,V>)current;
2979                         } else {
2980                             entry = (Entry<K,V>)((TreeNode)current).entry;
2981                         }
2982                         V v = entry.value;
2983                         current = entry.next;
2984                         action.accept(v);
2985                         if (map.modCount != expectedModCount)
2986                             throw new ConcurrentModificationException();
2987                         return true;
2988                     }
2989                 }
2990             }
2991             return false;
2992         }
2993 
2994         public int characteristics() {
2995             return (fence < 0 || est == map.size ? Spliterator.SIZED : 0);
2996         }
2997     }
2998 
2999     static final class EntrySpliterator<K,V>
3000         extends HashMapSpliterator<K,V>
3001         implements Spliterator<Map.Entry<K,V>> {
3002         EntrySpliterator(HashMap<K,V> m, int origin, int fence, int est,
3003                          int expectedModCount) {
3004             super(m, origin, fence, est, expectedModCount);
3005         }
3006 
3007         public EntrySpliterator<K,V> trySplit() {
3008             int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
3009             if (lo >= mid || current != null) {
3010                 return null;
3011             } else {
3012                 EntrySpliterator<K,V> retVal = new EntrySpliterator<K,V>(map,
3013                                  lo, index = mid, est >>>= 1, expectedModCount);
3014                 // Only 'this' Spliterator chould check for null.
3015                 retVal.acceptedNull = true;
3016                 return retVal;
3017             }
3018         }
3019 
3020         @SuppressWarnings("unchecked")
3021         public void forEachRemaining(Consumer<? super Map.Entry<K,V>> action) {
3022             int i, hi, mc;
3023             if (action == null)
3024                 throw new NullPointerException();
3025             HashMap<K,V> m = map;
3026             Object[] tab = m.table;
3027             if ((hi = fence) < 0) {
3028                 mc = expectedModCount = m.modCount;
3029                 hi = fence = tab.length;
3030             }
3031             else
3032                 mc = expectedModCount;
3033 
3034             if (!acceptedNull) {
3035                 acceptedNull = true;
3036                 if (m.nullKeyEntry != null) {
3037                     action.accept(m.nullKeyEntry);
3038                 }
3039             }
3040             if (tab.length >= hi && (i = index) >= 0 &&
3041                 (i < (index = hi) || current != null)) {
3042                 Object p = current;
3043                 current = null;
3044                 do {
3045                     if (p == null) {
3046                         p = tab[i++];
3047                         if (p instanceof HashMap.TreeBin) {
3048                             p = ((HashMap.TreeBin)p).first;
3049                         }
3050                     } else {
3051                         HashMap.Entry<K,V> entry;
3052                         if (p instanceof HashMap.Entry) {
3053                             entry = (HashMap.Entry<K,V>)p;
3054                         } else {
3055                             entry = (HashMap.Entry<K,V>)((TreeNode)p).entry;
3056                         }
3057                         action.accept(entry);
3058                         p = entry.next;
3059 
3060                     }
3061                 } while (p != null || i < hi);
3062                 if (m.modCount != mc)
3063                     throw new ConcurrentModificationException();
3064             }
3065         }
3066 
3067         @SuppressWarnings("unchecked")
3068         public boolean tryAdvance(Consumer<? super Map.Entry<K,V>> action) {
3069             int hi;
3070             if (action == null)
3071                 throw new NullPointerException();
3072             Object[] tab = map.table;
3073             hi = getFence();
3074 
3075             if (!acceptedNull) {
3076                 acceptedNull = true;
3077                 if (map.nullKeyEntry != null) {
3078                     action.accept(map.nullKeyEntry);
3079                     if (map.modCount != expectedModCount)
3080                         throw new ConcurrentModificationException();
3081                     return true;
3082                 }
3083             }
3084             if (tab.length >= hi && index >= 0) {
3085                 while (current != null || index < hi) {
3086                     if (current == null) {
3087                         current = tab[index++];
3088                         if (current instanceof HashMap.TreeBin) {
3089                             current = ((HashMap.TreeBin)current).first;
3090                         }
3091                     } else {
3092                         HashMap.Entry<K,V> e;
3093                         if (current instanceof HashMap.Entry) {
3094                             e = (Entry<K,V>)current;
3095                         } else {
3096                             e = (Entry<K,V>)((TreeNode)current).entry;
3097                         }
3098                         current = e.next;
3099                         action.accept(e);
3100                         if (map.modCount != expectedModCount)
3101                             throw new ConcurrentModificationException();
3102                         return true;
3103                     }
3104                 }
3105             }
3106             return false;
3107         }
3108 
3109         public int characteristics() {
3110             return (fence < 0 || est == map.size ? Spliterator.SIZED : 0) |
3111                 Spliterator.DISTINCT;
3112         }
3113     }
3114 }