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