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