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