目录
一、触发条件
二、源码分析
put方法
addEntry方法
单线程场景下扩容（没有问题）
resize方法
transfer方法
多线程场景下扩容（产生环）
三、总结
一、触发条件
- JDK1.7
- HashMap扩容
- 多线程同时扩容
二、源码分析
假设当前数组长度3（仅仅是假设，实际应该是2的n次方），其中一个bucket位置首次put 1，如图
扩容发生在put元素超出阈值情况下，源码从put方法入手
put方法
- 当扩容时，在put方法中，首先根据hashcode计算出所需插入新元素应当在数组中的什么位置（bucket），因此相同的hashcode意味着相同的bucket，就需要解决冲突。
- for循环去遍历这个bucket，bucket可能是空的，也可能存在Entry拉链（1个或多个），e = e.next指向链表中下一个元素；若bucket是空的，则直接调用下面的addEntry在bucket处增加Entry。
- 若bucket不是空的，for循环一个一个遍历拉链中的Entry去判断是否存在相同的hash，如果hash相同再去判断key是否相同。如果key相同，则替换value，并把旧的value返回；如果key不相同，说明需要解决冲突，在addEntry方法中插入元素同时解决冲突（链地址法）。
addEntry方法
threshold：阈值，已占用bucket数量超过阈值则开始扩容
- 若要插入bucket位置本没有元素，则table[bucketIndex]为null，而new Entry构造方法中将当前Entry的next指向e，因此新new出来的Entry放在bucket位置上，且其next=null；
- 若要插入bucket位置存在元素，需要解决冲突，table[bucketIndex]为链头元素，也就是bucket位置上的元素，而新new出来的Entry放在bucket位置上，且其next=旧的bucket元素，即采用头插法解决冲突。
因此，此时最初的HashMap，若其在1之后又put了2、3，且与1发生了hash冲突，于是采用头插法解决冲突，如下图：
单线程场景下扩容（没有问题）resize方法
resize(1 * table.length)，即数组容量修改为原来的两倍
transfer方法
具体的转移元素代码在transfer方法中。
- 双重循环，分别遍历旧的数组及每个数组下的拉链
- i = indexFor方法中return h & (length-1)，用于确定扩容后在新数组中的bucket位置，具体如何确定的可参考我的另一篇文章：
HashMap的桶位为什么是2的N次方（源码分析----1.8）_γìńɡ雄尐年ぐ的博客-CSDN博客public class HashMap
每一次遍历bucket下的拉链，e初始指向bucket位置，从头结点开始逐个向下遍历
- e.next = newTable[i]：e的next指向新的bucket位置，于是与之前的next断链
- newTable[i] = e：把e指向的元素放入新的bucket中，则自然和上一个bucket元素形成拉链
- e = e.next：继续遍历旧的拉链后续元素
下图为元素转移过程，可以看出，转移后的拉链逆序存放。
转移前后对比效果
多线程场景下扩容（产生环）
假设两个线程同时put，恰好需要扩容，那么两个线程会分别在自己的线程内存中生成一个两倍长度的数组，而被转移的旧HashMap需要被两个线程共享。
假设线程2恰好在第一次执行上图行之后暂停执行，而线程1一直在顺利执行，线程2的后续操作在线程1所有的执行结束后执行，那么初始状态如下图所示：
- 分别使用e1、e2，next1、next2来代表两个线程当前指针位置
由于线程2卡住，那么先来执行线程1的操作，执行后如图：
- 可见最初指向初始数组的e2、next2在线程1的移动过程中，转移到了array1，此时线程2恢复，继续执行转移操作，则开始从array1转移元素至array2【为方便，array1代表线程1新建的数组，array2代表线程2新建的数组】
开始从array1转移元素至array2，从上图中不难发现，由于线程1转移过程中链表逆序的问题，导致线程2的e2及next2指向性发生了倒置，即next2不再是e2的下一个元素，而变成了上一个元素；那么依照之前的转移规律：
- 首先转移3至array2
- 于是array1中2的next为null，于是停止遍历该链表，于是1永远孤单的留在了array1不会被转移
- 由于①中next2在2，当3被转移过去后，e2指向next2（即2），此时next2 = e2.next（即3）
- 然后继续下一次循环，如③，e2指向next2（即3），next2 = e2.next（即2），于是成环，之后无限死循环。
三、总结
JDK1.7采用头插法解决hash冲突，单线程场景下扩容后的bucket所在拉链经过元素转移完全逆序，但对功能本身没有任何影响。
但当多线程场景下，两个线程恰好同时到来并需要扩容，每个线程会创建自己的数组， 而共享同一个扩容前的旧HashMap。而在扩容初始，线程2由于某个原因卡住，但已经给指针赋值，其与线程1的指针指向同一位置，且线程2的指针随线程1的元素转移而转移至array1，此时线程2恢复继续操作转移元素，但由于转移元素的逆序特性，导致线程2的当前元素指针（e2）与记录下一元素指针（next2）位置互换，next2无法起到记录下一元素的作用，导致转移元素丢失或滞留，而新转移过去的唯二元素形成环永远next下去。
