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 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);
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;
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 */
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;
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 }
|
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 public WeakHashMap(Map<? extends K, ? extends V> m) {
322 this(Math.max((int) Math.ceil(m.size() / (double)DEFAULT_LOAD_FACTOR),
323 DEFAULT_INITIAL_CAPACITY),
324 DEFAULT_LOAD_FACTOR);
325 putAll(m);
326 }
327
328 /**
329 * {@return the {@link ValuePolicy} for this WeakHashMap.}
330 */
331 public ValuePolicy valuePolicy() {
332 return valuePolicy;
333 }
334
335 // internal utilities
336
337 /**
338 * Value representing null keys inside tables.
339 */
340 private static final Object NULL_KEY = new Object();
341
342 /**
343 * Use NULL_KEY for key if it is null.
344 */
345 private static Object maskNull(Object key) {
346 return (key == null) ? NULL_KEY : key;
347 }
348
349 /**
350 * Returns internal representation of null key back to caller as null.
351 */
352 static Object unmaskNull(Object key) {
353 return (key == NULL_KEY) ? null : key;
354 }
355
356 /**
357 * Checks for equality of non-null reference x and possibly-null y. By
358 * default uses Object.equals.
359 */
360 private boolean matchesKey(Entry<K,V> e, Object key) {
361 // check if the given entry refers to the given key without
362 // keeping a strong reference to the entry's referent
363 // only identity objects can be compared to a reference
364 if (Objects.isIdentityObject(key) && e.refersTo(key)) return true;
365
366 // then check for equality if the referent is not cleared
367 Object k = e.get();
368 return k != null && key.equals(k);
369 }
370
371 /**
372 * Retrieve object hash code and applies a supplemental hash function to the
373 * result hash, which defends against poor quality hash functions. This is
374 * critical because HashMap uses power-of-two length hash tables, that
375 * otherwise encounter collisions for hashCodes that do not differ
376 * in lower bits.
377 */
378 final int hash(Object k) {
379 int h = k.hashCode();
380
381 // This function ensures that hashCodes that differ only by
382 // constant multiples at each bit position have a bounded
383 // number of collisions (approximately 8 at default load factor).
384 h ^= (h >>> 20) ^ (h >>> 12);
508 int h = hash(k);
509 Entry<K,V>[] tab = getTable();
510 int index = indexFor(h, tab.length);
511 Entry<K,V> e = tab[index];
512 while (e != null && !(e.hash == h && matchesKey(e, k)))
513 e = e.next;
514 return e;
515 }
516
517 /**
518 * Associates the specified value with the specified key in this map.
519 * If the map previously contained a mapping for this key, the old
520 * value is replaced.
521 *
522 * @param key key with which the specified value is to be associated.
523 * @param value value to be associated with the specified key.
524 * @return the previous value associated with {@code key}, or
525 * {@code null} if there was no mapping for {@code key}.
526 * (A {@code null} return can also indicate that the map
527 * previously associated {@code null} with {@code key}.)
528 * @throws IdentityException if {@code key} is a value object
529 * and the {@link #valuePolicy() valuePolicy} is {@link ValuePolicy#THROW}.
530 */
531 public V put(K key, V value) {
532 Object k = maskNull(key);
533 final boolean isValue = Objects.isValueObject(k);
534 if (isValue && valuePolicy == ValuePolicy.DISCARD) {
535 // put of a value object key with value policy DISCARD is more like remove(key)
536 return remove(key);
537 }
538 int h = hash(k);
539 Entry<K,V>[] tab = getTable();
540 int i = indexFor(h, tab.length);
541
542 for (Entry<K,V> e = tab[i]; e != null; e = e.next) {
543 if (h == e.hash && matchesKey(e, k)) {
544 V oldValue = e.value;
545 if (value != oldValue)
546 e.value = value;
547 return oldValue;
548 }
549 }
550
551 Entry<K,V> e = tab[i];
552 e = (isValue) ? newValueEntry(k, value, queue, h, e) : new Entry<>(k, value, queue, h, e);
553
554 modCount++;
555 tab[i] = e;
556 if (++size > threshold)
557 resize(tab.length * 2);
558 return null;
559 }
560
561 /**
562 * Return a new entry for keys that are value objects.
563 * The {@link ValuePolicy} for this WeakHashMap determines what entry is returned.
564 * <ul>
565 * <li> THROW - Throws an IdentityException</li>
566 * <li> STRONG - a StrongEntry </li>
567 * <li> SOFT - a SoftEntry</li>
568 * <li> DISCARD - null</li>
569 * </ul>
570 *
571 * @param key key with which the specified value is to be associated; non-null
572 * @param value value to be associated with the specified key
573 * @param queue queue
574 * @param hash hash
575 * @param next next
576 * @return a new entry or null to discard
577 * @throws IdentityException if the valuePolicy is {@link ValuePolicy#THROW}
578 */
579 private Entry<K, V> newValueEntry(Object key, V value,
580 ReferenceQueue<Object> queue,
581 int hash, Entry<K,V> next) {
582 return switch (valuePolicy) {
583 case THROW -> throw new IdentityException(key.getClass());
584 case STRONG -> StrongEntry.newStrongEntry(key, value, queue, hash, next);
585 case SOFT -> SoftEntry.newSoftEntry(key, value, queue, hash, next);
586 case DISCARD -> null;
587 };
588 }
589
590 /**
591 * Rehashes the contents of this map into a new array with a
592 * larger capacity. This method is called automatically when the
593 * number of keys in this map reaches its threshold.
594 *
595 * If current capacity is MAXIMUM_CAPACITY, this method does not
596 * resize the map, but sets threshold to Integer.MAX_VALUE.
597 * This has the effect of preventing future calls.
598 *
599 * @param newCapacity the new capacity, MUST be a power of two;
600 * must be greater than current capacity unless current
601 * capacity is MAXIMUM_CAPACITY (in which case value
602 * is irrelevant).
603 */
604 void resize(int newCapacity) {
605 Entry<K,V>[] oldTable = getTable();
606 int oldCapacity = oldTable.length;
607 if (oldCapacity == MAXIMUM_CAPACITY) {
608 threshold = Integer.MAX_VALUE;
609 return;
638 e.next = null; // Help GC
639 e.value = null; // " "
640 size--;
641 } else {
642 int i = indexFor(e.hash, dest.length);
643 e.next = dest[i];
644 dest[i] = e;
645 }
646 e = next;
647 }
648 }
649 }
650
651 /**
652 * Copies all of the mappings from the specified map to this map.
653 * These mappings will replace any mappings that this map had for any
654 * of the keys currently in the specified map.
655 *
656 * @param m mappings to be stored in this map.
657 * @throws NullPointerException if the specified map is null.
658 * @throws IdentityException if any of the {@code keys} is a value object
659 * and the {@link #valuePolicy() valuePolicy} is {@link ValuePolicy#THROW}.
660 */
661 public void putAll(Map<? extends K, ? extends V> m) {
662 int numKeysToBeAdded = m.size();
663 if (numKeysToBeAdded == 0)
664 return;
665
666 /*
667 * Expand the map if the map if the number of mappings to be added
668 * is greater than or equal to threshold. This is conservative; the
669 * obvious condition is (m.size() + size) >= threshold, but this
670 * condition could result in a map with twice the appropriate capacity,
671 * if the keys to be added overlap with the keys already in this map.
672 * By using the conservative calculation, we subject ourself
673 * to at most one extra resize.
674 */
675 if (numKeysToBeAdded > threshold) {
676 int targetCapacity = (int)Math.ceil(numKeysToBeAdded / (double)loadFactor);
677 if (targetCapacity > MAXIMUM_CAPACITY)
678 targetCapacity = MAXIMUM_CAPACITY;
679 int newCapacity = table.length;
680 while (newCapacity < targetCapacity)
681 newCapacity <<= 1;
682 if (newCapacity > table.length)
683 resize(newCapacity);
684 }
685
686 for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
687 put(e.getKey(), e.getValue());
688 }
689
690 /**
691 * {@inheritDoc}
692 * @param key {@inheritDoc}
693 * @param value {@inheritDoc}
694 * @return {@inheritDoc}
695 *
696 * @throws IdentityException if {@code key} is a value object
697 * and the {@link #valuePolicy() valuePolicy} is {@link ValuePolicy#THROW}.
698 */
699 public V putIfAbsent(K key, V value) {
700 V v = get(key);
701 if (v == null) {
702 v = put(key, value);
703 }
704
705 return v;
706 }
707
708 /**
709 * Removes the mapping for a key from this weak hash map if it is present.
710 * More formally, if this map contains a mapping from key {@code k} to
711 * value {@code v} such that <code>(key==null ? k==null :
712 * key.equals(k))</code>, that mapping is removed. (The map can contain
713 * at most one such mapping.)
714 *
715 * <p>Returns the value to which this map previously associated the key,
716 * or {@code null} if the map contained no mapping for the key. A
717 * return value of {@code null} does not <i>necessarily</i> indicate
718 * that the map contained no mapping for the key; it's also possible
719 * that the map explicitly mapped the key to {@code null}.
720 *
721 * <p>The map will not contain a mapping for the specified key once the
722 * call returns.
723 *
724 * @param key key whose mapping is to be removed from the map
725 * @return the previous value associated with {@code key}, or
726 * {@code null} if there was no mapping for {@code key}
727 */
877 if (k1 == k2 || (k1 != null && k1.equals(k2))) {
878 V v1 = getValue();
879 Object v2 = e.getValue();
880 if (v1 == v2 || (v1 != null && v1.equals(v2)))
881 return true;
882 }
883 return false;
884 }
885
886 public int hashCode() {
887 K k = getKey();
888 V v = getValue();
889 return Objects.hashCode(k) ^ Objects.hashCode(v);
890 }
891
892 public String toString() {
893 return getKey() + "=" + getValue();
894 }
895 }
896
897 /**
898 * A SoftEntry is used for value class keys in which the entries are retained
899 * until there is some memory pressure. An anchor object is used as the referent
900 * of a SoftReference and also as the referent of the WeakReference.
901 * After the SoftReference is cleared, due to GC pressure, the WeakReference is cleared too.
902 *
903 * @param <K> key
904 * @param <V> value
905 */
906 private static class SoftEntry<K, V> extends Entry<K, V> {
907 final Object realKey;
908 // SoftReference to the anchor to keep it alive until GC clears the SoftReference
909 private final SoftReference<Object> softAnchor;
910
911 static <K, V> SoftEntry<K, V> newSoftEntry(Object key, V value,
912 ReferenceQueue<Object> queue,
913 int hash, Entry<K, V> next) {
914 // Select a new anchor object; the entry will be retained until the anchor is collected
915 Object anchor = new Object();
916 return new SoftEntry<>(anchor, key, value, queue, hash, next);
917 }
918
919 private SoftEntry(Object anchor, Object key, V value,
920 ReferenceQueue<Object> queue,
921 int hash, Entry<K,V> next) {
922 super(anchor, value, queue, hash, next);
923 this.realKey = key;
924 this.softAnchor = new SoftReference<>(anchor);
925 }
926
927 /**
928 * The real key is not the referent.
929 * {{@inheritDoc}}
930 */
931 @Override
932 @SuppressWarnings("unchecked")
933 public K get() {
934 return (K) realKey;
935 }
936
937 @SuppressWarnings("unchecked")
938 public K getKey() {
939 return (K) realKey;
940 }
941 }
942
943 /**
944 * A StrongEntry is used for value class keys in which the entries are retained
945 * until removed. A singleton instance is used as the referent of the WeakReference.
946 * Since the anchor is never reclaimed, the Entry is retained forever.
947 *
948 * @param <K> key
949 * @param <V> value
950 */
951 private static class StrongEntry<K, V> extends Entry<K, V> {
952 final Object realKey;
953
954 // A permanent strong reference to an Object
955 private static final Object STRONG_ANCHOR = new Object();
956
957 static <K, V> StrongEntry<K, V> newStrongEntry(Object key, V value,
958 ReferenceQueue<Object> queue,
959 int hash, Entry<K, V> next) {
960 return new StrongEntry<>(STRONG_ANCHOR, key, value, queue, hash, next);
961 }
962
963 private StrongEntry(Object anchor, Object key, V value,
964 ReferenceQueue<Object> queue,
965 int hash, Entry<K,V> next) {
966 super(anchor, value, queue, hash, next);
967 this.realKey = key;
968 }
969
970 /**
971 * The real key is not the referent.
972 * {{@inheritDoc}}
973 */
974 @Override
975 @SuppressWarnings("unchecked")
976 public K get() {
977 return (K) realKey;
978 }
979
980
981 @SuppressWarnings("unchecked")
982 public K getKey() {
983 return (K) realKey;
984 }
985 }
986
987 private abstract class HashIterator<T> implements Iterator<T> {
988 private int index;
989 private Entry<K,V> entry;
990 private Entry<K,V> lastReturned;
991 private int expectedModCount = modCount;
992
993 /**
994 * Strong reference needed to avoid disappearance of key
995 * between hasNext and next
996 */
997 private Object nextKey;
998
999 /**
1000 * Strong reference needed to avoid disappearance of key
1001 * between nextEntry() and any use of the entry
1002 */
1003 private Object currentKey;
1004
1005 HashIterator() {
1006 index = isEmpty() ? 0 : table.length;
1564 /**
1565 * Creates a new, empty WeakHashMap suitable for the expected number of mappings.
1566 * The returned map uses the default load factor of 0.75, and its initial capacity is
1567 * generally large enough so that the expected number of mappings can be added
1568 * without resizing the map.
1569 *
1570 * @param numMappings the expected number of mappings
1571 * @param <K> the type of keys maintained by the new map
1572 * @param <V> the type of mapped values
1573 * @return the newly created map
1574 * @throws IllegalArgumentException if numMappings is negative
1575 * @since 19
1576 */
1577 public static <K, V> WeakHashMap<K, V> newWeakHashMap(int numMappings) {
1578 if (numMappings < 0) {
1579 throw new IllegalArgumentException("Negative number of mappings: " + numMappings);
1580 }
1581 return new WeakHashMap<>(HashMap.calculateHashMapCapacity(numMappings));
1582 }
1583
1584 /**
1585 * Enum for the ValuePolicy; when putting a key and value into a WeakHashMap
1586 * determines how keys that are value objects are retained (or not).
1587 * The default {@code ValuePolicy} is {@link ValuePolicy#SOFT}.
1588 * @since Valhalla
1589 */
1590 public enum ValuePolicy {
1591 /**
1592 * If the key is a value object, retain the key and value until removed or
1593 * there is memory pressure that causes soft references to be cleared.
1594 */
1595 SOFT,
1596 /**
1597 * If the key is a value object, retain the key and value until removed.
1598 */
1599 STRONG,
1600 /**
1601 * If the key is a value object, discard the key and value immediately;
1602 * such keys and values are not retained.
1603 */
1604 DISCARD,
1605 /**
1606 * If the key is a value object, throw {@link IdentityException};
1607 * such keys and values are not retained.
1608 */
1609 THROW;
1610
1611 /**
1612 * {@return the default ValuePolicy}
1613 *
1614 * The default {@code ValuePolicy} is {@link ValuePolicy#SOFT} unless overridden by
1615 * the system property {@systemProperty java.util.WeakHashMap.valueKeyRetention}.
1616 * If the property is set to the name of a {@code ValuePolicy} enum,
1617 * the default {@code ValuePolicy} is set using {@link ValuePolicy#valueOf(String)}.
1618 * If the property value is absent or not valid, the policy is set to {@link ValuePolicy#SOFT}.
1619 */
1620 public static ValuePolicy defaultValuePolicy() {
1621 return DEFAULT_VALUE_POLICY;
1622 }
1623
1624 // System property name for the default ValuePolicy
1625 private static final String WEAK_HASH_MAP_VALUE_KEY_RETENTION =
1626 "java.util.WeakHashMap.valueKeyRetention";
1627
1628 // Default WeakHashMap ValuePolicy for keys that are value objects
1629 private static final ValuePolicy DEFAULT_VALUE_POLICY = initDefaultValuePolicy();
1630
1631 /**
1632 * {@return the default policy for retention of keys that are value classes}
1633 * If the system property "java.util.WeakHashMap.valueKeyRetention"
1634 * is the name of a {@link ValuePolicy} enum return it,
1635 * otherwise return {@link ValuePolicy#SOFT}.
1636 */
1637 private static ValuePolicy initDefaultValuePolicy() {
1638 try {
1639 String p = GetPropertyAction
1640 .privilegedGetProperty(WEAK_HASH_MAP_VALUE_KEY_RETENTION);
1641 if (p != null) {
1642 return ValuePolicy.valueOf(p);
1643 }
1644 } catch (IllegalArgumentException ex) {
1645 }
1646
1647 return SOFT; // hardcoded default if property not set
1648 }
1649 }
1650
1651 }
|