歡迎光臨
每天分享高質量文章

【死磕 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中。

已同步到看一看
赞(0)

分享創造快樂