探究HashMap线性不安全（二）——链表成环的详细过程

内容

​　　网上很多资料都详细地讲解了hashmap底层的实现，但是讲到hashmap的并发操作不是线性安全时，往往一笔带过：在多个线程并发扩容时，会在执行transfer()方法转移键值对时，造成链表成环，导致程序在执行get操作时形成死循环。

​　　对于没有研究过该过程的童鞋，很难费解这句话的含义。下面笔者分四个小节带着大家共同研究一下jdk1.7和jdk1.8版本下hashmap的线性不安全是怎么造成的，详细探究链表成环的形成过程。如果对于hashmap底层的put、get操作不清楚，建议先学习参考1中的内容。

适合人群

​　　java进阶

参考

​ 1、 hashmap底层数据结构原理

​ 2、 为什么hashmap非线程安全

​ 3、 hashmap并发情况下的成环原因（笔者认为该文是一种误解）

正文

​　　本节将详细探究hashmap扩容的键值对迁移过程，多线程并发执行transfer()方法是如何产生环形链表的。transfer()方法的代码为：

 1 void transfer(entry[] newtable, boolean rehash) {
 2     int newcapacity = newtable.length;
 3     //遍历table数组中键值对链
 4     for (entry<k,v> e : table) {
 5         //遍历键值对e链上的所有键值对，当e指向null时结束
 6         while(null != e) {
 7             entry<k,v> next = e.next;//断点一
 8             //通常rehash为false，不会重新计算键值对key的hash值
 9             if (rehash) {
10                 e.hash = null == e.key ? 0 : hash(e.key);
11             }
12             //根据扩容后的table数组长度计算键值对的index
13             int i = indexfor(e.hash, newcapacity);
14             //头插法，将后遍历的键值对存到链条的头部
15             e.next = newtable[i];
16             newtable[i] = e;
17             //链条中的下一个键值对继续执行while循环。
18             e = next;
19         }
20     }
21 }

 情景：

​　　两个线程a、b同时向hashmap中写入键值对，某个时刻hashmap已经到了resize的临界点。由于多线程的执行没有必然的先后顺序，存在线程a未完成扩容，而线程b又进行扩容的情况，即两个线程都可能会执行扩容方法transfer()。此时两个线程都会遍历table数组中的键值对链，对于每个链执行while循环，迁移所有键值对。

　　假定hashmap中table数组的初始长度为4

​　　假如线程a和线程b都遍历到index为2的键值链（即entry3->entry2->null这条链）。由于cpu时间片分配的不确定性，线程b执行到代码中断点一的位置后暂停，此时线程b中的e指向entry3，e.next指向entry2。而线程a继续执行，完成了扩容操作。hashmap的数据结构为下图所示。

​　　重点！！：e和e.next为线程b中的引用变量，分别指向hashmap中的entry3和entry2。由于entry3和entry2是线程共享的，因此受线程a执行的影响，entry3将指向null，entry2指向entry3。

​　　此时线程b中局部变量newtable的结构：

执行第一次循环：e为entry3，e.next为entry2（线程b暂停前e和e.next引用变量的指向）

 1 //遍历e所在链上的所有键值对
 2 while(null != e) {
 3     //断点1，此时线程b中的e为entry3，e.next为entry2
 4     entry<k,v> next = e.next;
 5     //通常rehash为false，不会重新计算键值对key的hash值
 6     if (rehash) {
 7         e.hash = null == e.key ? 0 : hash(e.key);
 8     }
 9     //根据扩容后的table数组长度计算键值对的index
10     int i = indexfor(e.hash, newcapacity);
11     //头插法
12     e.next = newtable[i];//将entry3的next设置为null
13     newtable[i] = e;//将entry3放置到线程b newtable下标为3的位置
14     //继续处理entry2
15     e = next;
16 }

 执行完第一次循环后线程b中局部变量newtable的结构：

执行完第一次循环后hashmap对象的结构：

执行第二次循环：e为entry2，e.next为entry3（受线程a影响，e和e.next引用变量的指向发生改变）

 1 //遍历键值对e链上的所有键值对
 2 while(null != e) {
 3     //断点1，e为entry2，e.next为entry3
 4     entry<k,v> next = e.next;
 5     //通常rehash为false，不会重新计算键值对key的hash值
 6     if (rehash) {
 7         e.hash = null == e.key ? 0 : hash(e.key);
 8     }
 9     //由线程a的执行结果可知，entry2的index也为3
10     int i = indexfor(e.hash, newcapacity);
11     //头插法，
12     e.next = newtable[i];//将entry2的next设置为entry3
13     newtable[i] = e; //newtable[3]设置为entry2
14     //另e等于entry3，继续执行while循环。
15     e = next;
16 }

执行完第二次循环后线程b中局部变量newtable的结构：

执行完第二次循环后hashmap对象的结构：

执行第三次循环：e变为entry3，e.next为null

 1 //遍历键值对e链上的所有键值对
 2 while(null != e) {
 3     //断点1，此时线程b中的e变为entry3，e.next为null
 4     entry<k,v> next = e.next;
 5     //通常rehash为false，不会重新计算键值对key的hash值
 6     if (rehash) {
 7         e.hash = null == e.key ? 0 : hash(e.key);
 8     }
 9     //由线程a的执行结果可知，entry3的index为3
10     int i = indexfor(e.hash, newcapacity);
11     //头插法
12     e.next = newtable[i];//将entry3的next设置为当前链条的首个键值对entry2
13     newtable[i] = e;//newtable[3]设置为entry3
14     //另e=next=null，结束while循环。
15     e = next;
16 }

执行完第三次循环后线程b中局部变量newtable的结构：

执行完第三次循环后hashmap对象的结构：

​　　至此，线程b因为改变了entry3的next属性，在hashmap对象中产生了环形链表。下一节，将探究环形链表是如何在hashmap查询时产生死循环的。