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             boolean modified = false;
1001             for (Iterator<K> i = iterator(); i.hasNext(); ) {
1002                 if (c.contains(i.next())) {
1003                     i.remove();
1004                     modified = true;
1005                 }
1006             }
1007             return modified;
1008         }
1009         public void clear() {
1010             IdentityHashMap.this.clear();
1011         }
1012         public int hashCode() {
1013             int result = 0;
1014             for (K key : this)
1015                 result += System.identityHashCode(key);
1016             return result;
1017         }
1018         public Object[] toArray() {
1019             return toArray(new Object[0]);
1020         }
1021         @SuppressWarnings("unchecked")
1022         public <T> T[] toArray(T[] a) {
1023             int expectedModCount = modCount;
1024             int size = size();
1025             if (a.length < size)
1026                 a = (T[]) Array.newInstance(a.getClass().getComponentType(), size);
1027             Object[] tab = table;
1028             int ti = 0;
1029             for (int si = 0; si < tab.length; si += 2) {
1030                 Object key;
1031                 if ((key = tab[si]) != null) { // key present ?
1032                     // more elements than expected -> concurrent modification from other thread
1033                     if (ti >= size) {
1034                         throw new ConcurrentModificationException();
1035                     }
1036                     a[ti++] = (T) unmaskNull(key); // unmask key
1037                 }
1038             }
1039             // fewer elements than expected or concurrent modification from other thread detected
1040             if (ti < size || expectedModCount != modCount) {
1041                 throw new ConcurrentModificationException();
1042             }
1043             // final null marker as per spec
1044             if (ti < a.length) {
1045                 a[ti] = null;
1046             }
1047             return a;
1048         }
1049 
1050         public Spliterator<K> spliterator() {
1051             return new KeySpliterator<>(IdentityHashMap.this, 0, -1, 0, 0);
1052         }
1053     }
1054 
1055     /**
1056      * Returns a {@link Collection} view of the values contained in this map.
1057      * The collection is backed by the map, so changes to the map are
1058      * reflected in the collection, and vice-versa.  If the map is
1059      * modified while an iteration over the collection is in progress,
1060      * the results of the iteration are undefined.  The collection
1061      * supports element removal, which removes the corresponding
1062      * mapping from the map, via the <tt>Iterator.remove</tt>,
1063      * <tt>Collection.remove</tt>, <tt>removeAll</tt>,
1064      * <tt>retainAll</tt> and <tt>clear</tt> methods.  It does not
1065      * support the <tt>add</tt> or <tt>addAll</tt> methods.
1066      *
1067      * <p><b>While the object returned by this method implements the
1068      * <tt>Collection</tt> interface, it does <i>not</i> obey
1069      * <tt>Collection's</tt> general contract.  Like its backing map,
1070      * the collection returned by this method defines element equality as
1071      * reference-equality rather than object-equality.  This affects the
1072      * behavior of its <tt>contains</tt>, <tt>remove</tt> and
1073      * <tt>containsAll</tt> methods.</b>
1074      */
1075     public Collection<V> values() {
1076         Collection<V> vs = values;
1077         if (vs != null)
1078             return vs;
1079         else
1080             return values = new Values();
1081     }
1082 
1083     private class Values extends AbstractCollection<V> {
1084         public Iterator<V> iterator() {
1085             return new ValueIterator();
1086         }
1087         public int size() {
1088             return size;
1089         }
1090         public boolean contains(Object o) {
1091             return containsValue(o);
1092         }
1093         public boolean remove(Object o) {
1094             for (Iterator<V> i = iterator(); i.hasNext(); ) {
1095                 if (i.next() == o) {
1096                     i.remove();
1097                     return true;
1098                 }
1099             }
1100             return false;
1101         }
1102         public void clear() {
1103             IdentityHashMap.this.clear();
1104         }
1105         public Object[] toArray() {
1106             return toArray(new Object[0]);
1107         }
1108         @SuppressWarnings("unchecked")
1109         public <T> T[] toArray(T[] a) {
1110             int expectedModCount = modCount;
1111             int size = size();
1112             if (a.length < size)
1113                 a = (T[]) Array.newInstance(a.getClass().getComponentType(), size);
1114             Object[] tab = table;
1115             int ti = 0;
1116             for (int si = 0; si < tab.length; si += 2) {
1117                 if (tab[si] != null) { // key present ?
1118                     // more elements than expected -> concurrent modification from other thread
1119                     if (ti >= size) {
1120                         throw new ConcurrentModificationException();
1121                     }
1122                     a[ti++] = (T) tab[si+1]; // copy value
1123                 }
1124             }
1125             // fewer elements than expected or concurrent modification from other thread detected
1126             if (ti < size || expectedModCount != modCount) {
1127                 throw new ConcurrentModificationException();
1128             }
1129             // final null marker as per spec
1130             if (ti < a.length) {
1131                 a[ti] = null;
1132             }
1133             return a;
1134         }
1135 
1136         public Spliterator<V> spliterator() {
1137             return new ValueSpliterator<>(IdentityHashMap.this, 0, -1, 0, 0);
1138         }
1139     }
1140 
1141     /**
1142      * Returns a {@link Set} view of the mappings contained in this map.
1143      * Each element in the returned set is a reference-equality-based
1144      * <tt>Map.Entry</tt>.  The set is backed by the map, so changes
1145      * to the map are reflected in the set, and vice-versa.  If the
1146      * map is modified while an iteration over the set is in progress,
1147      * the results of the iteration are undefined.  The set supports
1148      * element removal, which removes the corresponding mapping from
1149      * the map, via the <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
1150      * <tt>removeAll</tt>, <tt>retainAll</tt> and <tt>clear</tt>
1151      * methods.  It does not support the <tt>add</tt> or
1152      * <tt>addAll</tt> methods.
1153      *
1154      * <p>Like the backing map, the <tt>Map.Entry</tt> objects in the set
1155      * returned by this method define key and value equality as
1156      * reference-equality rather than object-equality.  This affects the
1157      * behavior of the <tt>equals</tt> and <tt>hashCode</tt> methods of these
1158      * <tt>Map.Entry</tt> objects.  A reference-equality based <tt>Map.Entry
1159      * e</tt> is equal to an object <tt>o</tt> if and only if <tt>o</tt> is a
1160      * <tt>Map.Entry</tt> and <tt>e.getKey()==o.getKey() &amp;&amp;
1161      * e.getValue()==o.getValue()</tt>.  To accommodate these equals
1162      * semantics, the <tt>hashCode</tt> method returns
1163      * <tt>System.identityHashCode(e.getKey()) ^
1164      * System.identityHashCode(e.getValue())</tt>.
1165      *
1166      * <p><b>Owing to the reference-equality-based semantics of the
1167      * <tt>Map.Entry</tt> instances in the set returned by this method,
1168      * it is possible that the symmetry and transitivity requirements of
1169      * the {@link Object#equals(Object)} contract may be violated if any of
1170      * the entries in the set is compared to a normal map entry, or if
1171      * the set returned by this method is compared to a set of normal map
1172      * entries (such as would be returned by a call to this method on a normal
1173      * map).  However, the <tt>Object.equals</tt> contract is guaranteed to
1174      * hold among identity-based map entries, and among sets of such entries.
1175      * </b>
1176      *
1177      * @return a set view of the identity-mappings contained in this map
1178      */
1179     public Set<Map.Entry<K,V>> entrySet() {
1180         Set<Map.Entry<K,V>> es = entrySet;
1181         if (es != null)
1182             return es;
1183         else
1184             return entrySet = new EntrySet();
1185     }
1186 
1187     private class EntrySet extends AbstractSet<Map.Entry<K,V>> {
1188         public Iterator<Map.Entry<K,V>> iterator() {
1189             return new EntryIterator();
1190         }
1191         public boolean contains(Object o) {
1192             if (!(o instanceof Map.Entry))
1193                 return false;
1194             Map.Entry<?,?> entry = (Map.Entry<?,?>)o;
1195             return containsMapping(entry.getKey(), entry.getValue());
1196         }
1197         public boolean remove(Object o) {
1198             if (!(o instanceof Map.Entry))
1199                 return false;
1200             Map.Entry<?,?> entry = (Map.Entry<?,?>)o;
1201             return removeMapping(entry.getKey(), entry.getValue());
1202         }
1203         public int size() {
1204             return size;
1205         }
1206         public void clear() {
1207             IdentityHashMap.this.clear();
1208         }
1209         /*
1210          * Must revert from AbstractSet's impl to AbstractCollection's, as
1211          * the former contains an optimization that results in incorrect
1212          * behavior when c is a smaller "normal" (non-identity-based) Set.
1213          */
1214         public boolean removeAll(Collection<?> c) {
1215             boolean modified = false;
1216             for (Iterator<Map.Entry<K,V>> i = iterator(); i.hasNext(); ) {
1217                 if (c.contains(i.next())) {
1218                     i.remove();
1219                     modified = true;
1220                 }
1221             }
1222             return modified;
1223         }
1224 
1225         public Object[] toArray() {
1226             return toArray(new Object[0]);
1227         }
1228 
1229         @SuppressWarnings("unchecked")
1230         public <T> T[] toArray(T[] a) {
1231             int expectedModCount = modCount;
1232             int size = size();
1233             if (a.length < size)
1234                 a = (T[]) Array.newInstance(a.getClass().getComponentType(), size);
1235             Object[] tab = table;
1236             int ti = 0;
1237             for (int si = 0; si < tab.length; si += 2) {
1238                 Object key;
1239                 if ((key = tab[si]) != null) { // key present ?
1240                     // more elements than expected -> concurrent modification from other thread
1241                     if (ti >= size) {
1242                         throw new ConcurrentModificationException();
1243                     }
1244                     a[ti++] = (T) new AbstractMap.SimpleEntry(unmaskNull(key), tab[si + 1]);
1245                 }
1246             }
1247             // fewer elements than expected or concurrent modification from other thread detected
1248             if (ti < size || expectedModCount != modCount) {
1249                 throw new ConcurrentModificationException();
1250             }
1251             // final null marker as per spec
1252             if (ti < a.length) {
1253                 a[ti] = null;
1254             }
1255             return a;
1256         }
1257 
1258         public Spliterator<Map.Entry<K,V>> spliterator() {
1259             return new EntrySpliterator<>(IdentityHashMap.this, 0, -1, 0, 0);
1260         }
1261     }
1262 
1263 
1264     private static final long serialVersionUID = 8188218128353913216L;
1265 
1266     /**
1267      * Save the state of the <tt>IdentityHashMap</tt> instance to a stream
1268      * (i.e., serialize it).
1269      *
1270      * @serialData The <i>size</i> of the HashMap (the number of key-value
1271      *          mappings) (<tt>int</tt>), followed by the key (Object) and
1272      *          value (Object) for each key-value mapping represented by the
1273      *          IdentityHashMap.  The key-value mappings are emitted in no
1274      *          particular order.
1275      */
1276     private void writeObject(java.io.ObjectOutputStream s)
1277         throws java.io.IOException  {
1278         // Write out and any hidden stuff
1279         s.defaultWriteObject();
1280 
1281         // Write out size (number of Mappings)
1282         s.writeInt(size);
1283 
1284         // Write out keys and values (alternating)
1285         Object[] tab = table;
1286         for (int i = 0; i < tab.length; i += 2) {
1287             Object key = tab[i];
1288             if (key != null) {
1289                 s.writeObject(unmaskNull(key));
1290                 s.writeObject(tab[i + 1]);
1291             }
1292         }
1293     }
1294 
1295     /**
1296      * Reconstitute the <tt>IdentityHashMap</tt> instance from a stream (i.e.,
1297      * deserialize it).
1298      */
1299     private void readObject(java.io.ObjectInputStream s)
1300         throws java.io.IOException, ClassNotFoundException  {
1301         // Read in any hidden stuff
1302         s.defaultReadObject();
1303 
1304         // Read in size (number of Mappings)
1305         int size = s.readInt();
1306 
1307         // Allow for 33% growth (i.e., capacity is >= 2* size()).
1308         init(capacity((size*4)/3));
1309 
1310         // Read the keys and values, and put the mappings in the table
1311         for (int i=0; i<size; i++) {
1312             @SuppressWarnings("unchecked")
1313                 K key = (K) s.readObject();
1314             @SuppressWarnings("unchecked")
1315                 V value = (V) s.readObject();
1316             putForCreate(key, value);
1317         }
1318     }
1319 
1320     /**
1321      * The put method for readObject.  It does not resize the table,
1322      * update modCount, etc.
1323      */
1324     private void putForCreate(K key, V value)
1325         throws IOException
1326     {
1327         Object k = maskNull(key);
1328         Object[] tab = table;
1329         int len = tab.length;
1330         int i = hash(k, len);
1331 
1332         Object item;
1333         while ( (item = tab[i]) != null) {
1334             if (item == k)
1335                 throw new java.io.StreamCorruptedException();
1336             i = nextKeyIndex(i, len);
1337         }
1338         tab[i] = k;
1339         tab[i + 1] = value;
1340     }
1341 
1342     @Override
1343     public void forEach(BiConsumer<? super K, ? super V> action) {
1344         Objects.requireNonNull(action);
1345         int expectedModCount = modCount;
1346 
1347         Object[] t = table;
1348         for (int index = 0; index < t.length; index += 2) {
1349             if (t[index] != null) {
1350                 action.accept((K) unmaskNull(t[index]), (V) t[index + 1]);
1351             }
1352 
1353             if (modCount != expectedModCount)
1354                 throw new ConcurrentModificationException();
1355         }
1356     }
1357 
1358     @Override
1359     public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
1360         Objects.requireNonNull(function);
1361         int expectedModCount = modCount;
1362 
1363         Object[] t = table;
1364         for (int index = 0; index < t.length; index += 2) {
1365             if (t[index] != null) {
1366                 t[index + 1] = function.apply((K) unmaskNull(t[index]), (V) t[index + 1]);
1367             }
1368             
1369             if (modCount != expectedModCount)
1370                 throw new ConcurrentModificationException();
1371         }
1372     }
1373 
1374     /**
1375      * Similar form as array-based Spliterators, but skips blank elements,
1376      * and guestimates size as decreasing by half per split.
1377      */
1378     static class IdentityHashMapSpliterator<K,V> {
1379         final IdentityHashMap<K,V> map;
1380         int index;             // current index, modified on advance/split
1381         int fence;             // -1 until first use; then one past last index
1382         int est;               // size estimate
1383         int expectedModCount;  // initialized when fence set
1384 
1385         IdentityHashMapSpliterator(IdentityHashMap<K,V> map, int origin,
1386                                    int fence, int est, int expectedModCount) {
1387             this.map = map;
1388             this.index = origin;
1389             this.fence = fence;
1390             this.est = est;
1391             this.expectedModCount = expectedModCount;
1392         }
1393 
1394         final int getFence() { // initialize fence and size on first use
1395             int hi;
1396             if ((hi = fence) < 0) {
1397                 est = map.size;
1398                 expectedModCount = map.modCount;
1399                 hi = fence = map.table.length;
1400             }
1401             return hi;
1402         }
1403 
1404         public final long estimateSize() {
1405             getFence(); // force init
1406             return (long) est;
1407         }
1408     }
1409 
1410     static final class KeySpliterator<K,V>
1411         extends IdentityHashMapSpliterator<K,V>
1412         implements Spliterator<K> {
1413         KeySpliterator(IdentityHashMap<K,V> map, int origin, int fence, int est,
1414                        int expectedModCount) {
1415             super(map, origin, fence, est, expectedModCount);
1416         }
1417 
1418         public KeySpliterator<K,V> trySplit() {
1419             int hi = getFence(), lo = index, mid = ((lo + hi) >>> 1) & ~1;
1420             return (lo >= mid) ? null :
1421                 new KeySpliterator<K,V>(map, lo, index = mid, est >>>= 1,
1422                                         expectedModCount);
1423         }
1424 
1425         @SuppressWarnings("unchecked")
1426         public void forEachRemaining(Consumer<? super K> action) {
1427             if (action == null)
1428                 throw new NullPointerException();
1429             int i, hi, mc; Object key;
1430             IdentityHashMap<K,V> m; Object[] a;
1431             if ((m = map) != null && (a = m.table) != null &&
1432                 (i = index) >= 0 && (index = hi = getFence()) <= a.length) {
1433                 for (; i < hi; i += 2) {
1434                     if ((key = a[i]) != null)
1435                         action.accept((K)unmaskNull(key));
1436                 }
1437                 if (m.modCount == expectedModCount)
1438                     return;
1439             }
1440             throw new ConcurrentModificationException();
1441         }
1442 
1443         @SuppressWarnings("unchecked")
1444         public boolean tryAdvance(Consumer<? super K> action) {
1445             if (action == null)
1446                 throw new NullPointerException();
1447             Object[] a = map.table;
1448             int hi = getFence();
1449             while (index < hi) {
1450                 Object key = a[index];
1451                 index += 2;
1452                 if (key != null) {
1453                     action.accept((K)unmaskNull(key));
1454                     if (map.modCount != expectedModCount)
1455                         throw new ConcurrentModificationException();
1456                     return true;
1457                 }
1458             }
1459             return false;
1460         }
1461 
1462         public int characteristics() {
1463             return (fence < 0 || est == map.size ? SIZED : 0) | Spliterator.DISTINCT;
1464         }
1465     }
1466 
1467     static final class ValueSpliterator<K,V>
1468         extends IdentityHashMapSpliterator<K,V>
1469         implements Spliterator<V> {
1470         ValueSpliterator(IdentityHashMap<K,V> m, int origin, int fence, int est,
1471                          int expectedModCount) {
1472             super(m, origin, fence, est, expectedModCount);
1473         }
1474 
1475         public ValueSpliterator<K,V> trySplit() {
1476             int hi = getFence(), lo = index, mid = ((lo + hi) >>> 1) & ~1;
1477             return (lo >= mid) ? null :
1478                 new ValueSpliterator<K,V>(map, lo, index = mid, est >>>= 1,
1479                                           expectedModCount);
1480         }
1481 
1482         public void forEachRemaining(Consumer<? super V> action) {
1483             if (action == null)
1484                 throw new NullPointerException();
1485             int i, hi, mc;
1486             IdentityHashMap<K,V> m; Object[] a;
1487             if ((m = map) != null && (a = m.table) != null &&
1488                 (i = index) >= 0 && (index = hi = getFence()) <= a.length) {
1489                 for (; i < hi; i += 2) {
1490                     if (a[i] != null) {
1491                         @SuppressWarnings("unchecked") V v = (V)a[i+1];
1492                         action.accept(v);
1493                     }
1494                 }
1495                 if (m.modCount == expectedModCount)
1496                     return;
1497             }
1498             throw new ConcurrentModificationException();
1499         }
1500 
1501         public boolean tryAdvance(Consumer<? super V> action) {
1502             if (action == null)
1503                 throw new NullPointerException();
1504             Object[] a = map.table;
1505             int hi = getFence();
1506             while (index < hi) {
1507                 Object key = a[index];
1508                 @SuppressWarnings("unchecked") V v = (V)a[index+1];
1509                 index += 2;
1510                 if (key != null) {
1511                     action.accept(v);
1512                     if (map.modCount != expectedModCount)
1513                         throw new ConcurrentModificationException();
1514                     return true;
1515                 }
1516             }
1517             return false;
1518         }
1519 
1520         public int characteristics() {
1521             return (fence < 0 || est == map.size ? SIZED : 0);
1522         }
1523 
1524     }
1525 
1526     static final class EntrySpliterator<K,V>
1527         extends IdentityHashMapSpliterator<K,V>
1528         implements Spliterator<Map.Entry<K,V>> {
1529         EntrySpliterator(IdentityHashMap<K,V> m, int origin, int fence, int est,
1530                          int expectedModCount) {
1531             super(m, origin, fence, est, expectedModCount);
1532         }
1533 
1534         public EntrySpliterator<K,V> trySplit() {
1535             int hi = getFence(), lo = index, mid = ((lo + hi) >>> 1) & ~1;
1536             return (lo >= mid) ? null :
1537                 new EntrySpliterator<K,V>(map, lo, index = mid, est >>>= 1,
1538                                           expectedModCount);
1539         }
1540 
1541         public void forEachRemaining(Consumer<? super Map.Entry<K, V>> action) {
1542             if (action == null)
1543                 throw new NullPointerException();
1544             int i, hi, mc;
1545             IdentityHashMap<K,V> m; Object[] a;
1546             if ((m = map) != null && (a = m.table) != null &&
1547                 (i = index) >= 0 && (index = hi = getFence()) <= a.length) {
1548                 for (; i < hi; i += 2) {
1549                     Object key = a[i];
1550                     if (key != null) {
1551                         @SuppressWarnings("unchecked") K k =
1552                             (K)unmaskNull(key);
1553                         @SuppressWarnings("unchecked") V v = (V)a[i+1];
1554                         action.accept
1555                             (new AbstractMap.SimpleImmutableEntry<K,V>(k, v));
1556 
1557                     }
1558                 }
1559                 if (m.modCount == expectedModCount)
1560                     return;
1561             }
1562             throw new ConcurrentModificationException();
1563         }
1564 
1565         public boolean tryAdvance(Consumer<? super Map.Entry<K,V>> action) {
1566             if (action == null)
1567                 throw new NullPointerException();
1568             Object[] a = map.table;
1569             int hi = getFence();
1570             while (index < hi) {
1571                 Object key = a[index];
1572                 @SuppressWarnings("unchecked") V v = (V)a[index+1];
1573                 index += 2;
1574                 if (key != null) {
1575                     @SuppressWarnings("unchecked") K k =
1576                         (K)unmaskNull(key);
1577                     action.accept
1578                         (new AbstractMap.SimpleImmutableEntry<K,V>(k, v));
1579                     if (map.modCount != expectedModCount)
1580                         throw new ConcurrentModificationException();
1581                     return true;
1582                 }
1583             }
1584             return false;
1585         }
1586 
1587         public int characteristics() {
1588             return (fence < 0 || est == map.size ? SIZED : 0) | Spliterator.DISTINCT;
1589         }
1590     }
1591 
1592 }