环形链表

多线程并发会形成环形链表，这是在jdk1.7下会发生

/**
* Transfers all entries from current table to newTable.
*/
void transfer(Entry[] newTable) {
 Entry[] src = table;
 int newCapacity = newTable.length;
 for (int j = 0; j < src.length; j++) {
   Entry<K,V> e = src[j];
   if (e != null) {
       src[j] = null;
       do {
           // B线程执行到这里之后就暂停了
           Entry<K,V> next = e.next;
           int i = indexFor(e.hash, newCapacity);
           e.next = newTable[i];
           newTable[i] = e;
           e = next;
       } while (e != null);
   }
 }

单线程扩容图解

扩容后插入是属于头插法，因此结果就是倒序形成的

第一次循环

第一次循环：Entry next = e.next; 因为for循环遍历，所以链表头就是变量e；同时执行Entry next = e.next; 图形为:

头插法，转移key=3的节点
1. 第一: e.next = newTable[7];将3和7断开连接
2. 第二: newTable[7] = e; 把e变量指向连接到新数组上
3. 第三 : e = next; 则e对象赋值为7 entry，e变量指向next

第二次循环

Entry next = e.next; 此时e其实指向的是7这个节点，由于7的next是null，next则为null。（延用第一次循环后的图）

e.next = newTable[i]; 就是把e的next节点指向新数组中那个3的节点。则 e.next=key(3);

newTable[i] = e;新数组的那个位置直接不指向原来的3节点而是指向7节点。e = next;把e节点与7节点断链。

多线程图解

此时有A，B两个线程。A线程执行到图中这块就停止了，B线程做一次扩容

线程B扩容时，节点的变化

图解如下图： A线程停下后，对应的entry元素如下图。由于线程是隔离的，读到的变量其实还是之前一开始没有变的值。

此时，A停，B线程重头开始执行，完成完成的单线程扩容过程！实现新数组的扩容重排！此时，线程B扩容完成

线程A接着扩容

void transfer(Entry[] newTable) {
 Entry[] src = table;
 int newCapacity = newTable.length;
 for (int j = 0; j < src.length; j++) {
   Entry<K,V> e = src[j];
   if (e != null) {
       src[j] = null;
       do {
           // B线程执行到这里之后就暂停了
           Entry<K,V> next = e.next;
           int i = indexFor(e.hash, newCapacity);
           e.next = newTable[i];
           newTable[i] = e;
           e = next;
       } while (e != null);
   }
 }

此时A线程开始执行：此时，entry节点属性已经发生了变化，但是线程A线程的局部变量中的e和next的指针是没有变的

此时：开始执行那个循环
第一层循环
第一步： e.next = newTable[i];
第二步: newTable[i] = e;
第三步: e = next;

第二层循环
Entry next = e.next;此时next指向了3的节点

此时，已经看出了问题出现了，next变量，又指回了3 entry节点；
第一步： e.next = newTable[i]; 就是将3节点指向新数组那个节点上，其实这里没有什么变动和原来一样。
第二步: newTable[i] = e;把7节点挂到新数组上
第三步: e = next; e指向3节点

到此其实就应该完成转换了，万万没想到还有while判断要执行呢，此时e != null是成立的，因此就又会循环一次
Entry next = e.next;这段代码后next 指向了 null；

第一步： e.next = newTable[i];
第二步: newTable[i] = e;
第三步: e = next;

此刻, 死循环出现了!!
第二步: newTable[i] = e;
第三步: e = next;