開篇
?作為Map系列的最后一篇，我覺得有必要講講WeakHashMap這個(gè)類，因?yàn)檫@個(gè)類可以解決一些oom的問題，典型的場(chǎng)景是在一個(gè)HashMap中put不同的key/value對(duì)象腹鹉，如果此時(shí)設(shè)置key為null而未清除map當(dāng)中的key對(duì)象，那么就無法通過gc回收該對(duì)象。
?在這篇文章中我希望能夠講明白WeakHashMap是如何解決key和value的gc回收問題，希望能夠?qū)σ恍?yīng)用場(chǎng)景產(chǎn)生幫助。
WeakHashMap使用舉例
?在下面這個(gè)例子當(dāng)中通過設(shè)置w1=null，會(huì)觸發(fā)gc對(duì)WeakHashMap當(dāng)中的w1進(jìn)行主動(dòng)回收。
import java.util.Iterator;
import java.util.Map;
import java.util.WeakHashMap;
import java.util.Date;
import java.lang.ref.WeakReference;
public class WeakHashMapTest {
public static void main(String[] args) throws Exception {
testWeakHashMapAPIs();
}
private static void testWeakHashMapAPIs() {
// 初始化3個(gè)“弱鍵”
String w1 = new String("one");
String w2 = new String("two");
String w3 = new String("three");
// 新建WeakHashMap
Map wmap = new WeakHashMap();
// 添加鍵值對(duì)
wmap.put(w1, "w1");
wmap.put(w2, "w2");
wmap.put(w3, "w3");
// 打印出wmap
System.out.printf("\nwmap:%s\n",wmap );
// containsKey(Object key) :是否包含鍵key
System.out.printf("contains key two : %s\n",wmap.containsKey("two"));
System.out.printf("contains key five : %s\n",wmap.containsKey("five"));
// containsValue(Object value) :是否包含值value
System.out.printf("contains value 0 : %s\n",wmap.containsValue(new Integer(0)));
// remove(Object key) ： 刪除鍵key對(duì)應(yīng)的鍵值對(duì)
wmap.remove("three");
System.out.printf("wmap: %s\n",wmap );
// ---- 測(cè)試 WeakHashMap 的自動(dòng)回收特性 ----
// 將w1設(shè)置null骤肛。
// 這意味著“弱鍵”w1再?zèng)]有被其它對(duì)象引用腋颠，調(diào)用gc時(shí)會(huì)回收WeakHashMap中與“w1”對(duì)應(yīng)的鍵值對(duì)
w1 = null;
// 內(nèi)存回收繁成。這里，會(huì)回收WeakHashMap中與“w1”對(duì)應(yīng)的鍵值對(duì)
System.gc();
// 遍歷WeakHashMap
Iterator iter = wmap.entrySet().iterator();
while (iter.hasNext()) {
Map.Entry en = (Map.Entry)iter.next();
System.out.printf("next : %s - %s\n",en.getKey(),en.getValue());
}
// 打印WeakHashMap的實(shí)際大小
System.out.printf(" after gc WeakHashMap size:%s\n", wmap.size());
}
}
--------------------------------輸出結(jié)果--------------------------------
wmap:{three=w3, one=w1, two=w2}
contains key two : true
contains key five : false
contains value 0 : false
wmap: {one=w1, two=w2}
next : two - w2
after gc WeakHashMap size:1
WeakHashMap類圖
?WeakHashMap的類圖非常簡(jiǎn)單淑玫，簡(jiǎn)單跟HashMap很像巾腕，基本上實(shí)現(xiàn)了Map接口而已，所以可以按照HashMap的角度進(jìn)行解讀混移。
WeakHashMap的工作原理
?WeakHashMap的核心在于key通過WeakReference進(jìn)行包裝祠墅，弱引用(Weak Reference)簡(jiǎn)單來說就是將對(duì)象留在內(nèi)存的能力不是那么強(qiáng)的引用。使用WeakReference歌径，垃圾回收器會(huì)幫你來決定引用的對(duì)象何時(shí)回收并且將對(duì)象從內(nèi)存移除毁嗦。
?創(chuàng)建弱引用如下： WeakReference<Widget> weakWidget = new WeakReference<Widget>(widget); 使用weakWidget.get()就可以得到真實(shí)的Widget對(duì)象，因?yàn)槿跻貌荒茏钃趵厥掌鲗?duì)其回收回铛，你會(huì)發(fā)現(xiàn)（當(dāng)沒有任何強(qiáng)引用到widget對(duì)象時(shí)）使用get時(shí)突然返回null狗准。
?解決上述的widget序列數(shù)記錄的問題克锣，最簡(jiǎn)單的辦法就是使用Java內(nèi)置的WeakHashMap類。WeakHashMap和HashMap幾乎一樣腔长，唯一的區(qū)別就是它的鍵（不是值!!!）使用WeakReference引用袭祟。當(dāng)WeakHashMap的鍵標(biāo)記為垃圾的時(shí)候，這個(gè)鍵對(duì)應(yīng)的條目就會(huì)自動(dòng)被移除捞附。這就避免了上面不需要的Widget對(duì)象手動(dòng)刪除的問題巾乳。使用WeakHashMap可以很便捷地轉(zhuǎn)為HashMap或者M(jìn)ap。
?引用隊(duì)列(Reference Queue)鸟召，一旦弱引用對(duì)象開始返回null胆绊，該弱引用指向的對(duì)象就被標(biāo)記成了垃圾。而這個(gè)弱引用對(duì)象（非其指向的對(duì)象）就沒有什么用了欧募。通常這時(shí)候需要進(jìn)行一些清理工作压状。比如WeakHashMap會(huì)在這時(shí)候移除沒用的條目來避免保存無限制增長的沒有意義的弱引用。
?引用隊(duì)列可以很容易地實(shí)現(xiàn)跟蹤不需要的引用跟继。當(dāng)你在構(gòu)造WeakReference時(shí)傳入一個(gè)ReferenceQueue對(duì)象种冬，當(dāng)該引用指向的對(duì)象被標(biāo)記為垃圾的時(shí)候，這個(gè)引用對(duì)象會(huì)自動(dòng)地加入到引用隊(duì)列里面舔糖。接下來娱两，你就可以在固定的周期，處理傳入的引用隊(duì)列剩盒，比如做一些清理工作來處理這些沒有用的引用對(duì)象谷婆。
WeakHashMap類定義
? WeakHashMap當(dāng)中對(duì)于保存key/value的數(shù)據(jù)結(jié)構(gòu)其實(shí)和HashMap是一致的，真正差別的在于Entry<K,V>變量的不同辽聊。
? Entry是繼承自WeakReference類，其構(gòu)造函數(shù)內(nèi)部通過super(key, queue)方法重新構(gòu)建了key的對(duì)象期贫，這個(gè)作用包括key能夠被gc回收跟匆，同時(shí)value也在具體的map的操作類似size()/put()等方法中被回收。
? WeakReference的用法可以參見下面的章節(jié)或者參考文章通砍，弄懂了WeakReference也就明白了WeakHashMap玛臂。
public class WeakHashMap<K,V>
extends AbstractMap<K,V>
implements Map<K,V> {
private static final int DEFAULT_INITIAL_CAPACITY = 16;
private static final int MAXIMUM_CAPACITY = 1 << 30;
private static final float DEFAULT_LOAD_FACTOR = 0.75f;
//存儲(chǔ)map的key/value的數(shù)據(jù)結(jié)構(gòu)
Entry<K,V>[] table;
private int size;
private int threshold;
private final float loadFactor;
//用于回收map當(dāng)中value數(shù)據(jù)結(jié)構(gòu)的核心queue變量
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 V put(K key, V value) {
Object k = maskNull(key);
int h = hash(k);
Entry<K,V>[] tab = getTable();
int i = indexFor(h, tab.length);
//省略相同代碼的判斷
modCount++;
Entry<K,V> e = tab[i];
tab[i] = new Entry<>(k, value, queue, h, e);
if (++size >= threshold)
resize(tab.length * 2);
return null;
}
}
WeakHashMap的Entry初始化過程
? WeakHashMap本身的構(gòu)建函數(shù)其實(shí)跟HashMap是一致的，所以沒有需要說明的封孙，核心的Entry才是WeakHashMap的核心實(shí)現(xiàn)迹冤。
? Entry的初始化過程其實(shí)逐步通過super()調(diào)用到WeakReference進(jìn)行初始化的，就是說真正放到table當(dāng)中Entry的key繼承了WeakReference從而實(shí)現(xiàn)了WeakHashMapkey的可回收虎忌，而value的回收是通過ReferenceQueue<Object> queue來實(shí)現(xiàn)的泡徙。
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 class WeakReference<T> extends Reference<T> {
public WeakReference(T referent, ReferenceQueue<? super T> q) {
super(referent, q);
}
}
public abstract class Reference<T> {
Reference(T referent, ReferenceQueue<? super T> queue) {
this.referent = referent;
this.queue = (queue == null) ? ReferenceQueue.NULL : queue;
}
}
WeakHashMap常用操作
WeakHashMap的回收機(jī)制
?WeakHashMap的Key使用WeakReference進(jìn)行包裝，垃圾回收器會(huì)幫你來決定引用的對(duì)象何時(shí)回收并且將對(duì)象從內(nèi)存移除膜蠢。
?構(gòu)造WeakReference的時(shí)候我們傳入了ReferenceQueue對(duì)象super(key, queue)堪藐，當(dāng)該引用指向的對(duì)象被標(biāo)記為垃圾的時(shí)候莉兰，這個(gè)引用對(duì)象會(huì)自動(dòng)地加入到引用隊(duì)列里面。在WeakHashMap的源碼當(dāng)中執(zhí)行這個(gè)操作的函數(shù)是expungeStaleEntries礁竞，而且是在WeakHashMap的get/set/size這種操作中嵌入了expungeStaleEntries操作糖荒。刪除的邏輯就是比較Entry對(duì)象是否相等。
WeakHashMap的put操作
?之所以分析put操作是因?yàn)樵趐ut操作過程中我們可以清晰地看到Entry的創(chuàng)建過程模捂，可以看到通過WeakReference 和ReferenceQueue來對(duì)key進(jìn)行包裝捶朵，從而保證了key在對(duì)象被設(shè)置為null的時(shí)候可以被自動(dòng)清除。
?在put的過程中可以看到resize()的過程狂男，我們以2倍的長度進(jìn)行resize泉孩，resize的內(nèi)部操作就是將數(shù)據(jù)從oldTable拷貝到newTable的過程，中間有一段反向的邏輯應(yīng)該是為了節(jié)省空間猜測(cè)并淋。
public V put(K key, V value) {
Object k = maskNull(key);
int h = hash(k);
Entry<K,V>[] tab = getTable();
int i = indexFor(h, tab.length);
for (Entry<K,V> e = tab[i]; e != null; e = e.next) {
if (h == e.hash && eq(k, e.get())) {
V oldValue = e.value;
if (value != oldValue)
e.value = value;
return oldValue;
}
}
modCount++;
Entry<K,V> e = tab[i];
tab[i] = new Entry<>(k, value, queue, h, e);
if (++size >= threshold)
resize(tab.length * 2);
return null;
}
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;
}
}
void resize(int newCapacity) {
Entry<K,V>[] oldTable = getTable();
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
Entry<K,V>[] newTable = newTable(newCapacity);
transfer(oldTable, newTable);
table = newTable;
if (size >= threshold / 2) {
threshold = (int)(newCapacity * loadFactor);
} else {
expungeStaleEntries();
transfer(newTable, oldTable);
table = oldTable;
}
}
WeakHashMap的get操作
? WeakHashMap的get操作當(dāng)中也是按照對(duì)key進(jìn)行hash后定位table桶寓搬，然后對(duì)table進(jìn)行一輪value的回收，然后在遍歷table桶下面所有的元素進(jìn)行比較返回查找值县耽。
public V get(Object key) {
Object k = maskNull(key);
int h = hash(k);
Entry<K,V>[] tab = getTable();
int index = indexFor(h, tab.length);
Entry<K,V> e = tab[index];
while (e != null) {
if (e.hash == h && eq(k, e.get()))
return e.value;
e = e.next;
}
return null;
}
private Entry<K,V>[] getTable() {
expungeStaleEntries();
return table;
}
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;
}
}
}
}
WeakHashMap迭代器
? WeakHashMap迭代器的實(shí)現(xiàn)是非常巧妙的句喷，通過只創(chuàng)建一個(gè)KeySet對(duì)象來完成迭代器的工作，從這點(diǎn)上我們也可以看出來WeakHashMap是線程不安全的兔毙。
? 類KeySet內(nèi)部通過創(chuàng)建KeyIterator類對(duì)象唾琼，KeyIterator繼承自類HashIterator，內(nèi)部的hasNext從table的尾部開始往前進(jìn)行遍歷澎剥，每次記錄上一次遍歷的位置從而繼續(xù)往前遍歷锡溯。hasNext判斷當(dāng)前的Entry是否為null，如果為null就繼續(xù)往前遍歷哑姚。
? KeyIterator的next方法負(fù)責(zé)返回當(dāng)前Entry的key值并將Entry往下一個(gè)Entry進(jìn)行推進(jìn)祭饭，所以next的分工是往下一個(gè)Entry推進(jìn)，hasNext是table桶整體往前推進(jìn)叙量。
public Set<K> keySet() {
Set<K> ks = keySet;
if (ks == null) {
ks = new KeySet();
keySet = ks;
}
return ks;
}
private class KeySet extends AbstractSet<K> {
public Iterator<K> iterator() {
return new KeyIterator();
}
}
private class KeyIterator extends HashIterator<K> {
public K next() {
return nextEntry().getKey();
}
}
private abstract class HashIterator<T> implements Iterator<T> {
private int index;
private Entry<K,V> entry;
private Entry<K,V> lastReturned;
private int expectedModCount = modCount;
private Object nextKey;
private Object currentKey;
HashIterator() {
index = isEmpty() ? 0 : table.length;
}
public boolean hasNext() {
Entry<K,V>[] t = table;
while (nextKey == null) {
Entry<K,V> e = entry;
int i = index;
while (e == null && i > 0)
e = t[--i];
entry = e;
// index從上一個(gè)位置開始找起
index = i;
if (e == null) {
currentKey = null;
return false;
}
nextKey = e.get();
if (nextKey == null)
entry = entry.next;
}
return true;
}
protected Entry<K,V> nextEntry() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (nextKey == null && !hasNext())
throw new NoSuchElementException();
lastReturned = entry;
entry = entry.next;
currentKey = nextKey;
nextKey = null;
return lastReturned;
}
public void remove() {
if (lastReturned == null)
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
WeakHashMap.this.remove(currentKey);
expectedModCount = modCount;
lastReturned = null;
currentKey = null;
}
}
