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线程不安全的地方在哪？以后详细分析
