HashMap链表成环（JDK1.7）原因及源码分析

HashMap链表成环（JDK1.7）原因及源码分析

目录

一、触发条件

二、源码分析

put方法

addEntry方法

单线程场景下扩容（没有问题）

resize方法

transfer方法

多线程场景下扩容（产生环）

三、总结

---

一、触发条件

1. JDK1.7
2. HashMap扩容
3. 多线程同时扩容

二、源码分析

假设当前数组长度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 extends AbstractMap implements Map, Cloneable, Serializable { static class Node implements Map.Entry { final int hash; final K key; V value; No.https://blog.csdn.net/qq_26012495/article/details/117632355?spm=1001.2014.3001.5501

 每一次遍历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下去。