1 /*
2 * Copyright (c) 1998, 2025, 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
26 package java.util;
27
28 import java.lang.ref.ReferenceQueue;
29 import java.lang.ref.WeakReference;
30 import java.util.function.BiConsumer;
31 import java.util.function.BiFunction;
32 import java.util.function.Consumer;
33
34
35 /**
36 * Hash table based implementation of the {@code Map} interface, with
37 * <em>weak keys</em>.
38 * An entry in a {@code WeakHashMap} will automatically be removed when
39 * its key is no longer in ordinary use. More precisely, the presence of a
40 * mapping for a given key will not prevent the key from being discarded by the
41 * garbage collector, that is, made finalizable, finalized, and then reclaimed.
42 * When a key has been discarded its entry is effectively removed from the map,
43 * so this class behaves somewhat differently from other {@code Map}
44 * implementations.
45 *
46 * <p> Both null values and the null key are supported. This class has
47 * performance characteristics similar to those of the {@code HashMap}
48 * class, and has the same efficiency parameters of <em>initial capacity</em>
49 * and <em>load factor</em>.
50 *
51 * <p> Like most collection classes, this class is not synchronized.
52 * A synchronized {@code WeakHashMap} may be constructed using the
53 * {@link Collections#synchronizedMap Collections.synchronizedMap}
54 * method.
55 *
56 * <p> This class is intended primarily for use with key objects whose
57 * {@code equals} methods test for object identity using the
58 * {@code ==} operator. Once such a key is discarded it can never be
59 * recreated, so it is impossible to do a lookup of that key in a
60 * {@code WeakHashMap} at some later time and be surprised that its entry
61 * has been removed. This class will work perfectly well with key objects
62 * whose {@code equals} methods are not based upon object identity, such
63 * as {@code String} instances. With such recreatable key objects,
64 * however, the automatic removal of {@code WeakHashMap} entries whose
65 * keys have been discarded may prove to be confusing.
70 * the garbage collector may discard keys at any time, a
71 * {@code WeakHashMap} may behave as though an unknown thread is silently
72 * removing entries. In particular, even if you synchronize on a
73 * {@code WeakHashMap} instance and invoke none of its mutator methods, it
74 * is possible for the {@code size} method to return smaller values over
75 * time, for the {@code isEmpty} method to return {@code false} and
76 * then {@code true}, for the {@code containsKey} method to return
77 * {@code true} and later {@code false} for a given key, for the
78 * {@code get} method to return a value for a given key but later return
79 * {@code null}, for the {@code put} method to return
80 * {@code null} and the {@code remove} method to return
81 * {@code false} for a key that previously appeared to be in the map, and
82 * for successive examinations of the key set, the value collection, and
83 * the entry set to yield successively smaller numbers of elements.
84 *
85 * <p> Each key object in a {@code WeakHashMap} is stored indirectly as
86 * the referent of a weak reference. Therefore a key will automatically be
87 * removed only after the weak references to it, both inside and outside of the
88 * map, have been cleared by the garbage collector.
89 *
90 * <p> <strong>Implementation note:</strong> The value objects in a
91 * {@code WeakHashMap} are held by ordinary strong references. Thus care
92 * should be taken to ensure that value objects do not strongly refer to their
93 * own keys, either directly or indirectly, since that will prevent the keys
94 * from being discarded. Note that a value object may refer indirectly to its
95 * key via the {@code WeakHashMap} itself; that is, a value object may
96 * strongly refer to some other key object whose associated value object, in
97 * turn, strongly refers to the key of the first value object. If the values
98 * in the map do not rely on the map holding strong references to them, one way
99 * to deal with this is to wrap values themselves within
100 * {@code WeakReferences} before
101 * inserting, as in: {@code m.put(key, new WeakReference(value))},
102 * and then unwrapping upon each {@code get}.
103 *
104 * <p>The iterators returned by the {@code iterator} method of the collections
105 * returned by all of this class's "collection view methods" are
106 * <i>fail-fast</i>: if the map is structurally modified at any time after the
107 * iterator is created, in any way except through the iterator's own
108 * {@code remove} method, the iterator will throw a {@link
109 * ConcurrentModificationException}. Thus, in the face of concurrent
110 * modification, the iterator fails quickly and cleanly, rather than risking
111 * arbitrary, non-deterministic behavior at an undetermined time in the future.
112 *
113 * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
114 * as it is, generally speaking, impossible to make any hard guarantees in the
115 * presence of unsynchronized concurrent modification. Fail-fast iterators
116 * throw {@code ConcurrentModificationException} on a best-effort basis.
117 * Therefore, it would be wrong to write a program that depended on this
237 public WeakHashMap(int initialCapacity) {
238 this(initialCapacity, DEFAULT_LOAD_FACTOR);
239 }
240
241 /**
242 * Constructs a new, empty {@code WeakHashMap} with the default initial
243 * capacity (16) and load factor (0.75).
244 */
245 public WeakHashMap() {
246 this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
247 }
248
249 /**
250 * Constructs a new {@code WeakHashMap} with the same mappings as the
251 * specified map. The {@code WeakHashMap} is created with the default
252 * load factor (0.75) and an initial capacity sufficient to hold the
253 * mappings in the specified map.
254 *
255 * @param m the map whose mappings are to be placed in this map
256 * @throws NullPointerException if the specified map is null
257 * @since 1.3
258 */
259 @SuppressWarnings("this-escape")
260 public WeakHashMap(Map<? extends K, ? extends V> m) {
261 this(Math.max((int) Math.ceil(m.size() / (double)DEFAULT_LOAD_FACTOR),
262 DEFAULT_INITIAL_CAPACITY),
263 DEFAULT_LOAD_FACTOR);
264 putAll(m);
265 }
266
267 // internal utilities
268
269 /**
270 * Value representing null keys inside tables.
271 */
272 private static final Object NULL_KEY = new Object();
273
274 /**
275 * Use NULL_KEY for key if it is null.
276 */
277 private static Object maskNull(Object key) {
278 return (key == null) ? NULL_KEY : key;
279 }
280
281 /**
282 * Returns internal representation of null key back to caller as null.
283 */
284 static Object unmaskNull(Object key) {
285 return (key == NULL_KEY) ? null : key;
286 }
287
288 /**
289 * Checks for equality of non-null reference x and possibly-null y. By
290 * default uses Object.equals.
291 */
292 private boolean matchesKey(Entry<K,V> e, Object key) {
293 // check if the given entry refers to the given key without
294 // keeping a strong reference to the entry's referent
295 if (e.refersTo(key)) return true;
296
297 // then check for equality if the referent is not cleared
298 Object k = e.get();
299 return k != null && key.equals(k);
300 }
301
302 /**
303 * Retrieve object hash code and applies a supplemental hash function to the
304 * result hash, which defends against poor quality hash functions. This is
305 * critical because HashMap uses power-of-two length hash tables, that
306 * otherwise encounter collisions for hashCodes that do not differ
307 * in lower bits.
308 */
309 final int hash(Object k) {
310 int h = k.hashCode();
439 int h = hash(k);
440 Entry<K,V>[] tab = getTable();
441 int index = indexFor(h, tab.length);
442 Entry<K,V> e = tab[index];
443 while (e != null && !(e.hash == h && matchesKey(e, k)))
444 e = e.next;
445 return e;
446 }
447
448 /**
449 * Associates the specified value with the specified key in this map.
450 * If the map previously contained a mapping for this key, the old
451 * value is replaced.
452 *
453 * @param key key with which the specified value is to be associated.
454 * @param value value to be associated with the specified key.
455 * @return the previous value associated with {@code key}, or
456 * {@code null} if there was no mapping for {@code key}.
457 * (A {@code null} return can also indicate that the map
458 * previously associated {@code null} with {@code key}.)
459 */
460 public V put(@jdk.internal.RequiresIdentity K key, V value) {
461 Object k = maskNull(key);
462 int h = hash(k);
463 Entry<K,V>[] tab = getTable();
464 int i = indexFor(h, tab.length);
465
466 for (Entry<K,V> e = tab[i]; e != null; e = e.next) {
467 if (h == e.hash && matchesKey(e, k)) {
468 V oldValue = e.value;
469 if (value != oldValue)
470 e.value = value;
471 return oldValue;
472 }
473 }
474
475 modCount++;
476 Entry<K,V> e = tab[i];
477 tab[i] = new Entry<>(k, value, queue, h, e);
478 if (++size > threshold)
479 resize(tab.length * 2);
480 return null;
481 }
529 Entry<K,V> next = e.next;
530 if (e.refersTo(null)) {
531 e.next = null; // Help GC
532 e.value = null; // " "
533 size--;
534 } else {
535 int i = indexFor(e.hash, dest.length);
536 e.next = dest[i];
537 dest[i] = e;
538 }
539 e = next;
540 }
541 }
542 }
543
544 /**
545 * Copies all of the mappings from the specified map to this map.
546 * These mappings will replace any mappings that this map had for any
547 * of the keys currently in the specified map.
548 *
549 * @param m mappings to be stored in this map.
550 * @throws NullPointerException if the specified map is null.
551 */
552 public void putAll(Map<? extends K, ? extends V> m) {
553 int numKeysToBeAdded = m.size();
554 if (numKeysToBeAdded == 0)
555 return;
556
557 /*
558 * Expand the map if the map if the number of mappings to be added
559 * is greater than or equal to threshold. This is conservative; the
560 * obvious condition is (m.size() + size) >= threshold, but this
561 * condition could result in a map with twice the appropriate capacity,
562 * if the keys to be added overlap with the keys already in this map.
563 * By using the conservative calculation, we subject ourself
564 * to at most one extra resize.
565 */
566 if (numKeysToBeAdded > threshold) {
567 int targetCapacity = (int)Math.ceil(numKeysToBeAdded / (double)loadFactor);
568 if (targetCapacity > MAXIMUM_CAPACITY)
569 targetCapacity = MAXIMUM_CAPACITY;
570 int newCapacity = table.length;
|
1 /*
2 * Copyright (c) 1998, 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
26 package java.util;
27
28 import java.lang.ref.ReferenceQueue;
29 import java.lang.ref.WeakReference;
30 import java.util.function.BiConsumer;
31 import java.util.function.BiFunction;
32 import java.util.function.Consumer;
33
34
35 /**
36 * Hash table based implementation of the {@code Map} interface, with
37 * <em>weak keys</em>.
38 * An entry in a {@code WeakHashMap} will automatically be removed when
39 * its key is no longer in ordinary use. More precisely, the presence of a
40 * mapping for a given key will not prevent the key from being discarded by the
41 * garbage collector, that is, made finalizable, finalized, and then reclaimed.
42 * When a key has been discarded its entry is effectively removed from the map,
43 * so this class behaves somewhat differently from other {@code Map}
44 * implementations.
45 *
46 * <div class="preview-block">
47 * <div class="preview-comment">
48 * {@linkplain java.util.Objects#hasIdentity Value objects} can not be used as
49 * keys in a {@code WeakHashMap}. The {@link #put(Object, Object) put(K, V)}
50 * method, and all methods that associate a value with a key, throw {@link
51 * IdentityException} if the key is a value object.
52 * The {@link WeakHashMap#WeakHashMap(Map)} constructor and the {@link
53 * #putAll(Map)} method also throw {@code IdentityException} if invoked with
54 * a {@code Map} containing a key that is a value object.
55 * </div>
56 * </div>
57 *
58 * <p> Both null values and the null key are supported. This class has
59 * performance characteristics similar to those of the {@code HashMap}
60 * class, and has the same efficiency parameters of <em>initial capacity</em>
61 * and <em>load factor</em>.
62 *
63 * <p> Like most collection classes, this class is not synchronized.
64 * A synchronized {@code WeakHashMap} may be constructed using the
65 * {@link Collections#synchronizedMap Collections.synchronizedMap}
66 * method.
67 *
68 * <p> This class is intended primarily for use with key objects whose
69 * {@code equals} methods test for object identity using the
70 * {@code ==} operator. Once such a key is discarded it can never be
71 * recreated, so it is impossible to do a lookup of that key in a
72 * {@code WeakHashMap} at some later time and be surprised that its entry
73 * has been removed. This class will work perfectly well with key objects
74 * whose {@code equals} methods are not based upon object identity, such
75 * as {@code String} instances. With such recreatable key objects,
76 * however, the automatic removal of {@code WeakHashMap} entries whose
77 * keys have been discarded may prove to be confusing.
82 * the garbage collector may discard keys at any time, a
83 * {@code WeakHashMap} may behave as though an unknown thread is silently
84 * removing entries. In particular, even if you synchronize on a
85 * {@code WeakHashMap} instance and invoke none of its mutator methods, it
86 * is possible for the {@code size} method to return smaller values over
87 * time, for the {@code isEmpty} method to return {@code false} and
88 * then {@code true}, for the {@code containsKey} method to return
89 * {@code true} and later {@code false} for a given key, for the
90 * {@code get} method to return a value for a given key but later return
91 * {@code null}, for the {@code put} method to return
92 * {@code null} and the {@code remove} method to return
93 * {@code false} for a key that previously appeared to be in the map, and
94 * for successive examinations of the key set, the value collection, and
95 * the entry set to yield successively smaller numbers of elements.
96 *
97 * <p> Each key object in a {@code WeakHashMap} is stored indirectly as
98 * the referent of a weak reference. Therefore a key will automatically be
99 * removed only after the weak references to it, both inside and outside of the
100 * map, have been cleared by the garbage collector.
101 *
102 * <p> <strong>Implementation note:</strong> The values in a
103 * {@code WeakHashMap} are held by ordinary strong references. Thus care
104 * should be taken to ensure that values do not strongly refer to their
105 * own keys, either directly or indirectly, since that will prevent the keys
106 * from being discarded. Note that a value may refer indirectly to its
107 * key via the {@code WeakHashMap} itself; that is, a value may
108 * strongly refer to some other key object whose associated value, in
109 * turn, strongly refers to the key of the first value. If the values
110 * in the map do not rely on the map holding strong references to them, one way
111 * to deal with this is to wrap values themselves within
112 * {@code WeakReferences} before
113 * inserting, as in: {@code m.put(key, new WeakReference(value))},
114 * and then unwrapping upon each {@code get}.
115 *
116 * <p>The iterators returned by the {@code iterator} method of the collections
117 * returned by all of this class's "collection view methods" are
118 * <i>fail-fast</i>: if the map is structurally modified at any time after the
119 * iterator is created, in any way except through the iterator's own
120 * {@code remove} method, the iterator will throw a {@link
121 * ConcurrentModificationException}. Thus, in the face of concurrent
122 * modification, the iterator fails quickly and cleanly, rather than risking
123 * arbitrary, non-deterministic behavior at an undetermined time in the future.
124 *
125 * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
126 * as it is, generally speaking, impossible to make any hard guarantees in the
127 * presence of unsynchronized concurrent modification. Fail-fast iterators
128 * throw {@code ConcurrentModificationException} on a best-effort basis.
129 * Therefore, it would be wrong to write a program that depended on this
249 public WeakHashMap(int initialCapacity) {
250 this(initialCapacity, DEFAULT_LOAD_FACTOR);
251 }
252
253 /**
254 * Constructs a new, empty {@code WeakHashMap} with the default initial
255 * capacity (16) and load factor (0.75).
256 */
257 public WeakHashMap() {
258 this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
259 }
260
261 /**
262 * Constructs a new {@code WeakHashMap} with the same mappings as the
263 * specified map. The {@code WeakHashMap} is created with the default
264 * load factor (0.75) and an initial capacity sufficient to hold the
265 * mappings in the specified map.
266 *
267 * @param m the map whose mappings are to be placed in this map
268 * @throws NullPointerException if the specified map is null
269 * @throws IdentityException if any of the keys in the specified map
270 * is a value object
271 * @since 1.3
272 */
273 @SuppressWarnings("this-escape")
274 public WeakHashMap(Map<? extends K, ? extends V> m) {
275 this(Math.max((int) Math.ceil(m.size() / (double)DEFAULT_LOAD_FACTOR),
276 DEFAULT_INITIAL_CAPACITY),
277 DEFAULT_LOAD_FACTOR);
278 putAll(m);
279 }
280
281 // internal utilities
282
283 /**
284 * Value representing null keys inside tables.
285 */
286 private static final Object NULL_KEY = new Object();
287
288 /**
289 * Use NULL_KEY for key if it is null.
290 */
291 private static Object maskNull(Object key) {
292 return (key == null) ? NULL_KEY : key;
293 }
294
295 /**
296 * Returns internal representation of null key back to caller as null.
297 */
298 static Object unmaskNull(Object key) {
299 return (key == NULL_KEY) ? null : key;
300 }
301
302 /**
303 * Checks for equality of non-null reference x and possibly-null y. By
304 * default uses Object.equals.
305 * The key may be a value object, but it will never be equal to the referent
306 * so does not need a separate Objects.hasIdentity check.
307 */
308 private boolean matchesKey(Entry<K,V> e, Object key) {
309 // check if the given entry refers to the given key without
310 // keeping a strong reference to the entry's referent
311 if (e.refersTo(key)) return true;
312
313 // then check for equality if the referent is not cleared
314 Object k = e.get();
315 return k != null && key.equals(k);
316 }
317
318 /**
319 * Retrieve object hash code and applies a supplemental hash function to the
320 * result hash, which defends against poor quality hash functions. This is
321 * critical because HashMap uses power-of-two length hash tables, that
322 * otherwise encounter collisions for hashCodes that do not differ
323 * in lower bits.
324 */
325 final int hash(Object k) {
326 int h = k.hashCode();
455 int h = hash(k);
456 Entry<K,V>[] tab = getTable();
457 int index = indexFor(h, tab.length);
458 Entry<K,V> e = tab[index];
459 while (e != null && !(e.hash == h && matchesKey(e, k)))
460 e = e.next;
461 return e;
462 }
463
464 /**
465 * Associates the specified value with the specified key in this map.
466 * If the map previously contained a mapping for this key, the old
467 * value is replaced.
468 *
469 * @param key key with which the specified value is to be associated.
470 * @param value value to be associated with the specified key.
471 * @return the previous value associated with {@code key}, or
472 * {@code null} if there was no mapping for {@code key}.
473 * (A {@code null} return can also indicate that the map
474 * previously associated {@code null} with {@code key}.)
475 * @throws IdentityException if {@code key} is a {@link
476 * java.util.Objects#hasIdentity(Object) value object}
477 */
478 public V put(@jdk.internal.RequiresIdentity K key, V value) {
479 Object k = maskNull(key);
480 Objects.requireIdentity(k);
481 int h = hash(k);
482 Entry<K,V>[] tab = getTable();
483 int i = indexFor(h, tab.length);
484
485 for (Entry<K,V> e = tab[i]; e != null; e = e.next) {
486 if (h == e.hash && matchesKey(e, k)) {
487 V oldValue = e.value;
488 if (value != oldValue)
489 e.value = value;
490 return oldValue;
491 }
492 }
493
494 modCount++;
495 Entry<K,V> e = tab[i];
496 tab[i] = new Entry<>(k, value, queue, h, e);
497 if (++size > threshold)
498 resize(tab.length * 2);
499 return null;
500 }
548 Entry<K,V> next = e.next;
549 if (e.refersTo(null)) {
550 e.next = null; // Help GC
551 e.value = null; // " "
552 size--;
553 } else {
554 int i = indexFor(e.hash, dest.length);
555 e.next = dest[i];
556 dest[i] = e;
557 }
558 e = next;
559 }
560 }
561 }
562
563 /**
564 * Copies all of the mappings from the specified map to this map.
565 * These mappings will replace any mappings that this map had for any
566 * of the keys currently in the specified map.
567 *
568 * @apiNote If the specified map contains keys that are
569 * {@linkplain java.util.Objects#hasIdentity value objects},
570 * an {@linkplain IdentityException} is thrown when the first value object
571 * key is encountered. Zero or more mappings may have already been copied to
572 * this map.
573 *
574 * @param m mappings to be stored in this map.
575 * @throws NullPointerException if the specified map is null.
576 * @throws IdentityException if any of the {@code keys} is a value object
577 */
578 public void putAll(Map<? extends K, ? extends V> m) {
579 int numKeysToBeAdded = m.size();
580 if (numKeysToBeAdded == 0)
581 return;
582
583 /*
584 * Expand the map if the map if the number of mappings to be added
585 * is greater than or equal to threshold. This is conservative; the
586 * obvious condition is (m.size() + size) >= threshold, but this
587 * condition could result in a map with twice the appropriate capacity,
588 * if the keys to be added overlap with the keys already in this map.
589 * By using the conservative calculation, we subject ourself
590 * to at most one extra resize.
591 */
592 if (numKeysToBeAdded > threshold) {
593 int targetCapacity = (int)Math.ceil(numKeysToBeAdded / (double)loadFactor);
594 if (targetCapacity > MAXIMUM_CAPACITY)
595 targetCapacity = MAXIMUM_CAPACITY;
596 int newCapacity = table.length;
|