Welcome to pay attention to my public number “Tong Elder brother read source code”, view more source code series articles, with Tong elder brother tour the ocean of source code.
Introduction to the
WeakHashMap is a weak reference map, internal keys will be stored as weak references, when THE JVM GC, if these keys do not have strong references, will be recycled by GC, the next time when we operate map will delete the corresponding Entry, based on this feature, WeakHashMap is particularly useful for cache processing.
Inheritance system
As can be seen, WeakHashMap does not implement Clone and Serializable interfaces, so it does not have Clone and serialization features.
Storage structure
WeakHashMap will recycle the key without strong reference during GC, so it is doomed that there will not be too many elements in it, so it does not need to be processed like HashMap when there are many elements into a red-black tree.
Therefore, WeakHashMap only has (array + linked list) storage structure.
The source code parsing
attribute
/** * Default initial capacity is 16 */
private static final int DEFAULT_INITIAL_CAPACITY = 16;
/** * The maximum capacity is 2 ^ 30 */
private static final int MAXIMUM_CAPACITY = 1 << 30;
/** * Default load factor */
private static final float DEFAULT_LOAD_FACTOR = 0.75 f;
/ * * * * /
Entry<K,V>[] table;
/** * Number of elements */
private int size;
/** * Capacity expansion threshold, equal to capacity * loadFactor */
private int threshold;
/** * load factor */
private final float loadFactor;
/** * references the queue to which Entry is added when weak keys fail */
private final ReferenceQueue<Object> queue = new ReferenceQueue<>();
Copy the code(1) Capacity
The capacity is the length of the array, that is, the number of buckets. The default value is 16, and the maximum value is 2 to the power of 30. When the capacity reaches 64, it can be treed.
(2) Loading factor
The load factor is used to calculate the capacity to be expanded. The default load factor is 0.75.
(3) Reference queue
When a weak key is invalid, an Entry is added to the queue, and the invalid Entry is deleted when the map is accessed next time.
Entry inner class
WeakHashMap Internal storage node without key attribute.
private static class Entry<K.V> extends WeakReference<Object> implements Map.Entry<K.V> {
// You can see that there is no key because the key is stored as a weak reference in the Referen class
V value;
final int hash;
Entry<K,V> next;
Entry(Object key, V value,
ReferenceQueue<Object> queue,
int hash, Entry<K,V> next) {
// Call WeakReference's constructor to initialize the key and reference queue
super(key, queue);
this.value = value;
this.hash = hash;
this.next = next; }}public class WeakReference<T> extends Reference<T> {
public WeakReference(T referent, ReferenceQueue<? super T> q) {
// Call Reference's constructor to initialize the key and Reference queue
super(referent, q); }}public abstract class Reference<T> {
// Where the key is actually stored
private T referent; /* Treated specially by GC */
// Reference queue
volatile ReferenceQueue<? super T> queue;
Reference(T referent, ReferenceQueue<? super T> queue) {
this.referent = referent;
this.queue = (queue == null)? ReferenceQueue.NULL : queue; }}Copy the codeFrom the Entry constructor, we know that the key and queue will eventually be passed to the Reference constructor, where the key is the referent property of Reference. It will be treated specially by gc, that is, when no strong Reference exists, it will be cleared by the next GC.
A constructor
public WeakHashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Initial Capacity: "+
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal Load factor: "+
loadFactor);
int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1;
table = newTable(capacity);
this.loadFactor = loadFactor;
threshold = (int)(capacity * loadFactor);
}
public WeakHashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public WeakHashMap(a) {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
public WeakHashMap(Map<? extends K, ? extends V> m) {
this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
DEFAULT_INITIAL_CAPACITY),
DEFAULT_LOAD_FACTOR);
putAll(m);
}
Copy the codeThe construction method is similar to that of a HashMap. The initial capacity is greater than or equal to the nearest incoming capacity, 2 to the n power, and the threshold is equal to capacity * loadFactor.
Put (K key, V value) method
Methods to add elements.
public V put(K key, V value) {
// If key is empty, use an empty object instead
Object k = maskNull(key);
// Computes the hash value of the key
int h = hash(k);
/ / get barrels
Entry<K,V>[] tab = getTable();
// Calculate the element in which bucket, h & (length-1)
int i = indexFor(h, tab.length);
// Iterate through the bucket list
for(Entry<K,V> e = tab[i]; e ! =null; e = e.next) {
if (h == e.hash && eq(k, e.get())) {
// If an element is found, it replaces the old value with the new value and returns the old value
V oldValue = e.value;
if(value ! = oldValue) e.value = value;return oldValue;
}
}
modCount++;
// Insert the new value to the head of the list if it is not found
Entry<K,V> e = tab[i];
tab[i] = new Entry<>(k, value, queue, h, e);
// If the number of elements inserted reaches the threshold, expand the number of buckets twice the size
if (++size >= threshold)
resize(tab.length * 2);
return null;
}
Copy the code(1) Compute hash;
This is different from a HashMap, where zero is returned if the key is empty, which uses an empty object.
The HashMap uses only one xor. Here it uses four. The HashMap gives the interpretation that once is enough, and even if there is a conflict, it will be converted to a red-black tree.
(2) Calculate which bucket it is in;
(3) Traversing the linked list corresponding to buckets;
(4) If the element is found, it replaces the old value with the new value and returns the old value;
(5) Insert a new element into the head of the list if it is not found;
The HashMap is inserted at the end of the list.
(6) If the number of elements reaches the threshold, expand the capacity to twice the size;
In HashMap, capacity expansion is performed when the value is greater than threshold.
The resize (int newCapacity) method
Capacity expansion method.
void resize(int newCapacity) {
// Retrieves old buckets. Invalid entries are excluded from getTable()
Entry<K,V>[] oldTable = getTable();
/ / the old capacity
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
/ / new barrels
Entry<K,V>[] newTable = newTable(newCapacity);
// Move elements from the old bucket to the new bucket
transfer(oldTable, newTable);
// Assign a bucket variable to the new bucket
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. */
// If the number of elements is greater than half of the threshold, use a new bucket and a new capacity, and calculate a new threshold
if (size >= threshold / 2) {
threshold = (int)(newCapacity * loadFactor);
} else {
// If not, move the element back to the old bucket
// Since invalid entries will be cleared during transfer, the number of elements may not be so large, so there is no need to expandexpungeStaleEntries(); transfer(newTable, oldTable); table = oldTable; }}private void transfer(Entry<K,V>[] src, Entry<K,V>[] dest) {
// Walk through the old bucket
for (int j = 0; j < src.length; ++j) {
Entry<K,V> e = src[j];
src[j] = null;
while(e ! =null) {
Entry<K,V> next = e.next;
Object key = e.get();
// If the key is null, the entire Entry is cleared
if (key == null) {
e.next = null; // Help GC
e.value = null; / / ""
size--;
} else {
// Otherwise calculate the position in the new bucket and place the element at the head of the new bucket's corresponding list
inti = indexFor(e.hash, dest.length); e.next = dest[i]; dest[i] = e; } e = next; }}}Copy the code(1) Judge whether the old capacity has reached the maximum capacity;
(2) Create a new bucket and transfer all elements to the new bucket;
(3) If the number of elements after transfer is less than half of the threshold for capacity expansion, the elements are transferred back to the old bucket and the old bucket continues to be used, indicating that capacity expansion is not required;
(4) Otherwise, use a new bucket and calculate a new capacity expansion threshold;
(5) The element whose key is null will be removed in the process of element transfer, so the size will be smaller;
Get (Object key) method
Gets the element.
public V get(Object key) {
Object k = maskNull(key);
/ / calculate the hash
int h = hash(k);
Entry<K,V>[] tab = getTable();
int index = indexFor(h, tab.length);
Entry<K,V> e = tab[index];
// Run through the list and return if found
while(e ! =null) {
if (e.hash == h && eq(k, e.get()))
return e.value;
e = e.next;
}
return null;
}
Copy the code(1) Compute the hash value;
(2) Traverse the linked list corresponding to the bucket;
(3) Return the value of the element if found;
(4) Return null if not found;
Remove (Object key) method
Remove elements.
public V remove(Object key) {
Object k = maskNull(key);
/ / calculate the hash
int h = hash(k);
Entry<K,V>[] tab = getTable();
int i = indexFor(h, tab.length);
// The first element of the bucket in which the element is located
Entry<K,V> prev = tab[i];
Entry<K,V> e = prev;
// Iterate over the list
while(e ! =null) {
Entry<K,V> next = e.next;
if (h == e.hash && eq(k, e.get())) {
// Delete the element if it is found
modCount++;
size--;
if (prev == e)
// If it is a head node, the head node points to the next node
tab[i] = next;
else
// If it is not the head node, delete the node
prev.next = next;
return e.value;
}
prev = e;
e = next;
}
return null;
}
Copy the code(1) Compute hash;
(2) Find the bucket;
(3) Traversing the linked list corresponding to buckets;
(4) Delete the node if it is found and return the value of the node;
(5) Return null if not found;
ExpungeStaleEntries () method
Delete invalid entries.
private void expungeStaleEntries(a) {
// Traverse the reference queue
for(Object x; (x = queue.poll()) ! =null;) {synchronized (queue) {
@SuppressWarnings("unchecked")
Entry<K,V> e = (Entry<K,V>) x;
int i = indexFor(e.hash, table.length);
// Find the bucket
Entry<K,V> prev = table[i];
Entry<K,V> p = prev;
// Iterate over the list
while(p ! =null) {
Entry<K,V> next = p.next;
// Find the element
if (p == e) {
// Delete the element
if (prev == e)
table[i] = next;
else
prev.next = next;
// Must not null out e.next;
// stale entries may be in use by a HashIterator
e.value = null; // Help GC
size--;
break; } prev = p; p = next; }}}}Copy the code(1) When the key is invalid, GC will automatically add the corresponding Entry to the reference queue;
(2) All map operations, such as getTable(), size(), and resize(), are directly or indirectly invoked to remove invalid entries.
(3) The purpose of this method is to traverse the reference queue and remove the entries stored in it from the map. See the class comment for details.
(4) As you can see from this, removing Entry and setting value to NULL helps gc clean up elements, defensive programming.
Use case
Having said so much, one can’t get by without giving an example of its use.
package com.coolcoding.code;
import java.util.Map;
import java.util.WeakHashMap;
public class WeakHashMapTest {
public static void main(String[] args) {
Map<String, Integer> map = new WeakHashMap<>(3);
// Put three strings declared by new String()
map.put(new String("1"), 1);
map.put(new String("2"), 2);
map.put(new String("3"), 3);
// Put strings that are not declared by new String()
map.put("6".6);
// use key to strongly reference the string "3"
String key = null;
for (String s : map.keySet()) {
// This "3" is not a reference to the new String("3")
if (s.equals("3")) { key = s; }}{6=6, 1=1, 2=2, 3=3}, all keys can be printed without GC
System.out.println(map);
/ / gc
System.gc();
// Put a String declared by new String()
map.put(new String("4"), 4);
// output {4=4, 6=6, 3=3}, after gc values and strongly referenced keys can be printed out
System.out.println(map);
// Key and "3" references are broken
key = null;
/ / gc
System.gc();
// output {6=6}, strong referenced keys can be printed after gcSystem.out.println(map); }}Copy the codeIn this case, variables declared by new String() are weak references. Using the “6” declaration will always be in the constant pool and will not be cleaned up, so the “6” element will always be in the map and all other elements will be cleaned up by gc.
conclusion
(1) WeakHashMap uses (array + linked list) storage structure;
(2) Key in WeakHashMap is a weak reference, which will be cleared during GC;
(3) Entries corresponding to invalid keys are excluded in each map operation.
(4) When you use String as a key, you must use new String() to declare the key. Other basic types are wrapped in the same type.
(5) WeakHashMap is commonly used as cache;
Source address with detailed comments
WeakHashMap.java
eggs
What do you know about strong, Soft, weak, and virtual references?
(1) Strong reference
Use the most common references. If an object has a strong reference, it will never be collected by gc. If memory runs out, the GC would rather throw outofMemoryErrors than reclaim objects with strong references.
(2) Soft reference
If an object has only soft references, it will not be recycled if there is enough memory, but it will be recycled if there is not enough memory. As long as the object with a soft reference is not reclaimed, the program is fine.
(3) Weak reference
If an object has only weak references, it will be reclaimed when the GC scans it, regardless of whether there is enough memory.
(4) Virtual reference
If an object has only virtual references, it can be reclaimed by gc at any time, just as if it had no references at all.
Soft (weak, virtual) references must be used with a ReferenceQueue (ReferenceQueue) into which the gc will put the soft (weak, virtual) reference when it retrieves the object referenced by it.
For example, the Entry above is a weak reference to a key. When the key is reclaimed, the Entry is placed in a queue.
Welcome to pay attention to my public number “Tong Elder brother read source code”, view more source code series articles, with Tong elder brother tour the ocean of source code.
