1 /*
   2  * Copyright (c) 2000, 2018, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.  Oracle designates this
   8  * particular file as subject to the "Classpath" exception as provided
   9  * by Oracle in the LICENSE file that accompanied this code.
  10  *
  11  * This code is distributed in the hope that it will be useful, but WITHOUT
  12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14  * version 2 for more details (a copy is included in the LICENSE file that
  15  * accompanied this code).
  16  *
  17  * You should have received a copy of the GNU General Public License version
  18  * 2 along with this work; if not, write to the Free Software Foundation,
  19  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  20  *
  21  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  22  * or visit www.oracle.com if you need additional information or have any
  23  * questions.
  24  */
  25 
  26 package java.util;
  27 
  28 import java.lang.reflect.Array;
  29 import java.util.function.BiConsumer;
  30 import java.util.function.BiFunction;
  31 import java.util.function.Consumer;
  32 import jdk.internal.misc.SharedSecrets;
  33 
  34 /**
  35  * This class implements the {@code Map} interface with a hash table, using
  36  * reference-equality in place of object-equality when comparing keys (and
  37  * values).  In other words, in an {@code IdentityHashMap}, two keys
  38  * {@code k1} and {@code k2} are considered equal if and only if
  39  * {@code (k1==k2)}.  (In normal {@code Map} implementations (like
  40  * {@code HashMap}) two keys {@code k1} and {@code k2} are considered equal
  41  * if and only if {@code (k1==null ? k2==null : k1.equals(k2))}.)
  42  *
  43  * <p><b>This class is <i>not</i> a general-purpose {@code Map}
  44  * implementation!  While this class implements the {@code Map} interface, it
  45  * intentionally violates {@code Map's} general contract, which mandates the
  46  * use of the {@code equals} method when comparing objects.  This class is
  47  * designed for use only in the rare cases wherein reference-equality
  48  * semantics are required.</b>
  49  *
  50  * <p>A typical use of this class is <i>topology-preserving object graph
  51  * transformations</i>, such as serialization or deep-copying.  To perform such
  52  * a transformation, a program must maintain a "node table" that keeps track
  53  * of all the object references that have already been processed.  The node
  54  * table must not equate distinct objects even if they happen to be equal.
  55  * Another typical use of this class is to maintain <i>proxy objects</i>.  For
  56  * example, a debugging facility might wish to maintain a proxy object for
  57  * each object in the program being debugged.
  58  *
  59  * <p>This class provides all of the optional map operations, and permits
  60  * {@code null} values and the {@code null} key.  This class makes no
  61  * guarantees as to the order of the map; in particular, it does not guarantee
  62  * that the order will remain constant over time.
  63  *
  64  * <p>This class provides constant-time performance for the basic
  65  * operations ({@code get} and {@code put}), assuming the system
  66  * identity hash function ({@link System#identityHashCode(Object)})
  67  * disperses elements properly among the buckets.
  68  *
  69  * <p>This class has one tuning parameter (which affects performance but not
  70  * semantics): <i>expected maximum size</i>.  This parameter is the maximum
  71  * number of key-value mappings that the map is expected to hold.  Internally,
  72  * this parameter is used to determine the number of buckets initially
  73  * comprising the hash table.  The precise relationship between the expected
  74  * maximum size and the number of buckets is unspecified.
  75  *
  76  * <p>If the size of the map (the number of key-value mappings) sufficiently
  77  * exceeds the expected maximum size, the number of buckets is increased.
  78  * Increasing the number of buckets ("rehashing") may be fairly expensive, so
  79  * it pays to create identity hash maps with a sufficiently large expected
  80  * maximum size.  On the other hand, iteration over collection views requires
  81  * time proportional to the number of buckets in the hash table, so it
  82  * pays not to set the expected maximum size too high if you are especially
  83  * concerned with iteration performance or memory usage.
  84  *
  85  * <p><strong>Note that this implementation is not synchronized.</strong>
  86  * If multiple threads access an identity hash map concurrently, and at
  87  * least one of the threads modifies the map structurally, it <i>must</i>
  88  * be synchronized externally.  (A structural modification is any operation
  89  * that adds or deletes one or more mappings; merely changing the value
  90  * associated with a key that an instance already contains is not a
  91  * structural modification.)  This is typically accomplished by
  92  * synchronizing on some object that naturally encapsulates the map.
  93  *
  94  * If no such object exists, the map should be "wrapped" using the
  95  * {@link Collections#synchronizedMap Collections.synchronizedMap}
  96  * method.  This is best done at creation time, to prevent accidental
  97  * unsynchronized access to the map:<pre>
  98  *   Map m = Collections.synchronizedMap(new IdentityHashMap(...));</pre>
  99  *
 100  * <p>The iterators returned by the {@code iterator} method of the
 101  * collections returned by all of this class's "collection view
 102  * methods" are <i>fail-fast</i>: if the map is structurally modified
 103  * at any time after the iterator is created, in any way except
 104  * through the iterator's own {@code remove} method, the iterator
 105  * will throw a {@link ConcurrentModificationException}.  Thus, in the
 106  * face of concurrent modification, the iterator fails quickly and
 107  * cleanly, rather than risking arbitrary, non-deterministic behavior
 108  * at an undetermined time in the future.
 109  *
 110  * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
 111  * as it is, generally speaking, impossible to make any hard guarantees in the
 112  * presence of unsynchronized concurrent modification.  Fail-fast iterators
 113  * throw {@code ConcurrentModificationException} on a best-effort basis.
 114  * Therefore, it would be wrong to write a program that depended on this
 115  * exception for its correctness: <i>fail-fast iterators should be used only
 116  * to detect bugs.</i>
 117  *
 118  * <p>Implementation note: This is a simple <i>linear-probe</i> hash table,
 119  * as described for example in texts by Sedgewick and Knuth.  The array
 120  * alternates holding keys and values.  (This has better locality for large
 121  * tables than does using separate arrays.)  For many JRE implementations
 122  * and operation mixes, this class will yield better performance than
 123  * {@link HashMap} (which uses <i>chaining</i> rather than linear-probing).
 124  *
 125  * <p>This class is a member of the
 126  * <a href="{@docRoot}/java.base/java/util/package-summary.html#CollectionsFramework">
 127  * Java Collections Framework</a>.
 128  *
 129  * @see     System#identityHashCode(Object)
 130  * @see     Object#hashCode()
 131  * @see     Collection
 132  * @see     Map
 133  * @see     HashMap
 134  * @see     TreeMap
 135  * @author  Doug Lea and Josh Bloch
 136  * @since   1.4
 137  */
 138 
 139 public class IdentityHashMap<K,V>
 140     extends AbstractMap<K,V>
 141     implements Map<K,V>, java.io.Serializable, Cloneable
 142 {
 143     /**
 144      * The initial capacity used by the no-args constructor.
 145      * MUST be a power of two.  The value 32 corresponds to the
 146      * (specified) expected maximum size of 21, given a load factor
 147      * of 2/3.
 148      */
 149     private static final int DEFAULT_CAPACITY = 32;
 150 
 151     /**
 152      * The minimum capacity, used if a lower value is implicitly specified
 153      * by either of the constructors with arguments.  The value 4 corresponds
 154      * to an expected maximum size of 2, given a load factor of 2/3.
 155      * MUST be a power of two.
 156      */
 157     private static final int MINIMUM_CAPACITY = 4;
 158 
 159     /**
 160      * The maximum capacity, used if a higher value is implicitly specified
 161      * by either of the constructors with arguments.
 162      * MUST be a power of two <= 1<<29.
 163      *
 164      * In fact, the map can hold no more than MAXIMUM_CAPACITY-1 items
 165      * because it has to have at least one slot with the key == null
 166      * in order to avoid infinite loops in get(), put(), remove()
 167      */
 168     private static final int MAXIMUM_CAPACITY = 1 << 29;
 169 
 170     /**
 171      * The table, resized as necessary. Length MUST always be a power of two.
 172      */
 173     transient Object[] table; // non-private to simplify nested class access
 174 
 175     /**
 176      * The number of key-value mappings contained in this identity hash map.
 177      *
 178      * @serial
 179      */
 180     int size;
 181 
 182     /**
 183      * The number of modifications, to support fast-fail iterators
 184      */
 185     transient int modCount;
 186 
 187     /**
 188      * Value representing null keys inside tables.
 189      */
 190     static final Object NULL_KEY = new Object();
 191 
 192     /**
 193      * Use NULL_KEY for key if it is null.
 194      */
 195     private static Object maskNull(Object key) {
 196         return (key == null ? NULL_KEY : key);
 197     }
 198 
 199     /**
 200      * Returns internal representation of null key back to caller as null.
 201      */
 202     static final Object unmaskNull(Object key) {
 203         return (key == NULL_KEY ? null : key);
 204     }
 205 
 206     /**
 207      * Constructs a new, empty identity hash map with a default expected
 208      * maximum size (21).
 209      */
 210     public IdentityHashMap() {
 211         init(DEFAULT_CAPACITY);
 212     }
 213 
 214     /**
 215      * Constructs a new, empty map with the specified expected maximum size.
 216      * Putting more than the expected number of key-value mappings into
 217      * the map may cause the internal data structure to grow, which may be
 218      * somewhat time-consuming.
 219      *
 220      * @param expectedMaxSize the expected maximum size of the map
 221      * @throws IllegalArgumentException if {@code expectedMaxSize} is negative
 222      */
 223     public IdentityHashMap(int expectedMaxSize) {
 224         if (expectedMaxSize < 0)
 225             throw new IllegalArgumentException("expectedMaxSize is negative: "
 226                                                + expectedMaxSize);
 227         init(capacity(expectedMaxSize));
 228     }
 229 
 230     /**
 231      * Returns the appropriate capacity for the given expected maximum size.
 232      * Returns the smallest power of two between MINIMUM_CAPACITY and
 233      * MAXIMUM_CAPACITY, inclusive, that is greater than (3 *
 234      * expectedMaxSize)/2, if such a number exists.  Otherwise returns
 235      * MAXIMUM_CAPACITY.
 236      */
 237     private static int capacity(int expectedMaxSize) {
 238         // assert expectedMaxSize >= 0;
 239         return
 240             (expectedMaxSize > MAXIMUM_CAPACITY / 3) ? MAXIMUM_CAPACITY :
 241             (expectedMaxSize <= 2 * MINIMUM_CAPACITY / 3) ? MINIMUM_CAPACITY :
 242             Integer.highestOneBit(expectedMaxSize + (expectedMaxSize << 1));
 243     }
 244 
 245     /**
 246      * Initializes object to be an empty map with the specified initial
 247      * capacity, which is assumed to be a power of two between
 248      * MINIMUM_CAPACITY and MAXIMUM_CAPACITY inclusive.
 249      */
 250     private void init(int initCapacity) {
 251         // assert (initCapacity & -initCapacity) == initCapacity; // power of 2
 252         // assert initCapacity >= MINIMUM_CAPACITY;
 253         // assert initCapacity <= MAXIMUM_CAPACITY;
 254 
 255         table = new Object[2 * initCapacity];
 256     }
 257 
 258     /**
 259      * Constructs a new identity hash map containing the keys-value mappings
 260      * in the specified map.
 261      *
 262      * @param m the map whose mappings are to be placed into this map
 263      * @throws NullPointerException if the specified map is null
 264      */
 265     public IdentityHashMap(Map<? extends K, ? extends V> m) {
 266         // Allow for a bit of growth
 267         this((int) ((1 + m.size()) * 1.1));
 268         putAll(m);
 269     }
 270 
 271     /**
 272      * Returns the number of key-value mappings in this identity hash map.
 273      *
 274      * @return the number of key-value mappings in this map
 275      */
 276     public int size() {
 277         return size;
 278     }
 279 
 280     /**
 281      * Returns {@code true} if this identity hash map contains no key-value
 282      * mappings.
 283      *
 284      * @return {@code true} if this identity hash map contains no key-value
 285      *         mappings
 286      */
 287     public boolean isEmpty() {
 288         return size == 0;
 289     }
 290 
 291     /**
 292      * Returns index for Object x.
 293      */
 294     private static int hash(Object x, int length) {
 295         int h = System.identityHashCode(x);
 296         // Multiply by -127, and left-shift to use least bit as part of hash
 297         return ((h << 1) - (h << 8)) & (length - 1);
 298     }
 299 
 300     /**
 301      * Circularly traverses table of size len.
 302      */
 303     private static int nextKeyIndex(int i, int len) {
 304         return (i + 2 < len ? i + 2 : 0);
 305     }
 306 
 307     /**
 308      * Returns the value to which the specified key is mapped,
 309      * or {@code null} if this map contains no mapping for the key.
 310      *
 311      * <p>More formally, if this map contains a mapping from a key
 312      * {@code k} to a value {@code v} such that {@code (key == k)},
 313      * then this method returns {@code v}; otherwise it returns
 314      * {@code null}.  (There can be at most one such mapping.)
 315      *
 316      * <p>A return value of {@code null} does not <i>necessarily</i>
 317      * indicate that the map contains no mapping for the key; it's also
 318      * possible that the map explicitly maps the key to {@code null}.
 319      * The {@link #containsKey containsKey} operation may be used to
 320      * distinguish these two cases.
 321      *
 322      * @see #put(Object, Object)
 323      */
 324     @SuppressWarnings("unchecked")
 325     public V get(Object key) {
 326         Object k = maskNull(key);
 327         Object[] tab = table;
 328         int len = tab.length;
 329         int i = hash(k, len);
 330         while (true) {
 331             Object item = tab[i];
 332             if (item == k)
 333                 return (V) tab[i + 1];
 334             if (item == null)
 335                 return null;
 336             i = nextKeyIndex(i, len);
 337         }
 338     }
 339 
 340     /**
 341      * Tests whether the specified object reference is a key in this identity
 342      * hash map.
 343      *
 344      * @param   key   possible key
 345      * @return  {@code true} if the specified object reference is a key
 346      *          in this map
 347      * @see     #containsValue(Object)
 348      */
 349     public boolean containsKey(Object key) {
 350         Object k = maskNull(key);
 351         Object[] tab = table;
 352         int len = tab.length;
 353         int i = hash(k, len);
 354         while (true) {
 355             Object item = tab[i];
 356             if (item == k)
 357                 return true;
 358             if (item == null)
 359                 return false;
 360             i = nextKeyIndex(i, len);
 361         }
 362     }
 363 
 364     /**
 365      * Tests whether the specified object reference is a value in this identity
 366      * hash map.
 367      *
 368      * @param value value whose presence in this map is to be tested
 369      * @return {@code true} if this map maps one or more keys to the
 370      *         specified object reference
 371      * @see     #containsKey(Object)
 372      */
 373     public boolean containsValue(Object value) {
 374         Object[] tab = table;
 375         for (int i = 1; i < tab.length; i += 2)
 376             if (tab[i] == value && tab[i - 1] != null)
 377                 return true;
 378 
 379         return false;
 380     }
 381 
 382     /**
 383      * Tests if the specified key-value mapping is in the map.
 384      *
 385      * @param   key   possible key
 386      * @param   value possible value
 387      * @return  {@code true} if and only if the specified key-value
 388      *          mapping is in the map
 389      */
 390     private boolean containsMapping(Object key, Object value) {
 391         Object k = maskNull(key);
 392         Object[] tab = table;
 393         int len = tab.length;
 394         int i = hash(k, len);
 395         while (true) {
 396             Object item = tab[i];
 397             if (item == k)
 398                 return tab[i + 1] == value;
 399             if (item == null)
 400                 return false;
 401             i = nextKeyIndex(i, len);
 402         }
 403     }
 404 
 405     /**
 406      * Associates the specified value with the specified key in this identity
 407      * hash map.  If the map previously contained a mapping for the key, the
 408      * old value is replaced.
 409      *
 410      * @param key the key with which the specified value is to be associated
 411      * @param value the value to be associated with the specified key
 412      * @return the previous value associated with {@code key}, or
 413      *         {@code null} if there was no mapping for {@code key}.
 414      *         (A {@code null} return can also indicate that the map
 415      *         previously associated {@code null} with {@code key}.)
 416      * @see     Object#equals(Object)
 417      * @see     #get(Object)
 418      * @see     #containsKey(Object)
 419      */
 420     public V put(K key, V value) {
 421         final Object k = maskNull(key);
 422 
 423         retryAfterResize: for (;;) {
 424             final Object[] tab = table;
 425             final int len = tab.length;
 426             int i = hash(k, len);
 427 
 428             for (Object item; (item = tab[i]) != null;
 429                  i = nextKeyIndex(i, len)) {
 430                 if (item == k) {
 431                     @SuppressWarnings("unchecked")
 432                         V oldValue = (V) tab[i + 1];
 433                     tab[i + 1] = value;
 434                     return oldValue;
 435                 }
 436             }
 437 
 438             final int s = size + 1;
 439             // Use optimized form of 3 * s.
 440             // Next capacity is len, 2 * current capacity.
 441             if (s + (s << 1) > len && resize(len))
 442                 continue retryAfterResize;
 443 
 444             modCount++;
 445             tab[i] = k;
 446             tab[i + 1] = value;
 447             size = s;
 448             return null;
 449         }
 450     }
 451 
 452     /**
 453      * Resizes the table if necessary to hold given capacity.
 454      *
 455      * @param newCapacity the new capacity, must be a power of two.
 456      * @return whether a resize did in fact take place
 457      */
 458     private boolean resize(int newCapacity) {
 459         // assert (newCapacity & -newCapacity) == newCapacity; // power of 2
 460         int newLength = newCapacity * 2;
 461 
 462         Object[] oldTable = table;
 463         int oldLength = oldTable.length;
 464         if (oldLength == 2 * MAXIMUM_CAPACITY) { // can't expand any further
 465             if (size == MAXIMUM_CAPACITY - 1)
 466                 throw new IllegalStateException("Capacity exhausted.");
 467             return false;
 468         }
 469         if (oldLength >= newLength)
 470             return false;
 471 
 472         Object[] newTable = new Object[newLength];
 473 
 474         for (int j = 0; j < oldLength; j += 2) {
 475             Object key = oldTable[j];
 476             if (key != null) {
 477                 Object value = oldTable[j+1];
 478                 oldTable[j] = null;
 479                 oldTable[j+1] = null;
 480                 int i = hash(key, newLength);
 481                 while (newTable[i] != null)
 482                     i = nextKeyIndex(i, newLength);
 483                 newTable[i] = key;
 484                 newTable[i + 1] = value;
 485             }
 486         }
 487         table = newTable;
 488         return true;
 489     }
 490 
 491     /**
 492      * Copies all of the mappings from the specified map to this map.
 493      * These mappings will replace any mappings that this map had for
 494      * any of the keys currently in the specified map.
 495      *
 496      * @param m mappings to be stored in this map
 497      * @throws NullPointerException if the specified map is null
 498      */
 499     public void putAll(Map<? extends K, ? extends V> m) {
 500         int n = m.size();
 501         if (n == 0)
 502             return;
 503         if (n > size)
 504             resize(capacity(n)); // conservatively pre-expand
 505 
 506         for (Entry<? extends K, ? extends V> e : m.entrySet())
 507             put(e.getKey(), e.getValue());
 508     }
 509 
 510     /**
 511      * Removes the mapping for this key from this map if present.
 512      *
 513      * @param key key whose mapping is to be removed from the map
 514      * @return the previous value associated with {@code key}, or
 515      *         {@code null} if there was no mapping for {@code key}.
 516      *         (A {@code null} return can also indicate that the map
 517      *         previously associated {@code null} with {@code key}.)
 518      */
 519     public V remove(Object key) {
 520         Object k = maskNull(key);
 521         Object[] tab = table;
 522         int len = tab.length;
 523         int i = hash(k, len);
 524 
 525         while (true) {
 526             Object item = tab[i];
 527             if (item == k) {
 528                 modCount++;
 529                 size--;
 530                 @SuppressWarnings("unchecked")
 531                     V oldValue = (V) tab[i + 1];
 532                 tab[i + 1] = null;
 533                 tab[i] = null;
 534                 closeDeletion(i);
 535                 return oldValue;
 536             }
 537             if (item == null)
 538                 return null;
 539             i = nextKeyIndex(i, len);
 540         }
 541     }
 542 
 543     /**
 544      * Removes the specified key-value mapping from the map if it is present.
 545      *
 546      * @param   key   possible key
 547      * @param   value possible value
 548      * @return  {@code true} if and only if the specified key-value
 549      *          mapping was in the map
 550      */
 551     private boolean removeMapping(Object key, Object value) {
 552         Object k = maskNull(key);
 553         Object[] tab = table;
 554         int len = tab.length;
 555         int i = hash(k, len);
 556 
 557         while (true) {
 558             Object item = tab[i];
 559             if (item == k) {
 560                 if (tab[i + 1] != value)
 561                     return false;
 562                 modCount++;
 563                 size--;
 564                 tab[i] = null;
 565                 tab[i + 1] = null;
 566                 closeDeletion(i);
 567                 return true;
 568             }
 569             if (item == null)
 570                 return false;
 571             i = nextKeyIndex(i, len);
 572         }
 573     }
 574 
 575     /**
 576      * Rehash all possibly-colliding entries following a
 577      * deletion. This preserves the linear-probe
 578      * collision properties required by get, put, etc.
 579      *
 580      * @param d the index of a newly empty deleted slot
 581      */
 582     private void closeDeletion(int d) {
 583         // Adapted from Knuth Section 6.4 Algorithm R
 584         Object[] tab = table;
 585         int len = tab.length;
 586 
 587         // Look for items to swap into newly vacated slot
 588         // starting at index immediately following deletion,
 589         // and continuing until a null slot is seen, indicating
 590         // the end of a run of possibly-colliding keys.
 591         Object item;
 592         for (int i = nextKeyIndex(d, len); (item = tab[i]) != null;
 593              i = nextKeyIndex(i, len) ) {
 594             // The following test triggers if the item at slot i (which
 595             // hashes to be at slot r) should take the spot vacated by d.
 596             // If so, we swap it in, and then continue with d now at the
 597             // newly vacated i.  This process will terminate when we hit
 598             // the null slot at the end of this run.
 599             // The test is messy because we are using a circular table.
 600             int r = hash(item, len);
 601             if ((i < r && (r <= d || d <= i)) || (r <= d && d <= i)) {
 602                 tab[d] = item;
 603                 tab[d + 1] = tab[i + 1];
 604                 tab[i] = null;
 605                 tab[i + 1] = null;
 606                 d = i;
 607             }
 608         }
 609     }
 610 
 611     /**
 612      * Removes all of the mappings from this map.
 613      * The map will be empty after this call returns.
 614      */
 615     public void clear() {
 616         modCount++;
 617         Object[] tab = table;
 618         for (int i = 0; i < tab.length; i++)
 619             tab[i] = null;
 620         size = 0;
 621     }
 622 
 623     /**
 624      * Compares the specified object with this map for equality.  Returns
 625      * {@code true} if the given object is also a map and the two maps
 626      * represent identical object-reference mappings.  More formally, this
 627      * map is equal to another map {@code m} if and only if
 628      * {@code this.entrySet().equals(m.entrySet())}.
 629      *
 630      * <p><b>Owing to the reference-equality-based semantics of this map it is
 631      * possible that the symmetry and transitivity requirements of the
 632      * {@code Object.equals} contract may be violated if this map is compared
 633      * to a normal map.  However, the {@code Object.equals} contract is
 634      * guaranteed to hold among {@code IdentityHashMap} instances.</b>
 635      *
 636      * @param  o object to be compared for equality with this map
 637      * @return {@code true} if the specified object is equal to this map
 638      * @see Object#equals(Object)
 639      */
 640     public boolean equals(Object o) {
 641         if (o == this) {
 642             return true;
 643         } else if (o instanceof IdentityHashMap) {
 644             IdentityHashMap<?,?> m = (IdentityHashMap<?,?>) o;
 645             if (m.size() != size)
 646                 return false;
 647 
 648             Object[] tab = m.table;
 649             for (int i = 0; i < tab.length; i+=2) {
 650                 Object k = tab[i];
 651                 if (k != null && !containsMapping(k, tab[i + 1]))
 652                     return false;
 653             }
 654             return true;
 655         } else if (o instanceof Map) {
 656             Map<?,?> m = (Map<?,?>)o;
 657             return entrySet().equals(m.entrySet());
 658         } else {
 659             return false;  // o is not a Map
 660         }
 661     }
 662 
 663     /**
 664      * Returns the hash code value for this map.  The hash code of a map is
 665      * defined to be the sum of the hash codes of each entry in the map's
 666      * {@code entrySet()} view.  This ensures that {@code m1.equals(m2)}
 667      * implies that {@code m1.hashCode()==m2.hashCode()} for any two
 668      * {@code IdentityHashMap} instances {@code m1} and {@code m2}, as
 669      * required by the general contract of {@link Object#hashCode}.
 670      *
 671      * <p><b>Owing to the reference-equality-based semantics of the
 672      * {@code Map.Entry} instances in the set returned by this map's
 673      * {@code entrySet} method, it is possible that the contractual
 674      * requirement of {@code Object.hashCode} mentioned in the previous
 675      * paragraph will be violated if one of the two objects being compared is
 676      * an {@code IdentityHashMap} instance and the other is a normal map.</b>
 677      *
 678      * @return the hash code value for this map
 679      * @see Object#equals(Object)
 680      * @see #equals(Object)
 681      */
 682     public int hashCode() {
 683         int result = 0;
 684         Object[] tab = table;
 685         for (int i = 0; i < tab.length; i +=2) {
 686             Object key = tab[i];
 687             if (key != null) {
 688                 Object k = unmaskNull(key);
 689                 result += System.identityHashCode(k) ^
 690                           System.identityHashCode(tab[i + 1]);
 691             }
 692         }
 693         return result;
 694     }
 695 
 696     /**
 697      * Returns a shallow copy of this identity hash map: the keys and values
 698      * themselves are not cloned.
 699      *
 700      * @return a shallow copy of this map
 701      */
 702     public Object clone() {
 703         try {
 704             IdentityHashMap<?,?> m = (IdentityHashMap<?,?>) super.clone();
 705             m.entrySet = null;
 706             m.table = table.clone();
 707             return m;
 708         } catch (CloneNotSupportedException e) {
 709             throw new InternalError(e);
 710         }
 711     }
 712 
 713     private abstract class IdentityHashMapIterator<T> implements Iterator<T> {
 714         int index = (size != 0 ? 0 : table.length); // current slot.
 715         int expectedModCount = modCount; // to support fast-fail
 716         int lastReturnedIndex = -1;      // to allow remove()
 717         boolean indexValid; // To avoid unnecessary next computation
 718         Object[] traversalTable = table; // reference to main table or copy
 719 
 720         public boolean hasNext() {
 721             Object[] tab = traversalTable;
 722             for (int i = index; i < tab.length; i+=2) {
 723                 Object key = tab[i];
 724                 if (key != null) {
 725                     index = i;
 726                     return indexValid = true;
 727                 }
 728             }
 729             index = tab.length;
 730             return false;
 731         }
 732 
 733         protected int nextIndex() {
 734             if (modCount != expectedModCount)
 735                 throw new ConcurrentModificationException();
 736             if (!indexValid && !hasNext())
 737                 throw new NoSuchElementException();
 738 
 739             indexValid = false;
 740             lastReturnedIndex = index;
 741             index += 2;
 742             return lastReturnedIndex;
 743         }
 744 
 745         public void remove() {
 746             if (lastReturnedIndex == -1)
 747                 throw new IllegalStateException();
 748             if (modCount != expectedModCount)
 749                 throw new ConcurrentModificationException();
 750 
 751             expectedModCount = ++modCount;
 752             int deletedSlot = lastReturnedIndex;
 753             lastReturnedIndex = -1;
 754             // back up index to revisit new contents after deletion
 755             index = deletedSlot;
 756             indexValid = false;
 757 
 758             // Removal code proceeds as in closeDeletion except that
 759             // it must catch the rare case where an element already
 760             // seen is swapped into a vacant slot that will be later
 761             // traversed by this iterator. We cannot allow future
 762             // next() calls to return it again.  The likelihood of
 763             // this occurring under 2/3 load factor is very slim, but
 764             // when it does happen, we must make a copy of the rest of
 765             // the table to use for the rest of the traversal. Since
 766             // this can only happen when we are near the end of the table,
 767             // even in these rare cases, this is not very expensive in
 768             // time or space.
 769 
 770             Object[] tab = traversalTable;
 771             int len = tab.length;
 772 
 773             int d = deletedSlot;
 774             Object key = tab[d];
 775             tab[d] = null;        // vacate the slot
 776             tab[d + 1] = null;
 777 
 778             // If traversing a copy, remove in real table.
 779             // We can skip gap-closure on copy.
 780             if (tab != IdentityHashMap.this.table) {
 781                 IdentityHashMap.this.remove(key);
 782                 expectedModCount = modCount;
 783                 return;
 784             }
 785 
 786             size--;
 787 
 788             Object item;
 789             for (int i = nextKeyIndex(d, len); (item = tab[i]) != null;
 790                  i = nextKeyIndex(i, len)) {
 791                 int r = hash(item, len);
 792                 // See closeDeletion for explanation of this conditional
 793                 if ((i < r && (r <= d || d <= i)) ||
 794                     (r <= d && d <= i)) {
 795 
 796                     // If we are about to swap an already-seen element
 797                     // into a slot that may later be returned by next(),
 798                     // then clone the rest of table for use in future
 799                     // next() calls. It is OK that our copy will have
 800                     // a gap in the "wrong" place, since it will never
 801                     // be used for searching anyway.
 802 
 803                     if (i < deletedSlot && d >= deletedSlot &&
 804                         traversalTable == IdentityHashMap.this.table) {
 805                         int remaining = len - deletedSlot;
 806                         Object[] newTable = new Object[remaining];
 807                         System.arraycopy(tab, deletedSlot,
 808                                          newTable, 0, remaining);
 809                         traversalTable = newTable;
 810                         index = 0;
 811                     }
 812 
 813                     tab[d] = item;
 814                     tab[d + 1] = tab[i + 1];
 815                     tab[i] = null;
 816                     tab[i + 1] = null;
 817                     d = i;
 818                 }
 819             }
 820         }
 821     }
 822 
 823     private class KeyIterator extends IdentityHashMapIterator<K> {
 824         @SuppressWarnings("unchecked")
 825         public K next() {
 826             return (K) unmaskNull(traversalTable[nextIndex()]);
 827         }
 828     }
 829 
 830     private class ValueIterator extends IdentityHashMapIterator<V> {
 831         @SuppressWarnings("unchecked")
 832         public V next() {
 833             return (V) traversalTable[nextIndex() + 1];
 834         }
 835     }
 836 
 837     private class EntryIterator
 838         extends IdentityHashMapIterator<Map.Entry<K,V>>
 839     {
 840         private Entry lastReturnedEntry;
 841 
 842         public Map.Entry<K,V> next() {
 843             lastReturnedEntry = new Entry(nextIndex());
 844             return lastReturnedEntry;
 845         }
 846 
 847         public void remove() {
 848             lastReturnedIndex =
 849                 ((null == lastReturnedEntry) ? -1 : lastReturnedEntry.index);
 850             super.remove();
 851             lastReturnedEntry.index = lastReturnedIndex;
 852             lastReturnedEntry = null;
 853         }
 854 
 855         private class Entry implements Map.Entry<K,V> {
 856             private int index;
 857 
 858             private Entry(int index) {
 859                 this.index = index;
 860             }
 861 
 862             @SuppressWarnings("unchecked")
 863             public K getKey() {
 864                 checkIndexForEntryUse();
 865                 return (K) unmaskNull(traversalTable[index]);
 866             }
 867 
 868             @SuppressWarnings("unchecked")
 869             public V getValue() {
 870                 checkIndexForEntryUse();
 871                 return (V) traversalTable[index+1];
 872             }
 873 
 874             @SuppressWarnings("unchecked")
 875             public V setValue(V value) {
 876                 checkIndexForEntryUse();
 877                 V oldValue = (V) traversalTable[index+1];
 878                 traversalTable[index+1] = value;
 879                 // if shadowing, force into main table
 880                 if (traversalTable != IdentityHashMap.this.table)
 881                     put((K) traversalTable[index], value);
 882                 return oldValue;
 883             }
 884 
 885             public boolean equals(Object o) {
 886                 if (index < 0)
 887                     return super.equals(o);
 888 
 889                 if (!(o instanceof Map.Entry))
 890                     return false;
 891                 Map.Entry<?,?> e = (Map.Entry<?,?>)o;
 892                 return (e.getKey() == unmaskNull(traversalTable[index]) &&
 893                        e.getValue() == traversalTable[index+1]);
 894             }
 895 
 896             public int hashCode() {
 897                 if (lastReturnedIndex < 0)
 898                     return super.hashCode();
 899 
 900                 return (System.identityHashCode(unmaskNull(traversalTable[index])) ^
 901                        System.identityHashCode(traversalTable[index+1]));
 902             }
 903 
 904             public String toString() {
 905                 if (index < 0)
 906                     return super.toString();
 907 
 908                 return (unmaskNull(traversalTable[index]) + "="
 909                         + traversalTable[index+1]);
 910             }
 911 
 912             private void checkIndexForEntryUse() {
 913                 if (index < 0)
 914                     throw new IllegalStateException("Entry was removed");
 915             }
 916         }
 917     }
 918 
 919     // Views
 920 
 921     /**
 922      * This field is initialized to contain an instance of the entry set
 923      * view the first time this view is requested.  The view is stateless,
 924      * so there's no reason to create more than one.
 925      */
 926     private transient Set<Map.Entry<K,V>> entrySet;
 927 
 928     /**
 929      * Returns an identity-based set view of the keys contained in this map.
 930      * The set is backed by the map, so changes to the map are reflected in
 931      * the set, and vice-versa.  If the map is modified while an iteration
 932      * over the set is in progress, the results of the iteration are
 933      * undefined.  The set supports element removal, which removes the
 934      * corresponding mapping from the map, via the {@code Iterator.remove},
 935      * {@code Set.remove}, {@code removeAll}, {@code retainAll}, and
 936      * {@code clear} methods.  It does not support the {@code add} or
 937      * {@code addAll} methods.
 938      *
 939      * <p><b>While the object returned by this method implements the
 940      * {@code Set} interface, it does <i>not</i> obey {@code Set's} general
 941      * contract.  Like its backing map, the set returned by this method
 942      * defines element equality as reference-equality rather than
 943      * object-equality.  This affects the behavior of its {@code contains},
 944      * {@code remove}, {@code containsAll}, {@code equals}, and
 945      * {@code hashCode} methods.</b>
 946      *
 947      * <p><b>The {@code equals} method of the returned set returns {@code true}
 948      * only if the specified object is a set containing exactly the same
 949      * object references as the returned set.  The symmetry and transitivity
 950      * requirements of the {@code Object.equals} contract may be violated if
 951      * the set returned by this method is compared to a normal set.  However,
 952      * the {@code Object.equals} contract is guaranteed to hold among sets
 953      * returned by this method.</b>
 954      *
 955      * <p>The {@code hashCode} method of the returned set returns the sum of
 956      * the <i>identity hashcodes</i> of the elements in the set, rather than
 957      * the sum of their hashcodes.  This is mandated by the change in the
 958      * semantics of the {@code equals} method, in order to enforce the
 959      * general contract of the {@code Object.hashCode} method among sets
 960      * returned by this method.
 961      *
 962      * @return an identity-based set view of the keys contained in this map
 963      * @see Object#equals(Object)
 964      * @see System#identityHashCode(Object)
 965      */
 966     public Set<K> keySet() {
 967         Set<K> ks = keySet;
 968         if (ks == null) {
 969             ks = new KeySet();
 970             keySet = ks;
 971         }
 972         return ks;
 973     }
 974 
 975     private class KeySet extends AbstractSet<K> {
 976         public Iterator<K> iterator() {
 977             return new KeyIterator();
 978         }
 979         public int size() {
 980             return size;
 981         }
 982         public boolean contains(Object o) {
 983             return containsKey(o);
 984         }
 985         public boolean remove(Object o) {
 986             int oldSize = size;
 987             IdentityHashMap.this.remove(o);
 988             return size != oldSize;
 989         }
 990         /*
 991          * Must revert from AbstractSet's impl to AbstractCollection's, as
 992          * the former contains an optimization that results in incorrect
 993          * behavior when c is a smaller "normal" (non-identity-based) Set.
 994          */
 995         public boolean removeAll(Collection<?> c) {
 996             Objects.requireNonNull(c);
 997             boolean modified = false;
 998             for (Iterator<K> i = iterator(); i.hasNext(); ) {
 999                 if (c.contains(i.next())) {
1000                     i.remove();
1001                     modified = true;
1002                 }
1003             }
1004             return modified;
1005         }
1006         public void clear() {
1007             IdentityHashMap.this.clear();
1008         }
1009         public int hashCode() {
1010             int result = 0;
1011             for (K key : this)
1012                 result += System.identityHashCode(key);
1013             return result;
1014         }
1015         public Object[] toArray() {
1016             return toArray(new Object[0]);
1017         }
1018         @SuppressWarnings("unchecked")
1019         public <T> T[] toArray(T[] a) {
1020             int expectedModCount = modCount;
1021             int size = size();
1022             if (a.length < size)
1023                 a = (T[]) Array.newInstance(a.getClass().getComponentType(), size);
1024             Object[] tab = table;
1025             int ti = 0;
1026             for (int si = 0; si < tab.length; si += 2) {
1027                 Object key;
1028                 if ((key = tab[si]) != null) { // key present ?
1029                     // more elements than expected -> concurrent modification from other thread
1030                     if (ti >= size) {
1031                         throw new ConcurrentModificationException();
1032                     }
1033                     a[ti++] = (T) unmaskNull(key); // unmask key
1034                 }
1035             }
1036             // fewer elements than expected or concurrent modification from other thread detected
1037             if (ti < size || expectedModCount != modCount) {
1038                 throw new ConcurrentModificationException();
1039             }
1040             // final null marker as per spec
1041             if (ti < a.length) {
1042                 a[ti] = null;
1043             }
1044             return a;
1045         }
1046 
1047         public Spliterator<K> spliterator() {
1048             return new KeySpliterator<>(IdentityHashMap.this, 0, -1, 0, 0);
1049         }
1050     }
1051 
1052     /**
1053      * Returns a {@link Collection} view of the values contained in this map.
1054      * The collection is backed by the map, so changes to the map are
1055      * reflected in the collection, and vice-versa.  If the map is
1056      * modified while an iteration over the collection is in progress,
1057      * the results of the iteration are undefined.  The collection
1058      * supports element removal, which removes the corresponding
1059      * mapping from the map, via the {@code Iterator.remove},
1060      * {@code Collection.remove}, {@code removeAll},
1061      * {@code retainAll} and {@code clear} methods.  It does not
1062      * support the {@code add} or {@code addAll} methods.
1063      *
1064      * <p><b>While the object returned by this method implements the
1065      * {@code Collection} interface, it does <i>not</i> obey
1066      * {@code Collection's} general contract.  Like its backing map,
1067      * the collection returned by this method defines element equality as
1068      * reference-equality rather than object-equality.  This affects the
1069      * behavior of its {@code contains}, {@code remove} and
1070      * {@code containsAll} methods.</b>
1071      */
1072     public Collection<V> values() {
1073         Collection<V> vs = values;
1074         if (vs == null) {
1075             vs = new Values();
1076             values = vs;
1077         }
1078         return vs;
1079     }
1080 
1081     private class Values extends AbstractCollection<V> {
1082         public Iterator<V> iterator() {
1083             return new ValueIterator();
1084         }
1085         public int size() {
1086             return size;
1087         }
1088         public boolean contains(Object o) {
1089             return containsValue(o);
1090         }
1091         public boolean remove(Object o) {
1092             for (Iterator<V> i = iterator(); i.hasNext(); ) {
1093                 if (i.next() == o) {
1094                     i.remove();
1095                     return true;
1096                 }
1097             }
1098             return false;
1099         }
1100         public void clear() {
1101             IdentityHashMap.this.clear();
1102         }
1103         public Object[] toArray() {
1104             return toArray(new Object[0]);
1105         }
1106         @SuppressWarnings("unchecked")
1107         public <T> T[] toArray(T[] a) {
1108             int expectedModCount = modCount;
1109             int size = size();
1110             if (a.length < size)
1111                 a = (T[]) Array.newInstance(a.getClass().getComponentType(), size);
1112             Object[] tab = table;
1113             int ti = 0;
1114             for (int si = 0; si < tab.length; si += 2) {
1115                 if (tab[si] != null) { // key present ?
1116                     // more elements than expected -> concurrent modification from other thread
1117                     if (ti >= size) {
1118                         throw new ConcurrentModificationException();
1119                     }
1120                     a[ti++] = (T) tab[si+1]; // copy value
1121                 }
1122             }
1123             // fewer elements than expected or concurrent modification from other thread detected
1124             if (ti < size || expectedModCount != modCount) {
1125                 throw new ConcurrentModificationException();
1126             }
1127             // final null marker as per spec
1128             if (ti < a.length) {
1129                 a[ti] = null;
1130             }
1131             return a;
1132         }
1133 
1134         public Spliterator<V> spliterator() {
1135             return new ValueSpliterator<>(IdentityHashMap.this, 0, -1, 0, 0);
1136         }
1137     }
1138 
1139     /**
1140      * Returns a {@link Set} view of the mappings contained in this map.
1141      * Each element in the returned set is a reference-equality-based
1142      * {@code Map.Entry}.  The set is backed by the map, so changes
1143      * to the map are reflected in the set, and vice-versa.  If the
1144      * map is modified while an iteration over the set is in progress,
1145      * the results of the iteration are undefined.  The set supports
1146      * element removal, which removes the corresponding mapping from
1147      * the map, via the {@code Iterator.remove}, {@code Set.remove},
1148      * {@code removeAll}, {@code retainAll} and {@code clear}
1149      * methods.  It does not support the {@code add} or
1150      * {@code addAll} methods.
1151      *
1152      * <p>Like the backing map, the {@code Map.Entry} objects in the set
1153      * returned by this method define key and value equality as
1154      * reference-equality rather than object-equality.  This affects the
1155      * behavior of the {@code equals} and {@code hashCode} methods of these
1156      * {@code Map.Entry} objects.  A reference-equality based {@code Map.Entry
1157      * e} is equal to an object {@code o} if and only if {@code o} is a
1158      * {@code Map.Entry} and {@code e.getKey()==o.getKey() &&
1159      * e.getValue()==o.getValue()}.  To accommodate these equals
1160      * semantics, the {@code hashCode} method returns
1161      * {@code System.identityHashCode(e.getKey()) ^
1162      * System.identityHashCode(e.getValue())}.
1163      *
1164      * <p><b>Owing to the reference-equality-based semantics of the
1165      * {@code Map.Entry} instances in the set returned by this method,
1166      * it is possible that the symmetry and transitivity requirements of
1167      * the {@link Object#equals(Object)} contract may be violated if any of
1168      * the entries in the set is compared to a normal map entry, or if
1169      * the set returned by this method is compared to a set of normal map
1170      * entries (such as would be returned by a call to this method on a normal
1171      * map).  However, the {@code Object.equals} contract is guaranteed to
1172      * hold among identity-based map entries, and among sets of such entries.
1173      * </b>
1174      *
1175      * @return a set view of the identity-mappings contained in this map
1176      */
1177     public Set<Map.Entry<K,V>> entrySet() {
1178         Set<Map.Entry<K,V>> es = entrySet;
1179         if (es != null)
1180             return es;
1181         else
1182             return entrySet = new EntrySet();
1183     }
1184 
1185     private class EntrySet extends AbstractSet<Map.Entry<K,V>> {
1186         public Iterator<Map.Entry<K,V>> iterator() {
1187             return new EntryIterator();
1188         }
1189         public boolean contains(Object o) {
1190             if (!(o instanceof Map.Entry))
1191                 return false;
1192             Map.Entry<?,?> entry = (Map.Entry<?,?>)o;
1193             return containsMapping(entry.getKey(), entry.getValue());
1194         }
1195         public boolean remove(Object o) {
1196             if (!(o instanceof Map.Entry))
1197                 return false;
1198             Map.Entry<?,?> entry = (Map.Entry<?,?>)o;
1199             return removeMapping(entry.getKey(), entry.getValue());
1200         }
1201         public int size() {
1202             return size;
1203         }
1204         public void clear() {
1205             IdentityHashMap.this.clear();
1206         }
1207         /*
1208          * Must revert from AbstractSet's impl to AbstractCollection's, as
1209          * the former contains an optimization that results in incorrect
1210          * behavior when c is a smaller "normal" (non-identity-based) Set.
1211          */
1212         public boolean removeAll(Collection<?> c) {
1213             Objects.requireNonNull(c);
1214             boolean modified = false;
1215             for (Iterator<Map.Entry<K,V>> i = iterator(); i.hasNext(); ) {
1216                 if (c.contains(i.next())) {
1217                     i.remove();
1218                     modified = true;
1219                 }
1220             }
1221             return modified;
1222         }
1223 
1224         public Object[] toArray() {
1225             return toArray(new Object[0]);
1226         }
1227 
1228         @SuppressWarnings("unchecked")
1229         public <T> T[] toArray(T[] a) {
1230             int expectedModCount = modCount;
1231             int size = size();
1232             if (a.length < size)
1233                 a = (T[]) Array.newInstance(a.getClass().getComponentType(), size);
1234             Object[] tab = table;
1235             int ti = 0;
1236             for (int si = 0; si < tab.length; si += 2) {
1237                 Object key;
1238                 if ((key = tab[si]) != null) { // key present ?
1239                     // more elements than expected -> concurrent modification from other thread
1240                     if (ti >= size) {
1241                         throw new ConcurrentModificationException();
1242                     }
1243                     a[ti++] = (T) new AbstractMap.SimpleEntry<>(unmaskNull(key), tab[si + 1]);
1244                 }
1245             }
1246             // fewer elements than expected or concurrent modification from other thread detected
1247             if (ti < size || expectedModCount != modCount) {
1248                 throw new ConcurrentModificationException();
1249             }
1250             // final null marker as per spec
1251             if (ti < a.length) {
1252                 a[ti] = null;
1253             }
1254             return a;
1255         }
1256 
1257         public Spliterator<Map.Entry<K,V>> spliterator() {
1258             return new EntrySpliterator<>(IdentityHashMap.this, 0, -1, 0, 0);
1259         }
1260     }
1261 
1262 
1263     private static final long serialVersionUID = 8188218128353913216L;
1264 
1265     /**
1266      * Saves the state of the {@code IdentityHashMap} instance to a stream
1267      * (i.e., serializes it).
1268      *
1269      * @serialData The <i>size</i> of the HashMap (the number of key-value
1270      *          mappings) ({@code int}), followed by the key (Object) and
1271      *          value (Object) for each key-value mapping represented by the
1272      *          IdentityHashMap.  The key-value mappings are emitted in no
1273      *          particular order.
1274      */
1275     private void writeObject(java.io.ObjectOutputStream s)
1276         throws java.io.IOException  {
1277         // Write out and any hidden stuff
1278         s.defaultWriteObject();
1279 
1280         // Write out size (number of Mappings)
1281         s.writeInt(size);
1282 
1283         // Write out keys and values (alternating)
1284         Object[] tab = table;
1285         for (int i = 0; i < tab.length; i += 2) {
1286             Object key = tab[i];
1287             if (key != null) {
1288                 s.writeObject(unmaskNull(key));
1289                 s.writeObject(tab[i + 1]);
1290             }
1291         }
1292     }
1293 
1294     /**
1295      * Reconstitutes the {@code IdentityHashMap} instance from a stream (i.e.,
1296      * deserializes it).
1297      */
1298     private void readObject(java.io.ObjectInputStream s)
1299         throws java.io.IOException, ClassNotFoundException  {
1300         // Read in any hidden stuff
1301         s.defaultReadObject();
1302 
1303         // Read in size (number of Mappings)
1304         int size = s.readInt();
1305         if (size < 0)
1306             throw new java.io.StreamCorruptedException
1307                 ("Illegal mappings count: " + size);
1308         int cap = capacity(size);
1309         SharedSecrets.getJavaObjectInputStreamAccess().checkArray(s, Object[].class, cap);
1310         init(cap);
1311 
1312         // Read the keys and values, and put the mappings in the table
1313         for (int i=0; i<size; i++) {
1314             @SuppressWarnings("unchecked")
1315                 K key = (K) s.readObject();
1316             @SuppressWarnings("unchecked")
1317                 V value = (V) s.readObject();
1318             putForCreate(key, value);
1319         }
1320     }
1321 
1322     /**
1323      * The put method for readObject.  It does not resize the table,
1324      * update modCount, etc.
1325      */
1326     private void putForCreate(K key, V value)
1327         throws java.io.StreamCorruptedException
1328     {
1329         Object k = maskNull(key);
1330         Object[] tab = table;
1331         int len = tab.length;
1332         int i = hash(k, len);
1333 
1334         Object item;
1335         while ( (item = tab[i]) != null) {
1336             if (item == k)
1337                 throw new java.io.StreamCorruptedException();
1338             i = nextKeyIndex(i, len);
1339         }
1340         tab[i] = k;
1341         tab[i + 1] = value;
1342     }
1343 
1344     @SuppressWarnings("unchecked")
1345     @Override
1346     public void forEach(BiConsumer<? super K, ? super V> action) {
1347         Objects.requireNonNull(action);
1348         int expectedModCount = modCount;
1349 
1350         Object[] t = table;
1351         for (int index = 0; index < t.length; index += 2) {
1352             Object k = t[index];
1353             if (k != null) {
1354                 action.accept((K) unmaskNull(k), (V) t[index + 1]);
1355             }
1356 
1357             if (modCount != expectedModCount) {
1358                 throw new ConcurrentModificationException();
1359             }
1360         }
1361     }
1362 
1363     @SuppressWarnings("unchecked")
1364     @Override
1365     public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
1366         Objects.requireNonNull(function);
1367         int expectedModCount = modCount;
1368 
1369         Object[] t = table;
1370         for (int index = 0; index < t.length; index += 2) {
1371             Object k = t[index];
1372             if (k != null) {
1373                 t[index + 1] = function.apply((K) unmaskNull(k), (V) t[index + 1]);
1374             }
1375 
1376             if (modCount != expectedModCount) {
1377                 throw new ConcurrentModificationException();
1378             }
1379         }
1380     }
1381 
1382     /**
1383      * Similar form as array-based Spliterators, but skips blank elements,
1384      * and guestimates size as decreasing by half per split.
1385      */
1386     static class IdentityHashMapSpliterator<K,V> {
1387         final IdentityHashMap<K,V> map;
1388         int index;             // current index, modified on advance/split
1389         int fence;             // -1 until first use; then one past last index
1390         int est;               // size estimate
1391         int expectedModCount;  // initialized when fence set
1392 
1393         IdentityHashMapSpliterator(IdentityHashMap<K,V> map, int origin,
1394                                    int fence, int est, int expectedModCount) {
1395             this.map = map;
1396             this.index = origin;
1397             this.fence = fence;
1398             this.est = est;
1399             this.expectedModCount = expectedModCount;
1400         }
1401 
1402         final int getFence() { // initialize fence and size on first use
1403             int hi;
1404             if ((hi = fence) < 0) {
1405                 est = map.size;
1406                 expectedModCount = map.modCount;
1407                 hi = fence = map.table.length;
1408             }
1409             return hi;
1410         }
1411 
1412         public final long estimateSize() {
1413             getFence(); // force init
1414             return (long) est;
1415         }
1416     }
1417 
1418     static final class KeySpliterator<K,V>
1419         extends IdentityHashMapSpliterator<K,V>
1420         implements Spliterator<K> {
1421         KeySpliterator(IdentityHashMap<K,V> map, int origin, int fence, int est,
1422                        int expectedModCount) {
1423             super(map, origin, fence, est, expectedModCount);
1424         }
1425 
1426         public KeySpliterator<K,V> trySplit() {
1427             int hi = getFence(), lo = index, mid = ((lo + hi) >>> 1) & ~1;
1428             return (lo >= mid) ? null :
1429                 new KeySpliterator<>(map, lo, index = mid, est >>>= 1,
1430                                      expectedModCount);
1431         }
1432 
1433         @SuppressWarnings("unchecked")
1434         public void forEachRemaining(Consumer<? super K> action) {
1435             if (action == null)
1436                 throw new NullPointerException();
1437             int i, hi, mc; Object key;
1438             IdentityHashMap<K,V> m; Object[] a;
1439             if ((m = map) != null && (a = m.table) != null &&
1440                 (i = index) >= 0 && (index = hi = getFence()) <= a.length) {
1441                 for (; i < hi; i += 2) {
1442                     if ((key = a[i]) != null)
1443                         action.accept((K)unmaskNull(key));
1444                 }
1445                 if (m.modCount == expectedModCount)
1446                     return;
1447             }
1448             throw new ConcurrentModificationException();
1449         }
1450 
1451         @SuppressWarnings("unchecked")
1452         public boolean tryAdvance(Consumer<? super K> action) {
1453             if (action == null)
1454                 throw new NullPointerException();
1455             Object[] a = map.table;
1456             int hi = getFence();
1457             while (index < hi) {
1458                 Object key = a[index];
1459                 index += 2;
1460                 if (key != null) {
1461                     action.accept((K)unmaskNull(key));
1462                     if (map.modCount != expectedModCount)
1463                         throw new ConcurrentModificationException();
1464                     return true;
1465                 }
1466             }
1467             return false;
1468         }
1469 
1470         public int characteristics() {
1471             return (fence < 0 || est == map.size ? SIZED : 0) | Spliterator.DISTINCT;
1472         }
1473     }
1474 
1475     static final class ValueSpliterator<K,V>
1476         extends IdentityHashMapSpliterator<K,V>
1477         implements Spliterator<V> {
1478         ValueSpliterator(IdentityHashMap<K,V> m, int origin, int fence, int est,
1479                          int expectedModCount) {
1480             super(m, origin, fence, est, expectedModCount);
1481         }
1482 
1483         public ValueSpliterator<K,V> trySplit() {
1484             int hi = getFence(), lo = index, mid = ((lo + hi) >>> 1) & ~1;
1485             return (lo >= mid) ? null :
1486                 new ValueSpliterator<>(map, lo, index = mid, est >>>= 1,
1487                                        expectedModCount);
1488         }
1489 
1490         public void forEachRemaining(Consumer<? super V> action) {
1491             if (action == null)
1492                 throw new NullPointerException();
1493             int i, hi, mc;
1494             IdentityHashMap<K,V> m; Object[] a;
1495             if ((m = map) != null && (a = m.table) != null &&
1496                 (i = index) >= 0 && (index = hi = getFence()) <= a.length) {
1497                 for (; i < hi; i += 2) {
1498                     if (a[i] != null) {
1499                         @SuppressWarnings("unchecked") V v = (V)a[i+1];
1500                         action.accept(v);
1501                     }
1502                 }
1503                 if (m.modCount == expectedModCount)
1504                     return;
1505             }
1506             throw new ConcurrentModificationException();
1507         }
1508 
1509         public boolean tryAdvance(Consumer<? super V> action) {
1510             if (action == null)
1511                 throw new NullPointerException();
1512             Object[] a = map.table;
1513             int hi = getFence();
1514             while (index < hi) {
1515                 Object key = a[index];
1516                 @SuppressWarnings("unchecked") V v = (V)a[index+1];
1517                 index += 2;
1518                 if (key != null) {
1519                     action.accept(v);
1520                     if (map.modCount != expectedModCount)
1521                         throw new ConcurrentModificationException();
1522                     return true;
1523                 }
1524             }
1525             return false;
1526         }
1527 
1528         public int characteristics() {
1529             return (fence < 0 || est == map.size ? SIZED : 0);
1530         }
1531 
1532     }
1533 
1534     static final class EntrySpliterator<K,V>
1535         extends IdentityHashMapSpliterator<K,V>
1536         implements Spliterator<Map.Entry<K,V>> {
1537         EntrySpliterator(IdentityHashMap<K,V> m, int origin, int fence, int est,
1538                          int expectedModCount) {
1539             super(m, origin, fence, est, expectedModCount);
1540         }
1541 
1542         public EntrySpliterator<K,V> trySplit() {
1543             int hi = getFence(), lo = index, mid = ((lo + hi) >>> 1) & ~1;
1544             return (lo >= mid) ? null :
1545                 new EntrySpliterator<>(map, lo, index = mid, est >>>= 1,
1546                                        expectedModCount);
1547         }
1548 
1549         public void forEachRemaining(Consumer<? super Map.Entry<K, V>> action) {
1550             if (action == null)
1551                 throw new NullPointerException();
1552             int i, hi, mc;
1553             IdentityHashMap<K,V> m; Object[] a;
1554             if ((m = map) != null && (a = m.table) != null &&
1555                 (i = index) >= 0 && (index = hi = getFence()) <= a.length) {
1556                 for (; i < hi; i += 2) {
1557                     Object key = a[i];
1558                     if (key != null) {
1559                         @SuppressWarnings("unchecked") K k =
1560                             (K)unmaskNull(key);
1561                         @SuppressWarnings("unchecked") V v = (V)a[i+1];
1562                         action.accept
1563                             (new AbstractMap.SimpleImmutableEntry<>(k, v));
1564 
1565                     }
1566                 }
1567                 if (m.modCount == expectedModCount)
1568                     return;
1569             }
1570             throw new ConcurrentModificationException();
1571         }
1572 
1573         public boolean tryAdvance(Consumer<? super Map.Entry<K,V>> action) {
1574             if (action == null)
1575                 throw new NullPointerException();
1576             Object[] a = map.table;
1577             int hi = getFence();
1578             while (index < hi) {
1579                 Object key = a[index];
1580                 @SuppressWarnings("unchecked") V v = (V)a[index+1];
1581                 index += 2;
1582                 if (key != null) {
1583                     @SuppressWarnings("unchecked") K k =
1584                         (K)unmaskNull(key);
1585                     action.accept
1586                         (new AbstractMap.SimpleImmutableEntry<>(k, v));
1587                     if (map.modCount != expectedModCount)
1588                         throw new ConcurrentModificationException();
1589                     return true;
1590                 }
1591             }
1592             return false;
1593         }
1594 
1595         public int characteristics() {
1596             return (fence < 0 || est == map.size ? SIZED : 0) | Spliterator.DISTINCT;
1597         }
1598     }
1599 
1600 }