簡介
WeakHashMap 繼承于AbstractMap,實作了Map接口。
和HashMap一樣,WeakHashMap 也是一個散清單,它存儲的内容也是鍵值對(key-value)映射,而且鍵和值都可以是null。
不過WeakHashMap的鍵是“弱鍵”。在 WeakHashMap 中,當某個鍵不再正常使用時,會被從WeakHashMap中被自動移除。更精确地說,對于一個給定的鍵,其映射的存在并不阻止垃圾回收器對該鍵的丢棄,這就使該鍵成為可終止的,被終止,然後被回收。某個鍵被終止時,它對應的鍵值對也就從映射中有效地移除了。
這個“弱鍵”的原理呢?大緻上就是,通過WeakReference和ReferenceQueue實作的。 WeakHashMap的key是“弱鍵”,即是WeakReference類型的;ReferenceQueue是一個隊列,它會儲存被GC回收的“弱鍵”。實作步驟是:
(1) 建立WeakHashMap,将“鍵值對”添加到WeakHashMap中。
實際上,WeakHashMap是通過數組table儲存Entry(鍵值對);每一個Entry實際上是一個單向連結清單,即Entry是鍵值對連結清單。
(2) 當某“弱鍵”不再被其它對象引用,并被GC回收時。在GC回收該“弱鍵”時,這個“弱鍵”也同時會被添加到ReferenceQueue(queue)隊列中。
(3) 當下一次我們需要操作WeakHashMap時,會先同步table和queue。table中儲存了全部的鍵值對,而queue中儲存被GC回收的鍵值對;同步它們,就是删除table中被GC回收的鍵值對。
這就是“弱鍵”如何被自動從WeakHashMap中删除的步驟了。
繼承體系
可見,WeakHashMap沒有實作Clone和Serializable接口,是以不具有克隆和序列化的特性。
存儲結構
WeakHashMap因為gc的時候會把沒有強引用的key回收掉,是以注定了它裡面的元素不會太多,是以也就不需要像HashMap那樣元素多的時候轉化為紅黑樹來處理了。
是以,WeakHashMap的存儲結構隻有(數組 + 連結清單)。
源碼解析
屬性
// 預設的初始容量是16,必須是2的幂。
private static final int DEFAULT_INITIAL_CAPACITY = 16;
// 最大容量(必須是2的幂且小于2的30次方,傳入容量過大将被這個值替換)
private static final int MAXIMUM_CAPACITY = 1 << 30;
// 預設加載因子
private static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 存儲資料的Entry數組,長度是2的幂。
// WeakHashMap是采用拉鍊法實作的,每一個Entry本質上是一個單向連結清單
private Entry[] table;
// WeakHashMap的大小,它是WeakHashMap儲存的鍵值對的數量
private int size;
// WeakHashMap的門檻值,用于判斷是否需要調整WeakHashMap的容量(threshold = 容量*加載因子)
private int threshold;
// 加載因子實際大小
private final float loadFactor;
// queue儲存的是“已被GC清除”的“弱引用的鍵”。
// 弱引用和ReferenceQueue 是聯合使用的:如果弱引用所引用的對象被垃圾回收,Java虛拟機就會把這個弱引用加入到與之關聯的引用隊列中
private final ReferenceQueue<K> queue = new ReferenceQueue<K>();
// WeakHashMap被改變的次數
private volatile int modCount;
(1)容量
容量為數組的長度,亦即桶的個數,預設為16,最大為2的30次方。
(2)裝載因子
裝載因子用來計算容量達到多少時才進行擴容,預設裝載因子為0.75。
(3)引用隊列
當弱鍵失效的時候會把Entry添加到這個隊列中,當下次通路map的時候會把失效的Entry清除掉。
Entry内部類
WeakHashMap内部的存儲節點, 沒有key屬性。
private static class Entry<K,V> extends WeakReference<Object> implements Map.Entry<K,V> {
// 可以發現沒有key, 因為key是作為弱引用存到Referen類中
V value;
final int hash;
Entry<K,V> next;
Entry(Object key, V value,
ReferenceQueue<Object> queue,
int hash, Entry<K,V> next) {
// 調用WeakReference的構造方法初始化key和引用隊列
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) {
// 調用Reference的構造方法初始化key和引用隊列
super(referent, q);
}
}
public abstract class Reference<T> {
// 實際存儲key的地方
private T referent; /* Treated specially by GC */
// 引用隊列
volatile ReferenceQueue<? super T> queue;
Reference(T referent, ReferenceQueue<? super T> queue) {
this.referent = referent;
this.queue = (queue == null) ? ReferenceQueue.NULL : queue;
}
}
WeakReference是“弱鍵”實作的哈希表。它這個“弱鍵”的目的就是:實作對“鍵值對”的動态回收。當“弱鍵”不再被使用到時,GC會回收它,WeakReference也會将“弱鍵”對應的鍵值對删除。
“弱鍵”是一個“弱引用(WeakReference)”,在Java中,WeakReference和ReferenceQueue 是聯合使用的。在WeakHashMap中亦是如此:如果弱引用所引用的對象被垃圾回收,Java虛拟機就會把這個弱引用加入到與之關聯的引用隊列中。 接着,WeakHashMap會根據“引用隊列”,來删除“WeakHashMap中已被GC回收的‘弱鍵’對應的鍵值對”。
另外,了解上面思想的重點是通過 expungeStaleEntries() 函數去了解。
構造方法
public WeakHashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Initial Capacity: "+
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal Load factor: "+
loadFactor);
int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1;
table = newTable(capacity);
this.loadFactor = loadFactor;
threshold = (int)(capacity * loadFactor);
}
public WeakHashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public WeakHashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
public WeakHashMap(Map<? extends K, ? extends V> m) {
this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
DEFAULT_INITIAL_CAPACITY),
DEFAULT_LOAD_FACTOR);
putAll(m);
}
構造方法與HashMap基本類似,初始容量為大于等于傳入容量最近的2的n次方,擴容門檻threshold等于capacity * loadFactor。
put(K key, V value)方法
添加元素的方法。
public V put(K key, V value) {
// 如果key為空,用空對象代替
Object k = maskNull(key);
// 計算key的hash值
int h = hash(k);
// 擷取桶
Entry<K,V>[] tab = getTable();
// 計算元素在哪個桶中,h & (length-1)
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);
// 如果插入元素後數量達到了擴容門檻就把桶的數量擴容為2倍大小
if (++size >= threshold)
resize(tab.length * 2);
return null;
}
//計算hash
final int hash(Object k) {
int h = k.hashCode();
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
(1)計算hash:
這裡與HashMap有所不同,HashMap中如果key為空直接傳回0,這裡是用空對象來計算的。
另外打散方式也不同,HashMap隻用了一次異或,這裡用了四次,HashMap給出的解釋是一次夠了,而且就算沖突了也會轉換成紅黑樹,對效率沒什麼影響。
(2)計算在哪個桶中;
(3)周遊桶對應的連結清單;
(4)如果找到元素就用新值替換舊值,并傳回舊值;
(5)如果沒找到就在連結清單頭部插入新元素;
HashMap就插入到連結清單尾部。
(6)如果元素數量達到了擴容門檻,就把容量擴大到2倍大小;
HashMap中是大于threshold才擴容,這裡等于threshold就開始擴容了。
resize(int newCapacity)方法
擴容方法。
void resize(int newCapacity) {
// 擷取舊桶,getTable()的時候會剔除失效的Entry
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 ignoring null elements and processing ref queue caused massive
* shrinkage, then restore old table. This should be rare, but avoids
* unbounded expansion of garbage-filled tables.
*/
// 如果元素個數大于擴容門檻的一半,則使用新桶和新容量,并計算新的擴容門檻
if (size >= threshold / 2) {
threshold = (int)(newCapacity * loadFactor);
} else {
// 否則把元素再轉移回舊桶,還是使用舊桶
// 因為在transfer的時候會清除失效的Entry,是以元素個數可能沒有那麼大了,就不需要擴容了
expungeStaleEntries();
transfer(newTable, oldTable);
table = oldTable;
}
}
private void transfer(Entry<K,V>[] src, Entry<K,V>[] dest) {
// 周遊舊桶
for (int j = 0; j < src.length; ++j) {
Entry<K,V> e = src[j];
src[j] = null;
while (e != null) {
Entry<K,V> next = e.next;
Object key = e.get();
// 如果key等于了null就清除,說明key被gc清理掉了,則把整個Entry清除
if (key == null) {
e.next = null; // Help GC
e.value = null; // " "
size--;
} else {
// 否則就計算在新桶中的位置并把這個元素放在新桶對應連結清單的頭部
int i = indexFor(e.hash, dest.length);
e.next = dest[i];
dest[i] = e;
}
e = next;
}
}
}
(1)判斷舊容量是否達到最大容量;
(2)建立新桶并把元素全部轉移到新桶中;
(3)如果轉移後元素個數不到擴容門檻的一半,則把元素再轉移回舊桶,繼續使用舊桶,說明不需要擴容;
(4)否則使用新桶,并計算新的擴容門檻;
(5)轉移元素的過程中會把key為null的元素清除掉,是以size會變小;
get(Object key)方法
擷取元素。
public V get(Object key) {
Object k = maskNull(key);
// 計算hash
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;
}
(1)計算hash值;
(2)周遊所在桶對應的連結清單;
(3)如果找到了就傳回元素的value值;
(4)如果沒找到就傳回空;
remove(Object key)方法
移除元素。
public V remove(Object key) {
Object k = maskNull(key);
// 計算hash
int h = hash(k);
Entry<K,V>[] tab = getTable();
int i = indexFor(h, tab.length);
// 元素所在的桶的第一個元素
Entry<K,V> prev = tab[i];
Entry<K,V> e = prev;
// 周遊連結清單
while (e != null) {
Entry<K,V> next = e.next;
if (h == e.hash && eq(k, e.get())) {
// 如果找到了就删除元素
modCount++;
size--;
if (prev == e)
// 如果是頭節點,就把頭節點指向下一個節點
tab[i] = next;
else
// 如果不是頭節點,删除該節點
prev.next = next;
return e.value;
}
prev = e;
e = next;
}
return null;
}
(1)計算hash;
(2)找到所在的桶;
(3)周遊桶對應的連結清單;
(4)如果找到了就删除該節點,并傳回該節點的value值;
(5)如果沒找到就傳回null;
expungeStaleEntries()方法
剔除失效的Entry。
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;
}
}
}
}
(1)當key失效的時候gc會自動把對應的Entry添加到這個引用隊列中;
(2)所有對map的操作都會直接或間接地調用到這個方法先移除失效的Entry,比如getTable()、size()、resize();
(3)這個方法的目的就是周遊引用隊列,并把其中儲存的Entry從map中移除掉,具體的過程請看類注釋;
(4)從這裡可以看到移除Entry的同時把value也一并置為null幫助gc清理元素,防禦性程式設計。
使用案例
說了這麼多,不舉個使用的例子怎麼過得去。
package com.coolcoding.code;
import java.util.Map;
import java.util.WeakHashMap;
public class WeakHashMapTest {
public static void main(String[] args) {
Map<String, Integer> map = new WeakHashMap<>(3);
// 放入3個new String()聲明的字元串
map.put(new String("1"), 1);
map.put(new String("2"), 2);
map.put(new String("3"), 3);
// 放入不用new String()聲明的字元串
map.put("6", 6);
// 使用key強引用"3"這個字元串
String key = null;
for (String s : map.keySet()) {
// 這個"3"和new String("3")不是一個引用
if (s.equals("3")) {
key = s;
}
}
// 輸出{6=6, 1=1, 2=2, 3=3},未gc所有key都可以列印出來
System.out.println(map);
// gc一下
System.gc();
// 放一個new String()聲明的字元串
map.put(new String("4"), 4);
// 輸出{4=4, 6=6, 3=3},gc後放入的值和強引用的key可以列印出來
System.out.println(map);
// key與"3"的引用斷裂
key = null;
// gc一下
System.gc();
// 輸出{6=6},gc後強引用的key可以列印出來
System.out.println(map);
}
}
在這裡通過new String()聲明的變量才是弱引用,使用"6"這種聲明方式會一直存在于常量池中,不會被清理,是以"6"這個元素會一直在map裡面,其它的元素随着gc都會被清理掉。
總結
(1)WeakHashMap使用(數組 + 連結清單)存儲結構;
(2)WeakHashMap中的key是弱引用,gc的時候會被清除;
(3)每次對map的操作都會剔除失效key對應的Entry;
(4)使用String作為key時,一定要使用new String()這樣的方式聲明key,才會失效,其它的基本類型的包裝類型是一樣的;
(5)WeakHashMap常用來作為緩存使用;
彩蛋
強、軟、弱、虛引用知多少?
(1)強引用
使用最普遍的引用。如果一個對象具有強引用,它絕對不會被gc回收。如果記憶體空間不足了,gc甯願抛出OutOfMemoryError,也不是會回收具有強引用的對象。
(2)軟引用
如果一個對象隻具有軟引用,則記憶體空間足夠時不會回收它,但記憶體空間不夠時就會回收這部分對象。隻要這個具有軟引用對象沒有被回收,程式就可以正常使用。
(3)弱引用
如果一個對象隻具有弱引用,則不管記憶體空間夠不夠,當gc掃描到它時就會回收它。
(4)虛引用
如果一個對象隻具有虛引用,那麼它就和沒有任何引用一樣,任何時候都可能被gc回收。
軟(弱、虛)引用必須和一個引用隊列(ReferenceQueue)一起使用,當gc回收這個軟(弱、虛)引用引用的對象時,會把這個軟(弱、虛)引用放到這個引用隊列中。
比如,上述的Entry是一個弱引用,它引用的對象是key,當key被回收時,Entry會被放到queue中。
參考連結:https://www.cnblogs.com/tong-yuan/p/10639404.html
參考連結:https://www.cnblogs.com/skywang12345/p/3311092.html