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>.
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.
66 *
67 * <p> The behavior of the {@code WeakHashMap} class depends in part upon
68 * the actions of the garbage collector, so several familiar (though not
69 * required) {@code Map} invariants do not hold for this class. Because
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
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 /**
161 * The maximum capacity, used if a higher value is implicitly specified
162 * by either of the constructors with arguments.
163 * MUST be a power of two <= 1<<30.
164 */
165 private static final int MAXIMUM_CAPACITY = 1 << 30;
166
167 /**
168 * The load factor used when none specified in constructor.
169 */
170 private static final float DEFAULT_LOAD_FACTOR = 0.75f;
171
172 /**
173 * The table, resized as necessary. Length MUST Always be a power of two.
174 */
175 Entry<K,V>[] table;
176
177 /**
178 * The number of key-value mappings contained in this weak hash map.
179 */
180 private int size;
181
182 /**
183 * The next size value at which to resize (capacity * load factor).
184 */
185 private int threshold;
186
187 /**
188 * The load factor for the hash table.
189 */
190 private final float loadFactor;
191
192 /**
193 * Reference queue for cleared WeakEntries
194 */
195 private final ReferenceQueue<Object> queue = new ReferenceQueue<>();
196
197 /**
198 * The number of times this WeakHashMap has been structurally modified.
199 * Structural modifications are those that change the number of
200 * mappings in the map or otherwise modify its internal structure
201 * (e.g., rehash). This field is used to make iterators on
202 * Collection-views of the map fail-fast.
203 *
204 * @see ConcurrentModificationException
205 */
206 int modCount;
207
208 @SuppressWarnings("unchecked")
209 private Entry<K,V>[] newTable(int n) {
210 return (Entry<K,V>[]) new Entry<?,?>[n];
211 }
212
213 /**
214 * Constructs a new, empty {@code WeakHashMap} with the given initial
215 * capacity and the given load factor.
216 *
217 * @apiNote
218 * To create a {@code WeakHashMap} with an initial capacity that accommodates
219 * an expected number of mappings, use {@link #newWeakHashMap(int) newWeakHashMap}.
220 *
221 * @param initialCapacity The initial capacity of the {@code WeakHashMap}
222 * @param loadFactor The load factor of the {@code WeakHashMap}
223 * @throws IllegalArgumentException if the initial capacity is negative,
224 * or if the load factor is nonpositive.
225 */
226 public WeakHashMap(int initialCapacity, float loadFactor) {
227 if (initialCapacity < 0)
228 throw new IllegalArgumentException("Illegal Initial Capacity: "+
229 initialCapacity);
230 if (initialCapacity > MAXIMUM_CAPACITY)
231 initialCapacity = MAXIMUM_CAPACITY;
232
233 if (loadFactor <= 0 || Float.isNaN(loadFactor))
234 throw new IllegalArgumentException("Illegal Load factor: "+
235 loadFactor);
236 int capacity = HashMap.tableSizeFor(initialCapacity);
237 table = newTable(capacity);
238 this.loadFactor = loadFactor;
239 threshold = (int)(capacity * loadFactor);
240 }
241
242 /**
243 * Constructs a new, empty {@code WeakHashMap} with the given initial
244 * capacity and the default load factor (0.75).
245 *
246 * @apiNote
247 * To create a {@code WeakHashMap} with an initial capacity that accommodates
248 * an expected number of mappings, use {@link #newWeakHashMap(int) newWeakHashMap}.
249 *
250 * @param initialCapacity The initial capacity of the {@code WeakHashMap}
251 * @throws IllegalArgumentException if the initial capacity is negative
252 */
253 public WeakHashMap(int initialCapacity) {
254 this(initialCapacity, DEFAULT_LOAD_FACTOR);
255 }
256
257 /**
258 * Constructs a new, empty {@code WeakHashMap} with the default initial
259 * capacity (16) and load factor (0.75).
260 */
261 public WeakHashMap() {
262 this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
263 }
264
265 /**
266 * Constructs a new {@code WeakHashMap} with the same mappings as the
267 * specified map. The {@code WeakHashMap} is created with the default
268 * load factor (0.75) and an initial capacity sufficient to hold the
269 * mappings in the specified map.
270 *
271 * @param m the map whose mappings are to be placed in this map
272 * @throws NullPointerException if the specified map is null
273 * @since 1.3
274 */
275 @SuppressWarnings("this-escape")
276 public WeakHashMap(Map<? extends K, ? extends V> m) {
277 this(Math.max((int) Math.ceil(m.size() / (double)DEFAULT_LOAD_FACTOR),
278 DEFAULT_INITIAL_CAPACITY),
279 DEFAULT_LOAD_FACTOR);
280 putAll(m);
281 }
282
283 // internal utilities
284
285 /**
286 * Value representing null keys inside tables.
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();
329
330 // This function ensures that hashCodes that differ only by
331 // constant multiples at each bit position have a bounded
332 // number of collisions (approximately 8 at default load factor).
333 h ^= (h >>> 20) ^ (h >>> 12);
334 return h ^ (h >>> 7) ^ (h >>> 4);
335 }
336
337 /**
338 * Returns index for hash code h.
339 */
340 private static int indexFor(int h, int length) {
341 return h & (length-1);
342 }
343
344 /**
345 * Expunges stale entries from the table.
346 */
347 private void expungeStaleEntries() {
348 for (Object x; (x = queue.poll()) != null; ) {
349 synchronized (queue) {
350 @SuppressWarnings("unchecked")
351 Entry<K,V> e = (Entry<K,V>) x;
352 int i = indexFor(e.hash, table.length);
353
354 Entry<K,V> prev = table[i];
355 Entry<K,V> p = prev;
356 while (p != null) {
357 Entry<K,V> next = p.next;
358 if (p == e) {
359 if (prev == e)
360 table[i] = next;
361 else
362 prev.next = next;
363 // Must not null out e.next;
364 // stale entries may be in use by a HashIterator
365 e.value = null; // Help GC
366 size--;
367 break;
368 }
369 prev = p;
370 p = next;
371 }
372 }
373 }
374 }
375
376 /**
377 * Returns the table after first expunging stale entries.
378 */
379 private Entry<K,V>[] getTable() {
380 expungeStaleEntries();
381 return table;
382 }
383
384 /**
385 * Returns the number of key-value mappings in this map.
386 * This result is a snapshot, and may not reflect unprocessed
387 * entries that will be removed before next attempted access
388 * because they are no longer referenced.
389 */
390 public int size() {
391 if (size == 0)
392 return 0;
393 expungeStaleEntries();
394 return size;
395 }
396
397 /**
398 * Returns {@code true} if this map contains no key-value mappings.
399 * This result is a snapshot, and may not reflect unprocessed
400 * entries that will be removed before next attempted access
401 * because they are no longer referenced.
402 */
403 public boolean isEmpty() {
404 return size() == 0;
405 }
406
407 /**
408 * Returns the value to which the specified key is mapped,
409 * or {@code null} if this map contains no mapping for the key.
410 *
411 * <p>More formally, if this map contains a mapping from a key
412 * {@code k} to a value {@code v} such that
413 * {@code Objects.equals(key, k)},
414 * then this method returns {@code v}; otherwise
415 * it returns {@code null}. (There can be at most one such mapping.)
416 *
417 * <p>A return value of {@code null} does not <i>necessarily</i>
418 * indicate that the map contains no mapping for the key; it's also
419 * possible that the map explicitly maps the key to {@code null}.
420 * The {@link #containsKey containsKey} operation may be used to
421 * distinguish these two cases.
422 *
423 * @see #put(Object, Object)
424 */
425 public V get(Object key) {
426 Object k = maskNull(key);
427 int h = hash(k);
428 Entry<K,V>[] tab = getTable();
429 int index = indexFor(h, tab.length);
430 Entry<K,V> e = tab[index];
431 while (e != null) {
432 if (e.hash == h && matchesKey(e, k))
433 return e.value;
434 e = e.next;
435 }
436 return null;
437 }
438
439 /**
440 * Returns {@code true} if this map contains a mapping for the
441 * specified key.
442 *
443 * @param key The key whose presence in this map is to be tested
444 * @return {@code true} if there is a mapping for {@code key};
445 * {@code false} otherwise
446 */
447 public boolean containsKey(Object key) {
448 return getEntry(key) != null;
449 }
450
451 /**
452 * Returns the entry associated with the specified key in this map.
453 * Returns null if the map contains no mapping for this key.
454 */
455 Entry<K,V> getEntry(Object key) {
456 Object k = maskNull(key);
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 {@link
478 * java.util.Objects#isValueObject(Object) value object}
479 */
480 public V put(@jdk.internal.RequiresIdentity K key, V value) {
481 Object k = maskNull(key);
482 Objects.requireIdentity(k);
483 int h = hash(k);
484 Entry<K,V>[] tab = getTable();
485 int i = indexFor(h, tab.length);
486
487 for (Entry<K,V> e = tab[i]; e != null; e = e.next) {
488 if (h == e.hash && matchesKey(e, k)) {
489 V oldValue = e.value;
490 if (value != oldValue)
491 e.value = value;
492 return oldValue;
493 }
494 }
495
496 modCount++;
497 Entry<K,V> e = tab[i];
498 tab[i] = new Entry<>(k, value, queue, h, e);
499 if (++size > threshold)
500 resize(tab.length * 2);
501 return null;
502 }
503
504 /**
505 * Rehashes the contents of this map into a new array with a
506 * larger capacity. This method is called automatically when the
507 * number of keys in this map reaches its threshold.
508 *
509 * If current capacity is MAXIMUM_CAPACITY, this method does not
510 * resize the map, but sets threshold to Integer.MAX_VALUE.
511 * This has the effect of preventing future calls.
512 *
513 * @param newCapacity the new capacity, MUST be a power of two;
514 * must be greater than current capacity unless current
515 * capacity is MAXIMUM_CAPACITY (in which case value
516 * is irrelevant).
517 */
518 void resize(int newCapacity) {
519 Entry<K,V>[] oldTable = getTable();
520 int oldCapacity = oldTable.length;
521 if (oldCapacity == MAXIMUM_CAPACITY) {
522 threshold = Integer.MAX_VALUE;
523 return;
524 }
525
526 Entry<K,V>[] newTable = newTable(newCapacity);
527 transfer(oldTable, newTable);
528 table = newTable;
529
530 /*
531 * If ignoring null elements and processing ref queue caused massive
532 * shrinkage, then restore old table. This should be rare, but avoids
533 * unbounded expansion of garbage-filled tables.
534 */
535 if (size >= threshold / 2) {
536 threshold = (int)(newCapacity * loadFactor);
537 } else {
538 expungeStaleEntries();
539 transfer(newTable, oldTable);
540 table = oldTable;
541 }
542 }
543
544 /** Transfers all entries from src to dest tables */
545 private void transfer(Entry<K,V>[] src, Entry<K,V>[] dest) {
546 for (int j = 0; j < src.length; ++j) {
547 Entry<K,V> e = src[j];
548 src[j] = null;
549 while (e != null) {
550 Entry<K,V> next = e.next;
551 if (e.refersTo(null)) {
552 e.next = null; // Help GC
553 e.value = null; // " "
554 size--;
555 } else {
556 int i = indexFor(e.hash, dest.length);
557 e.next = dest[i];
558 dest[i] = e;
559 }
560 e = next;
561 }
562 }
563 }
564
565 /**
566 * Copies all of the mappings from the specified map to this map.
567 * These mappings will replace any mappings that this map had for any
568 * of the keys currently in the specified map.
569 *
570 * @apiNote If the specified map contains keys that are {@linkplain Objects#isValueObject value objects}
571 * an {@linkplain IdentityException} is thrown when the first value object key is encountered.
572 * Zero or more mappings may have already been copied to 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;
597 while (newCapacity < targetCapacity)
598 newCapacity <<= 1;
599 if (newCapacity > table.length)
600 resize(newCapacity);
601 }
602
603 for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
604 put(e.getKey(), e.getValue());
605 }
606
607 /**
608 * Removes the mapping for a key from this weak hash map if it is present.
609 * More formally, if this map contains a mapping from key {@code k} to
610 * value {@code v} such that <code>(key==null ? k==null :
611 * key.equals(k))</code>, that mapping is removed. (The map can contain
612 * at most one such mapping.)
613 *
614 * <p>Returns the value to which this map previously associated the key,
615 * or {@code null} if the map contained no mapping for the key. A
616 * return value of {@code null} does not <i>necessarily</i> indicate
617 * that the map contained no mapping for the key; it's also possible
618 * that the map explicitly mapped the key to {@code null}.
619 *
620 * <p>The map will not contain a mapping for the specified key once the
621 * call returns.
622 *
623 * @param key key whose mapping is to be removed from the map
624 * @return the previous value associated with {@code key}, or
625 * {@code null} if there was no mapping for {@code key}
626 */
627 public V remove(Object key) {
628 Object k = maskNull(key);
629 int h = hash(k);
630 Entry<K,V>[] tab = getTable();
631 int i = indexFor(h, tab.length);
632 Entry<K,V> prev = tab[i];
633 Entry<K,V> e = prev;
634
635 while (e != null) {
636 Entry<K,V> next = e.next;
637 if (h == e.hash && matchesKey(e, k)) {
638 modCount++;
639 size--;
640 if (prev == e)
641 tab[i] = next;
642 else
643 prev.next = next;
644 return e.value;
645 }
646 prev = e;
647 e = next;
648 }
649
650 return null;
651 }
652
653 /** Special version of remove needed by Entry set */
654 boolean removeMapping(Object o) {
655 if (!(o instanceof Map.Entry<?, ?> entry))
656 return false;
657 Entry<K,V>[] tab = getTable();
658 Object k = maskNull(entry.getKey());
659 int h = hash(k);
660 int i = indexFor(h, tab.length);
661 Entry<K,V> prev = tab[i];
662 Entry<K,V> e = prev;
663
664 while (e != null) {
665 Entry<K,V> next = e.next;
666 if (h == e.hash && e.equals(entry)) {
667 modCount++;
668 size--;
669 if (prev == e)
670 tab[i] = next;
671 else
672 prev.next = next;
673 return true;
674 }
675 prev = e;
676 e = next;
677 }
678
679 return false;
680 }
681
682 /**
683 * Removes all of the mappings from this map.
684 * The map will be empty after this call returns.
685 */
686 public void clear() {
687 // clear out ref queue. We don't need to expunge entries
688 // since table is getting cleared.
689 while (queue.poll() != null)
690 ;
691
692 modCount++;
693 Arrays.fill(table, null);
694 size = 0;
695
696 // Allocation of array may have caused GC, which may have caused
697 // additional entries to go stale. Removing these entries from the
698 // reference queue will make them eligible for reclamation.
699 while (queue.poll() != null)
700 ;
701 }
702
703 /**
704 * Returns {@code true} if this map maps one or more keys to the
705 * specified value.
706 *
707 * @param value value whose presence in this map is to be tested
708 * @return {@code true} if this map maps one or more keys to the
709 * specified value
710 */
711 public boolean containsValue(Object value) {
712 if (value==null)
713 return containsNullValue();
714
715 Entry<K,V>[] tab = getTable();
716 for (int i = tab.length; i-- > 0;)
717 for (Entry<K,V> e = tab[i]; e != null; e = e.next)
718 if (value.equals(e.value))
719 return true;
720 return false;
721 }
722
723 /**
724 * Special-case code for containsValue with null argument
725 */
726 private boolean containsNullValue() {
727 Entry<K,V>[] tab = getTable();
728 for (int i = tab.length; i-- > 0;)
729 for (Entry<K,V> e = tab[i]; e != null; e = e.next)
730 if (e.value==null)
731 return true;
732 return false;
733 }
734
735 /**
736 * The entries in this hash table extend WeakReference, using its main ref
737 * field as the key.
738 */
739 private static class Entry<K,V> extends WeakReference<Object> implements Map.Entry<K,V> {
740 V value;
741 final int hash;
742 Entry<K,V> next;
743
744 /**
745 * Creates new entry.
746 */
747 Entry(Object key, V value,
748 ReferenceQueue<Object> queue,
749 int hash, Entry<K,V> next) {
750 super(key, queue);
751 this.value = value;
752 this.hash = hash;
753 this.next = next;
754 }
755
756 @SuppressWarnings("unchecked")
757 public K getKey() {
758 return (K) WeakHashMap.unmaskNull(get());
759 }
760
761 public V getValue() {
762 return value;
763 }
764
765 public V setValue(V newValue) {
766 V oldValue = value;
767 value = newValue;
768 return oldValue;
769 }
770
771 public boolean equals(Object o) {
772 if (!(o instanceof Map.Entry<?, ?> e))
773 return false;
774 K k1 = getKey();
775 Object k2 = e.getKey();
776 if (k1 == k2 || (k1 != null && k1.equals(k2))) {
777 V v1 = getValue();
778 Object v2 = e.getValue();
779 if (v1 == v2 || (v1 != null && v1.equals(v2)))
780 return true;
781 }
782 return false;
783 }
784
785 public int hashCode() {
786 K k = getKey();
787 V v = getValue();
788 return Objects.hashCode(k) ^ Objects.hashCode(v);
789 }
790
791 public String toString() {
792 return getKey() + "=" + getValue();
793 }
794 }
795
796 private abstract class HashIterator<T> implements Iterator<T> {
797 private int index;
798 private Entry<K,V> entry;
799 private Entry<K,V> lastReturned;
800 private int expectedModCount = modCount;
801
802 /**
803 * Strong reference needed to avoid disappearance of key
804 * between hasNext and next
805 */
806 private Object nextKey;
807
808 /**
809 * Strong reference needed to avoid disappearance of key
810 * between nextEntry() and any use of the entry
811 */
812 private Object currentKey;
813
814 HashIterator() {
815 index = isEmpty() ? 0 : table.length;
816 }
817
818 public boolean hasNext() {
819 Entry<K,V>[] t = table;
820
821 while (nextKey == null) {
822 Entry<K,V> e = entry;
823 int i = index;
824 while (e == null && i > 0)
825 e = t[--i];
826 entry = e;
827 index = i;
828 if (e == null) {
829 currentKey = null;
830 return false;
831 }
832 nextKey = e.get(); // hold on to key in strong ref
833 if (nextKey == null)
834 entry = entry.next;
835 }
836 return true;
837 }
838
839 /** The common parts of next() across different types of iterators */
840 protected Entry<K,V> nextEntry() {
841 if (modCount != expectedModCount)
842 throw new ConcurrentModificationException();
843 if (nextKey == null && !hasNext())
844 throw new NoSuchElementException();
845
846 lastReturned = entry;
847 entry = entry.next;
848 currentKey = nextKey;
849 nextKey = null;
850 return lastReturned;
851 }
852
853 public void remove() {
854 if (lastReturned == null)
855 throw new IllegalStateException();
856 if (modCount != expectedModCount)
857 throw new ConcurrentModificationException();
858
859 WeakHashMap.this.remove(currentKey);
860 expectedModCount = modCount;
861 lastReturned = null;
862 currentKey = null;
863 }
864
865 }
866
867 private class ValueIterator extends HashIterator<V> {
868 public V next() {
869 return nextEntry().value;
870 }
871 }
872
873 private class KeyIterator extends HashIterator<K> {
874 public K next() {
875 return nextEntry().getKey();
876 }
877 }
878
879 private class EntryIterator extends HashIterator<Map.Entry<K,V>> {
880 public Map.Entry<K,V> next() {
881 return nextEntry();
882 }
883 }
884
885 // Views
886
887 private transient Set<Map.Entry<K,V>> entrySet;
888
889 /**
890 * Returns a {@link Set} view of the keys contained in this map.
891 * The set is backed by the map, so changes to the map are
892 * reflected in the set, and vice-versa. If the map is modified
893 * while an iteration over the set is in progress (except through
894 * the iterator's own {@code remove} operation), the results of
895 * the iteration are undefined. The set supports element removal,
896 * which removes the corresponding mapping from the map, via the
897 * {@code Iterator.remove}, {@code Set.remove},
898 * {@code removeAll}, {@code retainAll}, and {@code clear}
899 * operations. It does not support the {@code add} or {@code addAll}
900 * operations.
901 */
902 public Set<K> keySet() {
903 Set<K> ks = keySet;
904 if (ks == null) {
905 ks = new KeySet();
906 keySet = ks;
907 }
908 return ks;
909 }
910
911 private class KeySet extends AbstractSet<K> {
912 public Iterator<K> iterator() {
913 return new KeyIterator();
914 }
915
916 public int size() {
917 return WeakHashMap.this.size();
918 }
919
920 public boolean contains(Object o) {
921 return containsKey(o);
922 }
923
924 public boolean remove(Object o) {
925 if (containsKey(o)) {
926 WeakHashMap.this.remove(o);
927 return true;
928 }
929 else
930 return false;
931 }
932
933 public void clear() {
934 WeakHashMap.this.clear();
935 }
936
937 public Spliterator<K> spliterator() {
938 return new KeySpliterator<>(WeakHashMap.this, 0, -1, 0, 0);
939 }
940 }
941
942 /**
943 * Returns a {@link Collection} view of the values contained in this map.
944 * The collection is backed by the map, so changes to the map are
945 * reflected in the collection, and vice-versa. If the map is
946 * modified while an iteration over the collection is in progress
947 * (except through the iterator's own {@code remove} operation),
948 * the results of the iteration are undefined. The collection
949 * supports element removal, which removes the corresponding
950 * mapping from the map, via the {@code Iterator.remove},
951 * {@code Collection.remove}, {@code removeAll},
952 * {@code retainAll} and {@code clear} operations. It does not
953 * support the {@code add} or {@code addAll} operations.
954 */
955 public Collection<V> values() {
956 Collection<V> vs = values;
957 if (vs == null) {
958 vs = new Values();
959 values = vs;
960 }
961 return vs;
962 }
963
964 private class Values extends AbstractCollection<V> {
965 public Iterator<V> iterator() {
966 return new ValueIterator();
967 }
968
969 public int size() {
970 return WeakHashMap.this.size();
971 }
972
973 public boolean contains(Object o) {
974 return containsValue(o);
975 }
976
977 public void clear() {
978 WeakHashMap.this.clear();
979 }
980
981 public Spliterator<V> spliterator() {
982 return new ValueSpliterator<>(WeakHashMap.this, 0, -1, 0, 0);
983 }
984 }
985
986 /**
987 * Returns a {@link Set} view of the mappings contained in this map.
988 * The set is backed by the map, so changes to the map are
989 * reflected in the set, and vice-versa. If the map is modified
990 * while an iteration over the set is in progress (except through
991 * the iterator's own {@code remove} operation, or through the
992 * {@code setValue} operation on a map entry returned by the
993 * iterator) the results of the iteration are undefined. The set
994 * supports element removal, which removes the corresponding
995 * mapping from the map, via the {@code Iterator.remove},
996 * {@code Set.remove}, {@code removeAll}, {@code retainAll} and
997 * {@code clear} operations. It does not support the
998 * {@code add} or {@code addAll} operations.
999 */
1000 public Set<Map.Entry<K,V>> entrySet() {
1001 Set<Map.Entry<K,V>> es = entrySet;
1002 return es != null ? es : (entrySet = new EntrySet());
1003 }
1004
1005 private class EntrySet extends AbstractSet<Map.Entry<K,V>> {
1006 public Iterator<Map.Entry<K,V>> iterator() {
1007 return new EntryIterator();
1008 }
1009
1010 public boolean contains(Object o) {
1011 return o instanceof Map.Entry<?, ?> e
1012 && getEntry(e.getKey()) != null
1013 && getEntry(e.getKey()).equals(e);
1014 }
1015
1016 public boolean remove(Object o) {
1017 return removeMapping(o);
1018 }
1019
1020 public int size() {
1021 return WeakHashMap.this.size();
1022 }
1023
1024 public void clear() {
1025 WeakHashMap.this.clear();
1026 }
1027
1028 private List<Map.Entry<K,V>> deepCopy() {
1029 List<Map.Entry<K,V>> list = new ArrayList<>(size());
1030 for (Map.Entry<K,V> e : this)
1031 list.add(new AbstractMap.SimpleEntry<>(e));
1032 return list;
1033 }
1034
1035 public Object[] toArray() {
1036 return deepCopy().toArray();
1037 }
1038
1039 public <T> T[] toArray(T[] a) {
1040 return deepCopy().toArray(a);
1041 }
1042
1043 public Spliterator<Map.Entry<K,V>> spliterator() {
1044 return new EntrySpliterator<>(WeakHashMap.this, 0, -1, 0, 0);
1045 }
1046 }
1047
1048 @SuppressWarnings("unchecked")
1049 @Override
1050 public void forEach(BiConsumer<? super K, ? super V> action) {
1051 Objects.requireNonNull(action);
1052 int expectedModCount = modCount;
1053
1054 Entry<K, V>[] tab = getTable();
1055 for (Entry<K, V> entry : tab) {
1056 while (entry != null) {
1057 Object key = entry.get();
1058 if (key != null) {
1059 action.accept((K)WeakHashMap.unmaskNull(key), entry.value);
1060 }
1061 entry = entry.next;
1062
1063 if (expectedModCount != modCount) {
1064 throw new ConcurrentModificationException();
1065 }
1066 }
1067 }
1068 }
1069
1070 @SuppressWarnings("unchecked")
1071 @Override
1072 public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
1073 Objects.requireNonNull(function);
1074 int expectedModCount = modCount;
1075
1076 Entry<K, V>[] tab = getTable();
1077 for (Entry<K, V> entry : tab) {
1078 while (entry != null) {
1079 Object key = entry.get();
1080 if (key != null) {
1081 entry.value = function.apply((K)WeakHashMap.unmaskNull(key), entry.value);
1082 }
1083 entry = entry.next;
1084
1085 if (expectedModCount != modCount) {
1086 throw new ConcurrentModificationException();
1087 }
1088 }
1089 }
1090 }
1091
1092 /**
1093 * Similar form as other hash Spliterators, but skips dead
1094 * elements.
1095 */
1096 static class WeakHashMapSpliterator<K,V> {
1097 final WeakHashMap<K,V> map;
1098 WeakHashMap.Entry<K,V> current; // current node
1099 int index; // current index, modified on advance/split
1100 int fence; // -1 until first use; then one past last index
1101 int est; // size estimate
1102 int expectedModCount; // for comodification checks
1103
1104 WeakHashMapSpliterator(WeakHashMap<K,V> m, int origin,
1105 int fence, int est,
1106 int expectedModCount) {
1107 this.map = m;
1108 this.index = origin;
1109 this.fence = fence;
1110 this.est = est;
1111 this.expectedModCount = expectedModCount;
1112 }
1113
1114 final int getFence() { // initialize fence and size on first use
1115 int hi;
1116 if ((hi = fence) < 0) {
1117 WeakHashMap<K,V> m = map;
1118 est = m.size();
1119 expectedModCount = m.modCount;
1120 hi = fence = m.table.length;
1121 }
1122 return hi;
1123 }
1124
1125 public final long estimateSize() {
1126 getFence(); // force init
1127 return (long) est;
1128 }
1129 }
1130
1131 static final class KeySpliterator<K,V>
1132 extends WeakHashMapSpliterator<K,V>
1133 implements Spliterator<K> {
1134 KeySpliterator(WeakHashMap<K,V> m, int origin, int fence, int est,
1135 int expectedModCount) {
1136 super(m, origin, fence, est, expectedModCount);
1137 }
1138
1139 public KeySpliterator<K,V> trySplit() {
1140 int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
1141 return (lo >= mid) ? null :
1142 new KeySpliterator<>(map, lo, index = mid, est >>>= 1,
1143 expectedModCount);
1144 }
1145
1146 public void forEachRemaining(Consumer<? super K> action) {
1147 int i, hi, mc;
1148 if (action == null)
1149 throw new NullPointerException();
1150 WeakHashMap<K,V> m = map;
1151 WeakHashMap.Entry<K,V>[] tab = m.table;
1152 if ((hi = fence) < 0) {
1153 mc = expectedModCount = m.modCount;
1154 hi = fence = tab.length;
1155 }
1156 else
1157 mc = expectedModCount;
1158 if (tab.length >= hi && (i = index) >= 0 &&
1159 (i < (index = hi) || current != null)) {
1160 WeakHashMap.Entry<K,V> p = current;
1161 current = null; // exhaust
1162 do {
1163 if (p == null)
1164 p = tab[i++];
1165 else {
1166 Object x = p.get();
1167 p = p.next;
1168 if (x != null) {
1169 @SuppressWarnings("unchecked") K k =
1170 (K) WeakHashMap.unmaskNull(x);
1171 action.accept(k);
1172 }
1173 }
1174 } while (p != null || i < hi);
1175 }
1176 if (m.modCount != mc)
1177 throw new ConcurrentModificationException();
1178 }
1179
1180 public boolean tryAdvance(Consumer<? super K> action) {
1181 int hi;
1182 if (action == null)
1183 throw new NullPointerException();
1184 WeakHashMap.Entry<K,V>[] tab = map.table;
1185 if (tab.length >= (hi = getFence()) && index >= 0) {
1186 while (current != null || index < hi) {
1187 if (current == null)
1188 current = tab[index++];
1189 else {
1190 Object x = current.get();
1191 current = current.next;
1192 if (x != null) {
1193 @SuppressWarnings("unchecked") K k =
1194 (K) WeakHashMap.unmaskNull(x);
1195 action.accept(k);
1196 if (map.modCount != expectedModCount)
1197 throw new ConcurrentModificationException();
1198 return true;
1199 }
1200 }
1201 }
1202 }
1203 return false;
1204 }
1205
1206 public int characteristics() {
1207 return Spliterator.DISTINCT;
1208 }
1209 }
1210
1211 static final class ValueSpliterator<K,V>
1212 extends WeakHashMapSpliterator<K,V>
1213 implements Spliterator<V> {
1214 ValueSpliterator(WeakHashMap<K,V> m, int origin, int fence, int est,
1215 int expectedModCount) {
1216 super(m, origin, fence, est, expectedModCount);
1217 }
1218
1219 public ValueSpliterator<K,V> trySplit() {
1220 int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
1221 return (lo >= mid) ? null :
1222 new ValueSpliterator<>(map, lo, index = mid, est >>>= 1,
1223 expectedModCount);
1224 }
1225
1226 public void forEachRemaining(Consumer<? super V> action) {
1227 int i, hi, mc;
1228 if (action == null)
1229 throw new NullPointerException();
1230 WeakHashMap<K,V> m = map;
1231 WeakHashMap.Entry<K,V>[] tab = m.table;
1232 if ((hi = fence) < 0) {
1233 mc = expectedModCount = m.modCount;
1234 hi = fence = tab.length;
1235 }
1236 else
1237 mc = expectedModCount;
1238 if (tab.length >= hi && (i = index) >= 0 &&
1239 (i < (index = hi) || current != null)) {
1240 WeakHashMap.Entry<K,V> p = current;
1241 current = null; // exhaust
1242 do {
1243 if (p == null)
1244 p = tab[i++];
1245 else {
1246 Object x = p.get();
1247 V v = p.value;
1248 p = p.next;
1249 if (x != null)
1250 action.accept(v);
1251 }
1252 } while (p != null || i < hi);
1253 }
1254 if (m.modCount != mc)
1255 throw new ConcurrentModificationException();
1256 }
1257
1258 public boolean tryAdvance(Consumer<? super V> action) {
1259 int hi;
1260 if (action == null)
1261 throw new NullPointerException();
1262 WeakHashMap.Entry<K,V>[] tab = map.table;
1263 if (tab.length >= (hi = getFence()) && index >= 0) {
1264 while (current != null || index < hi) {
1265 if (current == null)
1266 current = tab[index++];
1267 else {
1268 Object x = current.get();
1269 V v = current.value;
1270 current = current.next;
1271 if (x != null) {
1272 action.accept(v);
1273 if (map.modCount != expectedModCount)
1274 throw new ConcurrentModificationException();
1275 return true;
1276 }
1277 }
1278 }
1279 }
1280 return false;
1281 }
1282
1283 public int characteristics() {
1284 return 0;
1285 }
1286 }
1287
1288 static final class EntrySpliterator<K,V>
1289 extends WeakHashMapSpliterator<K,V>
1290 implements Spliterator<Map.Entry<K,V>> {
1291 EntrySpliterator(WeakHashMap<K,V> m, int origin, int fence, int est,
1292 int expectedModCount) {
1293 super(m, origin, fence, est, expectedModCount);
1294 }
1295
1296 public EntrySpliterator<K,V> trySplit() {
1297 int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
1298 return (lo >= mid) ? null :
1299 new EntrySpliterator<>(map, lo, index = mid, est >>>= 1,
1300 expectedModCount);
1301 }
1302
1303
1304 public void forEachRemaining(Consumer<? super Map.Entry<K, V>> action) {
1305 int i, hi, mc;
1306 if (action == null)
1307 throw new NullPointerException();
1308 WeakHashMap<K,V> m = map;
1309 WeakHashMap.Entry<K,V>[] tab = m.table;
1310 if ((hi = fence) < 0) {
1311 mc = expectedModCount = m.modCount;
1312 hi = fence = tab.length;
1313 }
1314 else
1315 mc = expectedModCount;
1316 if (tab.length >= hi && (i = index) >= 0 &&
1317 (i < (index = hi) || current != null)) {
1318 WeakHashMap.Entry<K,V> p = current;
1319 current = null; // exhaust
1320 do {
1321 if (p == null)
1322 p = tab[i++];
1323 else {
1324 Object x = p.get();
1325 V v = p.value;
1326 p = p.next;
1327 if (x != null) {
1328 @SuppressWarnings("unchecked") K k =
1329 (K) WeakHashMap.unmaskNull(x);
1330 action.accept
1331 (new AbstractMap.SimpleImmutableEntry<>(k, v));
1332 }
1333 }
1334 } while (p != null || i < hi);
1335 }
1336 if (m.modCount != mc)
1337 throw new ConcurrentModificationException();
1338 }
1339
1340 public boolean tryAdvance(Consumer<? super Map.Entry<K,V>> action) {
1341 int hi;
1342 if (action == null)
1343 throw new NullPointerException();
1344 WeakHashMap.Entry<K,V>[] tab = map.table;
1345 if (tab.length >= (hi = getFence()) && index >= 0) {
1346 while (current != null || index < hi) {
1347 if (current == null)
1348 current = tab[index++];
1349 else {
1350 Object x = current.get();
1351 V v = current.value;
1352 current = current.next;
1353 if (x != null) {
1354 @SuppressWarnings("unchecked") K k =
1355 (K) WeakHashMap.unmaskNull(x);
1356 action.accept
1357 (new AbstractMap.SimpleImmutableEntry<>(k, v));
1358 if (map.modCount != expectedModCount)
1359 throw new ConcurrentModificationException();
1360 return true;
1361 }
1362 }
1363 }
1364 }
1365 return false;
1366 }
1367
1368 public int characteristics() {
1369 return Spliterator.DISTINCT;
1370 }
1371 }
1372
1373 /**
1374 * Creates a new, empty WeakHashMap suitable for the expected number of mappings.
1375 * The returned map uses the default load factor of 0.75, and its initial capacity is
1376 * generally large enough so that the expected number of mappings can be added
1377 * without resizing the map.
1378 *
1379 * @param numMappings the expected number of mappings
1380 * @param <K> the type of keys maintained by the new map
1381 * @param <V> the type of mapped values
1382 * @return the newly created map
1383 * @throws IllegalArgumentException if numMappings is negative
1384 * @since 19
1385 */
1386 public static <K, V> WeakHashMap<K, V> newWeakHashMap(int numMappings) {
1387 if (numMappings < 0) {
1388 throw new IllegalArgumentException("Negative number of mappings: " + numMappings);
1389 }
1390 return new WeakHashMap<>(HashMap.calculateHashMapCapacity(numMappings));
1391 }
1392
1393 }