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<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 value object
478 */
479 public V put(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 }
502
503 /**
504 * Rehashes the contents of this map into a new array with a
505 * larger capacity. This method is called automatically when the
506 * number of keys in this map reaches its threshold.
507 *
508 * If current capacity is MAXIMUM_CAPACITY, this method does not
509 * resize the map, but sets threshold to Integer.MAX_VALUE.
510 * This has the effect of preventing future calls.
511 *
512 * @param newCapacity the new capacity, MUST be a power of two;
513 * must be greater than current capacity unless current
514 * capacity is MAXIMUM_CAPACITY (in which case value
515 * is irrelevant).
516 */
517 void resize(int newCapacity) {
518 Entry<K,V>[] oldTable = getTable();
519 int oldCapacity = oldTable.length;
520 if (oldCapacity == MAXIMUM_CAPACITY) {
521 threshold = Integer.MAX_VALUE;
522 return;
523 }
524
525 Entry<K,V>[] newTable = newTable(newCapacity);
526 transfer(oldTable, newTable);
527 table = newTable;
528
529 /*
530 * If ignoring null elements and processing ref queue caused massive
531 * shrinkage, then restore old table. This should be rare, but avoids
532 * unbounded expansion of garbage-filled tables.
533 */
534 if (size >= threshold / 2) {
535 threshold = (int)(newCapacity * loadFactor);
536 } else {
537 expungeStaleEntries();
538 transfer(newTable, oldTable);
539 table = oldTable;
540 }
541 }
542
543 /** Transfers all entries from src to dest tables */
544 private void transfer(Entry<K,V>[] src, Entry<K,V>[] dest) {
545 for (int j = 0; j < src.length; ++j) {
546 Entry<K,V> e = src[j];
547 src[j] = null;
548 while (e != null) {
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;
596 while (newCapacity < targetCapacity)
597 newCapacity <<= 1;
598 if (newCapacity > table.length)
599 resize(newCapacity);
600 }
601
602 for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
603 put(e.getKey(), e.getValue());
604 }
605
606 /**
607 * Removes the mapping for a key from this weak hash map if it is present.
608 * More formally, if this map contains a mapping from key {@code k} to
609 * value {@code v} such that <code>(key==null ? k==null :
610 * key.equals(k))</code>, that mapping is removed. (The map can contain
611 * at most one such mapping.)
612 *
613 * <p>Returns the value to which this map previously associated the key,
614 * or {@code null} if the map contained no mapping for the key. A
615 * return value of {@code null} does not <i>necessarily</i> indicate
616 * that the map contained no mapping for the key; it's also possible
617 * that the map explicitly mapped the key to {@code null}.
618 *
619 * <p>The map will not contain a mapping for the specified key once the
620 * call returns.
621 *
622 * @param key key whose mapping is to be removed from the map
623 * @return the previous value associated with {@code key}, or
624 * {@code null} if there was no mapping for {@code key}
625 */
626 public V remove(Object key) {
627 Object k = maskNull(key);
628 int h = hash(k);
629 Entry<K,V>[] tab = getTable();
630 int i = indexFor(h, tab.length);
631 Entry<K,V> prev = tab[i];
632 Entry<K,V> e = prev;
633
634 while (e != null) {
635 Entry<K,V> next = e.next;
636 if (h == e.hash && matchesKey(e, k)) {
637 modCount++;
638 size--;
639 if (prev == e)
640 tab[i] = next;
641 else
642 prev.next = next;
643 return e.value;
644 }
645 prev = e;
646 e = next;
647 }
648
649 return null;
650 }
651
652 /** Special version of remove needed by Entry set */
653 boolean removeMapping(Object o) {
654 if (!(o instanceof Map.Entry<?, ?> entry))
655 return false;
656 Entry<K,V>[] tab = getTable();
657 Object k = maskNull(entry.getKey());
658 int h = hash(k);
659 int i = indexFor(h, tab.length);
660 Entry<K,V> prev = tab[i];
661 Entry<K,V> e = prev;
662
663 while (e != null) {
664 Entry<K,V> next = e.next;
665 if (h == e.hash && e.equals(entry)) {
666 modCount++;
667 size--;
668 if (prev == e)
669 tab[i] = next;
670 else
671 prev.next = next;
672 return true;
673 }
674 prev = e;
675 e = next;
676 }
677
678 return false;
679 }
680
681 /**
682 * Removes all of the mappings from this map.
683 * The map will be empty after this call returns.
684 */
685 public void clear() {
686 // clear out ref queue. We don't need to expunge entries
687 // since table is getting cleared.
688 while (queue.poll() != null)
689 ;
690
691 modCount++;
692 Arrays.fill(table, null);
693 size = 0;
694
695 // Allocation of array may have caused GC, which may have caused
696 // additional entries to go stale. Removing these entries from the
697 // reference queue will make them eligible for reclamation.
698 while (queue.poll() != null)
699 ;
700 }
701
702 /**
703 * Returns {@code true} if this map maps one or more keys to the
704 * specified value.
705 *
706 * @param value value whose presence in this map is to be tested
707 * @return {@code true} if this map maps one or more keys to the
708 * specified value
709 */
710 public boolean containsValue(Object value) {
711 if (value==null)
712 return containsNullValue();
713
714 Entry<K,V>[] tab = getTable();
715 for (int i = tab.length; i-- > 0;)
716 for (Entry<K,V> e = tab[i]; e != null; e = e.next)
717 if (value.equals(e.value))
718 return true;
719 return false;
720 }
721
722 /**
723 * Special-case code for containsValue with null argument
724 */
725 private boolean containsNullValue() {
726 Entry<K,V>[] tab = getTable();
727 for (int i = tab.length; i-- > 0;)
728 for (Entry<K,V> e = tab[i]; e != null; e = e.next)
729 if (e.value==null)
730 return true;
731 return false;
732 }
733
734 /**
735 * The entries in this hash table extend WeakReference, using its main ref
736 * field as the key.
737 */
738 private static class Entry<K,V> extends WeakReference<Object> implements Map.Entry<K,V> {
739 V value;
740 final int hash;
741 Entry<K,V> next;
742
743 /**
744 * Creates new entry.
745 */
746 Entry(Object key, V value,
747 ReferenceQueue<Object> queue,
748 int hash, Entry<K,V> next) {
749 super(key, queue);
750 this.value = value;
751 this.hash = hash;
752 this.next = next;
753 }
754
755 @SuppressWarnings("unchecked")
756 public K getKey() {
757 return (K) WeakHashMap.unmaskNull(get());
758 }
759
760 public V getValue() {
761 return value;
762 }
763
764 public V setValue(V newValue) {
765 V oldValue = value;
766 value = newValue;
767 return oldValue;
768 }
769
770 public boolean equals(Object o) {
771 if (!(o instanceof Map.Entry<?, ?> e))
772 return false;
773 K k1 = getKey();
774 Object k2 = e.getKey();
775 if (k1 == k2 || (k1 != null && k1.equals(k2))) {
776 V v1 = getValue();
777 Object v2 = e.getValue();
778 if (v1 == v2 || (v1 != null && v1.equals(v2)))
779 return true;
780 }
781 return false;
782 }
783
784 public int hashCode() {
785 K k = getKey();
786 V v = getValue();
787 return Objects.hashCode(k) ^ Objects.hashCode(v);
788 }
789
790 public String toString() {
791 return getKey() + "=" + getValue();
792 }
793 }
794
795 private abstract class HashIterator<T> implements Iterator<T> {
796 private int index;
797 private Entry<K,V> entry;
798 private Entry<K,V> lastReturned;
799 private int expectedModCount = modCount;
800
801 /**
802 * Strong reference needed to avoid disappearance of key
803 * between hasNext and next
804 */
805 private Object nextKey;
806
807 /**
808 * Strong reference needed to avoid disappearance of key
809 * between nextEntry() and any use of the entry
810 */
811 private Object currentKey;
812
813 HashIterator() {
814 index = isEmpty() ? 0 : table.length;
815 }
816
817 public boolean hasNext() {
818 Entry<K,V>[] t = table;
819
820 while (nextKey == null) {
821 Entry<K,V> e = entry;
822 int i = index;
823 while (e == null && i > 0)
824 e = t[--i];
825 entry = e;
826 index = i;
827 if (e == null) {
828 currentKey = null;
829 return false;
830 }
831 nextKey = e.get(); // hold on to key in strong ref
832 if (nextKey == null)
833 entry = entry.next;
834 }
835 return true;
836 }
837
838 /** The common parts of next() across different types of iterators */
839 protected Entry<K,V> nextEntry() {
840 if (modCount != expectedModCount)
841 throw new ConcurrentModificationException();
842 if (nextKey == null && !hasNext())
843 throw new NoSuchElementException();
844
845 lastReturned = entry;
846 entry = entry.next;
847 currentKey = nextKey;
848 nextKey = null;
849 return lastReturned;
850 }
851
852 public void remove() {
853 if (lastReturned == null)
854 throw new IllegalStateException();
855 if (modCount != expectedModCount)
856 throw new ConcurrentModificationException();
857
858 WeakHashMap.this.remove(currentKey);
859 expectedModCount = modCount;
860 lastReturned = null;
861 currentKey = null;
862 }
863
864 }
865
866 private class ValueIterator extends HashIterator<V> {
867 public V next() {
868 return nextEntry().value;
869 }
870 }
871
872 private class KeyIterator extends HashIterator<K> {
873 public K next() {
874 return nextEntry().getKey();
875 }
876 }
877
878 private class EntryIterator extends HashIterator<Map.Entry<K,V>> {
879 public Map.Entry<K,V> next() {
880 return nextEntry();
881 }
882 }
883
884 // Views
885
886 private transient Set<Map.Entry<K,V>> entrySet;
887
888 /**
889 * Returns a {@link Set} view of the keys contained in this map.
890 * The set is backed by the map, so changes to the map are
891 * reflected in the set, and vice-versa. If the map is modified
892 * while an iteration over the set is in progress (except through
893 * the iterator's own {@code remove} operation), the results of
894 * the iteration are undefined. The set supports element removal,
895 * which removes the corresponding mapping from the map, via the
896 * {@code Iterator.remove}, {@code Set.remove},
897 * {@code removeAll}, {@code retainAll}, and {@code clear}
898 * operations. It does not support the {@code add} or {@code addAll}
899 * operations.
900 */
901 public Set<K> keySet() {
902 Set<K> ks = keySet;
903 if (ks == null) {
904 ks = new KeySet();
905 keySet = ks;
906 }
907 return ks;
908 }
909
910 private class KeySet extends AbstractSet<K> {
911 public Iterator<K> iterator() {
912 return new KeyIterator();
913 }
914
915 public int size() {
916 return WeakHashMap.this.size();
917 }
918
919 public boolean contains(Object o) {
920 return containsKey(o);
921 }
922
923 public boolean remove(Object o) {
924 if (containsKey(o)) {
925 WeakHashMap.this.remove(o);
926 return true;
927 }
928 else
929 return false;
930 }
931
932 public void clear() {
933 WeakHashMap.this.clear();
934 }
935
936 public Spliterator<K> spliterator() {
937 return new KeySpliterator<>(WeakHashMap.this, 0, -1, 0, 0);
938 }
939 }
940
941 /**
942 * Returns a {@link Collection} view of the values contained in this map.
943 * The collection is backed by the map, so changes to the map are
944 * reflected in the collection, and vice-versa. If the map is
945 * modified while an iteration over the collection is in progress
946 * (except through the iterator's own {@code remove} operation),
947 * the results of the iteration are undefined. The collection
948 * supports element removal, which removes the corresponding
949 * mapping from the map, via the {@code Iterator.remove},
950 * {@code Collection.remove}, {@code removeAll},
951 * {@code retainAll} and {@code clear} operations. It does not
952 * support the {@code add} or {@code addAll} operations.
953 */
954 public Collection<V> values() {
955 Collection<V> vs = values;
956 if (vs == null) {
957 vs = new Values();
958 values = vs;
959 }
960 return vs;
961 }
962
963 private class Values extends AbstractCollection<V> {
964 public Iterator<V> iterator() {
965 return new ValueIterator();
966 }
967
968 public int size() {
969 return WeakHashMap.this.size();
970 }
971
972 public boolean contains(Object o) {
973 return containsValue(o);
974 }
975
976 public void clear() {
977 WeakHashMap.this.clear();
978 }
979
980 public Spliterator<V> spliterator() {
981 return new ValueSpliterator<>(WeakHashMap.this, 0, -1, 0, 0);
982 }
983 }
984
985 /**
986 * Returns a {@link Set} view of the mappings contained in this map.
987 * The set is backed by the map, so changes to the map are
988 * reflected in the set, and vice-versa. If the map is modified
989 * while an iteration over the set is in progress (except through
990 * the iterator's own {@code remove} operation, or through the
991 * {@code setValue} operation on a map entry returned by the
992 * iterator) the results of the iteration are undefined. The set
993 * supports element removal, which removes the corresponding
994 * mapping from the map, via the {@code Iterator.remove},
995 * {@code Set.remove}, {@code removeAll}, {@code retainAll} and
996 * {@code clear} operations. It does not support the
997 * {@code add} or {@code addAll} operations.
998 */
999 public Set<Map.Entry<K,V>> entrySet() {
1000 Set<Map.Entry<K,V>> es = entrySet;
1001 return es != null ? es : (entrySet = new EntrySet());
1002 }
1003
1004 private class EntrySet extends AbstractSet<Map.Entry<K,V>> {
1005 public Iterator<Map.Entry<K,V>> iterator() {
1006 return new EntryIterator();
1007 }
1008
1009 public boolean contains(Object o) {
1010 return o instanceof Map.Entry<?, ?> e
1011 && getEntry(e.getKey()) != null
1012 && getEntry(e.getKey()).equals(e);
1013 }
1014
1015 public boolean remove(Object o) {
1016 return removeMapping(o);
1017 }
1018
1019 public int size() {
1020 return WeakHashMap.this.size();
1021 }
1022
1023 public void clear() {
1024 WeakHashMap.this.clear();
1025 }
1026
1027 private List<Map.Entry<K,V>> deepCopy() {
1028 List<Map.Entry<K,V>> list = new ArrayList<>(size());
1029 for (Map.Entry<K,V> e : this)
1030 list.add(new AbstractMap.SimpleEntry<>(e));
1031 return list;
1032 }
1033
1034 public Object[] toArray() {
1035 return deepCopy().toArray();
1036 }
1037
1038 public <T> T[] toArray(T[] a) {
1039 return deepCopy().toArray(a);
1040 }
1041
1042 public Spliterator<Map.Entry<K,V>> spliterator() {
1043 return new EntrySpliterator<>(WeakHashMap.this, 0, -1, 0, 0);
1044 }
1045 }
1046
1047 @SuppressWarnings("unchecked")
1048 @Override
1049 public void forEach(BiConsumer<? super K, ? super V> action) {
1050 Objects.requireNonNull(action);
1051 int expectedModCount = modCount;
1052
1053 Entry<K, V>[] tab = getTable();
1054 for (Entry<K, V> entry : tab) {
1055 while (entry != null) {
1056 Object key = entry.get();
1057 if (key != null) {
1058 action.accept((K)WeakHashMap.unmaskNull(key), entry.value);
1059 }
1060 entry = entry.next;
1061
1062 if (expectedModCount != modCount) {
1063 throw new ConcurrentModificationException();
1064 }
1065 }
1066 }
1067 }
1068
1069 @SuppressWarnings("unchecked")
1070 @Override
1071 public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
1072 Objects.requireNonNull(function);
1073 int expectedModCount = modCount;
1074
1075 Entry<K, V>[] tab = getTable();
1076 for (Entry<K, V> entry : tab) {
1077 while (entry != null) {
1078 Object key = entry.get();
1079 if (key != null) {
1080 entry.value = function.apply((K)WeakHashMap.unmaskNull(key), entry.value);
1081 }
1082 entry = entry.next;
1083
1084 if (expectedModCount != modCount) {
1085 throw new ConcurrentModificationException();
1086 }
1087 }
1088 }
1089 }
1090
1091 /**
1092 * Similar form as other hash Spliterators, but skips dead
1093 * elements.
1094 */
1095 static class WeakHashMapSpliterator<K,V> {
1096 final WeakHashMap<K,V> map;
1097 WeakHashMap.Entry<K,V> current; // current node
1098 int index; // current index, modified on advance/split
1099 int fence; // -1 until first use; then one past last index
1100 int est; // size estimate
1101 int expectedModCount; // for comodification checks
1102
1103 WeakHashMapSpliterator(WeakHashMap<K,V> m, int origin,
1104 int fence, int est,
1105 int expectedModCount) {
1106 this.map = m;
1107 this.index = origin;
1108 this.fence = fence;
1109 this.est = est;
1110 this.expectedModCount = expectedModCount;
1111 }
1112
1113 final int getFence() { // initialize fence and size on first use
1114 int hi;
1115 if ((hi = fence) < 0) {
1116 WeakHashMap<K,V> m = map;
1117 est = m.size();
1118 expectedModCount = m.modCount;
1119 hi = fence = m.table.length;
1120 }
1121 return hi;
1122 }
1123
1124 public final long estimateSize() {
1125 getFence(); // force init
1126 return (long) est;
1127 }
1128 }
1129
1130 static final class KeySpliterator<K,V>
1131 extends WeakHashMapSpliterator<K,V>
1132 implements Spliterator<K> {
1133 KeySpliterator(WeakHashMap<K,V> m, int origin, int fence, int est,
1134 int expectedModCount) {
1135 super(m, origin, fence, est, expectedModCount);
1136 }
1137
1138 public KeySpliterator<K,V> trySplit() {
1139 int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
1140 return (lo >= mid) ? null :
1141 new KeySpliterator<>(map, lo, index = mid, est >>>= 1,
1142 expectedModCount);
1143 }
1144
1145 public void forEachRemaining(Consumer<? super K> action) {
1146 int i, hi, mc;
1147 if (action == null)
1148 throw new NullPointerException();
1149 WeakHashMap<K,V> m = map;
1150 WeakHashMap.Entry<K,V>[] tab = m.table;
1151 if ((hi = fence) < 0) {
1152 mc = expectedModCount = m.modCount;
1153 hi = fence = tab.length;
1154 }
1155 else
1156 mc = expectedModCount;
1157 if (tab.length >= hi && (i = index) >= 0 &&
1158 (i < (index = hi) || current != null)) {
1159 WeakHashMap.Entry<K,V> p = current;
1160 current = null; // exhaust
1161 do {
1162 if (p == null)
1163 p = tab[i++];
1164 else {
1165 Object x = p.get();
1166 p = p.next;
1167 if (x != null) {
1168 @SuppressWarnings("unchecked") K k =
1169 (K) WeakHashMap.unmaskNull(x);
1170 action.accept(k);
1171 }
1172 }
1173 } while (p != null || i < hi);
1174 }
1175 if (m.modCount != mc)
1176 throw new ConcurrentModificationException();
1177 }
1178
1179 public boolean tryAdvance(Consumer<? super K> action) {
1180 int hi;
1181 if (action == null)
1182 throw new NullPointerException();
1183 WeakHashMap.Entry<K,V>[] tab = map.table;
1184 if (tab.length >= (hi = getFence()) && index >= 0) {
1185 while (current != null || index < hi) {
1186 if (current == null)
1187 current = tab[index++];
1188 else {
1189 Object x = current.get();
1190 current = current.next;
1191 if (x != null) {
1192 @SuppressWarnings("unchecked") K k =
1193 (K) WeakHashMap.unmaskNull(x);
1194 action.accept(k);
1195 if (map.modCount != expectedModCount)
1196 throw new ConcurrentModificationException();
1197 return true;
1198 }
1199 }
1200 }
1201 }
1202 return false;
1203 }
1204
1205 public int characteristics() {
1206 return Spliterator.DISTINCT;
1207 }
1208 }
1209
1210 static final class ValueSpliterator<K,V>
1211 extends WeakHashMapSpliterator<K,V>
1212 implements Spliterator<V> {
1213 ValueSpliterator(WeakHashMap<K,V> m, int origin, int fence, int est,
1214 int expectedModCount) {
1215 super(m, origin, fence, est, expectedModCount);
1216 }
1217
1218 public ValueSpliterator<K,V> trySplit() {
1219 int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
1220 return (lo >= mid) ? null :
1221 new ValueSpliterator<>(map, lo, index = mid, est >>>= 1,
1222 expectedModCount);
1223 }
1224
1225 public void forEachRemaining(Consumer<? super V> action) {
1226 int i, hi, mc;
1227 if (action == null)
1228 throw new NullPointerException();
1229 WeakHashMap<K,V> m = map;
1230 WeakHashMap.Entry<K,V>[] tab = m.table;
1231 if ((hi = fence) < 0) {
1232 mc = expectedModCount = m.modCount;
1233 hi = fence = tab.length;
1234 }
1235 else
1236 mc = expectedModCount;
1237 if (tab.length >= hi && (i = index) >= 0 &&
1238 (i < (index = hi) || current != null)) {
1239 WeakHashMap.Entry<K,V> p = current;
1240 current = null; // exhaust
1241 do {
1242 if (p == null)
1243 p = tab[i++];
1244 else {
1245 Object x = p.get();
1246 V v = p.value;
1247 p = p.next;
1248 if (x != null)
1249 action.accept(v);
1250 }
1251 } while (p != null || i < hi);
1252 }
1253 if (m.modCount != mc)
1254 throw new ConcurrentModificationException();
1255 }
1256
1257 public boolean tryAdvance(Consumer<? super V> action) {
1258 int hi;
1259 if (action == null)
1260 throw new NullPointerException();
1261 WeakHashMap.Entry<K,V>[] tab = map.table;
1262 if (tab.length >= (hi = getFence()) && index >= 0) {
1263 while (current != null || index < hi) {
1264 if (current == null)
1265 current = tab[index++];
1266 else {
1267 Object x = current.get();
1268 V v = current.value;
1269 current = current.next;
1270 if (x != null) {
1271 action.accept(v);
1272 if (map.modCount != expectedModCount)
1273 throw new ConcurrentModificationException();
1274 return true;
1275 }
1276 }
1277 }
1278 }
1279 return false;
1280 }
1281
1282 public int characteristics() {
1283 return 0;
1284 }
1285 }
1286
1287 static final class EntrySpliterator<K,V>
1288 extends WeakHashMapSpliterator<K,V>
1289 implements Spliterator<Map.Entry<K,V>> {
1290 EntrySpliterator(WeakHashMap<K,V> m, int origin, int fence, int est,
1291 int expectedModCount) {
1292 super(m, origin, fence, est, expectedModCount);
1293 }
1294
1295 public EntrySpliterator<K,V> trySplit() {
1296 int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
1297 return (lo >= mid) ? null :
1298 new EntrySpliterator<>(map, lo, index = mid, est >>>= 1,
1299 expectedModCount);
1300 }
1301
1302
1303 public void forEachRemaining(Consumer<? super Map.Entry<K, V>> action) {
1304 int i, hi, mc;
1305 if (action == null)
1306 throw new NullPointerException();
1307 WeakHashMap<K,V> m = map;
1308 WeakHashMap.Entry<K,V>[] tab = m.table;
1309 if ((hi = fence) < 0) {
1310 mc = expectedModCount = m.modCount;
1311 hi = fence = tab.length;
1312 }
1313 else
1314 mc = expectedModCount;
1315 if (tab.length >= hi && (i = index) >= 0 &&
1316 (i < (index = hi) || current != null)) {
1317 WeakHashMap.Entry<K,V> p = current;
1318 current = null; // exhaust
1319 do {
1320 if (p == null)
1321 p = tab[i++];
1322 else {
1323 Object x = p.get();
1324 V v = p.value;
1325 p = p.next;
1326 if (x != null) {
1327 @SuppressWarnings("unchecked") K k =
1328 (K) WeakHashMap.unmaskNull(x);
1329 action.accept
1330 (new AbstractMap.SimpleImmutableEntry<>(k, v));
1331 }
1332 }
1333 } while (p != null || i < hi);
1334 }
1335 if (m.modCount != mc)
1336 throw new ConcurrentModificationException();
1337 }
1338
1339 public boolean tryAdvance(Consumer<? super Map.Entry<K,V>> action) {
1340 int hi;
1341 if (action == null)
1342 throw new NullPointerException();
1343 WeakHashMap.Entry<K,V>[] tab = map.table;
1344 if (tab.length >= (hi = getFence()) && index >= 0) {
1345 while (current != null || index < hi) {
1346 if (current == null)
1347 current = tab[index++];
1348 else {
1349 Object x = current.get();
1350 V v = current.value;
1351 current = current.next;
1352 if (x != null) {
1353 @SuppressWarnings("unchecked") K k =
1354 (K) WeakHashMap.unmaskNull(x);
1355 action.accept
1356 (new AbstractMap.SimpleImmutableEntry<>(k, v));
1357 if (map.modCount != expectedModCount)
1358 throw new ConcurrentModificationException();
1359 return true;
1360 }
1361 }
1362 }
1363 }
1364 return false;
1365 }
1366
1367 public int characteristics() {
1368 return Spliterator.DISTINCT;
1369 }
1370 }
1371
1372 /**
1373 * Creates a new, empty WeakHashMap suitable for the expected number of mappings.
1374 * The returned map uses the default load factor of 0.75, and its initial capacity is
1375 * generally large enough so that the expected number of mappings can be added
1376 * without resizing the map.
1377 *
1378 * @param numMappings the expected number of mappings
1379 * @param <K> the type of keys maintained by the new map
1380 * @param <V> the type of mapped values
1381 * @return the newly created map
1382 * @throws IllegalArgumentException if numMappings is negative
1383 * @since 19
1384 */
1385 public static <K, V> WeakHashMap<K, V> newWeakHashMap(int numMappings) {
1386 if (numMappings < 0) {
1387 throw new IllegalArgumentException("Negative number of mappings: " + numMappings);
1388 }
1389 return new WeakHashMap<>(HashMap.calculateHashMapCapacity(numMappings));
1390 }
1391
1392 }