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