HashMap之链表导致死循环

描述：HashMap采用拉链法（数组链表）解决Hash冲突,因为是链表结构，那么就很容易形成闭合的链路。

在单线程情况下，只有一个线程对HashMap的数据结构进行操作，是不可能产生闭合的回路的。
那就只有在多线程并发的情况下才会出现这种情况，那就是在put操作的时候，如果size > nitialCapacity*loadFactor，那么这时候HashMap就会进行rehash操作，随之HashMap的结构就会发生翻天覆地的变化。很有可能就是在两个线程在这个时候同时触发了rehash操作，产生了闭合的回路。

public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
//存在key，则替换掉旧的value
for (Entry e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
//table[i]为空，这时直接生成一个新的entry放在table[i]上
addEntry(hash, key, value, i);
return null;
}

void addEntry(int hash, K key, V value, int bucketIndex) {
Entry e = table[bucketIndex];
table[bucketIndex] = new Entry(hash, key, value, e);
if (size++ >= threshold)
resize(2 * table.length);
}

void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable = new Entry[newCapacity];
//将旧的Entry数组的数据转移到新的Entry数组上
transfer(newTable);
table = newTable;
threshold = (int)(newCapacity * loadFactor);
}

void transfer(Entry[] newTable) {
Entry[] src = table;
int newCapacity = newTable.length;
/*
* 在转换的过程中，HashMap相当于是把原来链表上元素的的顺序颠倒了。
* 比如说 原来某一个Entry[i]上链表的顺序是e1->e2->null,那么经过操作之后
* 就变成了e2->e1->null
*/
for (int j = 0; j  e = src[j];
if (e != null) {
src[j] = null;
do {
//我认为此处是出现死循环的罪魁祸首
Entry next = e.next;
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
} while (e != null);
}
}
}
那么回路究竟是如何产生的呢，问题就出在next=e.next这个地方，在多线程并发的环境下，为了便于分析，我们假设就两个线程P1,P2。src[i]的链表顺序是e1->e2->null。我们分别线程P1,P2的执行情况。
首先，P1，和P2进入到了for循环中，这时候在线程p1和p2中，局部变量分别如下：
|----| e | next|
| p1| e1 | e2 |
| p2| e1 | e2 |
此时两个Entry的顺序是依然是最开始的状态e1->e2->null, 但是此时p1可能某些原因线程暂停了，p2则继续执行，并执行完了do while循环。这时候Entry的顺序就变成了e2->e1->null。在等到P2执行完之后，可能p1才继续执行，这时候在P1线程中局部变量e的值为e1，next的值为e2(注意此时两个元素在内存中的顺序变成了e2->e1->null)，下面P1线程进入了do while循环。这时候P1线程在新的Entry数组中找到e1的位置，
e.next = newTable[i];
newTable[i] = e;
下面会把next赋值给e，这时候e的值成为了e2，继续下一次循环，这时候
|----| e | next|
| p1| e2 | e1 |
e2->next=e1，这个是线程P2的"功劳"。程序执行完这次循环之后，e=e1,继续第三次循环，这时候根据算法，就会进行e1->next=e2。
这样在线程P1中执行了 e1->next=e2,在线程P2中执行了 e2->next=e1，这样就形成了一个环。在get操作的时候，next值永远不为null，造成了死循环。
在高并发情况下，不建议使用HashMap，建议采用ConcurrentHashMap。