HashMap jdk1.7 扩容死锁详解

• 源码
• 什么是链表闭环
• 什么是头插法
• HashMap JDK7闭环产生过程
• • 原因详述
  • 线程2扩容完成后
  • 线程2扩容完成后，线程1开始扩容
  • • 逐行代码画图分析线程1产生闭环的过程

void transfer(Entry[] newTable, boolean rehash) {  
        int newCapacity = newTable.length;//新容量  
        for (Entry e : table) { //遍历所有桶，table为当前Map中的Entry[]
            while(null != e) {  //遍历桶中所有元素（是一个链表）
            // 这个next就是B节点，线程1执行到这步时，假如线程1被调起来了，让给线程2继续执行
                Entry next = e.next;
                if (rehash) {//如果是重新Hash，则需要重新计算hash值  
                    e.hash = null == e.key ? 0 : hash(e.key);  
                }
                int i = indexFor(e.hash, newCapacity);//定位Hash桶  
                e.next = newTable[i];//这里就是头插，只是在第一个元素插进来时 newTable[i]是null，当然，链表最后一个元素指向null是正常的
                newTable[i] = e;//newTable[i]的值总是最新插入的值
                e = next;//继续下一个元素  
            }  
        }  
    }

闭环链表：

每次新来元素的next变量都指向当前链表的头节点；

1. 假设线程1和线程2同时并且都是第一次执行到代码Entry next = e.next;，且都执行完这句代码。
2. 这时线程1执行完这句代码后被停止，线程2还能继续往下执行，并将整个Map扩容执行完成，线程2执行完成后，线程1才再被调度；
3. 在1和2条件成立的情况下：线程1再去执行以下3行代码就会出现链表的闭环：

	e.next = newTable[i];//这里就是头插，只是在第一个元素插进来时 newTable[i]是null，当然，链表最后一个元素指向null是正常的
	newTable[i] = e;//newTable[i]的值总是最新插入的值
	e = next;//继续下一个元素  

Map扩容前，当前桶位的链表结构
注意：假设所有元素在扩容后，还是放在该桶位

线程2扩容完成后

1. 首先要理解线程2扩容完成后，线程1再扩容时链表的结构，且要注意for (Entry e : table) 中e为局部变量和Entry next next局部变量指向问题；

也就是说，线程1在扩容时，是根据上图中的右侧图为基准了

重点解析以下3行代码的执行过程
解析过程重点关注变量e和next指针的变化

	e.next = newTable[i];//这里就是头插，只是在第一个元素插进来时 newTable[i]是null，当然，链表最后一个元素指向null是正常的
	newTable[i] = e;//newTable[i]的值总是最新插入的值
	e = next;//继续下一个元素  

第一次while循环
以下所有图中变量都是线程1中的

第二次while循环
注意：起始图默认已执行完Entry next = e.next;
其实对比上图和下图最左边的图形，可以看到e和next的指向发生了交换，再看下图中最右侧的图，会发现e又指向了3这个元素，但是3这个元素在线程1中已经被循环处理过一次了，所以第三次while循环还是处理3这个元素；

第三次while循环
注意：起始图默认已执行完Entry next = e.next;
在下图右侧图中，执行当前代码后，会发现3元素的next节点又指向2元素，这里就形成了闭环;