摘要：另外打散方式也不同，只用了一次異或，這里用了四次，給出的解釋是一次夠了，而且就算沖突了也會(huì)轉(zhuǎn)換成紅黑樹，對(duì)效率沒什么影響。
介紹
WeakHashMap是一種弱引用map，內(nèi)部的key會(huì)存儲(chǔ)為弱引用，當(dāng)jvm gc的時(shí)候，如果這些key沒有強(qiáng)引用存在的話，會(huì)被gc回收掉，下一次當(dāng)我們操作map的時(shí)候會(huì)把對(duì)應(yīng)的Entry整個(gè)刪除掉，基于這種特性，WeakHashMap特別適用于緩存處理。
繼承體系
存儲(chǔ)結(jié)構(gòu)
WeakHashMap因?yàn)間c的時(shí)候會(huì)把沒有強(qiáng)引用的key回收掉，所以注定了它里面的元素不會(huì)太多，因此也就不需要像HashMap那樣元素多的時(shí)候轉(zhuǎn)化為紅黑樹來處理了。
因此，WeakHashMap的存儲(chǔ)結(jié)構(gòu)只有（數(shù)組 + 鏈表）。
源碼解析
屬性
/**
* 默認(rèn)初始容量為16
*/
private static final int DEFAULT_INITIAL_CAPACITY = 16;
/**
* 最大容量為2的30次方
*/
private static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* 默認(rèn)裝載因子
*/
private static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* 桶
*/
Entry[] table;
/**
* 元素個(gè)數(shù)
*/
private int size;
/**
* 擴(kuò)容門檻，等于capacity * loadFactor
*/
private int threshold;
/**
* 裝載因子
*/
private final float loadFactor;
/**
* 引用隊(duì)列，當(dāng)弱鍵失效的時(shí)候會(huì)把Entry添加到這個(gè)隊(duì)列中
*/
private final ReferenceQueue queue = new ReferenceQueue<>();
容量
容量為數(shù)組的長度，亦即桶的個(gè)數(shù)，默認(rèn)為16，最大為2的30次方，當(dāng)容量達(dá)到64時(shí)才可以樹化。
裝載因子
裝載因子用來計(jì)算容量達(dá)到多少時(shí)才進(jìn)行擴(kuò)容，默認(rèn)裝載因子為0.75。
引用隊(duì)列
當(dāng)弱鍵失效的時(shí)候會(huì)把Entry添加到這個(gè)隊(duì)列中，當(dāng)下次訪問map的時(shí)候會(huì)把失效的Entry清除掉。
Entry內(nèi)部類
WeakHashMap內(nèi)部的存儲(chǔ)節(jié)點(diǎn), 沒有key屬性。
private static class Entry extends WeakReference implements Map.Entry {
// 可以發(fā)現(xiàn)沒有key, 因?yàn)閗ey是作為弱引用存到Referen類中
V value;
final int hash;
Entry next;
Entry(Object key, V value,
ReferenceQueue queue,
int hash, Entry next) {
// 調(diào)用WeakReference的構(gòu)造方法初始化key和引用隊(duì)列
super(key, queue);
this.value = value;
this.hash = hash;
this.next = next;
}
}
public class WeakReference extends Reference {
public WeakReference(T referent, ReferenceQueue q) {
// 調(diào)用Reference的構(gòu)造方法初始化key和引用隊(duì)列
super(referent, q);
}
}
public abstract class Reference {
// 實(shí)際存儲(chǔ)key的地方
private T referent; /* Treated specially by GC */
// 引用隊(duì)列
volatile ReferenceQueue queue;
Reference(T referent, ReferenceQueue queue) {
this.referent = referent;
this.queue = (queue == null) ? ReferenceQueue.NULL : queue;
}
}
從Entry的構(gòu)造方法我們知道，key和queue最終會(huì)傳到到Reference的構(gòu)造方法中，這里的key就是Reference的referent屬性，它會(huì)被gc特殊對(duì)待，即當(dāng)沒有強(qiáng)引用存在時(shí)，當(dāng)下一次gc的時(shí)候會(huì)被清除。
構(gòu)造方法
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 m) {
this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
DEFAULT_INITIAL_CAPACITY),
DEFAULT_LOAD_FACTOR);
putAll(m);
}
構(gòu)造方法與HashMap基本類似，初始容量為大于等于傳入容量最近的2的n次方，擴(kuò)容門檻threshold等于capacity * loadFactor
put(K key, V value)方法
增加元素的方法
public V put(K key, V value) {
// 如果key為空，用空對(duì)象代替
Object k = maskNull(key);
// 計(jì)算key的hash值
int h = hash(k);
// 獲取桶
Entry[] tab = getTable();
// 計(jì)算元素在哪個(gè)桶中，h & (length-1)
int i = indexFor(h, tab.length);
// 遍歷桶對(duì)應(yīng)的鏈表
for (Entry 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 e = tab[i];
tab[i] = new Entry<>(k, value, queue, h, e);
// 如果插入元素后數(shù)量達(dá)到了擴(kuò)容門檻就把桶的數(shù)量擴(kuò)容為2倍大小
if (++size >= threshold)
resize(tab.length * 2);
return null;
}
計(jì)算hash；
計(jì)算在哪個(gè)桶中；
遍歷桶對(duì)應(yīng)的鏈表；
如果找到元素就用新值替換舊值，并返回舊值；
如果沒找到就在鏈表頭部插入新元素；
HashMap就插入到鏈表尾部。
如果元素?cái)?shù)量達(dá)到了擴(kuò)容門檻，就把容量擴(kuò)大到2倍大小；
HashMap中是大于threshold才擴(kuò)容，這里等于threshold就開始擴(kuò)容了。
resize(int newCapacity)方法
擴(kuò)容方法。
void resize(int newCapacity) {
// 獲取舊桶，getTable()的時(shí)候會(huì)剔除失效的Entry
Entry[] oldTable = getTable();
// 舊容量
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
// 新桶
Entry[] newTable = newTable(newCapacity);
// 把元素從舊桶轉(zhuǎn)移到新桶
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.
*/
// 如果元素個(gè)數(shù)大于擴(kuò)容門檻的一半，則使用新桶和新容量，并計(jì)算新的擴(kuò)容門檻
if (size >= threshold / 2) {
threshold = (int)(newCapacity * loadFactor);
} else {
// 否則把元素再轉(zhuǎn)移回舊桶，還是使用舊桶
// 因?yàn)樵趖ransfer的時(shí)候會(huì)清除失效的Entry，所以元素個(gè)數(shù)可能沒有那么大了，就不需要擴(kuò)容了
expungeStaleEntries();
transfer(newTable, oldTable);
table = oldTable;
}
}
private void transfer(Entry[] src, Entry[] dest) {
// 遍歷舊桶
for (int j = 0; j < src.length; ++j) {
Entry e = src[j];
src[j] = null;
while (e != null) {
Entry next = e.next;
Object key = e.get();
// 如果key等于了null就清除，說明key被gc清理掉了，則把整個(gè)Entry清除
if (key == null) {
e.next = null; // Help GC
e.value = null; // " "
size--;
} else {
// 否則就計(jì)算在新桶中的位置并把這個(gè)元素放在新桶對(duì)應(yīng)鏈表的頭部
int i = indexFor(e.hash, dest.length);
e.next = dest[i];
dest[i] = e;
}
e = next;
}
}
}
判斷舊容量是否達(dá)到最大容量；
新建新桶并把元素全部轉(zhuǎn)移到新桶中；
如果轉(zhuǎn)移后元素個(gè)數(shù)不到擴(kuò)容門檻的一半，則把元素再轉(zhuǎn)移回舊桶，繼續(xù)使用舊桶，說明不需要擴(kuò)容；
否則使用新桶，并計(jì)算新的擴(kuò)容門檻；
轉(zhuǎn)移元素的過程中會(huì)把key為null的元素清除掉，所以size會(huì)變??；
get(Object key)方法
獲取元素。
public V get(Object key) {
Object k = maskNull(key);
// 計(jì)算hash
int h = hash(k);
Entry[] tab = getTable();
int index = indexFor(h, tab.length);
Entry e = tab[index];
// 遍歷鏈表，找到了就返回
while (e != null) {
if (e.hash == h && eq(k, e.get()))
return e.value;
e = e.next;
}
return null;
}
計(jì)算hash值；
遍歷所在桶對(duì)應(yīng)的鏈表；
如果找到了就返回元素的value值；
如果沒找到就返回空；
remove(Object key)方法
移除元素
public V remove(Object key) {
Object k = maskNull(key);
// 計(jì)算hash
int h = hash(k);
Entry[] tab = getTable();
int i = indexFor(h, tab.length);
// 元素所在的桶的第一個(gè)元素
Entry prev = tab[i];
Entry e = prev;
// 遍歷鏈表
while (e != null) {
Entry next = e.next;
if (h == e.hash && eq(k, e.get())) {
// 如果找到了就刪除元素
modCount++;
size--;
if (prev == e)
// 如果是頭節(jié)點(diǎn)，就把頭節(jié)點(diǎn)指向下一個(gè)節(jié)點(diǎn)
tab[i] = next;
else
// 如果不是頭節(jié)點(diǎn)，刪除該節(jié)點(diǎn)
prev.next = next;
return e.value;
}
prev = e;
e = next;
}
return null;
}
計(jì)算hash；
找到所在的桶；
遍歷桶對(duì)應(yīng)的鏈表；
如果找到了就刪除該節(jié)點(diǎn)，并返回該節(jié)點(diǎn)的value值；
如果沒找到就返回null；
expungeStaleEntries()方法
剔除失效的Entry。
private void expungeStaleEntries() {
// 遍歷引用隊(duì)列
for (Object x; (x = queue.poll()) != null; ) {
synchronized (queue) {
@SuppressWarnings("unchecked")
Entry e = (Entry) x;
int i = indexFor(e.hash, table.length);
// 找到所在的桶
Entry prev = table[i];
Entry p = prev;
// 遍歷鏈表
while (p != null) {
Entry 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;
}
}
}
}
當(dāng)key失效的時(shí)候gc會(huì)自動(dòng)把對(duì)應(yīng)的Entry添加到這個(gè)引用隊(duì)列中；
所有對(duì)map的操作都會(huì)直接或間接地調(diào)用到這個(gè)方法先移除失效的Entry，比如getTable()、size()、resize()；
這個(gè)方法的目的就是遍歷引用隊(duì)列，并把其中保存的Entry從map中移除掉，具體的過程請(qǐng)看類注釋；
從這里可以看到移除Entry的同時(shí)把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 map = new WeakHashMap<>(3);
// 放入3個(gè)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強(qiáng)引用"3"這個(gè)字符串
String key = null;
for (String s : map.keySet()) {
// 這個(gè)"3"和new String("3")不是一個(gè)引用
if (s.equals("3")) {
key = s;
}
}
// 輸出{6=6, 1=1, 2=2, 3=3}，未gc所有key都可以打印出來
System.out.println(map);
// gc一下
System.gc();
// 放一個(gè)new String()聲明的字符串
map.put(new String("4"), 4);
// 輸出{4=4, 6=6, 3=3}，gc后放入的值和強(qiáng)引用的key可以打印出來
System.out.println(map);
// key與"3"的引用斷裂
key = null;
// gc一下
System.gc();
// 輸出{6=6}，gc后強(qiáng)引用的key可以打印出來
System.out.println(map);
}
}
在這里通過new String()聲明的變量才是弱引用，使用”6″這種聲明方式會(huì)一直存在于常量池中，不會(huì)被清理，所以”6″這個(gè)元素會(huì)一直在map里面，其它的元素隨著gc都會(huì)被清理掉。
總結(jié)
WeakHashMap使用（數(shù)組 + 鏈表）存儲(chǔ)結(jié)構(gòu)；
WeakHashMap中的key是弱引用，gc的時(shí)候會(huì)被清除；
每次對(duì)map的操作都會(huì)剔除失效key對(duì)應(yīng)的Entry；
使用String作為key時(shí)，一定要使用new String()這樣的方式聲明key，才會(huì)失效，其它的基本類型的包裝類型是一樣的；
WeakHashMap常用來作為緩存使用；
強(qiáng)、軟、弱、虛引用總結(jié)
強(qiáng)引用
使用最普遍的引用。如果一個(gè)對(duì)象具有強(qiáng)引用，它絕對(duì)不會(huì)被gc回收。如果內(nèi)存空間不足了，gc寧愿拋出OutOfMemoryError，也不是會(huì)回收具有強(qiáng)引用的對(duì)象。
軟引用
如果一個(gè)對(duì)象只具有軟引用，則內(nèi)存空間足夠時(shí)不會(huì)回收它，但內(nèi)存空間不夠時(shí)就會(huì)回收這部分對(duì)象。只要這個(gè)具有軟引用對(duì)象沒有被回收，程序就可以正常使用。
弱引用
如果一個(gè)對(duì)象只具有弱引用，則不管內(nèi)存空間夠不夠，當(dāng)gc掃描到它時(shí)就會(huì)回收它。
虛引用
如果一個(gè)對(duì)象只具有虛引用，那么它就和沒有任何引用一樣，任何時(shí)候都可能被gc回收。
軟（弱、虛）引用必須和一個(gè)引用隊(duì)列（ReferenceQueue）一起使用，當(dāng)gc回收這個(gè)軟（弱、虛）引用引用的對(duì)象時(shí)，會(huì)把這個(gè)軟（弱、虛）引用放到這個(gè)引用隊(duì)列中。
比如，上述的Entry是一個(gè)弱引用，它引用的對(duì)象是key，當(dāng)key被回收時(shí)，Entry會(huì)被放到queue中。
