JDK原始碼分析(9)之 WeakHashMap 相關
平時我們使用最多的資料結構肯定是 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
實現;