引言
結(jié)合網(wǎng)上的各種資料，記錄HashMap源碼閱讀的過程。
存儲結(jié)構(gòu)
HashMap(1.8)的存儲結(jié)構(gòu)為數(shù)組+鏈表+紅黑樹。
transient Node<K,V>[] table;
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
.....
}
HashMap中一些關(guān)鍵的字段
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
int threshold;
final float loadFactor;
DEFAULT_INITIAL_CAPACITY表示Node[] table的初始化長度length(默認(rèn)值是16)， loadFactor為負(fù)載因子(默認(rèn)值是0.75)，threshold是擴(kuò)容的閾值，是HashMap所能容納的最大的Node(鍵值對)個數(shù)。threshold = DEFAULT_INITIAL_CAPACITY *loadFactor。TREEIFY_THRESHOLD為鏈表轉(zhuǎn)換為紅黑是的閾值，當(dāng)鏈表的長度大于TREEIFY_THRESHOLD是轉(zhuǎn)換為紅黑樹。UNTREEIFY_THRESHOLD為紅黑是拆解為鏈表的閾值，當(dāng)紅黑樹上的節(jié)點(diǎn)數(shù)量小于UNTREEIFY_THRESHOLD是，拆解為鏈表。
確定數(shù)組下標(biāo)位置
HashMap確定數(shù)組下標(biāo)的過程可分為三個步驟：取key對應(yīng)的哈希值、高低16為異或運(yùn)算、取模得到數(shù)組下標(biāo)。下面重點(diǎn)來介紹一下后面兩步運(yùn)算的原理。下面先來介紹HashMap的取模運(yùn)算。
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
取模得到數(shù)組下標(biāo)：HashMap的取模運(yùn)算不是采用hash% table.length的形式，而是采用hash&(table.length-1)的形式，采用與運(yùn)算可以更加高效的定位到數(shù)組下標(biāo)的位置。如下圖所示：
<img src="https://user-gold-cdn.xitu.io/2020/7/3/17313b7c2841c714?w=2322&h=500&f=png&s=39311" alt="低位與.png" title="低位與.png" />
高低16為異或運(yùn)算：因?yàn)镠ashMap使用與運(yùn)算定位數(shù)組代替取余運(yùn)算來得到數(shù)組下標(biāo)，雖然性能得到了提升，但這也產(chǎn)生了一個弊端，當(dāng)數(shù)組的長度不大時，參與到定位下標(biāo)運(yùn)算的永遠(yuǎn)都是低位的二進(jìn)制，高維二進(jìn)制無法參與進(jìn)來，因此采用高低16位異或的形式讓高位也參與到定位數(shù)組下標(biāo)的運(yùn)算中去。
<img src="https://user-gold-cdn.xitu.io/2020/7/3/17313ba3a1a0c6d2?w=2363&h=932&f=png&s=69493" alt="高低16位異或.png" title="高低16位異或.png" />
擴(kuò)容機(jī)制
當(dāng)數(shù)組中Node節(jié)點(diǎn)的數(shù)量超過閾值threshold時需要調(diào)用resize()方法進(jìn)行擴(kuò)容。
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
// 超過最大值就不再擴(kuò)充了。
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 沒超過最大值，將新數(shù)組的最大容量擴(kuò)充為原來的2倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 計算新的擴(kuò)容閾值
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
// 創(chuàng)建新的Node數(shù)組
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
// 如果只有一個Node元素，則直接添加到新數(shù)組中。
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
// 如果是紅黑樹的樹節(jié)點(diǎn)，則拆分后添加到新數(shù)組中。
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
// 當(dāng)前數(shù)組下標(biāo)對應(yīng)的鏈表的首位指針（下標(biāo)位置不變）
Node<K,V> loHead = null, loTail = null;
// 新數(shù)組下標(biāo)對應(yīng)的鏈表的首位指針（下標(biāo)位置改變）
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
// 不需要改變數(shù)組下標(biāo)位置
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
// 需要改變數(shù)組下標(biāo)位置（當(dāng)前位置+舊的數(shù)組容量）
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
//
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
擴(kuò)容的重點(diǎn)在計算數(shù)組下標(biāo)。1.7會重新計算所有元素的在新的數(shù)組中的下標(biāo)位置，1.8在采用更加高效的方式計算新的數(shù)組下標(biāo)。由于擴(kuò)容總是擴(kuò)大位原數(shù)組容量的兩倍，如上圖所示，在進(jìn)行hash(key)&newTab.length時，實(shí)際上只多出了紅框框出來的一位，如果紅框框出來的部分與操作為0，這數(shù)組下標(biāo)位置不變。如果紅框框出來的部分與操作為1，則新的數(shù)組下標(biāo)為舊數(shù)組下標(biāo)加上新增位代表的數(shù)字（即舊數(shù)組容量）。如下圖所示，1.8通過判斷e.hash & oldCap（oldCap的二進(jìn)制表示就是新增位），如果是0，則下標(biāo)位置不變，如果是1，新下標(biāo)位置為舊的下標(biāo)位加上舊數(shù)組容量。
1.8對1.7死循環(huán)問題的改進(jìn)
1.7中擴(kuò)容是采用的頭插法，在多線程情況下會產(chǎn)生死循環(huán)。1.8采用尾插法解決1.7的死循環(huán)問題，1.8中分別記錄了當(dāng)前下標(biāo)位置和新的下標(biāo)位置的首位指針，添加節(jié)點(diǎn)時，分別添加到對應(yīng)的尾指針后面。
