HashMap源碼解讀：擴容
引言
HashMap的擴容是個很重要的操作，jdk1.7往前這裡會發生死鍊問題，都是值得研究的。我最開始以為HashMap線程不安全的原因是因為擴容，沒有注意到jdk版本的影響，就去看1.8的擴容為啥會發生死鍊，但是以也發現了這個方法裡的巧妙設計。
分析
以下這段代碼是jdk1.8HashMap擴容時，周遊原HashMap的桶，将元素放到新HashMap的桶裡。
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
// 疑問一：桶裡隻有一個元素時，直接覆寫到新的桶裡，不擔心Hash碰撞嗎？
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
// 疑問二：計算桶的位置時，為什麼不是e.hash & (newCap - 1)
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
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;
}
}
}
} 複制
疑問一
桶裡隻有一個元素時，直接覆寫到新的桶裡，不擔心Hash碰撞嗎？
newTab[e.hash & (newCap - 1)] = e; 複制
這點想了許久沒想明白，最終颠倒了下思路，利用反證法才解釋清除了為什麼這裡不用擔心Hash碰撞。
假定：在新桶裡的元素都是來自同一個舊桶裡。那麼就不擔心Hash碰撞，這裡明确了舊桶裡隻有一個元素，是以可以直接覆寫到新桶裡。似乎一切都說的通了，那我們來證明下這個假定。
看看是怎麼計算的新桶的位置，這和put元素時相同，那麼我們梳理下這兩者的聯系。
假定以前容量為16，那麼現在容量為32。
假定e.hash=110111001
- 計算舊桶位置（以前put時）oldIndex=110111001&1111=1001
- 計算新桶的位置B（擴容時）newIndex=110111001&11111=11001
新桶裡的元素，e.hash後五位是相同的，那後四位肯定相同，意思是舊桶位置也相同。到此，這個上訴的假定已被我們證明了，疑點也被解釋清楚了！
一個新桶裡的元素都來自于同一個舊桶，那反過來也是這樣嗎？
肯定不是的，從上面計算桶的位置可知，hashcode的第五位（從左往右）不同取值會産生2種情況，1001和11001。不過這兩種情況是有關聯的，仔細看看兩種情況。
- 當第五位為0時，新桶的位置和舊桶相同，都是1001=9（10進制）。
- 當第五位為1時，新桶位置為11001=9（10進制）+10000（2進制）=9+16=25
結論：舊桶裡的元素，擴容後，有兩種可能。一、新桶的位置和舊桶相同。二、新桶位置=舊桶位置+擴容前的容量。
當我們思考到這裡時，後面的問題都不是問題了。
疑問二
計算桶的位置時，為什麼不是e.hash & (newCap - 1)
do {
next = e.next;
// 資訊一
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
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;
} 複制
閱讀這段代碼，得出兩個資訊
- 通過條件
(e.hash & oldCap) == 0
- 将兩個連結清單放到了兩個桶裡，一個桶的位置和舊桶相同，另一個是舊桶位置+擴容前的容量
看到第二個資訊時，是不是很興奮，這不就是我們通過疑問一推導出來的嗎？
我們再來看看第一個資訊，這個條件和疑問一推導出來的條件（hashcode的第五位取值）有何關聯。
e.hash & oldCap=110111001 & 16 = 110111001 & 10000 = 1（第五位）
破案了，一切真相大白！這個條件就是在取hashcode的第五位，和我們前面推導的一緻！
到此，HashMap擴容的神秘面紗已經被我們揭開了。感謝我的朋友
LiJun
和我一起分析，推導，享受了解源碼那一刻的興奮
其他疑問
HashMap jdk7，8線程不安全的地方在哪？以後詳細分析