Overview of WeakHashMap

WeakHashMap is a map that stores mapping data based on hash table implemented by weak keys. When the JVM cleans up and reclaims the objects pointed to by these weak keys, WeakHashMap automatically and effectively removes the reclaimed maps from the map.

Relevant knowledge cited

There are four kinds of references in Java: Strong Reference, Soft Reference, Weak Reference and Phantom Reference.
You can see several corresponding packages in the java.lang.ref package:

• Strong Reference
  Strong references are references to the default implementation of java. The JVM retains strong references for as long as possible. When no object points to it, the JVM will reclaim it.

  //This is a strong quotation
  Object obj = new Object();

• Weak Reference
  Weak references refer to objects that do not have any strong references and will be reclaimed the next time the gc of the JVM is reclaimed.

  //Here is a strong reference
  Object obj = new Object();
  //new A Weak Reference
  WeakReference<Object> weakRef = new WeakReference<Object>(obj);
  //No strong references after obj = null
  obj = null;
  //Because the gc time of the jvm is uncertain, the loop
  while(true){
      //weakRef.get() returns the object when it has not been reclaimed, otherwise returns null
      if(weakRef.get() != null){
          System.out.println("is alive");
      }
      else{
          System.out.println("is not alive");
          break;
      }
  }

  Operation results:

  ...
  ...
  is alive
  is alive
  is alive
  is alive
  is alive
  is alive
  is not alive

• Soft Reference
  Soft reference and weak reference are basically the same in nature. The difference is that soft reference JVM only recycles soft reference when virtual machine memory is insufficient, which makes soft reference very suitable for caching applications.
• Phantom Reference
  The get method of this reference type returns null at any time. Its only function is to record when an object was reclaimed by gc.

Here comes the problem. How to record object recycling?
From the class included in the picture above, you can see that there is a class of Reference Queue, which is translated into Chinese as a reference queue. What is it used for?
The original java provides this reference queue, which can be passed as a parameter to the reference constructor. Then when the object is recycled, one thing will be done, that is, to put the recycled object in this queue.

Examples of using Reference Queue to record objects being recycled:

Object obj = new Object();
ReferenceQueue<Object> queue = new ReferenceQueue<>();
WeakReference<Object> weakRef = new WeakReference<Object>(obj, queue);

System.out.println(obj);
obj = null;
System.gc();
while(true){
    //Has been recycled
    if(weakRef.get() == null){
        Object o;
        //Get from the queue
        if((o = queue.poll()) != null){
            System.out.println(o);
            break;
        }
    }
}

Operation results:

java.lang.Object@15db9742
java.lang.ref.WeakReference@6d06d69c

WeakHashMap

WeakHashMap is easy to understand when you have the concepts of reference and weak reference and understand HashMap. This paper is based on JDK 1.8

1. Class Definition

public class WeakHashMap<K,V>
    extends AbstractMap<K,V>
    implements Map<K,V> 

Like HashMap, HashMap inherits from AbstractMap and implements the Map interface. Unlike HashMap, it also implements Cloneable and Serializable interfaces, which means that WeakHashMap will not support cloning and serialization.

2. Attributes

//Default capacity
private static final int DEFAULT_INITIAL_CAPACITY = 16;
//Maximum capacity
private static final int MAXIMUM_CAPACITY = 1 << 30;
//Default load factor
private static final float DEFAULT_LOAD_FACTOR = 0.75f;
//Node array
Entry<K,V>[] table;
//size
private int size;
//threshold
private int threshold;
//Loading factor
private final float loadFactor;
//Reference Queue for recording gc recovery
private final ReferenceQueue<Object> queue = new ReferenceQueue<>();
//modify flag
int modCount;

You can see that basically there is not much in and out of HashMap, but the obvious difference is that there is an additional Reference Queue, which is clearly the reference queue through which WeakHashMap is automatically cleaned up.

2. Construction Method

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);
}
//Other construction parameters are basically the same as HashMap, omitted

A little bit different from HashMap is that HashMap has some different algorithms for determining capacities. HashMap is a five-pass unsigned right-shift union or operation

    static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

WeakHashMap is implemented through a while loop.
At the same time, the table array of HashMap is not initialized directly in the constructor, but delayed after adding elements.

3. Entry node

private static class Entry<K,V> extends WeakReference<Object> implements Map.Entry<K,V> {
    V value;
    final int hash;
    Entry<K,V> next;

    /**
     * Creates new entry.
     */
    Entry(Object key, V value,
          ReferenceQueue<Object> queue,
          int hash, Entry<K,V> next) {
        super(key, queue);
        this.value = value;
        this.hash  = hash;
        this.next  = next;
    }
   //......

Here's a look at the constructor, passing in a Reference Queue, which seems to have a very similar usage of gc recycling recorded by the Root's original Reeference Queue. Because Entry inherits the WeakReference class, today's Entry object management is not a strong reference, but a weak reference, WeakReference. So when it is recycled, it will naturally be recorded in this reference queue. After that, all you need to do is clean up.

3. Key Approaches

1. Get method. In order to get the elements in the map from the table array that has been automatically cleaned up each time, the corresponding cleanup operation is added to the get method.

   public V get(Object key) {
   Object k = maskNull(key);
   int h = hash(k);
   //this getTable It's after getting cleaned up. table
   Entry<K,V>[] tab = getTable();
   int index = indexFor(h, tab.length);
   Entry<K,V> e = tab[index];
   while (e != null) {
       if (e.hash == h && eq(k, e.get()))
           return e.value;
       e = e.next;
   }
   return null;
   }
   
   
   

   How to clean up:

   private Entry<K,V>[] getTable() {
       //expunge means erased Stale: obsolete
       expungeStaleEntries();
       return table;
   }
   private void expungeStaleEntries() {
       //Traveling out of a queue
       for (Object x; (x = queue.poll()) != null; ) {
           synchronized (queue) {
               @SuppressWarnings("unchecked")
                   Entry<K,V> e = (Entry<K,V>) x;
               //Find the index by hash
               int i = indexFor(e.hash, table.length);
   
               Entry<K,V> prev = table[i];
               Entry<K,V> p = prev;
               //Traversal list
               while (p != null) {
                   //Record next node
                   Entry<K,V> next = p.next;
                   //If equal
                   if (p == e) {
                       //It happens to be the first node.
                       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;
                   }
                   //p records the next node for traversal and pref is the last node of p
                   prev = p;
                   p = next;
               }
           }
       }
   }

   Now it's clear that it's traversing the recovered records in the queue, and then finding and deleting the records in the table array and the list that handles hash conflicts.
   The expungeStaleEntries method above is also used in resize and size method calls for the first time. I won't go into details here.

2. hash method

   final int hash(Object k) {
       int h = k.hashCode();
   
       // This function ensures that hashCodes that differ only by
       // constant multiples at each bit position have a bounded
       // number of collisions (approximately 8 at default load factor).
       h ^= (h >>> 20) ^ (h >>> 12);
       return h ^ (h >>> 7) ^ (h >>> 4);
   }

It's different from HashMap, but it's a bit complicated. .

Features of WeakHashMap

• Store key-value pair mappings.
• key and value can be null
• Thread insecurity
• When keys are recycled by gc, maps in maps can be cleaned up automatically
• Cloning and serialization are not supported