【死磕 Java 集合】— WeakHashMap原始碼分析

簡介

WeakHashMap是一種弱取用map，內部的key會儲存為弱取用，當jvm gc的時候，如果這些key沒有強取用存在的話，會被gc回收掉，下一次當我們操作map的時候會把對應的Entry整個刪除掉，基於這種特性，WeakHashMap特別適用於快取處理。

繼承體系

可見，WeakHashMap沒有實現Clone和Serializable介面，所以不具有克隆和序列化的特性。

儲存結構

WeakHashMap因為gc的時候會把沒有強取用的key回收掉，所以註定了它裡面的元素不會太多，因此也就不需要像HashMap那樣元素多的時候轉化為紅黑樹來處理了。

因此，WeakHashMap的儲存結構只有（陣列 + 連結串列）。

原始碼解析

屬性

1. /**
2. * 預設初始容量為16
3. */
4. private static final int DEFAULT_INITIAL_CAPACITY = 16;
5.  
6. /**
7. * 最大容量為2的30次方
8. */
9. private static final int MAXIMUM_CAPACITY = 1 << 30;
10.  
11. /**
12. * 預設裝載因子
13. */
14. private static final float DEFAULT_LOAD_FACTOR = 0.75f;
15.  
16. /**
17. * 桶
18. */
19. Entry[] table;
20.  
21. /**
22. * 元素個數
23. */
24. private int size;
25.  
26. /**
27. * 擴容門檻，等於capacity * loadFactor
28. */
29. private int threshold;
30.  
31. /**
32. * 裝載因子
33. */
34. private final float loadFactor;
35.  
36. /**
37. * 取用佇列，當弱鍵失效的時候會把Entry新增到這個佇列中
38. */
39. private final ReferenceQueue<Object> queue = new ReferenceQueue<>();

（1）容量

容量為陣列的長度，亦即桶的個數，預設為16，最大為2的30次方，當容量達到64時才可以樹化。

（2）裝載因子

裝載因子用來計算容量達到多少時才進行擴容，預設裝載因子為0.75。

（3）取用佇列

當弱鍵失效的時候會把Entry新增到這個佇列中，當下次訪問map的時候會把失效的Entry清除掉。

Entry內部類

WeakHashMap內部的儲存節點, 沒有key屬性。

1. private static class Entry extends WeakReference<Object> implements Map.Entry {
2. // 可以發現沒有key, 因為key是作為弱取用存到Referen類中
3. V value;
4. final int hash;
5. Entry next;
6.  
7. Entry(Object key, V value,
8. ReferenceQueue<Object> queue,
9. int hash, Entry next) {
10. // 呼叫WeakReference的構造方法初始化key和取用佇列
11. super(key, queue);
12. this.value = value;
13. this.hash = hash;
14. this.next = next;
15. }
16. }
17.  
18. public class WeakReference extends Reference {
19. public WeakReference(T referent, ReferenceQueue super T> q) {
20. // 呼叫Reference的構造方法初始化key和取用佇列
21. super(referent, q);
22. }
23. }
24.  
25. public abstract class Reference {
26. // 實際儲存key的地方
27. private T referent; /* Treated specially by GC */
28. // 取用佇列
29. volatile ReferenceQueue super T> queue;
30.  
31. Reference(T referent, ReferenceQueue super T> queue) {
32. this.referent = referent;
33. this.queue = (queue == null) ? ReferenceQueue.NULL : queue;
34. }
35. }

從Entry的構造方法我們知道，key和queue最終會傳到到Reference的構造方法中，這裡的key就是Reference的referent屬性，它會被gc特殊對待，即當沒有強取用存在時，當下一次gc的時候會被清除。

構造方法

