弄懂HashMap(JDK7)在多线程下形成死锁的原因
想必大家通过各种渠道都已经知道了HashMap是线程不安全的，当然HashMap的线程不安全表现在很多方面，今天我们主要是彻底弄清楚HashMap在多线程下造成死锁的原因。
阅读HashMap源码的时候我们知道，HashMap在扩容的时候会调用transfer函数。就是将原Hash表上的元素全部转移到新的hash表上，我们将transfer的函数再次贴出来：
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}rehash的过程就是将旧表中的entry全部转移到新表中，每次都是采用头插法。
正常单线程下的rehash过程如下图所示：
并发下的Rehash：
假设有两个线程要进行rehash。我用红色和浅蓝色标注了一下。
假设线程1执行到下面红色这一句后，切换到线程二：
而我们的线程二执行完成了。于是我们有下面的这个样子。
上面的图片来自网络。我觉得上面的图片还是有些问题的，下面线程二中执行完后，旧的hash表1处的指针不应该是null而应该是指向key(3)结点的。因为在遍历时，并没有语句使旧的hash表的某个位置为null，那么它依然是指向原来的结点key(3)。不过这个对最终的影响不大。
接下来，线程切换到Thread1来执行了：
注意，因为Thread1的 e 指向了key(3)，而next指向了key(7)，其在线程二rehash后，指向了线程二重组后的链表。我们可以看到链表的顺序被反转后。
- 先是执行 e.next = newTable[i];
- 然后是newTable[i] = e;，，
- 而下一次循环的e = next, next = e.next导致了导致了e指向了key(7),next指向了key(3)
3）一切安好。
线程一接着工作。把key(7)摘下来，放到newTable[i]的第一个，然后把e和next往下移。
4）环形链接出现。
e.next = newTable[i] 导致 key(3).next 指向了 key(7)
注意：此时的key(7).next 已经指向了key(3)， 环形链表就这样出现了。
总结一下：HashMap出现死循环的条件是，当两个线程同时对原有的旧的Hash表扩容时，当其中一个线程正在扩容时（遍历单向链表）切换到另外一个线程进行扩容操作，并且在线程二中完成了所有的扩容操作，此时再切换到线程1中就可能造成单向链表形成一个环，从而在下一次查询操作时就可能发生死循环。