1 /*
2 * Copyright (c) 2000, 2024, 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 * reference-equality in place of object-equality when comparing keys (and
39 * values). 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 reference-equality
50 * semantics are required.</b>
51 *
52 * <p>The view collections of this map also have reference-equality semantics
53 * for their elements. See the {@link keySet() keySet}, {@link values() values},
54 * and {@link entrySet() entrySet} methods for further information.
55 *
56 * <p>A typical use of this class is <i>topology-preserving object graph
57 * transformations</i>, such as serialization or deep-copying. To perform such
58 * a transformation, a program must maintain a "node table" that keeps track
59 * of all the object references that have already been processed. The node
60 * table must not equate distinct objects even if they happen to be equal.
61 * Another typical use of this class is to maintain <i>proxy objects</i>. For
62 * example, a debugging facility might wish to maintain a proxy object for
63 * each object in the program being debugged.
64 *
65 * <p>This class provides all of the optional map operations, and permits
66 * {@code null} values and the {@code null} key. This class makes no
67 * guarantees as to the order of the map; in particular, it does not guarantee
68 * that the order will remain constant over time.
69 *
70 * <p>This class provides constant-time performance for the basic
71 * operations ({@code get} and {@code put}), assuming the system
72 * identity hash function ({@link System#identityHashCode(Object)})
73 * disperses elements properly among the buckets.
74 *
225 /**
226 * Constructs a new, empty map with the specified expected maximum size.
227 * Putting more than the expected number of key-value mappings into
228 * the map may cause the internal data structure to grow, which may be
229 * somewhat time-consuming.
230 *
231 * @param expectedMaxSize the expected maximum size of the map
232 * @throws IllegalArgumentException if {@code expectedMaxSize} is negative
233 */
234 public IdentityHashMap(int expectedMaxSize) {
235 if (expectedMaxSize < 0)
236 throw new IllegalArgumentException("expectedMaxSize is negative: "
237 + expectedMaxSize);
238 init(capacity(expectedMaxSize));
239 }
240
241 /**
242 * Returns the appropriate capacity for the given expected maximum size.
243 * Returns the smallest power of two between MINIMUM_CAPACITY and
244 * MAXIMUM_CAPACITY, inclusive, that is greater than (3 *
245 * expectedMaxSize)/2, if such a number exists. Otherwise returns
246 * MAXIMUM_CAPACITY.
247 */
248 private static int capacity(int expectedMaxSize) {
249 // assert expectedMaxSize >= 0;
250 return
251 (expectedMaxSize > MAXIMUM_CAPACITY / 3) ? MAXIMUM_CAPACITY :
252 (expectedMaxSize <= 2 * MINIMUM_CAPACITY / 3) ? MINIMUM_CAPACITY :
253 Integer.highestOneBit(expectedMaxSize + (expectedMaxSize << 1));
254 }
255
256 /**
257 * Initializes object to be an empty map with the specified initial
258 * capacity, which is assumed to be a power of two between
259 * MINIMUM_CAPACITY and MAXIMUM_CAPACITY inclusive.
260 */
261 private void init(int initCapacity) {
262 // assert (initCapacity & -initCapacity) == initCapacity; // power of 2
263 // assert initCapacity >= MINIMUM_CAPACITY;
264 // assert initCapacity <= MAXIMUM_CAPACITY;
265
401 * @return {@code true} if and only if the specified key-value
402 * mapping is in the map
403 */
404 private boolean containsMapping(Object key, Object value) {
405 Object k = maskNull(key);
406 Object[] tab = table;
407 int len = tab.length;
408 int i = hash(k, len);
409 while (true) {
410 Object item = tab[i];
411 if (item == k)
412 return tab[i + 1] == value;
413 if (item == null)
414 return false;
415 i = nextKeyIndex(i, len);
416 }
417 }
418
419 /**
420 * Associates the specified value with the specified key in this identity
421 * hash map. If this map already {@link containsKey(Object) contains}
422 * a mapping for the key, the old value is replaced, otherwise, a new mapping
423 * is inserted into this map.
424 *
425 * @param key the key with which the specified value is to be associated
426 * @param value the value to be associated with the specified key
427 * @return the previous value associated with {@code key}, or
428 * {@code null} if there was no mapping for {@code key}.
429 * (A {@code null} return can also indicate that the map
430 * previously associated {@code null} with {@code key}.)
431 * @see Object#equals(Object)
432 * @see #get(Object)
433 * @see #containsKey(Object)
434 */
435 public V put(K key, V value) {
436 final Object k = maskNull(key);
437
438 retryAfterResize: for (;;) {
439 final Object[] tab = table;
440 final int len = tab.length;
441 int i = hash(k, len);
489 for (int j = 0; j < oldLength; j += 2) {
490 Object key = oldTable[j];
491 if (key != null) {
492 Object value = oldTable[j+1];
493 oldTable[j] = null;
494 oldTable[j+1] = null;
495 int i = hash(key, newLength);
496 while (newTable[i] != null)
497 i = nextKeyIndex(i, newLength);
498 newTable[i] = key;
499 newTable[i + 1] = value;
500 }
501 }
502 table = newTable;
503 return true;
504 }
505
506 /**
507 * Copies all of the mappings from the specified map to this map.
508 * For each mapping in the specified map, if this map already
509 * {@link containsKey(Object) contains} a mapping for the key,
510 * its value is replaced with the value from the specified map;
511 * otherwise, a new mapping is inserted into this map.
512 *
513 * @param m mappings to be stored in this map
514 * @throws NullPointerException if the specified map is null
515 */
516 public void putAll(Map<? extends K, ? extends V> m) {
517 int n = m.size();
518 if (n == 0)
519 return;
520 if (n > size)
521 resize(capacity(n)); // conservatively pre-expand
522
523 for (Entry<? extends K, ? extends V> e : m.entrySet())
524 put(e.getKey(), e.getValue());
525 }
526
527 /**
528 * Removes the mapping for this key from this map if present.
529 * The mapping is removed if and only if the mapping has a key
628 }
629
630 /**
631 * Removes all of the mappings from this map.
632 * The map will be empty after this call returns.
633 */
634 public void clear() {
635 modCount++;
636 Object[] tab = table;
637 for (int i = 0; i < tab.length; i++)
638 tab[i] = null;
639 size = 0;
640 }
641
642 /**
643 * Compares the specified object with this map for equality. Returns
644 * {@code true} if the given object is also a map and the two maps
645 * represent identical object-reference mappings. More formally, this
646 * map is equal to another map {@code m} if and only if
647 * {@code this.entrySet().equals(m.entrySet())}. See the
648 * {@link entrySet() entrySet} method for the specification of equality
649 * of this map's entries.
650 *
651 * <p><b>Owing to the reference-equality-based semantics of this map it is
652 * possible that the symmetry and transitivity requirements of the
653 * {@code Object.equals} contract may be violated if this map is compared
654 * to a normal map. However, the {@code Object.equals} contract is
655 * guaranteed to hold among {@code IdentityHashMap} instances.</b>
656 *
657 * @param o object to be compared for equality with this map
658 * @return {@code true} if the specified object is equal to this map
659 * @see Object#equals(Object)
660 */
661 public boolean equals(Object o) {
662 if (o == this) {
663 return true;
664 } else if (o instanceof IdentityHashMap<?, ?> m) {
665 if (m.size() != size)
666 return false;
667
668 Object[] tab = m.table;
669 for (int i = 0; i < tab.length; i+=2) {
670 Object k = tab[i];
671 if (k != null && !containsMapping(k, tab[i + 1]))
672 return false;
673 }
674 return true;
675 } else if (o instanceof Map<?, ?> m) {
676 return entrySet().equals(m.entrySet());
677 } else {
678 return false; // o is not a Map
679 }
680 }
681
682 /**
683 * Returns the hash code value for this map. The hash code of a map is
684 * defined to be the sum of the hash codes of each entry of this map.
685 * See the {@link entrySet() entrySet} method for a specification of the
686 * hash code of this map's entries.
687 *
688 * <p>This specification ensures that {@code m1.equals(m2)}
689 * implies that {@code m1.hashCode()==m2.hashCode()} for any two
690 * {@code IdentityHashMap} instances {@code m1} and {@code m2}, as
691 * required by the general contract of {@link Object#hashCode}.
692 *
693 * <p><b>Owing to the reference-equality-based semantics of the
694 * {@code Map.Entry} instances in the set returned by this map's
695 * {@code entrySet} method, it is possible that the contractual
696 * requirement of {@code Object.hashCode} mentioned in the previous
697 * paragraph will be violated if one of the two objects being compared is
698 * an {@code IdentityHashMap} instance and the other is a normal map.</b>
699 *
700 * @return the hash code value for this map
701 * @see Object#equals(Object)
702 * @see #equals(Object)
703 */
704 public int hashCode() {
705 int result = 0;
1430 Object[] tab = table;
1431 int len = tab.length;
1432 int i = hash(k, len);
1433
1434 while (true) {
1435 Object item = tab[i];
1436 if (item == k) {
1437 if (tab[i + 1] != oldValue)
1438 return false;
1439 tab[i + 1] = newValue;
1440 return true;
1441 }
1442 if (item == null)
1443 return false;
1444 i = nextKeyIndex(i, len);
1445 }
1446 }
1447
1448 /**
1449 * Similar form as array-based Spliterators, but skips blank elements,
1450 * and guestimates size as decreasing by half per split.
1451 */
1452 static class IdentityHashMapSpliterator<K,V> {
1453 final IdentityHashMap<K,V> map;
1454 int index; // current index, modified on advance/split
1455 int fence; // -1 until first use; then one past last index
1456 int est; // size estimate
1457 int expectedModCount; // initialized when fence set
1458
1459 IdentityHashMapSpliterator(IdentityHashMap<K,V> map, int origin,
1460 int fence, int est, int expectedModCount) {
1461 this.map = map;
1462 this.index = origin;
1463 this.fence = fence;
1464 this.est = est;
1465 this.expectedModCount = expectedModCount;
1466 }
1467
1468 final int getFence() { // initialize fence and size on first use
1469 int hi;
1470 if ((hi = fence) < 0) {
|
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 *
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
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);
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
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;
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) {
|