1. public WeakHashMap(int initialCapacity, float loadFactor) {
2. if (initialCapacity < 0)
3. throw new IllegalArgumentException("Illegal Initial Capacity: "+
4. initialCapacity);
5. if (initialCapacity > MAXIMUM_CAPACITY)
6. initialCapacity = MAXIMUM_CAPACITY;
7.  
8. if (loadFactor <= 0 || Float.isNaN(loadFactor))
9. throw new IllegalArgumentException("Illegal Load factor: "+
10. loadFactor);
11. int capacity = 1;
12. while (capacity < initialCapacity)
13. capacity <<= 1;
14. table = newTable(capacity);
15. this.loadFactor = loadFactor;
16. threshold = (int)(capacity * loadFactor);
17. }
18.  
19. public WeakHashMap(int initialCapacity) {
20. this(initialCapacity, DEFAULT_LOAD_FACTOR);
21. }
22.  
23. public WeakHashMap() {
24. this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
25. }
26.  
27. public WeakHashMap(Map extends K, ? extends V> m) {
28. this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
29. DEFAULT_INITIAL_CAPACITY),
30. DEFAULT_LOAD_FACTOR);
31. putAll(m);
32. }

構造方法與HashMap基本類似，初始容量為大於等於傳入容量最近的2的n次方，擴容門檻threshold等於capacity * loadFactor。

put(K key, V value)方法

新增元素的方法。

1. public V put(K key, V value) {
2. // 如果key為空，用空物件代替
3. Object k = maskNull(key);
4. // 計算key的hash值
5. int h = hash(k);
6. // 獲取桶
7. Entry[] tab = getTable();
8. // 計算元素在哪個桶中，h & (length-1)
9. int i = indexFor(h, tab.length);
10.  
11. // 遍歷桶對應的連結串列
12. for (Entry e = tab[i]; e != null; e = e.next) {
13. if (h == e.hash && eq(k, e.get())) {
14. // 如果找到了元素就使用新值替換舊值，並傳回舊值
15. V oldValue = e.value;
16. if (value != oldValue)
17. e.value = value;
18. return oldValue;
19. }
20. }
21.  
22. modCount++;
23. // 如果沒找到就把新值插入到連結串列的頭部
24. Entry e = tab[i];
25. tab[i] = new Entry<>(k, value, queue, h, e);
26. // 如果插入元素後數量達到了擴容門檻就把桶的數量擴容為2倍大小
27. if (++size >= threshold)
28. resize(tab.length * 2);
29. return null;
30. }

（1）計算hash；

這裡與HashMap有所不同，HashMap中如果key為空直接傳回0，這裡是用空物件來計算的。

另外打散方式也不同，HashMap只用了一次異或，這裡用了四次，HashMap給出的解釋是一次夠了，而且就算衝突了也會轉換成紅黑樹，對效率沒什麼影響。

（2）計算在哪個桶中；

（3）遍歷桶對應的連結串列；

（4）如果找到元素就用新值替換舊值，並傳回舊值；

（5）如果沒找到就在連結串列頭部插入新元素；

HashMap就插入到連結串列尾部。

（6）如果元素數量達到了擴容門檻，就把容量擴大到2倍大小；

HashMap中是大於threshold才擴容，這裡等於threshold就開始擴容了。

resize(int newCapacity)方法

擴容方法。

