前言:WeakHashMap可能平時使用的頻率并不高,但是你可能聽過WeakHashMap會進行自動回收吧,下面就對其原理進行分析。
注:本文jdk源碼版本為jdk1.8.0_172
1.WeakHashMap介紹
WeakHashMap是一種弱引用的map,底層資料結構為數組+連結清單,内部的key存儲為弱引用,在GC時如果key不存在強引用的情況下會被回收掉,而對于value的回收會在下一次操作map時回收掉,是以WeakHashMap适合緩存處理。
1 java.lang.Object
2 ↳ java.util.AbstractMap<K, V>
3 ↳ java.util.WeakHashMap<K, V>
4
5 public class WeakHashMap<K,V>
6 extends AbstractMap<K,V>
7 implements Map<K,V> {}
從WeakHashMap的繼承關系上來看,可知其繼承AbstractMap,實作了Map接口。其底層資料結構是Entry數組,Entry的資料結構如下:
從源碼上可知,Entry的内部并沒有存儲key的值,而是通過調用父類的構造方法,傳入key和ReferenceQueue,最終key和queue會關聯到Reference中,這裡是GC時,清清除key的關鍵,這裡大緻看下Reference的源碼:
1 private static class ReferenceHandler extends Thread {
2
3 private static void ensureClassInitialized(Class<?> clazz) {
4 try {
5 Class.forName(clazz.getName(), true, clazz.getClassLoader());
6 } catch (ClassNotFoundException e) {
7 throw (Error) new NoClassDefFoundError(e.getMessage()).initCause(e);
8 }
9 }
10
11 static {
12 // pre-load and initialize InterruptedException and Cleaner classes
13 // so that we don't get into trouble later in the run loop if there's
14 // memory shortage while loading/initializing them lazily.
15 ensureClassInitialized(InterruptedException.class);
16 ensureClassInitialized(Cleaner.class);
17 }
18
19 ReferenceHandler(ThreadGroup g, String name) {
20 super(g, name);
21 }
22
23 public void run() {
24 // 注意這裡為一個死循環
25 while (true) {
26 tryHandlePending(true);
27 }
28 }
29 }
30 static boolean tryHandlePending(boolean waitForNotify) {
31 Reference<Object> r;
32 Cleaner c;
33 try {
34 synchronized (lock) {
35 if (pending != null) {
36 r = pending;
37 // 'instanceof' might throw OutOfMemoryError sometimes
38 // so do this before un-linking 'r' from the 'pending' chain...
39 c = r instanceof Cleaner ? (Cleaner) r : null;
40 // unlink 'r' from 'pending' chain
41 pending = r.discovered;
42 r.discovered = null;
43 } else {
44 // The waiting on the lock may cause an OutOfMemoryError
45 // because it may try to allocate exception objects.
46 if (waitForNotify) {
47 lock.wait();
48 }
49 // retry if waited
50 return waitForNotify;
51 }
52 }
53 } catch (OutOfMemoryError x) {
54 // Give other threads CPU time so they hopefully drop some live references
55 // and GC reclaims some space.
56 // Also prevent CPU intensive spinning in case 'r instanceof Cleaner' above
57 // persistently throws OOME for some time...
58 Thread.yield();
59 // retry
60 return true;
61 } catch (InterruptedException x) {
62 // retry
63 return true;
64 }
65
66 // Fast path for cleaners
67 if (c != null) {
68 c.clean();
69 return true;
70 }
71 // 加入對列
72 ReferenceQueue<? super Object> q = r.queue;
73 if (q != ReferenceQueue.NULL) q.enqueue(r);
74 return true;
75 }
76
77 static {
78 ThreadGroup tg = Thread.currentThread().getThreadGroup();
79 for (ThreadGroup tgn = tg;
80 tgn != null;
81 tg = tgn, tgn = tg.getParent());
82 // 建立handler
83 Thread handler = new ReferenceHandler(tg, "Reference Handler");
84 /* If there were a special system-only priority greater than
85 * MAX_PRIORITY, it would be used here
86 */
87 // 線程優先級最大
88 handler.setPriority(Thread.MAX_PRIORITY);
89 // 設定為守護線程
90 handler.setDaemon(true);
91 handler.start();
92
93 // provide access in SharedSecrets
94 SharedSecrets.setJavaLangRefAccess(new JavaLangRefAccess() {
95 @Override
96 public boolean tryHandlePendingReference() {
97 return tryHandlePending(false);
98 }
99 });
100 }
View Code
通過檢視Reference源碼可知,在執行個體化時會建立一個守護線程,然後不斷循環将GC時的Entry入隊,關于如何清除value值的下面會進行分析。
2.具體源碼分析
put操作:
1 public V put(K key, V value) {
2 // 确定key值,允許key為null
3 Object k = maskNull(key);
4 // 擷取器hash值
5 int h = hash(k);
6 // 擷取tab
7 Entry<K,V>[] tab = getTable();
8 // 确定在tab中的位置 簡單的&操作
9 int i = indexFor(h, tab.length);
10 // 周遊,是否要進行覆寫操作
11 for (Entry<K,V> e = tab[i]; e != null; e = e.next) {
12 if (h == e.hash && eq(k, e.get())) {
13 V oldValue = e.value;
14 if (value != oldValue)
15 e.value = value;
16 return oldValue;
17 }
18 }
19
20 // 修改次數自增
21 modCount++;
22 // 取出i上的元素
23 Entry<K,V> e = tab[i];
24 // 建構連結清單,新元素在連結清單頭
25 tab[i] = new Entry<>(k, value, queue, h, e);
26 // 檢查是否需要擴容
27 if (++size >= threshold)
28 resize(tab.length * 2);
29 return null;
30 }
分析:
WeakHashMap的put操作與HashMap相似,都會進行覆寫操作(相同key),但是注意插入新節點是放在連結清單頭。上述代碼中還要一個關鍵的函數getTable,後面會對其進行具體分析,先記下。
get操作:
1 public V get(Object key) {
2 // 确定key
3 Object k = maskNull(key);
4 // 計算其hashCode
5 int h = hash(k);
6 Entry<K,V>[] tab = getTable();
7 int index = indexFor(h, tab.length);
8 // 擷取對應位置上的元素
9 Entry<K,V> e = tab[index];
10 while (e != null) {
11 // 如果hashCode相同,并且key也相同,則傳回,否則繼續循環
12 if (e.hash == h && eq(k, e.get()))
13 return e.value;
14 e = e.next;
15 }
16 // 未找到,則傳回null
17 return null;
18 }
get操作邏輯簡單,根據key周遊對應元素即可。
remove操作:
1 public V remove(Object key) {
2 Object k = maskNull(key);
3 int h = hash(k);
4 Entry<K,V>[] tab = getTable();
5 int i = indexFor(h, tab.length);
6 // 數組上第一個元素
7 Entry<K,V> prev = tab[i];
8 Entry<K,V> e = prev;
9 // 循環
10 while (e != null) {
11 Entry<K,V> next = e.next;
12 // 如果hash值相同,并且key一樣,則進行移除操作
13 if (h == e.hash && eq(k, e.get())) {
14 // 修改次數自增
15 modCount++;
16 // 元素個數自減
17 size--;
18 // 如果就是頭元素,則直接移除即可
19 if (prev == e)
20 tab[i] = next;
21 else
22 // 否則将前驅元素的next指派為next,則将e移除
23 prev.next = next;
24 return e.value;
25 }
26 // 更新prev和e,繼續循環
27 prev = e;
28 e = next;
29 }
30 return null;
31 }
移除元素操作的整體邏輯并不複雜,就是進行連結清單的正常操作,注意元素是連結清單頭時的特别處理,通過上述注釋,了解應該不困難。
resize操作(WeakHashMap的擴容操作)
1 void resize(int newCapacity) {
2 Entry<K,V>[] oldTable = getTable();
3 // 原數組長度
4 int oldCapacity = oldTable.length;
5 if (oldCapacity == MAXIMUM_CAPACITY) {
6 threshold = Integer.MAX_VALUE;
7 return;
8 }
9 // 建立新的數組
10 Entry<K,V>[] newTable = newTable(newCapacity);
11 // 資料轉移
12 transfer(oldTable, newTable);
13 table = newTable;
14
15 /*
16 * If ignoring null elements and processing ref queue caused massive
17 * shrinkage, then restore old table. This should be rare, but avoids
18 * unbounded expansion of garbage-filled tables.
19 */
20 // 确定擴容門檻值
21 if (size >= threshold / 2) {
22 threshold = (int)(newCapacity * loadFactor);
23 } else {
24 // 清除被GC的value
25 expungeStaleEntries();
26 // 數組轉移
27 transfer(newTable, oldTable);
28 table = oldTable;
29 }
30 }
31
32 private void transfer(Entry<K,V>[] src, Entry<K,V>[] dest) {
33 // 周遊原數組
34 for (int j = 0; j < src.length; ++j) {
35 // 取出元素
36 Entry<K,V> e = src[j];
37 src[j] = null;
38 // 鍊式找元素
39 while (e != null) {
40 Entry<K,V> next = e.next;
41 Object key = e.get();
42 // key被回收的情況
43 if (key == null) {
44 e.next = null; // Help GC
45 e.value = null; // " "
46 size--;
47 } else {
48 // 确定在新數組的位置
49 int i = indexFor(e.hash, dest.length);
50 // 插入元素 注意這裡為頭插法,會倒序
51 e.next = dest[i];
52 dest[i] = e;
53 }
54 e = next;
55 }
56 }
57 }
WeakHashMap的擴容函數中有點特别,因為key可能被GC掉,是以在擴容時也許要考慮這種情況,其他并沒有什麼特别的,通過以上注釋了解應該不難。
在以上源碼分析中多次出現一個函數:expungeStaleEntries
1 private void expungeStaleEntries() {
2 // 從隊列中取出被GC的Entry
3 for (Object x; (x = queue.poll()) != null; ) {
4 synchronized (queue) {
5 @SuppressWarnings("unchecked")
6 Entry<K,V> e = (Entry<K,V>) x;
7 // 确定元素在隊列中的位置
8 int i = indexFor(e.hash, table.length);
9 // 取出數組中的第一個元素 prev
10 Entry<K,V> prev = table[i];
11 Entry<K,V> p = prev;
12 // 循環
13 while (p != null) {
14 Entry<K,V> next = p.next;
15 // 找到
16 if (p == e) {
17 // 判斷是否是連結清單頭元素 第一次時
18 if (prev == e)
19 // 将next直接挂在i位置
20 table[i] = next;
21 else
22 // 進行截斷
23 prev.next = next;
24 // Must not null out e.next;
25 // stale entries may be in use by a HashIterator
26 e.value = null; // Help GC
27 size--;
28 break;
29 }
30 // 更新prev和p
31 prev = p;
32 p = next;
33 }
34 }
35 }
36 }
該函數的主要作用就是清除Entry的value,該Entry是在GC清除key的過程中入隊的。函數的邏輯并不複雜,通過上述注釋了解應該不難。
接下來看下該函數會在什麼時候調用:
從以上調用鍊可知,在擷取size(擷取WeakHashMap的元素個數)和resize(擴容時)會調用該函數清除被GC的key對應的value值。但還有一個getTable函數也會調用該函數:
從以上調用鍊可知,在get/put等操作中都會調用expungeStaleEntries函數進GC後的收尾工作,其實WeakHashMap清除無強引用的核心也就是該函數了,是以了解該函數的作用是非常重要的。
3.總結
#1.WeakHashMap非同步,預設容量為16,擴容因子預設為0.75,底層資料結構為Entry數組(數組+連結清單)。
#2.WeakHashMap中的弱引用key會在下一次GC被清除,注意隻會清除key,value會在每次map操作中清除。
#3.在WeakHashMap中強引用的key是不會被GC清除的。
by Shawn Chen,2019.09.09日,上午。