JDK源碼分析（9）之 WeakHashMap 相關

平時我們使用最多的數據結構肯定是 HashMap，但是在使用的時候我們必須知道每個鍵值對的生命周期，並且手動清除它；但是如果我們不是很清楚它的生命周期，這時候就比較麻煩；通常有這樣幾種處理方式：由一個線程定時處理，可以是或者；利用重寫，實現 FIFOCache 或者 LRUCache；可以 ...

平時我們使用最多的數據結構肯定是 HashMap，但是在使用的時候我們必須知道每個鍵值對的生命周期，並且手動清除它；但是如果我們不是很清楚它的生命周期，這時候就比較麻煩；通常有這樣幾種處理方式：

由一個線程定時處理，可以是Timer或者ScheduledThreadPoolExecutor；
利用重寫LinkedHashMap.removeEldestEntry()，實現 FIFOCache 或者 LRUCache；可以參考我之前寫的一篇博客 LinkedHashMap 相關；
利用 WeakHashMap 的特性，如果邏輯比較複雜還可以直接使用Reference；這裡可以參考 Reference 完全解讀和 Reference 框架概覽；

所以本文將主要介紹WeakHashMap的特性，以及補充一些關於 HashMap 實現的對比；相關 HashMap 的介紹也可以參考 HashMap 相關；

一、使用場景

上面也介紹了，WeakHashMap適用於不是非常重要的緩存類似的場景；例如：

WeakHashMap<Object, Integer> map = new WeakHashMap<>();

for (int i = 0; i < 100; i++) {
  map.put(new Object(), i);
}

System.out.println(map.size());  // 1
System.gc();                     // 2
System.out.println(map.size());  // 3
System.out.println(map.size());  // 4
System.out.println(map.size());  // 5
System.out.println(map);         // 6
System.out.println(map.size());  // 7

// 列印：
100
100
100
46
{}
0

對於以上的結果你可能和我列印的不一樣，WeakHashMap按照語義應該是，當 key 沒有強引用指向的時候，會自動清除 key 和 value；我這裡先解釋它的釋放過程，如果你覺得很清晰，那WeakHashMap你就算是掌握了；

首先 for 迴圈結束的時候，key 已經沒用強引用指向了，此時所有的 key 都是弱引用了；
接下來執行1，因為我這裡只有一個方法，新生代還有足夠的空間，所以不會觸發 GC，所以所有的 key 任然在堆裡面，所以列印100；
然後手動觸發 GC，雖然System.gc();不一定會立即執行，但是我這裡只有一個方法，所以肯定會執行 GC，這裡可以打開 GC 日誌查看，-verbose:gc；因為所有的 key 都是弱引用，所以referent被致為 null，同時將 key 註冊到 ReferenceQueue中；
在執行 3-7 的時候，按語義 map 應該為空；但是將 key 註冊到 ReferenceQueue並非原子性一次完成的，所以這裡會列印不同的值，每註冊完成一個，在 map 進行操作的時候，就會將其移除；

將上面的代碼改成多線程分析思路也是一樣的，如果你覺得有不清楚的地方可以查看下文；

二、WeakHashMap 源碼分析

1. 類定義

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

可以看到雖然WeakHashMap也是基於哈希表，但是卻並非像LinkedHashMap一樣是繼承於HashMap，並且WeakHashMap也沒有實現Cloneable, Serializable兩個介面，這是因為WeakHashMap基於WeakReference實現的，弱引用並不建議實現序列化，同時弱引用一般用於不是很重要的緩存，也就沒必要實現Cloneable, Serializable兩個介面了；

2. 核心方法

private final ReferenceQueue<Object> queue = new ReferenceQueue<>();

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

  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;
  }

  public K getKey() { }
  public V getValue() {
  public V setValue(V newValue) {
  public int hashCode() {
  public String toString() {
}

private void expungeStaleEntries() {
  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);

      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
          size--;
          break;
        }
        prev = p;
        p = next;
      }
    }
  }
}

上面代碼所列的ReferenceQueue，Entry，expungeStaleEntries()就是WeakHashMap實現的核心了；這裡強烈建議要先看 Reference 完全解讀和 Reference 框架概覽這兩篇博客，裡面同樣的內容我也不會再贅述了；

Entry<K,V> extends WeakReference<Object>，表明所有的節點都是WeakReference，而 key 則是 referent；
queue，所有 key 使用同一個ReferenceQueue監聽器，每當 key 被回收的時候，entry 將會被註冊到ReferenceQueue中；
expungeStaleEntries，將註冊到ReferenceQueue中的 entry 移除，並將 value 置為 null；WeakHashMap的所有操作都先執行expungeStaleEntries，這樣WeakHashMap就實現了自動回收不在需要的 key 和 value；

三、性能對比

其實上面的內容就已經將WeakHashMap的主要實現講完了，但是我之前在看HashMap源碼的時候，並沒有對比 JDK1.7 和 JDK1.8，但是在這裡發現其實WeakHashMap的實現和 JDK1.7 差不多，所以接下來我將主要對比一下WeakHashMap和HashMap；

1. 容量計算

在WeakHashMap和HashMap中都要求容量是2的冪，因為當容量為2的冪時，使用除留餘數法計算哈希桶位置時可以使用hash % length = hash & (length-1)的性質進行優化；

// WeakHashMap
int capacity = 1;
while (capacity < initialCapacity)
  capacity <<= 1;

// HashMap
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;
}

簡單測試可以得到：

	initCap = 10	50	100
WeakHashMap	30	32	26
HashMap	3	3	3

代碼比較簡單我就不貼了，從上表也可以看到了tableSizeFor不僅高效而且穩定；

2. 哈希計算

// WeakHashMap
final int hash(Object k) {
  int h = k.hashCode();
  h ^= (h >>> 20) ^ (h >>> 12);
  return h ^ (h >>> 7) ^ (h >>> 4);
}

// HashMap
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

兩種hash演算法都是要避免極端的hashCode()，但是HashMap卻更為透徹，因為影響哈希桶位置的只有 hash 的低位（容量2的n次方，n個低位），直接將高位與上低位，使高位 hash 參與位置計算，簡潔且高效；

此外還有put方法，但是裡面還牽涉紅黑樹，對於本文就扯得有點遠了，所以暫不講；

總結

WeakHashMap是WeakReference的典型應用，在靈活應用WeakHashMap之後，如果有更為複雜的邏輯，可以直接使用Reference實現；