1 /*
2 * Copyright (c) 1998, 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.lang.ref.WeakReference;
29 import java.lang.ref.ReferenceQueue;
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>.
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
118 * exception for its correctness: <i>the fail-fast behavior of iterators
119 * should be used only to detect bugs.</i>
120 *
121 * <p>This class is a member of the
122 * <a href="{@docRoot}/java.base/java/util/package-summary.html#CollectionsFramework">
123 * Java Collections Framework</a>.
124 *
125 * @param <K> the type of keys maintained by this map
126 * @param <V> the type of mapped values
127 *
128 * @author Doug Lea
129 * @author Josh Bloch
130 * @author Mark Reinhold
131 * @since 1.2
132 * @see java.util.HashMap
133 * @see java.lang.ref.WeakReference
134 */
135 public class WeakHashMap<@jdk.internal.RequiresIdentity K,V>
136 extends AbstractMap<K,V>
137 implements Map<K,V> {
138
139 /**
140 * The default initial capacity -- MUST be a power of two.
141 */
142 private static final int DEFAULT_INITIAL_CAPACITY = 16;
143
144 /**
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, 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
23 * questions.
24 */
25
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>.
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
118 * exception for its correctness: <i>the fail-fast behavior of iterators
119 * should be used only to detect bugs.</i>
120 *
121 * <p>This class is a member of the
122 * <a href="{@docRoot}/java.base/java/util/package-summary.html#CollectionsFramework">
123 * Java Collections Framework</a>.
124 *
125 * @apiNote
126 * <div class="preview-block">
127 * <div class="preview-comment">
128 * Objects that are {@linkplain Class#isValue() value objects} do not have identity
129 * and can not be used as keys in a {@code WeakHashMap}. {@linkplain java.lang.ref.Reference References}
130 * such as {@linkplain WeakReference WeakReference} used by {@code WeakhashMap}
131 * to hold the key cannot refer to a value object.
132 * Methods such as {@linkplain #get get} or {@linkplain #containsKey containsKey}
133 * will always return {@code null} or {@code false} respectively.
134 * The methods such as {@linkplain #put put}, {@linkplain #putAll putAll},
135 * {@linkplain #compute(Object, BiFunction) compute}, and
136 * {@linkplain #computeIfAbsent(Object, Function) computeIfAbsent} or any method putting
137 * a value object, as a key, throw {@link IdentityException}.
138 * </div>
139 * </div>
140 *
141 * @param <K> the type of keys maintained by this map
142 * @param <V> the type of mapped values
143 *
144 * @author Doug Lea
145 * @author Josh Bloch
146 * @author Mark Reinhold
147 * @since 1.2
148 * @see java.util.HashMap
149 * @see java.lang.ref.WeakReference
150 */
151 public class WeakHashMap<@jdk.internal.RequiresIdentity K,V>
152 extends AbstractMap<K,V>
153 implements Map<K,V> {
154
155 /**
156 * The default initial capacity -- MUST be a power of two.
157 */
158 private static final int DEFAULT_INITIAL_CAPACITY = 16;
159
160 /**
287 */
288 private static final Object NULL_KEY = new Object();
289
290 /**
291 * Use NULL_KEY for key if it is null.
292 */
293 private static Object maskNull(Object key) {
294 return (key == null) ? NULL_KEY : key;
295 }
296
297 /**
298 * Returns internal representation of null key back to caller as null.
299 */
300 static Object unmaskNull(Object key) {
301 return (key == NULL_KEY) ? null : key;
302 }
303
304 /**
305 * Checks for equality of non-null reference x and possibly-null y. By
306 * default uses Object.equals.
307 * The key may be a value object, but it will never be equal to the referent
308 * so does not need a separate Objects.hasIdentity check.
309 */
310 private boolean matchesKey(Entry<K,V> e, Object key) {
311 // check if the given entry refers to the given key without
312 // keeping a strong reference to the entry's referent
313 if (e.refersTo(key)) return true;
314
315 // then check for equality if the referent is not cleared
316 Object k = e.get();
317 return k != null && key.equals(k);
318 }
319
320 /**
321 * Retrieve object hash code and applies a supplemental hash function to the
322 * result hash, which defends against poor quality hash functions. This is
323 * critical because HashMap uses power-of-two length hash tables, that
324 * otherwise encounter collisions for hashCodes that do not differ
325 * in lower bits.
326 */
327 final int hash(Object k) {
328 int h = k.hashCode();
457 int h = hash(k);
458 Entry<K,V>[] tab = getTable();
459 int index = indexFor(h, tab.length);
460 Entry<K,V> e = tab[index];
461 while (e != null && !(e.hash == h && matchesKey(e, k)))
462 e = e.next;
463 return e;
464 }
465
466 /**
467 * Associates the specified value with the specified key in this map.
468 * If the map previously contained a mapping for this key, the old
469 * value is replaced.
470 *
471 * @param key key with which the specified value is to be associated.
472 * @param value value to be associated with the specified key.
473 * @return the previous value associated with {@code key}, or
474 * {@code null} if there was no mapping for {@code key}.
475 * (A {@code null} return can also indicate that the map
476 * previously associated {@code null} with {@code key}.)
477 * @throws IdentityException if {@code key} is a value object
478 */
479 public V put(@jdk.internal.RequiresIdentity K key, V value) {
480 Object k = maskNull(key);
481 Objects.requireIdentity(k);
482 int h = hash(k);
483 Entry<K,V>[] tab = getTable();
484 int i = indexFor(h, tab.length);
485
486 for (Entry<K,V> e = tab[i]; e != null; e = e.next) {
487 if (h == e.hash && matchesKey(e, k)) {
488 V oldValue = e.value;
489 if (value != oldValue)
490 e.value = value;
491 return oldValue;
492 }
493 }
494
495 modCount++;
496 Entry<K,V> e = tab[i];
497 tab[i] = new Entry<>(k, value, queue, h, e);
498 if (++size > threshold)
499 resize(tab.length * 2);
500 return null;
501 }
549 Entry<K,V> next = e.next;
550 if (e.refersTo(null)) {
551 e.next = null; // Help GC
552 e.value = null; // " "
553 size--;
554 } else {
555 int i = indexFor(e.hash, dest.length);
556 e.next = dest[i];
557 dest[i] = e;
558 }
559 e = next;
560 }
561 }
562 }
563
564 /**
565 * Copies all of the mappings from the specified map to this map.
566 * These mappings will replace any mappings that this map had for any
567 * of the keys currently in the specified map.
568 *
569 * @apiNote If the specified map contains keys that are {@linkplain Objects#isValueObject value objects}
570 * an {@linkplain IdentityException } is thrown when the first value object key is encountered.
571 * Zero or more mappings may have already been copied to this map.
572 *
573 * @param m mappings to be stored in this map.
574 * @throws NullPointerException if the specified map is null.
575 * @throws IdentityException if any of the {@code keys} is a value object
576 */
577 public void putAll(Map<? extends K, ? extends V> m) {
578 int numKeysToBeAdded = m.size();
579 if (numKeysToBeAdded == 0)
580 return;
581
582 /*
583 * Expand the map if the map if the number of mappings to be added
584 * is greater than or equal to threshold. This is conservative; the
585 * obvious condition is (m.size() + size) >= threshold, but this
586 * condition could result in a map with twice the appropriate capacity,
587 * if the keys to be added overlap with the keys already in this map.
588 * By using the conservative calculation, we subject ourself
589 * to at most one extra resize.
590 */
591 if (numKeysToBeAdded > threshold) {
592 int targetCapacity = (int)Math.ceil(numKeysToBeAdded / (double)loadFactor);
593 if (targetCapacity > MAXIMUM_CAPACITY)
594 targetCapacity = MAXIMUM_CAPACITY;
595 int newCapacity = table.length;
|