write sth. upfront
In a caching scenario, since memory is limited and cannot cache all objects, some deletion mechanism is needed to eliminate some objects. This time may quickly think of a variety of Cache data expiration strategy, there are also some excellent packages that provide feature-rich Cache, such as Google'sGuava CacheIt supports policies such as periodic data expiration, LRU, LFU, etc., but it still has the potential to cause useful data to be eliminated and useless data to be eliminated belatedly (this is all a small probability event if the policy is used properly).
Now there is a mechanism that allows the Cache not used in the key data is automatically cleaned up, used to remain, there will be no accidental deletion. WeakHashMap is suitable for this kind of caching scenario, because it has a self-cleaning mechanism!
If you let you manually implement a kind of self-cleaning HashMap, how can you do it? The first thing is to find a way to first know that a Key is certainly not in use, and then clean up the HashMap is not in use corresponding to the K-V. In the JVM, an object is not used means that there is no other useful object directly or indirectly executing it, the specific point is that in the GC process it is GCRoots unreachable. And aweak referenceIf the object pointed to by the object is determined to be a garbage object, Jvm will put the weakly referenced object into a ReferenceQueue, you only need to look at the contents of this Queue to know that an object is still available.
WeakHashMap Overview
As you can also tell from the name WeakHashMap, this is aweak referenceof Map, when a GC recovery is performed, theweak referenceThe object pointed to will be recovered by GC.
WeakHashMap may be recycled at any time precisely because it uses weak references. More intuitively, when usingWeakHashMap When you add or delete any element, even if it is not shown, the following may happen.
-
Calling the size() method twice returns different values;
-
Two calls to the isEmpty() method return false the first time and true the second time;
-
Two calls to the containsKey() method return true the first time and false the second time, even though the same key is used both times;
-
Two calls to the get() method return a value the first time and null the second time, even though the same object is used both times.
As you can see from the picture above:
-
WeakHashMap inherits from AbstractMap and implements the Map interface.
-
WeakHashMap is a hash table, but its keys are "weak keys".WeakHashMap protects several important member variables: table, size, threshold, loadFactor, modCount, queue.
-
A table is an Entry[] array type, and an Entry is actually a unidirectional linked table. The "key-value key pairs" of a hash table are stored in the Entry array.
-
size is the size of the Hashtable, it is the number of key-value pairs that the Hashtable holds.
-
threshold is the threshold value of the Hashtable to determine whether the capacity of the Hashtable needs to be adjusted or not. value of threshold = "capacity * loading factor".
-
loadFactor is the load factor.
-
modCount is used to implement the fail-fast mechanism
-
The queue holds "weakly referenced keys" that have been "cleared by GC".
-
basic usage
WeakHashMap < String, String > weakHashMap = new WeakHashMap < > (10);
String key0 = new String("str1");
String key2 = new String("str3");
// Store the elements
(key0, "data1").
(key0, "data1"); (key1, "data2"); String
(key2, "data3"); (key2, "data3"); // Stores the elements.
("weakHashMap: %s\n", weakHashMap);
// Whether or not it contains a key
("contains key str1 : %s\n", (key0)); ("contains key str2 : %s\n", "data3"); ("weakHashMap: %s\n", weakHashMap); // Does it contain a key?
("contains key str2 : %s\n", (key1));
// Remove the key
(key0); // Remove the key.
("weakHashMap after remove: %s\n", weakHashMap);; // remove key (key0); ("contains key str2 : %s\n", (key1))
// This means that the "weak key" key1 is no longer referenced by any other object, and the call to gc will reclaim the key-value pairs corresponding to key1 in the WeakHashMap
key1 = null; // Memory reclamation, this will reclaim the WeakHashMap key-value pair.
// Memory reclamation, here the key-value pair corresponding to "key0" in the WeakHashMap is reclaimed.
().
try {
(100); } catch (InterruptedException e) {
} catch (InterruptedException e) {
(); } catch (InterruptedException e) {
}
// Iterate over the WeakHashMap
for ( < String, String > m: ()) {
("next : %s > > > %s\n", (), ());
}
// Print the actual size of the WeakHashMap.
("after gc WeakHashMap size: %s\n", ()); }
underlying source code
constructor
// Default constructor.
WeakHashMap()
// Constructor that specifies the "capacity".
WeakHashMap(int capacity)
// Constructor that specifies the "capacity" and "load factor".
WeakHashMap(int capacity, float loadFactor) // Specify the constructor for "capacity" and "load factor".
// Constructor with "child Map".
WeakHashMap(Map<? extends K, ? extends V> map)
From the inheritance relationship of WeakHashMap, it can be seen that it inherits AbstractMap and implements the Map interface. Its underlying data structure is Entry array, and the data structure of Entry is as follows:
As you can see from the source code, Entry does not store the value of the key internally, but passes in the key and ReferenceQueue by calling the constructor method of the parent class (here with theThreadLocal is similar), eventually the key and queue will be associated to the Reference, here is the key to clear the key when GC, here is a general look at the Reference source code:
private static class ReferenceHandler extends Thread {
private static void ensureClassInitialized(Class <? > clazz) {
try {
((), true, ());
} catch (ClassNotFoundException e) {
throw (Error) new NoClassDefFoundError(()).initCause(e);
}
}
static {
// pre-load and initialize InterruptedException and Cleaner classes
// so that we don't get into trouble later in the run loop if there's
// memory shortage while loading/initializing them lazily.
ensureClassInitialized();
ensureClassInitialized();
}
ReferenceHandler(ThreadGroup g, String name) {
super(g, name);
}
public void run() {
// Note that this is a dead loop
while (true) {
tryHandlePending(true);
}
}
}
static boolean tryHandlePending(boolean waitForNotify) {
Reference < Object > r;
Cleaner c;
try {
synchronized(lock) {
if (pending != null) {
r = pending;
// 'instanceof' might throw OutOfMemoryError sometimes
// so do this before un-linking 'r' from the 'pending' chain...
c = r instanceof Cleaner ? (Cleaner) r : null;
// unlink 'r' from 'pending' chain
pending = ;
= null;
} else {
// The waiting on the lock may cause an OutOfMemoryError
// because it may try to allocate exception objects.
if (waitForNotify) {
();
}
// retry if waited
return waitForNotify;
}
}
} catch (OutOfMemoryError x) {
// Give other threads CPU time so they hopefully drop some live references
// and GC reclaims some space.
// Also prevent CPU intensive spinning in case 'r instanceof Cleaner' above
// persistently throws OOME for some time...
();
// retry
return true;
} catch (InterruptedException x) {
// retry
return true;
}
// Fast path for cleaners
if (c != null) {
();
return true;
}
// Accession of pairs of columns
ReferenceQueue <? super Object > q = ;
if (q != ) (r);
return true;
}
static {
ThreadGroup tg = ().getThreadGroup();
for (ThreadGroup tgn = tg; tgn != null; tg = tgn, tgn = ());
// establishhandler
Thread handler = new ReferenceHandler(tg, "Reference Handler");
/* If there were a special system-only priority greater than
* MAX_PRIORITY, it would be used here
*/
// Thread Priority Maximum
(Thread.MAX_PRIORITY);
// Set as a daemon thread
(true);
();
// provide access in SharedSecrets
(new JavaLangRefAccess() {@
Override
public boolean tryHandlePendingReference() {
return tryHandlePending(false);
}
});
}
put()
public V put(K key, V value) {
// Determine the value of the key, allowing the key to be null.
Object k = maskNull(key); // Determine the key value, allowing the key to be null.
// Getter hash value
int h = hash(k);
// Get the tab
Entry <K, V> [] tab = getTable();
// Determine position in tab Simple & operation
int i = indexFor(h, ); // Iterate over the tabs.
// Iterate over, whether to do an overwrite operation
for (Entry <K, V> e = tab[i]; e ! = null; e = ) {
if (h == && eq(k, ())) {
// already exists, overwrite the old value
V oldValue = ;
if (value ! = oldValue)
= value; return oldValue; // already exists, overwrite the old value.
return oldValue; }
}
}
// If it's not the old value, create a new Entry.
// Increment the modification count
modCount++.
// Take out the element on i
Entry <K, V> e = tab[i]; // build a chain table with new elements at the head.
// Build the chain, with the new element at the head of the chain
tab[i] = new Entry <> (k, value, queue, h, e); // check for expansion.
// Check if the table needs to be expanded
if (++size >= threshold)
resize( * 2); // check for expansion if (+size >= threshold)
return null; }
}
WeakHashMap put operation is similar to HashMap, will be overwrite operation (the same key), but note that the insertion of new nodes is placed in the chain table head; note that this is not the same place as HashMap, HashMap will be in the chain table is too long when the chain table will be converted to a red-black tree, to prevent extreme cases of hashcode conflicts resulting in performance problem, but there is no tree in WeakHashMap.
There is one more key function in the above code, getTable.
resize operation
WeakHashMap expansion operation: in size greater than the threshold, WeakHashMap also do resize operation, that is, double the tab expansion. resize in WeakHashMap than the HashMap resize to be simpler and better to understand some, but not as elegant as the HashMap resize.
There is another extra operation for resize in WeakHashMap, which is expungeStaleEntries(), because the key may be GC'd out, so you need to consider this situation when expanding the capacity as well
void resize(int newCapacity) {
Entry<K,V>[] oldTable = getTable();
// Original array length
int oldCapacity = ;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
// Creating a new array
Entry<K,V>[] newTable = newTable(newCapacity);
// data transfer
transfer(oldTable, newTable);
table = newTable;
/*
* If ignoring null elements and processing ref queue caused massive
* shrinkage, then restore old table. This should be rare, but avoids
* unbounded expansion of garbage-filled tables.
*/
// Determine expansion thresholds
if (size >= threshold / 2) {
threshold = (int)(newCapacity * loadFactor);
} else {
// sweepGC(used form a nominal expression)value
expungeStaleEntries();
// Array transfer
transfer(newTable, oldTable);
table = oldTable;
}
}
private void transfer(Entry<K,V>[] src, Entry<K,V>[] dest) {
// Iterate over the original array
for (int j = 0; j < ; ++j) {
// extract Element
Entry<K,V> e = src[j];
src[j] = null;
// chain search for an element
while (e != null) {
Entry<K,V> next = ;
Object key = ();
// key被回收(used form a nominal expression)情况
if (key == null) {
= null; // Help GC
= null; // " "
size--;
} else {
// 确定在新数组(used form a nominal expression)位置
int i = indexFor(, );
// inserted element Note that this is a header insertion，in reverse chronological order
= dest[i];
dest[i] = e;
}
e = next;
}
}
}
Expired element (weak reference) removal
The main purpose of this function is to clear the value of the Entry, which was queued during the GC clearing of the key.
private void expungeStaleEntries() {
// Remove the GC'd Entry from the queue.
for (Object x; (x = ()) ! = null;) {
synchronized(queue) {
@SuppressWarnings("unchecked")
Entry <K, V> e = (Entry <K, V> ) x;
// Determine the position of the element in the queue
int i = indexFor(, );
// Take the first element in the array prev
Entry <K, V> prev = table[i];
Entry <K, V> p = prev; // Loop over all the elements of the array.
// Loop
while (p ! = null) {
Entry <K, V> next = ;
// find
if (p == e) {
// Determine if it's the head element of the chain.
if (prev == e)
// Hook next directly to position i
table[i] = next;
table[i] = next; else
// truncate
table[i] = next; else // truncate
// Must not null out ;
// stale entries may be in use by a HashIterator
= null; // Help GC
size--;; // Help GC.
break; }
}
// Update prev and p
prev = p; p = next; }
p = next; }
}
}
}
}
When a key loses all its strong applications, the WeakReference object corresponding to its key will be put into the queue, and with the queue you will know which Entry needs to be cleaned up. This is the only place in the WeakHashMap where synchronization has been added.
In addition to the call to expungeStaleEntries() in resize as stated above, this cleanup method is also called in size(), getTable(), which means that almost all other methods call cleanup indirectly.
summarize
- WeakHashMap is non-synchronous, the default capacity is 16, the expansion factor is 0.75 by default, and the underlying data structure is an array of entries.(arrays + linked lists)。
- Weakly referenced keys in a WeakHashMap will be cleared at the next GC, noting that only theClear key, value will be cleared in each operation that calls expungeStaleEntries().
- take note ofWhen using WeakHashMap as cache, if only its key is only used by the WeakHashMap itself, and there is no strong reference to the key outside the WeakHashMap, then the GC will reclaim the entries corresponding to this key, so the WeakHashMap can't be used as the main cache, and the proper usage should be to use it as the secondary Memory cache, i.e. expired cache data or low-frequency cache data.
drawbacks
-
Non-thread-safe: the key modification method does not provide any synchronization, which will definitely lead to data inconsistency in a multi-threaded environment, so you need to pay more attention when using it.
-
Simply as Map is not as good as HashMap: HashMap in Jdk8 has done a lot of optimization, such as a single chained table will be converted into a red and black tree when too long, to reduce the complexity of the operation of the extreme cases. But WeakHashMap does not have the corresponding optimization, somewhat like jdk8 before the HashMap version.
-
Can't customize ReferenceQueue: WeakHashMap constructor can't specify a custom ReferenceQueue, if the user wants to use ReferenceQueue to do some extra cleanup work then it won't work. If you want to use the function of WeakHashMap, you also want to use ReferenceQueue, you have to implement a new set of WeakHashMap.
Usage Scenarios
-
Tomcat source code, the implementation of the cache will use WeakHashMap
-
Ali Arthas: Ali's open source Java diagnostic tool uses WeakHashMap to do class-byte code caching .
// resemble-bytecode cache
private final static Map<Class<?>/*Class*/, byte[]/*bytes of Class*/> classBytesCache
= new WeakHashMap<Class<?>, byte[]>();
About the Author.
From the first-line programmer Seven's exploration and practice, continuous learning iteration in the~
This article is included in my personal blog:https://
Public number: seven97, welcome to follow~