HashMap 之弱引用 - WeakHashMap

■ Java 引用的相關知識

　 1. 強引用

Object o = new Object();

• 強引用是Java預設實作的引用，JVM會盡可能長時間的保留強引用的存在（直到記憶體溢出）
• 當記憶體空間不足，Java虛拟機甯願抛出OutOfMemoryError錯誤，使程式異常終止，也不會靠随意回收具有強引用的對象來解決記憶體不足的問題：隻有當沒有任何對象指向它時JVM将會回收

　2. 軟引用

public class SoftReference<T> extends Reference<T> {...}

• 軟引用隻會在虛拟機記憶體不足的時候才會被回收
• 軟引用可以和一個引用隊列（ReferenceQueue）聯合使用，如果軟引用所引用的對象被垃圾回收器回收，Java虛拟機就會把這個軟引用加入到與之關聯的引用隊列中

   3. 弱引用

public class WeakReference<T> extends Reference<T> {...}

• 弱引用是指當對象沒有任何的強引用存在，在下次GC回收的時候它将會被回收
• 在垃圾回收器線程掃描它所管轄的記憶體區域的過程中，一旦發現了隻具有弱引用的對象，不管目前記憶體空間足夠與否，都會回收它的記憶體
• 需要注意的是：由于垃圾回收器是一個優先級很低的線程，是以不一定會很快發現那些隻具有弱引用的對象

■ WeakHashMap 的認識：

• WeakHashMap 是存儲鍵值對(key-value)的非同步且無序的散清單，鍵和值都允許為null，基本跟 HashMap一緻
• 特殊之處在于 WeakHashMap 裡的entry可能會被GC自動删除，即使沒有主動調用 remove() 或者 clear() 方法
• 其鍵為弱鍵，除了自身有對key的引用外，此key沒有其他引用那麼此map會自動丢棄此值
• 在《Effective Java》一書中第六條，消除陳舊對象時，提到了weakHashMap，用于短時間内就過期的緩存
• 由于與JDK1.7版本的HashMap實作原理一緻（具體請參見筆者的 HashMap一文通），這裡隻讨論不同
• 若有機會寫JVM篇的垃圾回收機制時會再進一步描述 Reference

   1. 類定義

public class WeakHashMap<K,V>

extends AbstractMap<K,V>

implements Map<K,V>

  2. 重要的全局變量

/**
  * The default initial capacity -- MUST be a power of two.
  * 預設容量，必須是2次幂
  */
private static final int DEFAULT_INITIAL_CAPACITY = 16;
/**
  * The maximum capacity, used if a higher value is implicitly specified by either of the
  * constructors with arguments. MUST be a power of two <= 1<<30.
  * 最大容量，必須為2次幂且 <= 1<<30
  */
private static final int MAXIMUM_CAPACITY = 1 << 30;
/**
  * The load factor used when none specified in constructor.
  * 負載因子
  */
private static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
  * The table, resized as necessary. Length MUST Always be a power of two.
  * 容量必須為2次幂的數組
  */
Entry<K,V>[] table;
/**
  * The number of key-value mappings contained in this weak hash map.
  * 擁有鍵值對的數量
  */
private int size;
/**
  * The next size value at which to resize (capacity * load factor).
  * 門檻值 -- 擴容判斷依據
  */
private int threshold;
/**
  * The load factor for the hash table.
  */
private final float loadFactor;
/**
  * Reference queue for cleared WeakEntries
  * 引用隊列，用于存儲已被GC清除的WeakEntries
  */
private final ReferenceQueue<Object> queue = new ReferenceQueue<>();      

  3. 構造器

// 預設構造函數
WeakHashMap()
// 指定"容量大小"的構造函數
WeakHashMap(int capacity)
// 指定"容量大小"和"負載因子"的構造函數
WeakHashMap(int capacity, float loadFactor)
// 包含"子Map"的構造函數
WeakHashMap(Map<? extends K, ? extends V> map)      

• 實作跟JDK1.7版本HashMap的實作一緻,具體請參見筆者的​​HashMap - 基于哈希表和 Map 接口的鍵值對利器 （JDK 1.7）​​

 4. Entry

/**
  * The entries in this hash table extend WeakReference, using its main ref field as the key.
  * 該Enty繼承WeakReference，進而具備弱引用的特性
  */
private static class Entry<K,V> extends WeakReference<Object> implements Map.Entry<K,V> {
    V value;
    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;
    }
    ....
}      

■ WeakHashMap 的重要方法

• 正常 put(), get(), remove() 等不詳細研究，來看下比較關鍵的 expungeStaleEntries()

/**
  * Expunges stale entries from the table. -- 删除過時的entry
  * 該方法是實作弱鍵回收的最關鍵方法，也是區分HashMap的根本方法
  * 核心：移除table和queue的并集元素（queue中存儲是已被GC的key，注意是key！！）
  * 效果：key在GC的時候被清除，value在key清除後通路WeakHashMap被清除
  */
private void expungeStaleEntries() {
    //從隊列中出隊周遊
    //poll 移除并返問隊列頭部的元素；如果隊列為空，則傳回null
    for (Object x; (x = queue.poll()) != null; ) {
        synchronized (queue) {
            //值得一提的是WeakHashMap是非線程安全的，這裡卻同步了一下
            //大神原本的用意是保證在多線程時能不破壞資料結構，但JavaDoc已經強調這類非安全，如下文
            //http://bugs.java.com/bugdatabase/view_bug.do?bug_id=6425537
            @SuppressWarnings("unchecked")
                Entry<K,V> e = (Entry<K,V>) x;
            //找到該隊列中的元素在數組中的位置，并移除該元素（table和queue都需要移除）    
            int i = indexFor(e.hash, table.length);
            Entry<K,V> prev = table[i];
            Entry<K,V> p = prev;
            while (p != null) {
                Entry<K,V> next = p.next;
                if (p == e) {
                    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 移除value
                    size--;
                    break;
                }
                prev = p;
                p = next;
            }
        }
    }
}