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
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 @SuppressWarnings("this-escape")
260 public WeakHashMap(Map<? extends K, ? extends V> m) {
261 this(Math.max((int) Math.ceil(m.size() / (double)DEFAULT_LOAD_FACTOR),
262 DEFAULT_INITIAL_CAPACITY),
263 DEFAULT_LOAD_FACTOR);
264 putAll(m);
265 }
266
267 // internal utilities
268
269 /**
270 * Value representing null keys inside tables.
271 */
272 private static final Object NULL_KEY = new Object();
273
274 /**
275 * Use NULL_KEY for key if it is null.
276 */
277 private static Object maskNull(Object key) {
278 return (key == null) ? NULL_KEY : key;
279 }
280
281 /**
282 * Returns internal representation of null key back to caller as null.
283 */
284 static Object unmaskNull(Object key) {
285 return (key == NULL_KEY) ? null : key;
286 }
287
288 /**
289 * Checks for equality of non-null reference x and possibly-null y. By
290 * default uses Object.equals.
291 */
292 private boolean matchesKey(Entry<K,V> e, Object key) {
293 // check if the given entry refers to the given key without
294 // keeping a strong reference to the entry's referent
295 if (e.refersTo(key)) return true;
296
297 // then check for equality if the referent is not cleared
298 Object k = e.get();
299 return k != null && key.equals(k);
300 }
301
302 /**
303 * Retrieve object hash code and applies a supplemental hash function to the
304 * result hash, which defends against poor quality hash functions. This is
305 * critical because HashMap uses power-of-two length hash tables, that
306 * otherwise encounter collisions for hashCodes that do not differ
307 * in lower bits.
308 */
309 final int hash(Object k) {
310 int h = k.hashCode();
311
312 // This function ensures that hashCodes that differ only by
313 // constant multiples at each bit position have a bounded
314 // number of collisions (approximately 8 at default load factor).
315 h ^= (h >>> 20) ^ (h >>> 12);
439 int h = hash(k);
440 Entry<K,V>[] tab = getTable();
441 int index = indexFor(h, tab.length);
442 Entry<K,V> e = tab[index];
443 while (e != null && !(e.hash == h && matchesKey(e, k)))
444 e = e.next;
445 return e;
446 }
447
448 /**
449 * Associates the specified value with the specified key in this map.
450 * If the map previously contained a mapping for this key, the old
451 * value is replaced.
452 *
453 * @param key key with which the specified value is to be associated.
454 * @param value value to be associated with the specified key.
455 * @return the previous value associated with {@code key}, or
456 * {@code null} if there was no mapping for {@code key}.
457 * (A {@code null} return can also indicate that the map
458 * previously associated {@code null} with {@code key}.)
459 */
460 public V put(K key, V value) {
461 Object k = maskNull(key);
462 int h = hash(k);
463 Entry<K,V>[] tab = getTable();
464 int i = indexFor(h, tab.length);
465
466 for (Entry<K,V> e = tab[i]; e != null; e = e.next) {
467 if (h == e.hash && matchesKey(e, k)) {
468 V oldValue = e.value;
469 if (value != oldValue)
470 e.value = value;
471 return oldValue;
472 }
473 }
474
475 modCount++;
476 Entry<K,V> e = tab[i];
477 tab[i] = new Entry<>(k, value, queue, h, e);
478 if (++size > threshold)
479 resize(tab.length * 2);
480 return null;
481 }
482
483 /**
484 * Rehashes the contents of this map into a new array with a
485 * larger capacity. This method is called automatically when the
486 * number of keys in this map reaches its threshold.
487 *
488 * If current capacity is MAXIMUM_CAPACITY, this method does not
489 * resize the map, but sets threshold to Integer.MAX_VALUE.
490 * This has the effect of preventing future calls.
491 *
492 * @param newCapacity the new capacity, MUST be a power of two;
493 * must be greater than current capacity unless current
494 * capacity is MAXIMUM_CAPACITY (in which case value
495 * is irrelevant).
496 */
497 void resize(int newCapacity) {
498 Entry<K,V>[] oldTable = getTable();
499 int oldCapacity = oldTable.length;
500 if (oldCapacity == MAXIMUM_CAPACITY) {
501 threshold = Integer.MAX_VALUE;
502 return;
531 e.next = null; // Help GC
532 e.value = null; // " "
533 size--;
534 } else {
535 int i = indexFor(e.hash, dest.length);
536 e.next = dest[i];
537 dest[i] = e;
538 }
539 e = next;
540 }
541 }
542 }
543
544 /**
545 * Copies all of the mappings from the specified map to this map.
546 * These mappings will replace any mappings that this map had for any
547 * of the keys currently in the specified map.
548 *
549 * @param m mappings to be stored in this map.
550 * @throws NullPointerException if the specified map is null.
551 */
552 public void putAll(Map<? extends K, ? extends V> m) {
553 int numKeysToBeAdded = m.size();
554 if (numKeysToBeAdded == 0)
555 return;
556
557 /*
558 * Expand the map if the map if the number of mappings to be added
559 * is greater than or equal to threshold. This is conservative; the
560 * obvious condition is (m.size() + size) >= threshold, but this
561 * condition could result in a map with twice the appropriate capacity,
562 * if the keys to be added overlap with the keys already in this map.
563 * By using the conservative calculation, we subject ourself
564 * to at most one extra resize.
565 */
566 if (numKeysToBeAdded > threshold) {
567 int targetCapacity = (int)Math.ceil(numKeysToBeAdded / (double)loadFactor);
568 if (targetCapacity > MAXIMUM_CAPACITY)
569 targetCapacity = MAXIMUM_CAPACITY;
570 int newCapacity = table.length;
571 while (newCapacity < targetCapacity)
572 newCapacity <<= 1;
573 if (newCapacity > table.length)
574 resize(newCapacity);
575 }
576
577 for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
578 put(e.getKey(), e.getValue());
579 }
580
581 /**
582 * Removes the mapping for a key from this weak hash map if it is present.
583 * More formally, if this map contains a mapping from key {@code k} to
584 * value {@code v} such that <code>(key==null ? k==null :
585 * key.equals(k))</code>, that mapping is removed. (The map can contain
586 * at most one such mapping.)
587 *
588 * <p>Returns the value to which this map previously associated the key,
589 * or {@code null} if the map contained no mapping for the key. A
590 * return value of {@code null} does not <i>necessarily</i> indicate
591 * that the map contained no mapping for the key; it's also possible
592 * that the map explicitly mapped the key to {@code null}.
593 *
594 * <p>The map will not contain a mapping for the specified key once the
595 * call returns.
596 *
597 * @param key key whose mapping is to be removed from the map
598 * @return the previous value associated with {@code key}, or
599 * {@code null} if there was no mapping for {@code key}
600 */
750 if (k1 == k2 || (k1 != null && k1.equals(k2))) {
751 V v1 = getValue();
752 Object v2 = e.getValue();
753 if (v1 == v2 || (v1 != null && v1.equals(v2)))
754 return true;
755 }
756 return false;
757 }
758
759 public int hashCode() {
760 K k = getKey();
761 V v = getValue();
762 return Objects.hashCode(k) ^ Objects.hashCode(v);
763 }
764
765 public String toString() {
766 return getKey() + "=" + getValue();
767 }
768 }
769
770 private abstract class HashIterator<T> implements Iterator<T> {
771 private int index;
772 private Entry<K,V> entry;
773 private Entry<K,V> lastReturned;
774 private int expectedModCount = modCount;
775
776 /**
777 * Strong reference needed to avoid disappearance of key
778 * between hasNext and next
779 */
780 private Object nextKey;
781
782 /**
783 * Strong reference needed to avoid disappearance of key
784 * between nextEntry() and any use of the entry
785 */
786 private Object currentKey;
787
788 HashIterator() {
789 index = isEmpty() ? 0 : table.length;
1347 /**
1348 * Creates a new, empty WeakHashMap suitable for the expected number of mappings.
1349 * The returned map uses the default load factor of 0.75, and its initial capacity is
1350 * generally large enough so that the expected number of mappings can be added
1351 * without resizing the map.
1352 *
1353 * @param numMappings the expected number of mappings
1354 * @param <K> the type of keys maintained by the new map
1355 * @param <V> the type of mapped values
1356 * @return the newly created map
1357 * @throws IllegalArgumentException if numMappings is negative
1358 * @since 19
1359 */
1360 public static <K, V> WeakHashMap<K, V> newWeakHashMap(int numMappings) {
1361 if (numMappings < 0) {
1362 throw new IllegalArgumentException("Negative number of mappings: " + numMappings);
1363 }
1364 return new WeakHashMap<>(HashMap.calculateHashMapCapacity(numMappings));
1365 }
1366
1367 }
|
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 sun.security.action.GetPropertyAction;
29
30 import java.lang.ref.SoftReference;
31 import java.lang.ref.WeakReference;
32 import java.lang.ref.ReferenceQueue;
33 import java.util.function.BiConsumer;
34 import java.util.function.BiFunction;
35 import java.util.function.Consumer;
36
37
38 /**
39 * Hash table based implementation of the {@code Map} interface, with
40 * <em>weak keys</em>.
41 * An entry in a {@code WeakHashMap} will automatically be removed when
42 * its key is no longer in ordinary use.
43 * More precisely, for keys that are identity objects, the presence of a
44 * mapping for a given key will not prevent the key from being discarded by the
45 * garbage collector, that is, made finalizable, finalized, and then reclaimed.
46 * For keys that are {@linkplain Class#isValue() value objects}, the retention of the
47 * key and value depends on the {@link ValuePolicy} for the {@code WeakHashMap} and
48 * the garbage collection handling of objects that are linked by {@link SoftReference}.
49 * When a key has been discarded its entry is effectively removed from the map,
50 * so this class behaves somewhat differently from other {@code Map}
51 * implementations.
52 *
53 * <p>
54 * Keys that are {@linkplain Class#isValue() value objects} do not have identity and cannot be
55 * the referent in any {@link java.lang.ref.Reference} including {@link WeakReference}.
56 * The retention of entries with keys that are value objects is selected
57 * using {@link ValuePolicy} when the {@code WeakHashMap} is created.
58 * The default {@code ValuePolicy} is {@link ValuePolicy#defaultValuePolicy()}.
59 * The retention modes implemented by {@link #put(Object, Object) WeakHashMap.put(k,v)} are:
60 * <UL>
61 * <LI> {@linkplain ValuePolicy#STRONG SOFT} - entries have a lifetime similar to
62 * referents of {@link SoftReference},
63 * <LI> {@linkplain ValuePolicy#STRONG STRONG} - entries are retained until removed,
64 * <LI> {@linkplain ValuePolicy#STRONG DISCARD} - entries are discarded and not put in the map,
65 * <LI> {@linkplain ValuePolicy#STRONG THROW} - entries are not inserted and
66 * {@link #put(Object, Object) put(k,v)} throws {@link IdentityException}
67 * </UL>
68 *
69 * <p> Both null values and the null key are supported. This class has
70 * performance characteristics similar to those of the {@code HashMap}
71 * class, and has the same efficiency parameters of <em>initial capacity</em>
72 * and <em>load factor</em>.
73 *
74 * <p> Like most collection classes, this class is not synchronized.
75 * A synchronized {@code WeakHashMap} may be constructed using the
76 * {@link Collections#synchronizedMap Collections.synchronizedMap}
77 * method.
78 *
79 * <p> <i>Update needed for Value Objects:
80 * <br>This class is intended primarily for use with key objects whose
81 * {@code equals} methods test for object identity using the
82 * {@code ==} operator. Once such a key is discarded it can never be
83 * recreated, so it is impossible to do a lookup of that key in a
84 * {@code WeakHashMap} at some later time and be surprised that its entry
85 * has been removed. This class will work perfectly well with key objects
86 * whose {@code equals} methods are not based upon object identity, such
87 * as {@code String} instances. With such recreatable key objects,
88 * however, the automatic removal of {@code WeakHashMap} entries whose
89 * keys have been discarded may prove to be confusing.</i>
90 *
91 * <p> The behavior of the {@code WeakHashMap} class depends in part upon
92 * the actions of the garbage collector, so several familiar (though not
93 * required) {@code Map} invariants do not hold for this class. Because
94 * the garbage collector may discard keys at any time, a
95 * {@code WeakHashMap} may behave as though an unknown thread is silently
96 * removing entries. In particular, even if you synchronize on a
97 * {@code WeakHashMap} instance and invoke none of its mutator methods, it
98 * is possible for the {@code size} method to return smaller values over
99 * time, for the {@code isEmpty} method to return {@code false} and
100 * then {@code true}, for the {@code containsKey} method to return
101 * {@code true} and later {@code false} for a given key, for the
102 * {@code get} method to return a value for a given key but later return
103 * {@code null}, for the {@code put} method to return
104 * {@code null} and the {@code remove} method to return
105 * {@code false} for a key that previously appeared to be in the map, and
106 * for successive examinations of the key set, the value collection, and
107 * the entry set to yield successively smaller numbers of elements.
108 *
109 * <p> Each key object in a {@code WeakHashMap} is stored indirectly as
196 * The load factor for the hash table.
197 */
198 private final float loadFactor;
199
200 /**
201 * Reference queue for cleared WeakEntries
202 */
203 private final ReferenceQueue<Object> queue = new ReferenceQueue<>();
204
205 /**
206 * The number of times this WeakHashMap has been structurally modified.
207 * Structural modifications are those that change the number of
208 * mappings in the map or otherwise modify its internal structure
209 * (e.g., rehash). This field is used to make iterators on
210 * Collection-views of the map fail-fast.
211 *
212 * @see ConcurrentModificationException
213 */
214 int modCount;
215
216 // Current policy with regard to keys that are Value classes.
217 private final ValuePolicy valuePolicy;
218
219 @SuppressWarnings("unchecked")
220 private Entry<K,V>[] newTable(int n) {
221 return (Entry<K,V>[]) new Entry<?,?>[n];
222 }
223
224 /**
225 * Constructs a new, empty {@code WeakHashMap} with the given initial
226 * capacity and the given load factor.
227 * The {@code WeakHashMap} is created using the {@linkplain ValuePolicy#defaultValuePolicy()
228 * default policy for value objects}.
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 * @param loadFactor The load factor of the {@code WeakHashMap}
236 * @throws IllegalArgumentException if the initial capacity is negative,
237 * or if the load factor is nonpositive.
238 */
239 public WeakHashMap(int initialCapacity, float loadFactor) {
240 this(initialCapacity, loadFactor, ValuePolicy.DEFAULT_VALUE_POLICY);
241 }
242
243 /**
244 * Constructs a new, empty {@code WeakHashMap} with the given initial
245 * capacity, the given load factor, and value policy.
246 *
247 * @param initialCapacity The initial capacity of the {@code WeakHashMap}
248 * @param loadFactor The load factor of the {@code WeakHashMap}
249 * @param valuePolicy The {@link ValuePolicy} for keys that are value objects
250 * @throws IllegalArgumentException if the initial capacity is negative,
251 * or if the load factor is nonpositive.
252 * @throws NullPointerException if {@code valuePolicy} is null
253 */
254 public WeakHashMap(int initialCapacity, float loadFactor, ValuePolicy valuePolicy) {
255 if (initialCapacity < 0)
256 throw new IllegalArgumentException("Illegal Initial Capacity: "+
257 initialCapacity);
258 if (initialCapacity > MAXIMUM_CAPACITY)
259 initialCapacity = MAXIMUM_CAPACITY;
260
261 if (loadFactor <= 0 || Float.isNaN(loadFactor))
262 throw new IllegalArgumentException("Illegal Load factor: "+
263 loadFactor);
264 this.valuePolicy = Objects.requireNonNull(valuePolicy, "valuePolicy");
265 int capacity = HashMap.tableSizeFor(initialCapacity);
266 table = newTable(capacity);
267 this.loadFactor = loadFactor;
268 threshold = (int)(capacity * loadFactor);
269 }
270
271 /**
272 * Constructs a new, empty {@code WeakHashMap} with the given initial
273 * capacity and the default load factor (0.75).
274 * The {@code WeakHashMap} is created using the {@linkplain ValuePolicy#defaultValuePolicy()
275 * default policy for value objects}.
276 *
277 * @apiNote
278 * To create a {@code WeakHashMap} with an initial capacity that accommodates
279 * an expected number of mappings, use {@link #newWeakHashMap(int) newWeakHashMap}.
280 *
281 * @param initialCapacity The initial capacity of the {@code WeakHashMap}
282 * @throws IllegalArgumentException if the initial capacity is negative
283 */
284 public WeakHashMap(int initialCapacity) {
285 this(initialCapacity, DEFAULT_LOAD_FACTOR);
286 }
287
288 /**
289 * Constructs a new, empty {@code WeakHashMap} with the default initial
290 * capacity (16) and load factor (0.75).
291 * The {@code WeakHashMap} is created using the {@linkplain ValuePolicy#defaultValuePolicy()
292 * default policy for value objects}.
293 */
294 public WeakHashMap() {
295 this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
296 }
297
298 /**
299 * Constructs a new, empty {@code WeakHashMap} with the {@link ValuePolicy},
300 * the default initial capacity (16) and load factor (0.75).
301 *
302 * @param valuePolicy The {@link ValuePolicy} for keys that are value objects; non-null
303 * @throws NullPointerException if {@code valuePolicy} is null
304 */
305 public WeakHashMap(ValuePolicy valuePolicy) {
306 this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR, valuePolicy);
307 }
308
309 /**
310 * Constructs a new {@code WeakHashMap} with the same mappings as the
311 * specified map. The {@code WeakHashMap} is created with the default
312 * load factor (0.75) and an initial capacity sufficient to hold the
313 * mappings in the specified map.
314 * The {@code WeakHashMap} is created using the {@linkplain ValuePolicy#defaultValuePolicy()
315 * default policy for value objects}.
316 *
317 * @param m the map whose mappings are to be placed in this map
318 * @throws NullPointerException if the specified map is null
319 * @since 1.3
320 */
321 @SuppressWarnings("this-escape")
322 public WeakHashMap(Map<? extends K, ? extends V> m) {
323 this(Math.max((int) Math.ceil(m.size() / (double)DEFAULT_LOAD_FACTOR),
324 DEFAULT_INITIAL_CAPACITY),
325 DEFAULT_LOAD_FACTOR);
326 putAll(m);
327 }
328
329 /**
330 * {@return the {@link ValuePolicy} for this WeakHashMap.}
331 */
332 public ValuePolicy valuePolicy() {
333 return valuePolicy;
334 }
335
336 // internal utilities
337
338 /**
339 * Value representing null keys inside tables.
340 */
341 private static final Object NULL_KEY = new Object();
342
343 /**
344 * Use NULL_KEY for key if it is null.
345 */
346 private static Object maskNull(Object key) {
347 return (key == null) ? NULL_KEY : key;
348 }
349
350 /**
351 * Returns internal representation of null key back to caller as null.
352 */
353 static Object unmaskNull(Object key) {
354 return (key == NULL_KEY) ? null : key;
355 }
356
357 /**
358 * Checks for equality of non-null reference x and possibly-null y. By
359 * default uses Object.equals.
360 */
361 private boolean matchesKey(Entry<K,V> e, Object key) {
362 // check if the given entry refers to the given key without
363 // keeping a strong reference to the entry's referent
364 // only identity objects can be compared to a reference
365 if (Objects.hasIdentity(key) && e.refersTo(key)) return true;
366
367 // then check for equality if the referent is not cleared
368 Object k = e.get();
369 return k != null && key.equals(k);
370 }
371
372 /**
373 * Retrieve object hash code and applies a supplemental hash function to the
374 * result hash, which defends against poor quality hash functions. This is
375 * critical because HashMap uses power-of-two length hash tables, that
376 * otherwise encounter collisions for hashCodes that do not differ
377 * in lower bits.
378 */
379 final int hash(Object k) {
380 int h = k.hashCode();
381
382 // This function ensures that hashCodes that differ only by
383 // constant multiples at each bit position have a bounded
384 // number of collisions (approximately 8 at default load factor).
385 h ^= (h >>> 20) ^ (h >>> 12);
509 int h = hash(k);
510 Entry<K,V>[] tab = getTable();
511 int index = indexFor(h, tab.length);
512 Entry<K,V> e = tab[index];
513 while (e != null && !(e.hash == h && matchesKey(e, k)))
514 e = e.next;
515 return e;
516 }
517
518 /**
519 * Associates the specified value with the specified key in this map.
520 * If the map previously contained a mapping for this key, the old
521 * value is replaced.
522 *
523 * @param key key with which the specified value is to be associated.
524 * @param value value to be associated with the specified key.
525 * @return the previous value associated with {@code key}, or
526 * {@code null} if there was no mapping for {@code key}.
527 * (A {@code null} return can also indicate that the map
528 * previously associated {@code null} with {@code key}.)
529 * @throws IdentityException if {@code key} is a value object
530 * and the {@link #valuePolicy() valuePolicy} is {@link ValuePolicy#THROW}.
531 */
532 public V put(K key, V value) {
533 Object k = maskNull(key);
534 final boolean hasIdentity = Objects.hasIdentity(k);
535 if (!hasIdentity && valuePolicy == ValuePolicy.DISCARD) {
536 // put of a value object key with value policy DISCARD is more like remove(key)
537 return remove(key);
538 }
539 int h = hash(k);
540 Entry<K,V>[] tab = getTable();
541 int i = indexFor(h, tab.length);
542
543 for (Entry<K,V> e = tab[i]; e != null; e = e.next) {
544 if (h == e.hash && matchesKey(e, k)) {
545 V oldValue = e.value;
546 if (value != oldValue)
547 e.value = value;
548 return oldValue;
549 }
550 }
551
552 Entry<K,V> e = tab[i];
553 e = hasIdentity ? new Entry<>(k, value, queue, h, e) : newValueEntry(k, value, queue, h, e);
554
555 modCount++;
556 tab[i] = e;
557 if (++size > threshold)
558 resize(tab.length * 2);
559 return null;
560 }
561
562 /**
563 * Return a new entry for keys that are value objects.
564 * The {@link ValuePolicy} for this WeakHashMap determines what entry is returned.
565 * <ul>
566 * <li> THROW - Throws an IdentityException</li>
567 * <li> STRONG - a StrongEntry </li>
568 * <li> SOFT - a SoftEntry</li>
569 * <li> DISCARD - null</li>
570 * </ul>
571 *
572 * @param key key with which the specified value is to be associated; non-null
573 * @param value value to be associated with the specified key
574 * @param queue queue
575 * @param hash hash
576 * @param next next
577 * @return a new entry or null to discard
578 * @throws IdentityException if the valuePolicy is {@link ValuePolicy#THROW}
579 */
580 private Entry<K, V> newValueEntry(Object key, V value,
581 ReferenceQueue<Object> queue,
582 int hash, Entry<K,V> next) {
583 return switch (valuePolicy) {
584 case THROW -> throw new IdentityException(key.getClass());
585 case STRONG -> StrongEntry.newStrongEntry(key, value, queue, hash, next);
586 case SOFT -> SoftEntry.newSoftEntry(key, value, queue, hash, next);
587 case DISCARD -> null;
588 };
589 }
590
591 /**
592 * Rehashes the contents of this map into a new array with a
593 * larger capacity. This method is called automatically when the
594 * number of keys in this map reaches its threshold.
595 *
596 * If current capacity is MAXIMUM_CAPACITY, this method does not
597 * resize the map, but sets threshold to Integer.MAX_VALUE.
598 * This has the effect of preventing future calls.
599 *
600 * @param newCapacity the new capacity, MUST be a power of two;
601 * must be greater than current capacity unless current
602 * capacity is MAXIMUM_CAPACITY (in which case value
603 * is irrelevant).
604 */
605 void resize(int newCapacity) {
606 Entry<K,V>[] oldTable = getTable();
607 int oldCapacity = oldTable.length;
608 if (oldCapacity == MAXIMUM_CAPACITY) {
609 threshold = Integer.MAX_VALUE;
610 return;
639 e.next = null; // Help GC
640 e.value = null; // " "
641 size--;
642 } else {
643 int i = indexFor(e.hash, dest.length);
644 e.next = dest[i];
645 dest[i] = e;
646 }
647 e = next;
648 }
649 }
650 }
651
652 /**
653 * Copies all of the mappings from the specified map to this map.
654 * These mappings will replace any mappings that this map had for any
655 * of the keys currently in the specified map.
656 *
657 * @param m mappings to be stored in this map.
658 * @throws NullPointerException if the specified map is null.
659 * @throws IdentityException if any of the {@code keys} is a value object
660 * and the {@link #valuePolicy() valuePolicy} is {@link ValuePolicy#THROW}.
661 */
662 public void putAll(Map<? extends K, ? extends V> m) {
663 int numKeysToBeAdded = m.size();
664 if (numKeysToBeAdded == 0)
665 return;
666
667 /*
668 * Expand the map if the map if the number of mappings to be added
669 * is greater than or equal to threshold. This is conservative; the
670 * obvious condition is (m.size() + size) >= threshold, but this
671 * condition could result in a map with twice the appropriate capacity,
672 * if the keys to be added overlap with the keys already in this map.
673 * By using the conservative calculation, we subject ourself
674 * to at most one extra resize.
675 */
676 if (numKeysToBeAdded > threshold) {
677 int targetCapacity = (int)Math.ceil(numKeysToBeAdded / (double)loadFactor);
678 if (targetCapacity > MAXIMUM_CAPACITY)
679 targetCapacity = MAXIMUM_CAPACITY;
680 int newCapacity = table.length;
681 while (newCapacity < targetCapacity)
682 newCapacity <<= 1;
683 if (newCapacity > table.length)
684 resize(newCapacity);
685 }
686
687 for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
688 put(e.getKey(), e.getValue());
689 }
690
691 /**
692 * {@inheritDoc}
693 * @param key {@inheritDoc}
694 * @param value {@inheritDoc}
695 * @return {@inheritDoc}
696 *
697 * @throws IdentityException if {@code key} is a value object
698 * and the {@link #valuePolicy() valuePolicy} is {@link ValuePolicy#THROW}.
699 */
700 public V putIfAbsent(K key, V value) {
701 V v = get(key);
702 if (v == null) {
703 v = put(key, value);
704 }
705
706 return v;
707 }
708
709 /**
710 * Removes the mapping for a key from this weak hash map if it is present.
711 * More formally, if this map contains a mapping from key {@code k} to
712 * value {@code v} such that <code>(key==null ? k==null :
713 * key.equals(k))</code>, that mapping is removed. (The map can contain
714 * at most one such mapping.)
715 *
716 * <p>Returns the value to which this map previously associated the key,
717 * or {@code null} if the map contained no mapping for the key. A
718 * return value of {@code null} does not <i>necessarily</i> indicate
719 * that the map contained no mapping for the key; it's also possible
720 * that the map explicitly mapped the key to {@code null}.
721 *
722 * <p>The map will not contain a mapping for the specified key once the
723 * call returns.
724 *
725 * @param key key whose mapping is to be removed from the map
726 * @return the previous value associated with {@code key}, or
727 * {@code null} if there was no mapping for {@code key}
728 */
878 if (k1 == k2 || (k1 != null && k1.equals(k2))) {
879 V v1 = getValue();
880 Object v2 = e.getValue();
881 if (v1 == v2 || (v1 != null && v1.equals(v2)))
882 return true;
883 }
884 return false;
885 }
886
887 public int hashCode() {
888 K k = getKey();
889 V v = getValue();
890 return Objects.hashCode(k) ^ Objects.hashCode(v);
891 }
892
893 public String toString() {
894 return getKey() + "=" + getValue();
895 }
896 }
897
898 /**
899 * A SoftEntry is used for value class keys in which the entries are retained
900 * until there is some memory pressure. An anchor object is used as the referent
901 * of a SoftReference and also as the referent of the WeakReference.
902 * After the SoftReference is cleared, due to GC pressure, the WeakReference is cleared too.
903 *
904 * @param <K> key
905 * @param <V> value
906 */
907 private static class SoftEntry<K, V> extends Entry<K, V> {
908 final Object realKey;
909 // SoftReference to the anchor to keep it alive until GC clears the SoftReference
910 private final SoftReference<Object> softAnchor;
911
912 static <K, V> SoftEntry<K, V> newSoftEntry(Object key, V value,
913 ReferenceQueue<Object> queue,
914 int hash, Entry<K, V> next) {
915 // Select a new anchor object; the entry will be retained until the anchor is collected
916 Object anchor = new Object();
917 return new SoftEntry<>(anchor, key, value, queue, hash, next);
918 }
919
920 private SoftEntry(Object anchor, Object key, V value,
921 ReferenceQueue<Object> queue,
922 int hash, Entry<K,V> next) {
923 super(anchor, value, queue, hash, next);
924 this.realKey = key;
925 this.softAnchor = new SoftReference<>(anchor);
926 }
927
928 /**
929 * The real key is not the referent.
930 * {{@inheritDoc}}
931 */
932 @Override
933 @SuppressWarnings("unchecked")
934 public K get() {
935 return (K) realKey;
936 }
937
938 @SuppressWarnings("unchecked")
939 public K getKey() {
940 return (K) realKey;
941 }
942 }
943
944 /**
945 * A StrongEntry is used for value class keys in which the entries are retained
946 * until removed. A singleton instance is used as the referent of the WeakReference.
947 * Since the anchor is never reclaimed, the Entry is retained forever.
948 *
949 * @param <K> key
950 * @param <V> value
951 */
952 private static class StrongEntry<K, V> extends Entry<K, V> {
953 final Object realKey;
954
955 // A permanent strong reference to an Object
956 private static final Object STRONG_ANCHOR = new Object();
957
958 static <K, V> StrongEntry<K, V> newStrongEntry(Object key, V value,
959 ReferenceQueue<Object> queue,
960 int hash, Entry<K, V> next) {
961 return new StrongEntry<>(STRONG_ANCHOR, key, value, queue, hash, next);
962 }
963
964 private StrongEntry(Object anchor, Object key, V value,
965 ReferenceQueue<Object> queue,
966 int hash, Entry<K,V> next) {
967 super(anchor, value, queue, hash, next);
968 this.realKey = key;
969 }
970
971 /**
972 * The real key is not the referent.
973 * {{@inheritDoc}}
974 */
975 @Override
976 @SuppressWarnings("unchecked")
977 public K get() {
978 return (K) realKey;
979 }
980
981
982 @SuppressWarnings("unchecked")
983 public K getKey() {
984 return (K) realKey;
985 }
986 }
987
988 private abstract class HashIterator<T> implements Iterator<T> {
989 private int index;
990 private Entry<K,V> entry;
991 private Entry<K,V> lastReturned;
992 private int expectedModCount = modCount;
993
994 /**
995 * Strong reference needed to avoid disappearance of key
996 * between hasNext and next
997 */
998 private Object nextKey;
999
1000 /**
1001 * Strong reference needed to avoid disappearance of key
1002 * between nextEntry() and any use of the entry
1003 */
1004 private Object currentKey;
1005
1006 HashIterator() {
1007 index = isEmpty() ? 0 : table.length;
1565 /**
1566 * Creates a new, empty WeakHashMap suitable for the expected number of mappings.
1567 * The returned map uses the default load factor of 0.75, and its initial capacity is
1568 * generally large enough so that the expected number of mappings can be added
1569 * without resizing the map.
1570 *
1571 * @param numMappings the expected number of mappings
1572 * @param <K> the type of keys maintained by the new map
1573 * @param <V> the type of mapped values
1574 * @return the newly created map
1575 * @throws IllegalArgumentException if numMappings is negative
1576 * @since 19
1577 */
1578 public static <K, V> WeakHashMap<K, V> newWeakHashMap(int numMappings) {
1579 if (numMappings < 0) {
1580 throw new IllegalArgumentException("Negative number of mappings: " + numMappings);
1581 }
1582 return new WeakHashMap<>(HashMap.calculateHashMapCapacity(numMappings));
1583 }
1584
1585 /**
1586 * Enum for the ValuePolicy; when putting a key and value into a WeakHashMap
1587 * determines how keys that are value objects are retained (or not).
1588 * The default {@code ValuePolicy} is {@link ValuePolicy#SOFT}.
1589 * @since Valhalla
1590 */
1591 public enum ValuePolicy {
1592 /**
1593 * If the key is a value object, retain the key and value until removed or
1594 * there is memory pressure that causes soft references to be cleared.
1595 */
1596 SOFT,
1597 /**
1598 * If the key is a value object, retain the key and value until removed.
1599 */
1600 STRONG,
1601 /**
1602 * If the key is a value object, discard the key and value immediately;
1603 * such keys and values are not retained.
1604 */
1605 DISCARD,
1606 /**
1607 * If the key is a value object, throw {@link IdentityException};
1608 * such keys and values are not retained.
1609 */
1610 THROW;
1611
1612 /**
1613 * {@return the default ValuePolicy}
1614 *
1615 * The default {@code ValuePolicy} is {@link ValuePolicy#SOFT} unless overridden by
1616 * the system property {@systemProperty java.util.WeakHashMap.valueKeyRetention}.
1617 * If the property is set to the name of a {@code ValuePolicy} enum,
1618 * the default {@code ValuePolicy} is set using {@link ValuePolicy#valueOf(String)}.
1619 * If the property value is absent or not valid, the policy is set to {@link ValuePolicy#SOFT}.
1620 */
1621 public static ValuePolicy defaultValuePolicy() {
1622 return DEFAULT_VALUE_POLICY;
1623 }
1624
1625 // System property name for the default ValuePolicy
1626 private static final String WEAK_HASH_MAP_VALUE_KEY_RETENTION =
1627 "java.util.WeakHashMap.valueKeyRetention";
1628
1629 // Default WeakHashMap ValuePolicy for keys that are value objects
1630 private static final ValuePolicy DEFAULT_VALUE_POLICY = initDefaultValuePolicy();
1631
1632 /**
1633 * {@return the default policy for retention of keys that are value classes}
1634 * If the system property "java.util.WeakHashMap.valueKeyRetention"
1635 * is the name of a {@link ValuePolicy} enum return it,
1636 * otherwise return {@link ValuePolicy#THROW}.
1637 */
1638 private static ValuePolicy initDefaultValuePolicy() {
1639 try {
1640 String p = GetPropertyAction
1641 .privilegedGetProperty(WEAK_HASH_MAP_VALUE_KEY_RETENTION);
1642 if (p != null) {
1643 return ValuePolicy.valueOf(p);
1644 }
1645 } catch (IllegalArgumentException ex) {
1646 }
1647
1648 return THROW; // hardcoded default if property not set
1649 }
1650 }
1651
1652 }
|