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