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