1. void resize(int newCapacity) {
2. // 獲取舊桶，getTable()的時候會剔除失效的Entry
3. Entry[] oldTable = getTable();
4. // 舊容量
5. int oldCapacity = oldTable.length;
6. if (oldCapacity == MAXIMUM_CAPACITY) {
7. threshold = Integer.MAX_VALUE;
8. return;
9. }
10.  
11. // 新桶
12. Entry[] newTable = newTable(newCapacity);
13. // 把元素從舊桶轉移到新桶
14. transfer(oldTable, newTable);
15. // 把新桶賦值桶變數
16. table = newTable;
17.  
18. /*
19. * If ignoring null elements and processing ref queue caused massive
20. * shrinkage, then restore old table. This should be rare, but avoids
21. * unbounded expansion of garbage-filled tables.
22. */
23. // 如果元素個數大於擴容門檻的一半，則使用新桶和新容量，並計算新的擴容門檻
24. if (size >= threshold / 2) {
25. threshold = (int)(newCapacity * loadFactor);
26. } else {
27. // 否則把元素再轉移回舊桶，還是使用舊桶
28. // 因為在transfer的時候會清除失效的Entry，所以元素個數可能沒有那麼大了，就不需要擴容了
29. expungeStaleEntries();
30. transfer(newTable, oldTable);
31. table = oldTable;
32. }
33. }
34.  
35. private void transfer(Entry[] src, Entry[] dest) {
36. // 遍歷舊桶
37. for (int j = 0; j < src.length; ++j) {
38. Entry e = src[j];
39. src[j] = null;
40. while (e != null) {
41. Entry next = e.next;
42. Object key = e.get();
43. // 如果key等於了null就清除，說明key被gc清理掉了，則把整個Entry清除
44. if (key == null) {
45. e.next = null; // Help GC
46. e.value = null; // " "
47. size--;
48. } else {
49. // 否則就計算在新桶中的位置並把這個元素放在新桶對應連結串列的頭部
50. int i = indexFor(e.hash, dest.length);
51. e.next = dest[i];
52. dest[i] = e;
53. }
54. e = next;
55. }
56. }
57. }

（1）判斷舊容量是否達到最大容量；

（2）新建新桶並把元素全部轉移到新桶中；

（3）如果轉移後元素個數不到擴容門檻的一半，則把元素再轉移回舊桶，繼續使用舊桶，說明不需要擴容；

（4）否則使用新桶，並計算新的擴容門檻；

（5）轉移元素的過程中會把key為null的元素清除掉，所以size會變小；

get(Object key)方法

獲取元素。

1. public V get(Object key) {
2. Object k = maskNull(key);
3. // 計算hash
4. int h = hash(k);
5. Entry[] tab = getTable();
6. int index = indexFor(h, tab.length);
7. Entry e = tab[index];
8. // 遍歷連結串列，找到了就傳回
9. while (e != null) {
10. if (e.hash == h && eq(k, e.get()))
11. return e.value;
12. e = e.next;
13. }
14. return null;
15. }

（1）計算hash值；

（2）遍歷所在桶對應的連結串列；

（3）如果找到了就傳回元素的value值；

（4）如果沒找到就傳回空；

remove(Object key)方法

移除元素。

1. public V remove(Object key) {
2. Object k = maskNull(key);
3. // 計算hash
4. int h = hash(k);
5. Entry[] tab = getTable();
6. int i = indexFor(h, tab.length);
7. // 元素所在的桶的第一個元素
8. Entry prev = tab[i];
9. Entry e = prev;
10.  
11. // 遍歷連結串列
12. while (e != null) {
13. Entry next = e.next;
14. if (h == e.hash && eq(k, e.get())) {
15. // 如果找到了就刪除元素
16. modCount++;
17. size--;
18.  
19. if (prev == e)
20. // 如果是頭節點，就把頭節點指向下一個節點
21. tab[i] = next;
22. else
23. // 如果不是頭節點，刪除該節點
24. prev.next = next;
25. return e.value;
26. }
27. prev = e;
28. e = next;
29. }
30.  
31. return null;
32. }

（1）計算hash；

（2）找到所在的桶；

（3）遍歷桶對應的連結串列；

（4）如果找到了就刪除該節點，並傳回該節點的value值；

（5）如果沒找到就傳回null；

expungeStaleEntries()方法

剔除失效的Entry。

1. private void expungeStaleEntries() {
2. // 遍歷取用佇列
3. for (Object x; (x = queue.poll()) != null; ) {
4. synchronized (queue) {
5. @SuppressWarnings("unchecked")
6. Entry e = (Entry) x;
7. int i = indexFor(e.hash, table.length);
8. // 找到所在的桶
9. Entry prev = table[i];
10. Entry p = prev;
11. // 遍歷連結串列
12. while (p != null) {
13. Entry next = p.next;
14. // 找到該元素
15. if (p == e) {
16. // 刪除該元素
17. if (prev == e)
18. table[i] = next;
19. else
20. prev.next = next;
21. // Must not null out e.next;
22. // stale entries may be in use by a HashIterator
23. e.value = null; // Help GC
24. size--;
25. break;
26. }
27. prev = p;
28. p = next;
29. }
30. }
31. }
32. }

