WeakHashMap.java revision 5172
196N/A * Copyright (c) 1998, 2010, Oracle and/or its affiliates. All rights reserved. 0N/A * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 0N/A * This code is free software; you can redistribute it and/or modify it 0N/A * under the terms of the GNU General Public License version 2 only, as 0N/A * published by the Free Software Foundation. Oracle designates this 0N/A * particular file as subject to the "Classpath" exception as provided 0N/A * by Oracle in the LICENSE file that accompanied this code. 0N/A * This code is distributed in the hope that it will be useful, but WITHOUT 0N/A * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 0N/A * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 0N/A * version 2 for more details (a copy is included in the LICENSE file that 0N/A * accompanied this code). 0N/A * You should have received a copy of the GNU General Public License version 0N/A * 2 along with this work; if not, write to the Free Software Foundation, 0N/A * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 0N/A * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 0N/A * or visit www.oracle.com if you need additional information or have any 0N/A * Hash table based implementation of the <tt>Map</tt> interface, with 0N/A * <em>weak keys</em>. 0N/A * An entry in a <tt>WeakHashMap</tt> will automatically be removed when 0N/A * its key is no longer in ordinary use. More precisely, the presence of a 0N/A * mapping for a given key will not prevent the key from being discarded by the 0N/A * garbage collector, that is, made finalizable, finalized, and then reclaimed. 0N/A * When a key has been discarded its entry is effectively removed from the map, 0N/A * so this class behaves somewhat differently from other <tt>Map</tt> 0N/A * <p> Both null values and the null key are supported. This class has 0N/A * performance characteristics similar to those of the <tt>HashMap</tt> 0N/A * class, and has the same efficiency parameters of <em>initial capacity</em> 0N/A * and <em>load factor</em>. 0N/A * <p> Like most collection classes, this class is not synchronized. 212N/A * A synchronized <tt>WeakHashMap</tt> may be constructed using the 0N/A * {@link Collections#synchronizedMap Collections.synchronizedMap} 212N/A * <p> This class is intended primarily for use with key objects whose 212N/A * <tt>equals</tt> methods test for object identity using the 212N/A * <tt>==</tt> operator. Once such a key is discarded it can never be 0N/A * recreated, so it is impossible to do a lookup of that key in a 0N/A * <tt>WeakHashMap</tt> at some later time and be surprised that its entry 0N/A * has been removed. This class will work perfectly well with key objects 0N/A * whose <tt>equals</tt> methods are not based upon object identity, such 0N/A * as <tt>String</tt> instances. With such recreatable key objects, 0N/A * however, the automatic removal of <tt>WeakHashMap</tt> entries whose 0N/A * keys have been discarded may prove to be confusing. 0N/A * <p> The behavior of the <tt>WeakHashMap</tt> class depends in part upon 0N/A * the actions of the garbage collector, so several familiar (though not 0N/A * required) <tt>Map</tt> invariants do not hold for this class. Because 0N/A * the garbage collector may discard keys at any time, a 0N/A * <tt>WeakHashMap</tt> may behave as though an unknown thread is silently 0N/A * removing entries. In particular, even if you synchronize on a 0N/A * <tt>WeakHashMap</tt> instance and invoke none of its mutator methods, it 0N/A * is possible for the <tt>size</tt> method to return smaller values over 0N/A * time, for the <tt>isEmpty</tt> method to return <tt>false</tt> and 0N/A * then <tt>true</tt>, for the <tt>containsKey</tt> method to return 0N/A * <tt>true</tt> and later <tt>false</tt> for a given key, for the 0N/A * <tt>get</tt> method to return a value for a given key but later return 0N/A * <tt>null</tt>, for the <tt>put</tt> method to return 0N/A * <tt>null</tt> and the <tt>remove</tt> method to return 0N/A * <tt>false</tt> for a key that previously appeared to be in the map, and 0N/A * for successive examinations of the key set, the value collection, and 0N/A * the entry set to yield successively smaller numbers of elements. 0N/A * <p> Each key object in a <tt>WeakHashMap</tt> is stored indirectly as 0N/A * the referent of a weak reference. Therefore a key will automatically be 0N/A * removed only after the weak references to it, both inside and outside of the 0N/A * map, have been cleared by the garbage collector. 0N/A * <p> <strong>Implementation note:</strong> The value objects in a 0N/A * <tt>WeakHashMap</tt> are held by ordinary strong references. Thus care 0N/A * should be taken to ensure that value objects do not strongly refer to their 0N/A * own keys, either directly or indirectly, since that will prevent the keys 0N/A * from being discarded. Note that a value object may refer indirectly to its 0N/A * key via the <tt>WeakHashMap</tt> itself; that is, a value object may 0N/A * strongly refer to some other key object whose associated value object, in 0N/A * turn, strongly refers to the key of the first value object. One way 0N/A * to deal with this is to wrap values themselves within 0N/A * <tt>WeakReferences</tt> before 0N/A * inserting, as in: <tt>m.put(key, new WeakReference(value))</tt>, 0N/A * and then unwrapping upon each <tt>get</tt>. 0N/A * <p>The iterators returned by the <tt>iterator</tt> method of the collections 0N/A * returned by all of this class's "collection view methods" are 0N/A * <i>fail-fast</i>: if the map is structurally modified at any time after the 0N/A * iterator is created, in any way except through the iterator's own 0N/A * <tt>remove</tt> method, the iterator will throw a {@link 0N/A * ConcurrentModificationException}. Thus, in the face of concurrent 0N/A * modification, the iterator fails quickly and cleanly, rather than risking 0N/A * arbitrary, non-deterministic behavior at an undetermined time in the future. 0N/A * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed 0N/A * as it is, generally speaking, impossible to make any hard guarantees in the 0N/A * presence of unsynchronized concurrent modification. Fail-fast iterators 0N/A * throw <tt>ConcurrentModificationException</tt> on a best-effort basis. 0N/A * Therefore, it would be wrong to write a program that depended on this 0N/A * exception for its correctness: <i>the fail-fast behavior of iterators 0N/A * should be used only to detect bugs.</i> 0N/A * <p>This class is a member of the 0N/A * Java Collections Framework</a>. 0N/A * @param <K> the type of keys maintained by this map 0N/A * @param <V> the type of mapped values 0N/A * @author Josh Bloch 0N/A * @author Mark Reinhold 0N/A * @see java.util.HashMap 0N/A * @see java.lang.ref.WeakReference 0N/A * The default initial capacity -- MUST be a power of two. 0N/A * The maximum capacity, used if a higher value is implicitly specified 0N/A * by either of the constructors with arguments. 0N/A * MUST be a power of two <= 1<<30. 0N/A * The load factor used when none specified in constructor. 0N/A * The table, resized as necessary. Length MUST Always be a power of two. 0N/A * The number of key-value mappings contained in this weak hash map. 0N/A * The next size value at which to resize (capacity * load factor). 0N/A * The load factor for the hash table. 0N/A * Reference queue for cleared WeakEntries 0N/A * The number of times this WeakHashMap has been structurally modified. 0N/A * Structural modifications are those that change the number of 0N/A * mappings in the map or otherwise modify its internal structure 0N/A * (e.g., rehash). This field is used to make iterators on 0N/A * Collection-views of the map fail-fast. 0N/A * @see ConcurrentModificationException 0N/A * The default threshold of map capacity above which alternative hashing is 0N/A * used for String keys. Alternative hashing reduces the incidence of 0N/A * collisions due to weak hash code calculation for String keys. 0N/A * This value may be overridden by defining the system property 0N/A * {@code jdk.map.althashing.threshold}. A property value of {@code 1} 0N/A * forces alternative hashing to be used at all times whereas 0N/A * {@code -1} value ensures that alternative hashing is never used. 0N/A * holds values which can't be initialized until after VM is booted. 0N/A * Table capacity above which to switch to use alternative hashing. 0N/A "jdk.map.althashing.threshold"));
0N/A // disable alternative hashing if -1 0N/A throw new Error(
"Illegal value for 'jdk.map.althashing.threshold'",
failed);
0N/A * If {@code true} then perform alternate hashing to reduce the incidence of 0N/A * collisions due to weak hash code calculation. 0N/A * A randomizing value associated with this instance that is applied to 0N/A * hash code of keys to make hash collisions harder to find. 0N/A * Constructs a new, empty <tt>WeakHashMap</tt> with the given initial 0N/A * capacity and the given load factor. 0N/A * @param initialCapacity The initial capacity of the <tt>WeakHashMap</tt> 0N/A * @param loadFactor The load factor of the <tt>WeakHashMap</tt> 0N/A * @throws IllegalArgumentException if the initial capacity is negative, 0N/A * or if the load factor is nonpositive. 0N/A * Constructs a new, empty <tt>WeakHashMap</tt> with the given initial 0N/A * capacity and the default load factor (0.75). 0N/A * @param initialCapacity The initial capacity of the <tt>WeakHashMap</tt> 0N/A * @throws IllegalArgumentException if the initial capacity is negative 0N/A * Constructs a new, empty <tt>WeakHashMap</tt> with the default initial 0N/A * capacity (16) and load factor (0.75). 0N/A * Constructs a new <tt>WeakHashMap</tt> with the same mappings as the 0N/A * specified map. The <tt>WeakHashMap</tt> is created with the default 0N/A * load factor (0.75) and an initial capacity sufficient to hold the 0N/A * mappings in the specified map. 0N/A * @param m the map whose mappings are to be placed in this map 0N/A * @throws NullPointerException if the specified map is null 0N/A // internal utilities 0N/A * Value representing null keys inside tables. 0N/A * Use NULL_KEY for key if it is null. 0N/A * Returns internal representation of null key back to caller as null. 0N/A * Checks for equality of non-null reference x and possibly-null y. By 0N/A * default uses Object.equals. 0N/A * Retrieve object hash code and applies a supplemental hash function to the 0N/A * result hash, which defends against poor quality hash functions. This is 0N/A * critical because HashMap uses power-of-two length hash tables, that 0N/A * otherwise encounter collisions for hashCodes that do not differ 0N/A // This function ensures that hashCodes that differ only by 0N/A // constant multiples at each bit position have a bounded 0N/A // number of collisions (approximately 8 at default load factor). 0N/A h ^= (h >>>
20) ^ (h >>>
12);
0N/A return h ^ (h >>>
7) ^ (h >>>
4);
0N/A * Returns index for hash code h. 0N/A * Expunges stale entries from the table. 0N/A // Must not null out e.next; 0N/A // stale entries may be in use by a HashIterator 0N/A * Returns the table after first expunging stale entries. 0N/A * Returns the number of key-value mappings in this map. 0N/A * This result is a snapshot, and may not reflect unprocessed 0N/A * entries that will be removed before next attempted access 0N/A * because they are no longer referenced. 0N/A * Returns <tt>true</tt> if this map contains no key-value mappings. 0N/A * This result is a snapshot, and may not reflect unprocessed 0N/A * entries that will be removed before next attempted access 0N/A * because they are no longer referenced. 0N/A * Returns the value to which the specified key is mapped, 0N/A * or {@code null} if this map contains no mapping for the key. 0N/A * <p>More formally, if this map contains a mapping from a key 0N/A * {@code k} to a value {@code v} such that {@code (key==null ? k==null : 0N/A * key.equals(k))}, then this method returns {@code v}; otherwise 0N/A * it returns {@code null}. (There can be at most one such mapping.) 0N/A * <p>A return value of {@code null} does not <i>necessarily</i> 0N/A * indicate that the map contains no mapping for the key; it's also 0N/A * possible that the map explicitly maps the key to {@code null}. 0N/A * The {@link #containsKey containsKey} operation may be used to 0N/A * distinguish these two cases. 0N/A * @see #put(Object, Object) 0N/A * Returns <tt>true</tt> if this map contains a mapping for the 0N/A * @param key The key whose presence in this map is to be tested 0N/A * @return <tt>true</tt> if there is a mapping for <tt>key</tt>; 0N/A * <tt>false</tt> otherwise 0N/A * Returns the entry associated with the specified key in this map. 0N/A * Returns null if the map contains no mapping for this key. 0N/A * Associates the specified value with the specified key in this map. 0N/A * If the map previously contained a mapping for this key, the old 0N/A * value is replaced. 0N/A * @param key key with which the specified value is to be associated. 0N/A * @param value value to be associated with the specified key. 0N/A * @return the previous value associated with <tt>key</tt>, or 0N/A * <tt>null</tt> if there was no mapping for <tt>key</tt>. 0N/A * (A <tt>null</tt> return can also indicate that the map 0N/A * previously associated <tt>null</tt> with <tt>key</tt>.) 0N/A * Rehashes the contents of this map into a new array with a 0N/A * larger capacity. This method is called automatically when the 0N/A * number of keys in this map reaches its threshold. 0N/A * If current capacity is MAXIMUM_CAPACITY, this method does not 0N/A * resize the map, but sets threshold to Integer.MAX_VALUE. 0N/A * This has the effect of preventing future calls. 0N/A * @param newCapacity the new capacity, MUST be a power of two; 0N/A * must be greater than current capacity unless current 0N/A * capacity is MAXIMUM_CAPACITY (in which case value 0N/A * If ignoring null elements and processing ref queue caused massive 0N/A * shrinkage, then restore old table. This should be rare, but avoids 0N/A * unbounded expansion of garbage-filled tables. 0N/A /** Transfers all entries from src to dest tables */ 0N/A * Copies all of the mappings from the specified map to this map. 0N/A * These mappings will replace any mappings that this map had for any 0N/A * of the keys currently in the specified map. 0N/A * @param m mappings to be stored in this map. 0N/A * @throws NullPointerException if the specified map is null. 33N/A * Expand the map if the map if the number of mappings to be added 33N/A * is greater than or equal to threshold. This is conservative; the 33N/A * obvious condition is (m.size() + size) >= threshold, but this 33N/A * condition could result in a map with twice the appropriate capacity, 33N/A * if the keys to be added overlap with the keys already in this map. 33N/A * By using the conservative calculation, we subject ourself 33N/A * to at most one extra resize. 0N/A * Removes the mapping for a key from this weak hash map if it is present. 296N/A * More formally, if this map contains a mapping from key <tt>k</tt> to 296N/A * value <tt>v</tt> such that <code>(key==null ? k==null : 0N/A * key.equals(k))</code>, that mapping is removed. (The map can contain 296N/A * at most one such mapping.) 0N/A * <p>Returns the value to which this map previously associated the key, 296N/A * or <tt>null</tt> if the map contained no mapping for the key. A 296N/A * return value of <tt>null</tt> does not <i>necessarily</i> indicate 296N/A * that the map contained no mapping for the key; it's also possible 296N/A * that the map explicitly mapped the key to <tt>null</tt>. 296N/A * <p>The map will not contain a mapping for the specified key once the 296N/A * @param key key whose mapping is to be removed from the map 296N/A * @return the previous value associated with <tt>key</tt>, or 0N/A * <tt>null</tt> if there was no mapping for <tt>key</tt> 0N/A /** Special version of remove needed by Entry set */ 293N/A * Removes all of the mappings from this map. 293N/A * The map will be empty after this call returns. 293N/A // clear out ref queue. We don't need to expunge entries 0N/A // since table is getting cleared. 0N/A // Allocation of array may have caused GC, which may have caused 0N/A // additional entries to go stale. Removing these entries from the 0N/A // reference queue will make them eligible for reclamation. 0N/A * Returns <tt>true</tt> if this map maps one or more keys to the 0N/A * @param value value whose presence in this map is to be tested 0N/A * @return <tt>true</tt> if this map maps one or more keys to the 113N/A * Special-case code for containsValue with null argument 113N/A * The entries in this hash table extend WeakReference, using its main ref 0N/A * Strong reference needed to avoid disappearance of key 0N/A * between hasNext and next 0N/A * Strong reference needed to avoid disappearance of key 0N/A * between nextEntry() and any use of the entry 0N/A /** The common parts of next() across different types of iterators */ 0N/A * Returns a {@link Set} view of the keys contained in this map. 0N/A * The set is backed by the map, so changes to the map are 0N/A * reflected in the set, and vice-versa. If the map is modified 0N/A * while an iteration over the set is in progress (except through 0N/A * the iterator's own <tt>remove</tt> operation), the results of 0N/A * the iteration are undefined. The set supports element removal, 0N/A * which removes the corresponding mapping from the map, via the 0N/A * <tt>Iterator.remove</tt>, <tt>Set.remove</tt>, 0N/A * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> 0N/A * operations. It does not support the <tt>add</tt> or <tt>addAll</tt> 0N/A * Returns a {@link Collection} view of the values contained in this map. 0N/A * The collection is backed by the map, so changes to the map are 0N/A * reflected in the collection, and vice-versa. If the map is 0N/A * modified while an iteration over the collection is in progress 0N/A * (except through the iterator's own <tt>remove</tt> operation), 0N/A * the results of the iteration are undefined. The collection 0N/A * supports element removal, which removes the corresponding 0N/A * mapping from the map, via the <tt>Iterator.remove</tt>, 0N/A * <tt>Collection.remove</tt>, <tt>removeAll</tt>, 0N/A * <tt>retainAll</tt> and <tt>clear</tt> operations. It does not 0N/A * support the <tt>add</tt> or <tt>addAll</tt> operations. 0N/A * Returns a {@link Set} view of the mappings contained in this map. 0N/A * The set is backed by the map, so changes to the map are 0N/A * reflected in the set, and vice-versa. If the map is modified 0N/A * while an iteration over the set is in progress (except through 0N/A * the iterator's own <tt>remove</tt> operation, or through the 0N/A * <tt>setValue</tt> operation on a map entry returned by the 0N/A * iterator) the results of the iteration are undefined. The set 0N/A * supports element removal, which removes the corresponding 0N/A * mapping from the map, via the <tt>Iterator.remove</tt>, 0N/A * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt> and 0N/A * <tt>clear</tt> operations. It does not support the 0N/A * <tt>add</tt> or <tt>addAll</tt> operations.