1 /*
   2  * Copyright (c) 1997, 2024, 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.sandbox.corelibs.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.Boolean;
  33 import java.lang.reflect.Field;
  34 import java.lang.reflect.InvocationTargetException;
  35 import java.lang.reflect.Method;
  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.Spliterator;
  52 import java.util.function.BiConsumer;
  53 import java.util.function.BiFunction;
  54 import java.util.function.Consumer;
  55 import java.util.function.Function;
  56 
  57 /**
  58  * HashMap using hashing and "open addressing".
  59  * Hash entries are inline class instances.
  60  * As described in <em>Introduction to Algorithms, 3rd Edition (The MIT Press)</em>,
  61  * Section 11 Hash tables and Section 11.4 Open addressing.
  62  *
  63  * Open addressing is used to locate other entries for keys with the same hash.
  64  * If multiple keys have the same hashcode, a rehashing mechanism
  65  * is used to place the 2nd and subsequent
  66  * key/value pairs at a non-optimal index in the table. Therefore,
  67  * finding the entry for a desired key must rehash and examine subsequent
  68  * entries until the value is value or it encounters an empty entry.
  69  * When an entry is removed, the entry is marked as deleted, (not empty)
  70  * to allow the search algorithm to keep looking; otherwise it would terminate
  71  * the scan on the deleted entry, when it might be the case for some (other) key
  72  * would have that same entry as part of its chain of possible locations for its hash.
  73  * The default load factor (.75) should be re-evaluated in light of the open addressing
  74  * computations.  A higher number would reduce unused (wasted) space at the cost of
  75  * increased search times, a lower number would increase unused (wasted) space but
  76  * improve search times (assuming even hashcode distributions).
  77  * Badly distributed hash values will result in incremental table growth and
  78  * linear search performance.
  79  * <p>
  80  * During insertion the Robin Hood hash algorithm does a small optimization
  81  * to reduce worst case rehash lengths.
  82  * Removal of entries, does a compaction of the following entries to fill
  83  * in free entries and reduce entry rehashling lengths based on
  84  * "On Deletions in Open Addressing Hashing", by Rosa M. Jimenez and Conrado Martinz.
  85  *
  86  * <p>
  87  * The only allocation that occurs during put operations is for the resizing of the entry table.
  88  *
  89  * <P>
  90  * Hash table based implementation of the {@code Map} interface.  This
  91  * implementation provides all of the optional map operations, and permits
  92  * {@code null} values and the {@code null} key.  (The {@code HashMap}
  93  * class is roughly equivalent to {@code Hashtable}, except that it is
  94  * unsynchronized and permits nulls.)  This class makes no guarantees as to
  95  * the order of the map; in particular, it does not guarantee that the order
  96  * will remain constant over time.
  97  *
  98  * <p>This implementation provides constant-time performance for the basic
  99  * operations ({@code get} and {@code put}), assuming the hash function
 100  * disperses the elements properly among the buckets.  Iteration over
 101  * collection views requires time proportional to the "capacity" of the
 102  * {@code HashMap} instance (the number of buckets) plus its size (the number
 103  * of key-value mappings).  Thus, it's very important not to set the initial
 104  * capacity too high (or the load factor too low) if iteration performance is
 105  * important.
 106  *
 107  * <p>An instance of {@code HashMap} has two parameters that affect its
 108  * performance: <i>initial capacity</i> and <i>load factor</i>.  The
 109  * <i>capacity</i> is the number of buckets in the hash table, and the initial
 110  * capacity is simply the capacity at the time the hash table is created.  The
 111  * <i>load factor</i> is a measure of how full the hash table is allowed to
 112  * get before its capacity is automatically increased.  When the number of
 113  * entries in the hash table exceeds the product of the load factor and the
 114  * current capacity, the hash table is <i>rehashed</i> (that is, internal data
 115  * structures are rebuilt) so that the hash table has approximately twice the
 116  * number of buckets.
 117  *
 118  * <p>As a general rule, the default load factor (.75) offers a good
 119  * tradeoff between time and space costs.  Higher values decrease the
 120  * space overhead but increase the lookup cost (reflected in most of
 121  * the operations of the {@code HashMap} class, including
 122  * {@code get} and {@code put}).  The expected number of entries in
 123  * the map and its load factor should be taken into account when
 124  * setting its initial capacity, so as to minimize the number of
 125  * rehash operations.  If the initial capacity is greater than the
 126  * maximum number of entries divided by the load factor, no rehash
 127  * operations will ever occur.
 128  *
 129  * <p>If many mappings are to be stored in a {@code HashMap}
 130  * instance, creating it with a sufficiently large capacity will allow
 131  * the mappings to be stored more efficiently than letting it perform
 132  * automatic rehashing as needed to grow the table.  Note that using
 133  * many keys with the same {@code hashCode()} is a sure way to slow
 134  * down performance of any hash table.
 135  * TBD: To ameliorate impact, when keys
 136  * are {@link Comparable}, this class may use comparison order among
 137  * keys to help break ties.
 138  *
 139  * <p><strong>Note that this implementation is not synchronized.</strong>
 140  * If multiple threads access a hash map concurrently, and at least one of
 141  * the threads modifies the map structurally, it <i>must</i> be
 142  * synchronized externally.  (A structural modification is any operation
 143  * that adds or deletes one or more mappings; merely changing the value
 144  * associated with a key that an instance already contains is not a
 145  * structural modification.)  This is typically accomplished by
 146  * synchronizing on some object that naturally encapsulates the map.
 147  *
 148  * If no such object exists, the map should be "wrapped" using the
 149  * {@link Collections#synchronizedMap Collections.synchronizedMap}
 150  * method.  This is best done at creation time, to prevent accidental
 151  * unsynchronized access to the map:<pre>
 152  *   Map m = Collections.synchronizedMap(new HashMap(...));</pre>
 153  *
 154  * <p>The iterators returned by all of this class's "collection view methods"
 155  * are <i>fail-fast</i>: if the map is structurally modified at any time after
 156  * the iterator is created, in any way except through the iterator's own
 157  * {@code remove} method, the iterator will throw a
 158  * {@link ConcurrentModificationException}.  Thus, in the face of concurrent
 159  * modification, the iterator fails quickly and cleanly, rather than risking
 160  * arbitrary, non-deterministic behavior at an undetermined time in the
 161  * future.
 162  *
 163  * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
 164  * as it is, generally speaking, impossible to make any hard guarantees in the
 165  * presence of unsynchronized concurrent modification.  Fail-fast iterators
 166  * throw {@code ConcurrentModificationException} on a best-effort basis.
 167  * Therefore, it would be wrong to write a program that depended on this
 168  * exception for its correctness: <i>the fail-fast behavior of iterators
 169  * should be used only to detect bugs.</i>
 170  *
 171  * <p>This class is a member of the
 172  * <a href="{@docRoot}/java.base/java/util/package-summary.html#CollectionsFramework">
 173  * Java Collections Framework</a>.
 174  *
 175  * @param <K> the type of keys maintained by this map
 176  * @param <V> the type of mapped values
 177  *
 178  * @author  Doug Lea
 179  * @author  Josh Bloch
 180  * @author  Arthur van Hoff
 181  * @author  Neal Gafter
 182  * @see     Object#hashCode()
 183  * @see     Collection
 184  * @see     Map
 185  * @see     TreeMap
 186  * @see     Hashtable
 187  * @since   1.2
 188  */
 189 public class HashMap<K,V> extends XAbstractMap<K,V>
 190         implements Map<K,V>, Cloneable, Serializable {
 191 
 192     private static final long serialVersionUID = 362498820763181265L;
 193 
 194     private static final boolean DEBUG = Boolean.getBoolean("DEBUG");
 195     private static final boolean VERIFYTABLEOK = Boolean.getBoolean("VERIFYTABLEOK");
 196 
 197     /*
 198      * Implementation notes.
 199      *
 200      * This map usually acts as a binned (bucketed) hash table.
 201      * The concurrent-programming-like SSA-based coding style helps
 202      * avoid aliasing errors amid all of the twisty pointer operations.
 203      */
 204 
 205     /**
 206      * The default initial capacity - MUST be a power of two.
 207      */
 208     static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
 209 
 210     /**
 211      * The maximum capacity, used if a higher value is implicitly specified
 212      * by either of the constructors with arguments.
 213      * MUST be a power of two <= 1<<30.
 214      */
 215     static final int MAXIMUM_CAPACITY = 1 << 30;
 216 
 217     /**
 218      * The load factor used when none specified in constructor.
 219      */
 220     static final float DEFAULT_LOAD_FACTOR = 0.75f;
 221 
 222     private final int REHASH_HASH = 2003; // Odd and small (a medium-small prime)
 223 
 224     /**
 225      * Basic hash bin node, used for most entries.
 226      */
 227     static value class YNode<K,V> implements Map.Entry<K,V> {
 228         final int hash;
 229         final short probes; // maybe only a byte
 230         final K key;
 231         final V value;
 232 
 233         YNode() {
 234             this.hash = 0;
 235             this.probes = 0;
 236             this.key = null;
 237             this.value = null;
 238         }
 239 
 240         YNode(int hash, K key, V value, int probes) {
 241             this.hash = hash;
 242             this.key = key;
 243             this.value = value;
 244             this.probes = (short)probes;
 245         }
 246 
 247         boolean isEmpty() {
 248             return probes == 0;
 249         }
 250 
 251         boolean isValue() {
 252             return probes > 0;
 253         }
 254 
 255         public final K getKey()        { return key; }
 256         public final V getValue()      { return value; }
 257         public final String toString() { return key + "=" + value + ", probes: " + probes
 258                 + ", hash: " + Integer.toString(hash, 16)
 259                 + ", hashCode: " + hashCode(); }
 260         public final int hashCode() {
 261             return Objects.hashCode(key) ^ Objects.hashCode(value);
 262         }
 263 
 264         public final V setValue(V newValue) {
 265             throw new IllegalStateException("YNode cannot set a value");
 266         }
 267 
 268         public final boolean equals(Object o) {
 269             if (o == this)
 270                 return true;
 271             if (o instanceof Map.Entry) {
 272                 Map.Entry<?,?> e = (Map.Entry<?,?>)o;
 273                 if (Objects.equals(key, e.getKey()) &&
 274                         Objects.equals(value, e.getValue()))
 275                     return true;
 276             }
 277             return false;
 278         }
 279     }
 280 
 281     value class YNodeWrapper implements Map.Entry<K,V> {
 282         final int index;
 283         final YNode<K,V> entry;
 284 
 285         YNodeWrapper(int index) {
 286             this.index = index;
 287             this.entry = table[index];
 288         }
 289 
 290         public K getKey() {
 291             return entry.key;
 292         }
 293 
 294         public V getValue() {
 295             return entry.value;
 296         }
 297 
 298         public String toString() {
 299             return entry.toString();
 300         }
 301 
 302         public int hashCode() {
 303             return entry.hashCode();
 304         }
 305 
 306         public boolean equals(Object o) {
 307             return entry.equals(o);
 308         }
 309         /**
 310          * Replaces the value corresponding to this entry with the specified
 311          * value (optional operation).  (Writes through to the map.)  The
 312          * behavior of this call is undefined if the mapping has already been
 313          * removed from the map (by the iterator's {@code remove} operation).
 314          *
 315          * @param value new value to be stored in this entry
 316          * @return old value corresponding to the entry
 317          * @throws UnsupportedOperationException if the {@code put} operation
 318          *         is not supported by the backing map
 319          * @throws ClassCastException if the class of the specified value
 320          *         prevents it from being stored in the backing map
 321          * @throws NullPointerException if the backing map does not permit
 322          *         null values, and the specified value is null
 323          * @throws IllegalArgumentException if some property of this value
 324          *         prevents it from being stored in the backing map
 325          * @throws IllegalStateException implementations may, but are not
 326          *         required to, throw this exception if the entry has been
 327          *         removed from the backing map.
 328          */
 329         public V setValue(V value) {
 330             table[index] = new YNode<>(entry.hash, entry.key, value, entry.probes);
 331             return entry.value;
 332         }
 333     }
 334     /* ---------------- Static utilities -------------- */
 335 
 336     /**
 337      * Computes key.hashCode() and spreads (XORs) higher bits of hash
 338      * to lower.  Because the table uses power-of-two masking, sets of
 339      * hashes that vary only in bits above the current mask will
 340      * always collide. (Among known examples are sets of Float keys
 341      * holding consecutive whole numbers in small tables.)  So we
 342      * apply a transform that spreads the impact of higher bits
 343      * downward. There is a tradeoff between speed, utility, and
 344      * quality of bit-spreading. Because many common sets of hashes
 345      * are already reasonably distributed (so don't benefit from
 346      * spreading), and because we use trees to handle large sets of
 347      * collisions in bins, we just XOR some shifted bits in the
 348      * cheapest possible way to reduce systematic lossage, as well as
 349      * to incorporate impact of the highest bits that would otherwise
 350      * never be used in index calculations because of table bounds.
 351      */
 352     static final int hash(Object key) {
 353         int h;
 354         return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
 355     }
 356 
 357     /**
 358      * Returns a power of two size for the given target capacity.
 359      */
 360     static final int tableSizeFor(int cap) {
 361         int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);
 362         return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
 363     }
 364 
 365     /* ---------------- Fields -------------- */
 366 
 367     /**
 368      * The table, initialized on first use, and resized as
 369      * necessary. When allocated, length is always a power of two.
 370      * (We also tolerate length zero in some operations to allow
 371      * bootstrapping mechanics that are currently not needed.)
 372      */
 373     transient YNode<K,V>[] table;
 374 
 375     /**
 376      * Holds cached entrySet(). Note that AbstractMap fields are used
 377      * for keySet() and values().
 378      */
 379     transient Set<Map.Entry<K,V>> entrySet;
 380 
 381     /**
 382      * The number of key-value mappings contained in this map.
 383      */
 384     transient int size;
 385 
 386     /**
 387      * The number of times this HashMap has been structurally modified
 388      * Structural modifications are those that change the number of mappings in
 389      * the HashMap or otherwise modify its internal structure (e.g.,
 390      * rehash).  This field is used to make iterators on Collection-views of
 391      * the HashMap fail-fast.  (See ConcurrentModificationException).
 392      */
 393     transient int modCount;
 394 
 395     /**
 396      * The next size value at which to resize (capacity * load factor).
 397      *
 398      * @serial
 399      */
 400     // (The javadoc description is true upon serialization.
 401     // Additionally, if the table array has not been allocated, this
 402     // field holds the initial array capacity, or zero signifying
 403     // DEFAULT_INITIAL_CAPACITY.)
 404     int threshold;
 405 
 406     /**
 407      * The load factor for the hash table.
 408      *
 409      * @serial
 410      */
 411     final float loadFactor;
 412 
 413     private transient int[] getProbes = new int[16];
 414     private transient int[] putProbes = new int[16];
 415     private transient int[] notFoundProbes = new int[16];
 416 
 417 
 418     /* ---------------- Public operations -------------- */
 419 
 420     /**
 421      * Constructs an empty {@code HashMap} with the specified initial
 422      * capacity and load factor.
 423      *
 424      * @param  initialCapacity the initial capacity
 425      * @param  loadFactor      the load factor
 426      * @throws IllegalArgumentException if the initial capacity is negative
 427      *         or the load factor is nonpositive
 428      */
 429     public HashMap(int initialCapacity, float loadFactor) {
 430         if (initialCapacity < 0)
 431             throw new IllegalArgumentException("Illegal initial capacity: " +
 432                     initialCapacity);
 433         if (initialCapacity > MAXIMUM_CAPACITY)
 434             initialCapacity = MAXIMUM_CAPACITY;
 435         if (loadFactor <= 0 || Float.isNaN(loadFactor))
 436             throw new IllegalArgumentException("Illegal load factor: " +
 437                     loadFactor);
 438         this.loadFactor = loadFactor;
 439         this.threshold = tableSizeFor(initialCapacity);
 440     }
 441 
 442     /**
 443      * Constructs an empty {@code HashMap} with the specified initial
 444      * capacity and the default load factor (0.75).
 445      *
 446      * @param  initialCapacity the initial capacity.
 447      * @throws IllegalArgumentException if the initial capacity is negative.
 448      */
 449     public HashMap(int initialCapacity) {
 450         this(initialCapacity, DEFAULT_LOAD_FACTOR);
 451     }
 452 
 453     /**
 454      * Constructs an empty {@code HashMap} with the default initial capacity
 455      * (16) and the default load factor (0.75).
 456      */
 457     public HashMap() {
 458         this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
 459     }
 460 
 461     /**
 462      * Constructs a new {@code HashMap} with the same mappings as the
 463      * specified {@code Map}.  The {@code HashMap} is created with
 464      * default load factor (0.75) and an initial capacity sufficient to
 465      * hold the mappings in the specified {@code Map}.
 466      *
 467      * @param   m the map whose mappings are to be placed in this map
 468      * @throws  NullPointerException if the specified map is null
 469      */
 470     public HashMap(Map<? extends K, ? extends V> m) {
 471         this.loadFactor = DEFAULT_LOAD_FACTOR;
 472         putMapEntries(m, false);
 473     }
 474 
 475     /**
 476      * Implements Map.putAll and Map constructor.
 477      *
 478      * @param m the map
 479      * @param evict false when initially constructing this map, else true.
 480      */
 481     final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
 482         int s = m.size();
 483         if (s > 0) {
 484             if (table == null) { // pre-size
 485                 float ft = ((float)s / loadFactor) + 1.0F;
 486                 int t = ((ft < (float)MAXIMUM_CAPACITY) ?
 487                         (int)ft : MAXIMUM_CAPACITY);
 488                 if (t > threshold)
 489                     threshold = tableSizeFor(t);
 490             } else {
 491                 // Because of linked-list bucket constraints, we cannot
 492                 // expand all at once, but can reduce total resize
 493                 // effort by repeated doubling now vs later
 494                 while (s > threshold && table.length < MAXIMUM_CAPACITY)
 495                     resize();
 496             }
 497 
 498             for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
 499                 K key = e.getKey();
 500                 V value = e.getValue();
 501                 putVal(hash(key), key, value, false);
 502             }
 503         }
 504     }
 505 
 506     /**
 507      * Returns the number of key-value mappings in this map.
 508      *
 509      * @return the number of key-value mappings in this map
 510      */
 511     public int size() {
 512         return size;
 513     }
 514 
 515     /**
 516      * Returns {@code true} if this map contains no key-value mappings.
 517      *
 518      * @return {@code true} if this map contains no key-value mappings
 519      */
 520     public boolean isEmpty() {
 521         return size == 0;
 522     }
 523 
 524     /**
 525      * Returns the value to which the specified key is mapped,
 526      * or {@code null} if this map contains no mapping for the key.
 527      *
 528      * <p>More formally, if this map contains a mapping from a key
 529      * {@code k} to a value {@code v} such that {@code (key==null ? k==null :
 530      * key.equals(k))}, then this method returns {@code v}; otherwise
 531      * it returns {@code null}.  (There can be at most one such mapping.)
 532      *
 533      * <p>A return value of {@code null} does not <i>necessarily</i>
 534      * indicate that the map contains no mapping for the key; it's also
 535      * possible that the map explicitly maps the key to {@code null}.
 536      * The {@link #containsKey containsKey} operation may be used to
 537      * distinguish these two cases.
 538      *
 539      * @see #put(Object, Object)
 540      */
 541     public V get(Object key) {
 542         final YNode<K, V>[] tab;
 543         final int mask;
 544 //        int probes = 0;
 545         if ((tab = table) != null && (mask = tab.length - 1) >= 0) {
 546             final int hash = hash(key);
 547             int h = hash;
 548             YNode<K, V> entry;
 549             while ((entry = tab[(mask & h)]).isValue()) {
 550 //                probes++;
 551                 K k;
 552                 if (entry.hash == hash &&
 553                         ((k = entry.key) == key || (key != null && key.equals(k)))) {
 554 //                    getProbes = incProbeCount(getProbes, probes);
 555                     return entry.value;
 556                 } else {
 557                     h += REHASH_HASH;
 558                 }
 559             }
 560         }
 561 //        notFoundProbes = incProbeCount(notFoundProbes, 0);
 562         return null;      // not found; empty table
 563     }
 564 
 565     /**
 566      * Same as Get caching the entry.
 567      * @param key the key
 568      * @return a value, or null
 569      */
 570     public V get1(Object key) {
 571         final int hash = hash(key);
 572         final YNode<K, V>[] tab;
 573         int n;
 574         if ((tab = table) != null && (n = tab.length) > 0) {
 575             int h = hash;
 576             int index = (n - 1) & h;
 577             YNode<K, V> entry = tab[index];
 578             for (; //int probes = 1
 579                  entry.isValue();
 580                  h += REHASH_HASH, index = (n - 1) & h, entry = tab[index]) {  //, probes++
 581                 K k;
 582                 if (entry.hash == hash &&
 583                         ((k = entry.key) == key || (key != null && key.equals(k)))) {
 584 //                    getProbes = incProbeCount(getProbes, probes);
 585                     return entry.value;
 586                 }
 587             }
 588         }
 589 //        notFoundProbes = incProbeCount(notFoundProbes, 0);
 590         return null;      // not found; empty table
 591     }
 592 
 593     /**
 594      * Implements Map.get and related methods.
 595      *
 596      * @param hash hash for key
 597      * @param key the key
 598      * @return the index of a matching node or -1
 599      */
 600     private final int getNode(final int hash, Object key) {
 601         YNode<K, V>[] tab;
 602         int n;
 603         if ((tab = table) != null && (n = tab.length) > 0) {
 604             final YNode<K, V> first;
 605             final int i = (n - 1) & hash;
 606             K k;
 607             if ((first = tab[i]).isValue() &&
 608                     first.hash == hash &&
 609                     ((k = first.key) == key || (key != null && key.equals(k)))) {
 610 //                getProbes = incProbeCount(getProbes, 1);
 611                 return i;
 612             }
 613             // non-empty table and not first entry
 614             int h = hash;
 615             for (int probes = 1; probes <= tab.length; probes++, h += REHASH_HASH) {
 616                 final int index = (n - 1) & h;
 617                 final YNode<K, V> entry = tab[index];
 618                 if (!entry.isValue()) {
 619 //                    notFoundProbes = incProbeCount(notFoundProbes, probes);
 620                     return -1;  // search ended without finding the key
 621                 } else if (entry.hash == hash &&
 622                         ((k = entry.key) == key || (key != null && key.equals(k)))) {
 623 //                    getProbes = incProbeCount(getProbes, probes);
 624                     return index;
 625                 }
 626             }
 627         }
 628 //        notFoundProbes = incProbeCount(notFoundProbes, 0);
 629         return -1;      // not found; empty table
 630     }
 631 
 632     /**
 633      * Returns {@code true} if this map contains a mapping for the
 634      * specified key.
 635      *
 636      * @param   key   The key whose presence in this map is to be tested
 637      * @return {@code true} if this map contains a mapping for the specified
 638      * key.
 639      */
 640     public boolean containsKey(Object key) {
 641         return getNode(hash(key), key) >= 0;
 642     }
 643 
 644     /**
 645      * Associates the specified value with the specified key in this map.
 646      * If the map previously contained a mapping for the key, the old
 647      * value is replaced.
 648      *
 649      * @param key key with which the specified value is to be associated
 650      * @param value value to be associated with the specified key
 651      * @return the previous value associated with {@code key}, or
 652      *         {@code null} if there was no mapping for {@code key}.
 653      *         (A {@code null} return can also indicate that the map
 654      *         previously associated {@code null} with {@code key}.)
 655      */
 656     public V put(K key, V value) {
 657         return putVal(hash(key), key, value, false);
 658     }
 659 
 660     /**
 661      * Implements Map.put and related methods.
 662      *
 663      * @param hash hash for key
 664      * @param key the key
 665      * @param value the value to put
 666      * @param onlyIfAbsent if true, don't change existing value
 667      * @return previous value, or null if none
 668      */
 669     private final V putVal(final int hash, final K key, final V value, boolean onlyIfAbsent) {
 670         YNode<K, V>[] tab;
 671         YNode<K, V> tp;
 672         int n, i;
 673         if ((tab = table) == null || (n = tab.length) == 0)
 674             n = (tab = resize()).length;
 675         debug("  putval", -1, new YNode<K,V>(hash, key, value, -1));
 676 
 677         int h = hash;
 678         int insert = -1;    // insertion point if not already present
 679         int insertProbes = -1;
 680         for (int probes = 1; ; probes++, h += REHASH_HASH) {
 681             if (probes > tab.length)
 682                 throw new IllegalStateException("No empty entries in table");
 683             final int index;
 684             final YNode<K, V> entry = tab[(index = ((n - 1) & h))];
 685 //            debug("    looking at", index, entry);
 686             if (entry.isEmpty()) {
 687                 // Absent; insert in the first place it could be added
 688                 // TBD: should it check onlyIfAbsent?
 689                 if (insert < 0) {
 690                     // no better place to insert than here
 691                     tab[index] = new YNode<>(hash, key, value, probes);
 692                     debug("    setting", index, tab[index]);
 693 //                    putProbes = incProbeCount(putProbes, probes);
 694                 } else {
 695                     // The new entry is more needy than the current one
 696                     final YNode<K,V> tmp = tab[insert];
 697                     tab[insert] = new YNode<>(hash, key, value, insertProbes);
 698                     debug("    robin-hood inserted", index, tab[index]);
 699 //                    putProbes = incProbeCount(putProbes, insertProbes);
 700                     putReinsert(insert, tmp);
 701                 }
 702                 break;  // break to update modCount and size
 703             }
 704 
 705             if (entry.isValue() && entry.hash == hash &&
 706                     (entry.key == key || (key != null && key.equals(entry.key)))) {
 707                 // TBD: consider if updated entry should be moved closer to the front
 708                 if (!onlyIfAbsent || entry.value == null) {
 709                     tab[index] = new YNode<>(hash, key, value, entry.probes);
 710                 }
 711                 debug("    oldvalue", index, entry);
 712                 debug("    updating", index, tab[index]);
 713 //                putProbes = incProbeCount(putProbes, probes);
 714                 return entry.value;
 715             }
 716 
 717             // Save first possible insert index
 718             if (insert < 0 && probes > entry.probes) {
 719                 insert = index;
 720                 insertProbes = probes;
 721             }
 722         }
 723         ++modCount;
 724         ++size;
 725         isTableOk(tab, "table not ok, putval");
 726         if (size >= threshold)
 727             resize();       // Ensure there is at least 1 empty available
 728         return null;
 729     }
 730 
 731     /**
 732      * Re-insert the entry in the table starting at the entry beyond the index.
 733      * Insert it at an empty slot.
 734      * Replace an entry with a lower probe count and repeat to reinsert that entry.
 735      * @param oldIndex the index just replaced
 736      * @param rEntry the entry to be replaced
 737      */
 738     private void putReinsert(final int oldIndex, YNode<K,V> rEntry) {
 739         final YNode<K, V>[] tab = table;
 740         final int n = tab.length;
 741 
 742         int h = oldIndex + REHASH_HASH;
 743         for (int probes = rEntry.probes + 1; probes <= n; probes++, h += REHASH_HASH) {
 744             isTableOk(tab, "bubble down loop");
 745             final int index = (n - 1) & h;
 746             final YNode<K,V> entry = tab[index];
 747             if (entry.isEmpty()) {
 748                 // Insert in the empty slot
 749                 tab[index] = new YNode<>(rEntry.hash, rEntry.key, rEntry.value, probes);
 750                 debug("    reinserted", index, tab[index]);
 751                 return;
 752             } else if (probes > entry.probes) {
 753                 // Replace a less deserving entry
 754                 tab[index] = new YNode<>(rEntry.hash, rEntry.key, rEntry.value, probes);
 755                 debug("    robin-hood bubble down", index, tab[index]);
 756                 rEntry = entry;
 757                 probes = rEntry.probes;
 758                 debug("    robin-hood moving", index, rEntry);
 759             } else {
 760                 debug("    robin-hood skipping", index, entry);
 761             }
 762         }
 763         throw new RuntimeException("bubble down failed");
 764     }
 765 
 766     private void debug(String msg, int index, YNode<K,V> entry) {
 767         if (DEBUG && System.out != null) {
 768             System.out.println(System.identityHashCode(this) + ": " + msg + ": index: " + index + ", node: " + Objects.toString(entry));
 769         }
 770     }
 771    private void debug2(String msg, int index, YNode<K,V> entry) {
 772         if (System.out != null) {
 773             System.out.println(System.identityHashCode(this) + ": " + msg + ": index: " + index +
 774                     ", " + "node: " + entry);
 775         }
 776     }
 777 
 778     /**
 779      * Initializes or doubles table size.  If null, allocates in
 780      * accord with initial capacity target held in field threshold.
 781      * Otherwise, because we are using power-of-two expansion, the
 782      * elements from each bin must either stay at same index, or move
 783      * with a power of two offset in the new table.
 784      *
 785      * @return the table
 786      */
 787     final YNode<K,V>[] resize() {
 788         YNode<K,V>[] oldTab = table;
 789         int oldCap = (oldTab == null) ? 0 : oldTab.length;
 790         int oldThr = threshold;
 791         int newCap, newThr = 0;
 792         if (oldCap > 0) {
 793             if (oldCap >= MAXIMUM_CAPACITY) {
 794                 threshold = Integer.MAX_VALUE;
 795                 return oldTab;
 796             }
 797             else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
 798                      oldCap >= DEFAULT_INITIAL_CAPACITY)
 799                 newThr = oldThr << 1; // double threshold
 800         }
 801         else if (oldThr > 0) // initial capacity was placed in threshold
 802             newCap = oldThr;
 803         else {               // zero initial threshold signifies using defaults
 804             newCap = DEFAULT_INITIAL_CAPACITY;
 805             newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
 806         }
 807         if (newThr == 0) {
 808             float ft = (float)newCap * loadFactor;
 809             newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
 810                     (int)ft : Integer.MAX_VALUE);
 811         }
 812         isTableOk(oldTab, "oldTab bad before resize");
 813         if (getProbes != null)
 814             Arrays.fill(getProbes, 0);
 815         if (putProbes != null)
 816             Arrays.fill(putProbes, 0);
 817         if (notFoundProbes != null)
 818             Arrays.fill(notFoundProbes, 0);
 819 
 820         // There must always be an empty entry, resize when it gets to capacity.
 821         threshold = (newThr > newCap) ? newCap : newThr;
 822         @SuppressWarnings({"rawtypes","unchecked"})
 823         YNode<K,V>[] newTab = (YNode<K,V>[])new YNode[newCap];
 824         table = newTab;
 825         if (oldTab != null) {
 826             for (int i = 0; i < oldCap; ++i) {
 827                 YNode<K,V> e;
 828                 if ((e = oldTab[i]).isValue()) {
 829                     final int ii;
 830                     if (newTab[ii = (newCap - 1) & e.hash].isEmpty()) {
 831                         newTab[ii] = new YNode<>(e.hash, e.key, e.value, 1);
 832                         putProbes = incProbeCount(putProbes, 1);
 833                     } else {
 834                         int h = e.hash + REHASH_HASH;
 835                         for (int probes = 2; ; probes++, h += REHASH_HASH) {
 836                             final int index;
 837                             if (newTab[(index = ((newCap - 1) & h))].isEmpty()) {
 838                                 newTab[index] = new YNode<>(e.hash, e.key, e.value, probes);
 839                                 putProbes = incProbeCount(putProbes, probes);
 840                                 break;
 841                             }
 842                             // TBD: Consider Robin-hood insert
 843                             if (probes > newTab.length)
 844                                 throw new IllegalStateException("NYI resize: no support for overflow");
 845                         }
 846                     }
 847                 }
 848             }
 849         }
 850 
 851         debug("resized", newTab.length, new YNode<K,V>());
 852         isTableOk(newTab, "newTab bad after resize");
 853         return newTab;
 854     }
 855 
 856     /**
 857      * Dump the hashtable.
 858      */
 859     public void dumpTable() {
 860         dumpTable(table, "dumpTable");
 861     }
 862 
 863     /**
 864      * Dump the hashtable
 865      * @param table the table
 866      * @param msg a message
 867      */
 868     private void dumpTable(YNode<K, V>[] table, String msg) {
 869         if (System.out == null || table == null)
 870             return;
 871         System.out.println(msg + ", size: " + size + ", len: " + table.length);
 872         for (int i = 0; i < table.length; ++i) {
 873             if (table[i].isValue())
 874                 System.out.println("   [" + i + "] " + table[i]);
 875         }
 876     }
 877 
 878     /**
 879      * Copies all of the mappings from the specified map to this map.
 880      * These mappings will replace any mappings that this map had for
 881      * any of the keys currently in the specified map.
 882      *
 883      * @param m mappings to be stored in this map
 884      * @throws NullPointerException if the specified map is null
 885      */
 886     public void putAll(Map<? extends K, ? extends V> m) {
 887         putMapEntries(m, true);
 888     }
 889 
 890     /**
 891      * Removes the mapping for the specified key from this map if present.
 892      *
 893      * @param  key key whose mapping is to be removed from the map
 894      * @return the previous value associated with {@code key}, or
 895      *         {@code null} if there was no mapping for {@code key}.
 896      *         (A {@code null} return can also indicate that the map
 897      *         previously associated {@code null} with {@code key}.)
 898      */
 899     public V remove(Object key) {
 900         YNode<K,V> entry = removeNode(hash(key), key, null, false, true);
 901         return entry.isValue() ? entry.value : null;
 902     }
 903 
 904     /**
 905      * Implements Map.remove and related methods.
 906      *
 907      * @param hash hash for key
 908      * @param key the key
 909      * @param value the value to match if matchValue, else ignored
 910      * @param matchValue if true only remove if value is equal
 911      * @param movable if false do not move other nodes while removing
 912      * @return the node, or null if none
 913      */
 914     @SuppressWarnings("unchecked")
 915     private final YNode<K,V> removeNode(final int hash, final Object key, final Object value,
 916                                          boolean matchValue, boolean movable) {
 917         YNode<K, V>[] tab;
 918         YNode<K, V> entry;
 919         V v = null;
 920         int curr;
 921         int n;
 922         debug("  removeNode", -2, new YNode<K,V>(hash, (K)key, (V)value, -2));
 923 
 924         if ((tab = table) != null && (n = tab.length) > 0 &&
 925                 (curr = getNode(hash, key)) >= 0 &&
 926                 (entry = tab[curr]).isValue() &&
 927                 ((!matchValue || (v = entry.value) == value ||
 928                         (value != null && value.equals(v))))) {
 929             // found entry; free and compress
 930             removeNode(curr);
 931             return entry;
 932         }
 933         return new YNode();
 934     }
 935 
 936     @SuppressWarnings("unchecked")
 937     private void removeNode(final int curr) {
 938         final YNode<K, V>[] tab = table;;
 939         final int n = tab.length;
 940 
 941         ++modCount;
 942         --size;
 943         int free = curr;        // The entry to be cleared, if not replaced
 944         int h = curr;
 945         int probes = 0;
 946         do {
 947             probes++;
 948             h += REHASH_HASH;
 949             final int index = (n - 1) & h;
 950             final YNode<K, V> entry = tab[index];
 951             if (entry.probes == 0) {
 952                 // Search ended at empty entry, clear the free entry
 953                 debug("    clearing", index, entry);
 954                 tab[free] = new YNode<>();
 955                 return;
 956             }
 957             if (entry.probes > probes) {
 958                 // move up the entry, skip if it is already in the best spot
 959                 debug("    replacing", free, entry);
 960                 tab[free] = new YNode<>(entry.hash, entry.key, entry.value, entry.probes - probes);
 961                 debug("         with", free, tab[free]);
 962                 free = index;
 963                 probes = 0;
 964             }
 965         } while (((n - 1) & h) != curr);
 966         isTableOk(tab, "table not ok, not found");
 967         throw new RuntimeException("removeNode too many probes");
 968     }
 969 
 970     /**
 971      * Removes all of the mappings from this map.
 972      * The map will be empty after this call returns.
 973      */
 974     @SuppressWarnings({"rawtypes","unchecked"})
 975     public void clear() {
 976         YNode<K,V>[] tab;
 977         modCount++;
 978         if ((tab = table) != null && size > 0) {
 979             size = 0;
 980             for (int i = 0; i < tab.length; i++)
 981                 tab[i] = new YNode();
 982         }
 983     }
 984 
 985     /**
 986      * Returns {@code true} if this map maps one or more keys to the
 987      * specified value.
 988      *
 989      * @param value value whose presence in this map is to be tested
 990      * @return {@code true} if this map maps one or more keys to the
 991      *         specified value
 992      */
 993     public boolean containsValue(Object value) {
 994         YNode<K,V>[] tab; V v;
 995         if ((tab = table) != null && size > 0) {
 996             for (YNode<K,V> te : tab) {
 997                 if (te.isValue()) {
 998                     if ((v = te.value) == value ||
 999                             (value != null && value.equals(v)))
1000                         return true;
1001                 }
1002             }
1003         }
1004         return false;
1005     }
1006 
1007     /**
1008      * Returns a {@link Set} view of the keys contained in this map.
1009      * The set is backed by the map, so changes to the map are
1010      * reflected in the set, and vice-versa.  If the map is modified
1011      * while an iteration over the set is in progress (except through
1012      * the iterator's own {@code remove} operation), the results of
1013      * the iteration are undefined.  The set supports element removal,
1014      * which removes the corresponding mapping from the map, via the
1015      * {@code Iterator.remove}, {@code Set.remove},
1016      * {@code removeAll}, {@code retainAll}, and {@code clear}
1017      * operations.  It does not support the {@code add} or {@code addAll}
1018      * operations.
1019      *
1020      * @return a set view of the keys contained in this map
1021      */
1022     public Set<K> keySet() {
1023         Set<K> ks = keySet;
1024         if (ks == null) {
1025             ks = new KeySet();
1026             keySet = ks;
1027         }
1028         return ks;
1029     }
1030 
1031     /**
1032      * Prepares the array for {@link Collection#toArray(Object[])} implementation.
1033      * If supplied array is smaller than this map size, a new array is allocated.
1034      * If supplied array is bigger than this map size, a null is written at size index.
1035      *
1036      * @param a an original array passed to {@code toArray()} method
1037      * @param <T> type of array elements
1038      * @return an array ready to be filled and returned from {@code toArray()} method.
1039      */
1040     @SuppressWarnings("unchecked")
1041     final <T> T[] prepareArray(T[] a) {
1042         int size = this.size;
1043         if (a.length < size) {
1044             return (T[]) java.lang.reflect.Array
1045                     .newInstance(a.getClass().getComponentType(), size);
1046         }
1047         if (a.length > size) {
1048             a[size] = null;
1049         }
1050         return a;
1051     }
1052 
1053     /**
1054      * Fills an array with this map keys and returns it. This method assumes
1055      * that input array is big enough to fit all the keys. Use
1056      * {@link #prepareArray(Object[])} to ensure this.
1057      *
1058      * @param a an array to fill
1059      * @param <T> type of array elements
1060      * @return supplied array
1061      */
1062     <T> T[] keysToArray(T[] a) {
1063         Object[] r = a;
1064         YNode<K,V>[] tab;
1065         int idx = 0;
1066         if (size > 0 && (tab = table) != null) {
1067             for (YNode<K,V> te : tab) {
1068                 if (te.isValue()) {
1069                     r[idx++] = te.key;
1070                 }
1071             }
1072         }
1073         return a;
1074     }
1075 
1076     /**
1077      * Fills an array with this map values and returns it. This method assumes
1078      * that input array is big enough to fit all the values. Use
1079      * {@link #prepareArray(Object[])} to ensure this.
1080      *
1081      * @param a an array to fill
1082      * @param <T> type of array elements
1083      * @return supplied array
1084      */
1085     <T> T[] valuesToArray(T[] a) {
1086         Object[] r = a;
1087         YNode<K,V>[] tab;
1088         int idx = 0;
1089         if (size > 0 && (tab = table) != null) {
1090             for (YNode<K,V> te : tab) {
1091                 if (te.isValue()) {
1092                     r[idx++] = te.value;
1093                 }
1094             }
1095         }
1096         return a;
1097     }
1098 
1099     final class KeySet extends AbstractSet<K> {
1100         public final int size()                 { return size; }
1101         public final void clear()               { HashMap.this.clear(); }
1102         public final Iterator<K> iterator()     { return new KeyIterator(); }
1103         public final boolean contains(Object o) { return containsKey(o); }
1104         public final boolean remove(Object key) {
1105             return removeNode(hash(key), key, null, false, true).isValue();
1106         }
1107 
1108         public Object[] toArray() {
1109             return keysToArray(new Object[size]);
1110         }
1111 
1112         public <T> T[] toArray(T[] a) {
1113             return keysToArray(prepareArray(a));
1114         }
1115 
1116         public final void forEach(Consumer<? super K> action) {
1117             YNode<K,V>[] tab;
1118             if (action == null)
1119                 throw new NullPointerException();
1120             if (size > 0 && (tab = table) != null) {
1121                 int mc = modCount;
1122                 for (YNode<K,V> te : tab) {
1123                     if (te.isValue()) {
1124                         action.accept(te.key);
1125                     }
1126                 }
1127                 if (modCount != mc)
1128                     throw new ConcurrentModificationException();
1129             }
1130         }
1131     }
1132 
1133     /**
1134      * Returns a {@link Collection} view of the values contained in this map.
1135      * The collection is backed by the map, so changes to the map are
1136      * reflected in the collection, and vice-versa.  If the map is
1137      * modified while an iteration over the collection is in progress
1138      * (except through the iterator's own {@code remove} operation),
1139      * the results of the iteration are undefined.  The collection
1140      * supports element removal, which removes the corresponding
1141      * mapping from the map, via the {@code Iterator.remove},
1142      * {@code Collection.remove}, {@code removeAll},
1143      * {@code retainAll} and {@code clear} operations.  It does not
1144      * support the {@code add} or {@code addAll} operations.
1145      *
1146      * @return a view of the values contained in this map
1147      */
1148     public Collection<V> values() {
1149         Collection<V> vs = values;
1150         if (vs == null) {
1151             vs = new Values();
1152             values = vs;
1153         }
1154         return vs;
1155     }
1156 
1157     final class Values extends AbstractCollection<V> {
1158         public final int size()                 { return size; }
1159         public final void clear()               { HashMap.this.clear(); }
1160         public final Iterator<V> iterator()     { return new ValueIterator(); }
1161         public final boolean contains(Object o) { return containsValue(o); }
1162 
1163         public Object[] toArray() {
1164             return valuesToArray(new Object[size]);
1165         }
1166 
1167         public <T> T[] toArray(T[] a) {
1168             return valuesToArray(prepareArray(a));
1169         }
1170 
1171         public final void forEach(Consumer<? super V> action) {
1172             YNode<K,V>[] tab;
1173             if (action == null)
1174                 throw new NullPointerException();
1175             if (size > 0 && (tab = table) != null) {
1176                 int mc = modCount;
1177                 for (YNode<K,V> te : tab) {
1178                     if (te.isValue()) {
1179                         action.accept(te.value);
1180                     }
1181                 }
1182                 if (modCount != mc)
1183                     throw new ConcurrentModificationException();
1184             }
1185         }
1186     }
1187 
1188     /**
1189      * Returns a {@link Set} view of the mappings contained in this map.
1190      * The set is backed by the map, so changes to the map are
1191      * reflected in the set, and vice-versa.  If the map is modified
1192      * while an iteration over the set is in progress (except through
1193      * the iterator's own {@code remove} operation, or through the
1194      * {@code setValue} operation on a map entry returned by the
1195      * iterator) the results of the iteration are undefined.  The set
1196      * supports element removal, which removes the corresponding
1197      * mapping from the map, via the {@code Iterator.remove},
1198      * {@code Set.remove}, {@code removeAll}, {@code retainAll} and
1199      * {@code clear} operations.  It does not support the
1200      * {@code add} or {@code addAll} operations.
1201      *
1202      * @return a set view of the mappings contained in this map
1203      */
1204     public Set<Map.Entry<K,V>> entrySet() {
1205         Set<Map.Entry<K,V>> es;
1206         return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;
1207     }
1208 
1209     final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
1210         public final int size()                 { return size; }
1211         public final void clear()               { HashMap.this.clear(); }
1212         public final Iterator<Map.Entry<K,V>> iterator() {
1213             return new EntryIterator();
1214         }
1215         public final boolean contains(Object o) {
1216             if (!(o instanceof Map.Entry))
1217                 return false;
1218             Map.Entry<?,?> e = (Map.Entry<?,?>) o;
1219             Object key = e.getKey();
1220             int index = getNode(hash(key), key);
1221             return index >= 0 && table[index].equals(e);
1222         }
1223         public final boolean remove(Object o) {
1224             if (o instanceof Map.Entry) {
1225                 Map.Entry<?,?> e = (Map.Entry<?,?>) o;
1226                 Object key = e.getKey();
1227                 Object value = e.getValue();
1228                 return removeNode(hash(key), key, value, true, true).isValue();
1229             }
1230             return false;
1231         }
1232 
1233         public final void forEach(Consumer<? super Map.Entry<K,V>> action) {
1234             YNode<K,V>[] tab;
1235             if (action == null)
1236                 throw new NullPointerException();
1237             if (size > 0 && (tab = table) != null) {
1238                 int mc = modCount;
1239                 for (YNode<K,V> te : tab) {
1240                     if (te.isValue()) {
1241                         action.accept(new YNodeWrapper(te.hash & (tab.length - 1)));
1242                     }
1243                 }
1244                 if (modCount != mc)
1245                     throw new ConcurrentModificationException();
1246             }
1247         }
1248     }
1249 
1250     // Overrides of JDK8 Map extension methods
1251 
1252     @Override
1253     public V getOrDefault(Object key, V defaultValue) {
1254         final int index;
1255         return (index = getNode(hash(key), key)) < 0 ? defaultValue : table[index].value;
1256     }
1257 
1258     @Override
1259     public V putIfAbsent(K key, V value) {
1260         return putVal(hash(key), key, value, true);
1261     }
1262 
1263     @Override
1264     public boolean remove(Object key, Object value) {
1265         return removeNode(hash(key), key, value, true, true).isValue();
1266     }
1267 
1268     @Override
1269     public boolean replace(K key, V oldValue, V newValue) {
1270         int hash, index;
1271         V v;
1272         if ((index = getNode((hash = hash(key)), key)) >= 0 &&
1273                 ((v = table[index].value) == oldValue || (v != null && v.equals(oldValue)))) {
1274             table[index] = new YNode<>(hash, key, newValue, table[index].probes);
1275             return true;
1276         }
1277         return false;
1278     }
1279 
1280     @Override
1281     public V replace(K key, V value) {
1282         int hash, index;
1283         V v;
1284         if ((index = getNode((hash = hash(key)), key)) >= 0) {
1285             V oldValue = table[index].value;
1286             table[index] = new YNode<>(hash, key, value, table[index].probes);
1287             return oldValue;
1288         }
1289         return null;
1290     }
1291 
1292     /**
1293      * {@inheritDoc}
1294      *
1295      * <p>This method will, on a best-effort basis, throw a
1296      * {@link ConcurrentModificationException} if it is detected that the
1297      * mapping function modifies this map during computation.
1298      *
1299      * @throws ConcurrentModificationException if it is detected that the
1300      * mapping function modified this map
1301      */
1302     @Override
1303     public V computeIfAbsent(K key,
1304                              Function<? super K, ? extends V> mappingFunction) {
1305         if (mappingFunction == null)
1306             throw new NullPointerException();
1307         int hash = hash(key);
1308         YNode<K,V>[] tab = table;
1309         YNode<K,V> entry;
1310         int index;
1311 
1312         index = getNode(hash, key);
1313         if (index >= 0 && (entry = tab[index]).value != null) {
1314             return entry.value;
1315         }
1316         int mc = modCount;
1317         V v = mappingFunction.apply(key);
1318         if (mc != modCount) { throw new ConcurrentModificationException(); }
1319         if (v == null) {
1320             return null;
1321         }
1322         putVal(hash, key, v, false);
1323         return v;
1324     }
1325 
1326     /**
1327      * {@inheritDoc}
1328      *
1329      * <p>This method will, on a best-effort basis, throw a
1330      * {@link ConcurrentModificationException} if it is detected that the
1331      * remapping function modifies this map during computation.
1332      *
1333      * @throws ConcurrentModificationException if it is detected that the
1334      * remapping function modified this map
1335      */
1336     @Override
1337     public V computeIfPresent(K key,
1338                               BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
1339         if (remappingFunction == null)
1340             throw new NullPointerException();
1341         YNode<K,V> oldValue;
1342         int hash = hash(key);
1343         int index = getNode(hash, key);
1344         if (index >= 0 && (oldValue = table[index]).value != null) {
1345             int mc = modCount;
1346             V v = remappingFunction.apply(key, oldValue.value);
1347             if (mc != modCount) { throw new ConcurrentModificationException(); }
1348             if (v != null) {
1349                 table[index] = new YNode<>(hash, key, v, oldValue.probes);
1350                 return v;
1351             } else
1352                 removeNode(hash, key, null, false, true);
1353         }
1354         return null;
1355     }
1356 
1357     /**
1358      * {@inheritDoc}
1359      *
1360      * <p>This method will, on a best-effort basis, throw a
1361      * {@link ConcurrentModificationException} if it is detected that the
1362      * remapping function modifies this map during computation.
1363      *
1364      * @throws ConcurrentModificationException if it is detected that the
1365      * remapping function modified this map
1366      */
1367     @Override
1368     @SuppressWarnings("unchecked")
1369     public V compute(K key,
1370                      BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
1371         if (remappingFunction == null)
1372             throw new NullPointerException();
1373 
1374         int hash = hash(key);
1375         int index = getNode(hash, key);
1376         YNode<K,V> oldValue = (index >= 0) ? table[index] : new YNode();
1377 
1378         int mc = modCount;
1379         V v = remappingFunction.apply(key, oldValue.value);
1380         if (mc != modCount) { throw new ConcurrentModificationException(); }
1381         if (v != null) {
1382             if (index >= 0) {
1383                 table[index] = new YNode<>(hash, key, v, oldValue.probes);
1384 //                modCount++;
1385             } else
1386                 putVal(hash, key, v, false);
1387         } else
1388             // TBD: 2nd lookup to remove even though we have index
1389             removeNode(hash, key, null, false, true);
1390         return v;
1391     }
1392 
1393     /**
1394      * {@inheritDoc}
1395      *
1396      * <p>This method will, on a best-effort basis, throw a
1397      * {@link ConcurrentModificationException} if it is detected that the
1398      * remapping function modifies this map during computation.
1399      *
1400      * @throws ConcurrentModificationException if it is detected that the
1401      * remapping function modified this map
1402      */
1403     @Override
1404     public V merge(K key, V value,
1405                    BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
1406         if (remappingFunction == null)
1407             throw new NullPointerException();
1408 
1409         final int hash = hash(key);
1410         final int index = getNode(hash, key);
1411         if (index >= 0) {
1412             int mc = modCount;
1413             V v = remappingFunction.apply(table[index].value, value);
1414             if (mc != modCount) { throw new ConcurrentModificationException(); }
1415             if (v != null) {
1416                 if (index >= 0) {
1417                     table[index] = new YNode<>(hash, key, v, table[index].probes);
1418 //                    modCount++;
1419                 } else
1420                     putVal(hash, key, v, false);
1421             } else {
1422                 // TBD: 2nd lookup to remove even though we have index
1423                 removeNode(hash, key, null, false, true);
1424             }
1425             return v;
1426         } else {
1427             // put new key/value (even if null)
1428             putVal(hash, key, value, false);
1429         }
1430         return value;
1431     }
1432 
1433     @Override
1434     public void forEach(BiConsumer<? super K, ? super V> action) {
1435         YNode<K,V>[] tab;
1436         if (action == null)
1437             throw new NullPointerException();
1438         if (size > 0 && (tab = table) != null) {
1439             int mc = modCount;
1440             for (YNode<K,V> te : tab) {
1441                 if (te.isValue()) {
1442                     action.accept(te.key, te.value);
1443                 }
1444             }
1445             if (modCount != mc)
1446                 throw new ConcurrentModificationException();
1447         }
1448     }
1449 
1450     @Override
1451     public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
1452         super.replaceAll(function);
1453     }
1454 
1455     /* ------------------------------------------------------------ */
1456     // Cloning and serialization
1457 
1458     /**
1459      * Returns a shallow copy of this {@code HashMap} instance: the keys and
1460      * values themselves are not cloned.
1461      *
1462      * @return a shallow copy of this map
1463      */
1464     @SuppressWarnings("unchecked")
1465     @Override
1466     public Object clone() {
1467         HashMap<K,V> result;
1468         try {
1469             result = (HashMap<K,V>)super.clone();
1470         } catch (CloneNotSupportedException e) {
1471             // this shouldn't happen, since we are Cloneable
1472             throw new InternalError(e);
1473         }
1474         result.reinitialize();
1475         result.putMapEntries(this, false);
1476         return result;
1477     }
1478 
1479     // These methods are also used when serializing HashSets
1480     final float loadFactor() { return loadFactor; }
1481     final int capacity() {
1482         return (table != null) ? table.length :
1483                 (threshold > 0) ? threshold :
1484                 DEFAULT_INITIAL_CAPACITY;
1485     }
1486 
1487     /**
1488      * Saves this map to a stream (that is, serializes it).
1489      *
1490      * @param s the stream
1491      * @throws IOException if an I/O error occurs
1492      * @serialData The <i>capacity</i> of the HashMap (the length of the
1493      *             bucket array) is emitted (int), followed by the
1494      *             <i>size</i> (an int, the number of key-value
1495      *             mappings), followed by the key (Object) and value (Object)
1496      *             for each key-value mapping.  The key-value mappings are
1497      *             emitted in no particular order.
1498      */
1499     private void writeObject(java.io.ObjectOutputStream s)
1500         throws IOException {
1501         int buckets = capacity();
1502         // Write out the threshold, loadfactor, and any hidden stuff
1503         s.defaultWriteObject();
1504         s.writeInt(buckets);
1505         s.writeInt(size);
1506         internalWriteEntries(s);
1507     }
1508 
1509     /**
1510      * Reconstitutes this map from a stream (that is, deserializes it).
1511      * @param s the stream
1512      * @throws ClassNotFoundException if the class of a serialized object
1513      *         could not be found
1514      * @throws IOException if an I/O error occurs
1515      */
1516     private void readObject(java.io.ObjectInputStream s)
1517         throws IOException, ClassNotFoundException {
1518         // Read in the threshold (ignored), loadfactor, and any hidden stuff
1519         s.defaultReadObject();
1520         reinitialize();
1521         if (loadFactor <= 0 || Float.isNaN(loadFactor))
1522             throw new InvalidObjectException("Illegal load factor: " +
1523                     loadFactor);
1524         s.readInt();                // Read and ignore number of buckets
1525         int mappings = s.readInt(); // Read number of mappings (size)
1526         if (mappings < 0)
1527             throw new InvalidObjectException("Illegal mappings count: " +
1528                     mappings);
1529         else if (mappings > 0) { // (if zero, use defaults)
1530             // Size the table using given load factor only if within
1531             // range of 0.25...4.0
1532             float lf = Math.min(Math.max(0.25f, loadFactor), 4.0f);
1533             float fc = (float)mappings / lf + 1.0f;
1534             int cap = ((fc < DEFAULT_INITIAL_CAPACITY) ?
1535                     DEFAULT_INITIAL_CAPACITY :
1536                     (fc >= MAXIMUM_CAPACITY) ?
1537                             MAXIMUM_CAPACITY :
1538                             tableSizeFor((int)fc));
1539             float ft = (float)cap * lf;
1540             threshold = ((cap < MAXIMUM_CAPACITY && ft < MAXIMUM_CAPACITY) ?
1541                     (int)ft : Integer.MAX_VALUE);
1542 
1543             // Check Map.Entry[].class since it's the nearest public type to
1544             // what we're actually creating.
1545 //            SharedSecrets.getJavaObjectInputStreamAccess().checkArray(s, Map.Entry[].class, cap);
1546             @SuppressWarnings({"rawtypes","unchecked"})
1547             YNode<K,V>[] tab = (YNode<K,V>[])new YNode[cap];
1548             table = tab;
1549 
1550             // Read the keys and values, and put the mappings in the HashMap
1551             for (int i = 0; i < mappings; i++) {
1552                 @SuppressWarnings("unchecked")
1553                 K key = (K) s.readObject();
1554                 @SuppressWarnings("unchecked")
1555                 V value = (V) s.readObject();
1556                 putVal(hash(key), key, value, false);
1557             }
1558         }
1559     }
1560 
1561     /* ------------------------------------------------------------ */
1562     // iterators
1563 
1564     abstract class HashIterator {
1565         int next;        // next entry to return
1566         int current;     // current entry
1567         int expectedModCount;  // for fast-fail
1568         int count;
1569 
1570         HashIterator() {
1571             expectedModCount = modCount;
1572             current = -1;
1573             next = (size > 0 && table != null) ? findNext(0) : -1;
1574             count = 0;
1575         }
1576 
1577         public final boolean hasNext() {
1578             return next >= 0;
1579         }
1580 
1581         final Entry<K,V> nextNode() {
1582             if (modCount != expectedModCount)
1583                 throw new ConcurrentModificationException("ex: " + expectedModCount + " != " + modCount);
1584             if (!hasNext())
1585                 throw new NoSuchElementException();
1586             current = next;
1587             assert current >= 0;
1588 
1589             next = (current + REHASH_HASH) & (table.length - 1);
1590             next = (next == 0) ? -1 : findNext(next);
1591             return new YNodeWrapper(current);
1592         }
1593 
1594         public final void remove() {
1595             if (current < 0 || current > table.length)
1596                 throw new IllegalStateException();
1597             if (modCount != expectedModCount)
1598                 throw new ConcurrentModificationException();
1599             YNode<K, V> p = table[current];
1600             removeNode(p.hash, p.key, null, false, false);
1601             if (table[current].isValue()) {
1602                 // a node was moved into current
1603                 next = current;
1604             }
1605             current = -1;
1606             expectedModCount = modCount;
1607         }
1608 
1609         /**
1610          * Find the next value entry in the rehash sequence.
1611          */
1612         private final int findNext(int index) {
1613             final YNode<K,V>[] t = table;
1614             final int lowbitmask = table.length - 1;
1615             index = index & lowbitmask;
1616             int count = 0;
1617             while (!t[index].isValue()) {
1618                 count ++;
1619                 index = (index + REHASH_HASH) & lowbitmask;
1620 		if (index == 0)
1621 		    return -1;
1622             }
1623             return index;
1624         }
1625     }
1626 
1627     final class KeyIterator extends HashIterator
1628             implements Iterator<K> {
1629         public final K next() { return nextNode().getKey(); }
1630     }
1631 
1632     final class ValueIterator extends HashIterator
1633             implements Iterator<V> {
1634         public final V next() { return nextNode().getValue(); }
1635     }
1636 
1637     final class EntryIterator extends HashIterator
1638             implements Iterator<Map.Entry<K,V>> {
1639         public final Map.Entry<K,V> next() { return nextNode(); }
1640     }
1641 
1642     /**
1643      * Reset to initial default state.  Called by clone and readObject.
1644      */
1645     void reinitialize() {
1646         table = null;
1647         entrySet = null;
1648         keySet = null;
1649         values = null;
1650         modCount = 0;
1651         threshold = 0;
1652         size = 0;
1653     }
1654 
1655     // Called only from writeObject, to ensure compatible ordering.
1656     void internalWriteEntries(java.io.ObjectOutputStream s) throws IOException {
1657         YNode<K,V>[] tab;
1658         if (size > 0 && (tab = table) != null) {
1659             for (YNode<K,V> te : tab) {
1660                 if (te.isValue()) {
1661                     s.writeObject(te.key);
1662                     s.writeObject(te.value);
1663                 }
1664             }
1665         }
1666     }
1667 
1668 
1669     /**
1670      * Check each entry in the table.
1671      *  - FindNode will find it from the key.
1672      *  - the probes value is correct.
1673      */
1674     boolean isTableOk(final YNode<K,V>[] tab, String msg) {
1675         int n;
1676         if (!VERIFYTABLEOK || tab == null || (n = tab.length) == 0)
1677             return true;
1678         boolean ok = true;
1679         int valueEntries = 0;
1680         for (int index = 0; index < tab.length; index++) {
1681             final YNode<K,V> te = tab[index];
1682             if (te.isValue()) {
1683                 valueEntries++;
1684                 if (te.key == this || te.value == this)
1685                     continue;   // skip self referential entries
1686                 int hash = hash(te.key);
1687                 int th = hash(te.key);
1688                 if (th != te.hash) {
1689                     ok = false;
1690                     debug2("ERROR: computed hash not equal stored hash: th: " + th, index, te);
1691                 }
1692 
1693                 int findex = getNode(hash, te.key);
1694                 if (findex < index) {
1695                     ok = false;
1696                     debug2("ERROR: getNode entry not found/found at wrong index: " + findex,
1697                             index , te);
1698                 }
1699                 if (findex >= 0) {
1700                     int h = hash;
1701                     for (int probes = 1; probes <= tab.length; probes++, h += REHASH_HASH) {
1702                         int i = (n - 1) & h;
1703                         if (i == findex) {
1704                             if (probes != te.probes) {
1705                                 ok = false;
1706                                 debug2("ERROR: computed probes not equal recorded " +
1707                                         "probes: " + probes, findex, te);
1708                             }
1709                             break;
1710                         }
1711                         if (probes == 500) {
1712                             debug2("probes > 500: " + probes, findex, te);
1713                         }
1714                     }
1715                 }
1716                 // Check for duplicate entry
1717                 for (int j = index + 1; j < tab.length; j++) {
1718                     if (te.hash == tab[j].hash &&
1719                             te.key.equals(tab[j].key)) {
1720                         debug2("ERROR: YNode at index ", index, te);
1721                         debug2("ERROR: duplicate YNode", j, tab[j]);
1722                     }
1723                 }
1724             }
1725         }
1726         if (valueEntries != size()) {
1727             debug2("ERROR: size wrong: " + valueEntries, size(), new YNode<K,V>());
1728             ok = false;
1729         }
1730         if (!ok) {
1731             if (System.out != null) {
1732                 Thread.dumpStack();
1733                 dumpTable(table, msg);
1734             }
1735         }
1736         return ok;
1737     }
1738 
1739     /**
1740      * Print stats of the table to the a stream.
1741      * @param out a stream
1742      */
1743     public void dumpStats(PrintStream out) {
1744         out.printf("%s instance: size: %d%n", this.getClass().getName(), this.size());
1745         long size = heapSize();
1746         long bytesPer = (this.size != 0) ? size / this.size() : 0;
1747         out.printf("    heap size: %d(bytes), avg bytes per entry: %d, table len: %d%n",
1748                 size, bytesPer, (table != null) ? table.length : 0);
1749         long[] types = entryTypes();
1750         out.printf("    values: %d, empty: %d%n",
1751                 types[0], types[1]);
1752         printStats(out, "hash collisions", entryRehashes());
1753         printStats(out, "getProbes      ", minCounts(getProbes));
1754         printStats(out, "putProbes      ", minCounts(putProbes));
1755         printStats(out, "notFoundProbes ", minCounts(notFoundProbes));
1756 
1757         isTableOk(table, "dumpStats");
1758     }
1759 
1760     private void printStats(PrintStream out, String label, int[] hist) {
1761         if (hist.length > 1) {
1762             out.printf("    %s: max: %d, mean: %3.2f, stddev: %3.2f, %s%n",
1763                     label, hist.length - 1,
1764                     computeMean(hist), computeStdDev(hist),
1765                     Arrays.toString(hist));
1766         } else if (hist.length > 0) {
1767             out.printf("    %s: max: %d, %s%n",
1768                     label, hist.length - 1,
1769                     Arrays.toString(hist));
1770         } else {
1771             out.printf("    %s: n/a%n", label);
1772         }
1773     }
1774 
1775     private double computeStdDev(int[] hist) {
1776         double mean = computeMean(hist);
1777         double sum = 0.0f;
1778         long count = 0L;
1779         for (int i = 1; i < hist.length; i++) {
1780             count += hist[i];
1781             sum += (i - mean) * (i - mean) * hist[i];
1782         }
1783         return Math.sqrt(sum / (count - 1));
1784     }
1785 
1786     private double computeMean(int[] hist) {
1787         long sum = 0L;
1788         long count = 0;
1789         for (int i = 1; i < hist.length; i++) {
1790             count += hist[i];
1791             sum += i * hist[i];
1792         }
1793         return (double)sum / (double)count;
1794     }
1795 
1796     private long[] entryTypes() {
1797         long[] counts = new long[2];
1798         if (table == null)
1799             return counts;
1800         for (YNode<K,V> te : table) {
1801             if (te.isEmpty())
1802                 counts[1]++;
1803             else
1804                 counts[0]++;
1805         }
1806         return counts;
1807     }
1808 
1809     private int[] incProbeCount(int[] counters, int probes) {
1810         if (counters == null)
1811             counters = new int[Math.max(probes + 1, 16)];
1812         else if (probes >= counters.length)
1813             counters = Arrays.copyOf(counters, Math.max(probes + 1, counters.length * 2));
1814         counters[probes]++;
1815         return counters;
1816     }
1817 
1818 
1819     // Returns a histogram array of the number of rehashs needed to find each key.
1820     private int[] entryRehashes() {
1821         if (table == null)
1822             return new int[0];
1823         int[] counts = new int[table.length + 1];
1824         YNode<K,V>[] tab = table;
1825         int n = tab.length;
1826         for (YNode<K,V> te : tab) {
1827 
1828             if (!te.isValue())
1829                 continue;
1830             int h = te.hash;
1831             int count;
1832             final K key = te.key;
1833             K k;
1834             for (count = 1; count < tab.length; count++, h += REHASH_HASH) {
1835                 final YNode<K, V> entry;
1836                 if ((entry = tab[(n - 1) & h]).isValue() &&
1837                         entry.hash == te.hash &&
1838                         ((k = entry.key) == key || (k != null && k.equals(key)))) {
1839                     break;
1840                 }
1841             }
1842 
1843             counts[count]++;
1844         }
1845 
1846         int i;
1847         for (i = counts.length - 1; i >= 0 && counts[i] == 0; i--) {
1848         }
1849         counts = Arrays.copyOf(counts, i + 1);
1850         return counts;
1851     }
1852 
1853     private int[] minCounts(int[] counts) {
1854         int i;
1855         for (i = counts.length - 1; i >= 0 && counts[i] == 0; i--) {
1856         }
1857         counts = Arrays.copyOf(counts, i + 1);
1858         return counts;
1859     }
1860 
1861     private long heapSize() {
1862         long acc = objectSizeMaybe(this);
1863         return acc + objectSizeMaybe(table);
1864     }
1865 
1866     private long objectSizeMaybe(Object o) {
1867         try {
1868             return (mObjectSize != null)
1869                     ? (long)mObjectSize.invoke(null, o)
1870                     : 0L;
1871         } catch (IllegalAccessException | InvocationTargetException e) {
1872             return 0L;
1873         }
1874     }
1875 
1876     private static boolean hasObjectSize = false;
1877     private static Method mObjectSize = getObjectSizeMethod();
1878 
1879     private static Method getObjectSizeMethod() {
1880         try {
1881             Method m = Objects.class.getDeclaredMethod("getObjectSize", Object.class);
1882             hasObjectSize = true;
1883             return m;
1884         } catch (NoSuchMethodException nsme) {
1885             return null;
1886         }
1887     }
1888 
1889 }