（1）當key失效的時候gc會自動把對應的Entry新增到這個取用佇列中；

（2）所有對map的操作都會直接或間接地呼叫到這個方法先移除失效的Entry，比如getTable()、size()、resize()；

（3）這個方法的目的就是遍歷取用佇列，並把其中儲存的Entry從map中移除掉，具體的過程請看類註釋；

（4）從這裡可以看到移除Entry的同時把value也一併置為null幫助gc清理元素，防禦性程式設計。

使用案例

說了這麼多，不舉個使用的例子怎麼過得去。

1. package com.coolcoding.code;
2.  
3. import java.util.Map;
4. import java.util.WeakHashMap;
5.  
6. public class WeakHashMapTest {
7.  
8. public static void main(String[] args) {
9. Map<String, Integer> map = new WeakHashMap<>(3);
10.  
11. // 放入3個new String()宣告的字串
12. map.put(new String("1"), 1);
13. map.put(new String("2"), 2);
14. map.put(new String("3"), 3);
15.  
16. // 放入不用new String()宣告的字串
17. map.put("6", 6);
18.  
19. // 使用key強取用"3"這個字串
20. String key = null;
21. for (String s : map.keySet()) {
22. // 這個"3"和new String("3")不是一個取用
23. if (s.equals("3")) {
24. key = s;
25. }
26. }
27.  
28. // 輸出{6=6, 1=1, 2=2, 3=3}，未gc所有key都可以打印出來
29. System.out.println(map);
30.  
31. // gc一下
32. System.gc();
33.  
34. // 放一個new String()宣告的字串
35. map.put(new String("4"), 4);
36.  
37. // 輸出{4=4, 6=6, 3=3}，gc後放入的值和強取用的key可以打印出來
38. System.out.println(map);
39.  
40. // key與"3"的取用斷裂
41. key = null;
42.  
43. // gc一下
44. System.gc();
45.  
46. // 輸出{6=6}，gc後強取用的key可以打印出來
47. System.out.println(map);
48. }
49. }

在這裡透過new String()宣告的變數才是弱取用，使用”6″這種宣告方式會一直存在於常量池中，不會被清理，所以”6″這個元素會一直在map裡面，其它的元素隨著gc都會被清理掉。

總結

（1）WeakHashMap使用（陣列 + 連結串列）儲存結構；

（2）WeakHashMap中的key是弱取用，gc的時候會被清除；

（3）每次對map的操作都會剔除失效key對應的Entry；

（4）使用String作為key時，一定要使用new String()這樣的方式宣告key，才會失效，其它的基本型別的包裝型別是一樣的；

（5）WeakHashMap常用來作為快取使用；

帶詳細註釋的原始碼地址

WeakHashMap.java

彩蛋

強、軟、弱、虛取用知多少？

（1）強取用

使用最普遍的取用。如果一個物件具有強取用，它絕對不會被gc回收。如果記憶體空間不足了，gc寧願丟擲OutOfMemoryError，也不是會回收具有強取用的物件。

（2）軟取用

如果一個物件只具有軟取用，則記憶體空間足夠時不會回收它，但記憶體空間不夠時就會回收這部分物件。只要這個具有軟取用物件沒有被回收，程式就可以正常使用。

（3）弱取用

如果一個物件只具有弱取用，則不管記憶體空間夠不夠，當gc掃描到它時就會回收它。

（4）虛取用

如果一個物件只具有虛取用，那麼它就和沒有任何取用一樣，任何時候都可能被gc回收。

軟（弱、虛）取用必須和一個取用佇列（ReferenceQueue）一起使用，當gc回收這個軟（弱、虛）取用取用的物件時，會把這個軟（弱、虛）取用放到這個取用佇列中。

比如，上述的Entry是一個弱取用，它取用的物件是key，當key被回收時，Entry會被放到queue中。