探究HashMap线性不安全（一）——重温HashMap的put操作

内容

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

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

适合人群

　　​java进阶

参考

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

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

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

正文

​　　了解过hashmap底层实现的童鞋都知道，向hashmap存入键值对时，如果当前map中键值对的个数size已经大于等于扩容的阈值threshold，并且对应链表上数据不为空时，线程会执行resize()方法对hashmap扩容。过程如下：

 1 public v put(k key, v value) {
 2     //判断key是否为null，如果是null则将该键值对存放到到index为0的位置上
 3     if (key == null)
 4         return putfornullkey(value);
 5     //计算key的hash值
 6     int hash = hash(key);
 7     //对hash值取模求key对应的index
 8     int i = indexfor(hash, table.length);
 9     //判断key是否已经存在，若存在则覆盖对应的value值，并返回旧value值
10     for (entry<k,v> e = table[i]; e != null; e = e.next) {
11         object k;
12         if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
13             v oldvalue = e.value;
14             e.value = value;
15             e.recordaccess(this);
16             return oldvalue;
17         }
18     }
19     
20     modcount++;
21     //若键值对不存在，则插入到table中
22     addentry(hash, key, value, i);
23     return null;
24 }　

 1 void addentry(int hash, k key, v value, int bucketindex) {
 2     //扩容的两个条件：map中键值对的个数size已经大于等于扩容的阈值threshold，table的当前位置上已经存在键值对。
 3     if ((size >= threshold) && (null != table[bucketindex])) {
 4         //扩容操作具体由resize()方法执行。
 5         resize(2 * table.length);
 6         hash = (null != key) ? hash(key) : 0;
 7         bucketindex = indexfor(hash, table.length);
 8     }
 9      //将键值对存入到指定index位置的链上
10     createentry(hash, key, value, bucketindex);
11 }

 　　resize()方法中的transfer()方法用于将oldtable中的原有键值对信息复制到扩容后的newtable中。

 1 void resize(int newcapacity) {    
 2     //使用oldtable指向扩容前的table
 3     entry[] oldtable = table;
 4     int oldcapacity = oldtable.length;
 5     //如果hashmap的容量已经达到最大值，那么将扩容阈值threshold设置为integer的最大值
 6     if (oldcapacity == maximum_capacity) {
 7         threshold = integer.max_value;
 8         return;
 9     }
10     //按照传入的容量，创建新的table
11     entry[] newtable = new entry[newcapacity];
12     //usealthashing在初始化后为false
13     boolean oldalthashing = usealthashing;
14     usealthashing |= sun.misc.vm.isbooted() &&
15             (newcapacity >= holder.alternative_hashing_threshold);
16     //jvm启动后，但由于扩容后的容量newcapacity<alternative_hashing_threshold，usealthashing也为false
17     //false与false异或，rehash=false，因此不会对key值重新进行hash计算。
18     boolean rehash = oldalthashing ^ usealthashing;
19     //进行新旧table数据的迁移
20     transfer(newtable, rehash);
21     //将table指向迁移后的newtable
22     table = newtable;
23     //按照计算公式为newcapacity * loadfactor更新扩容阈值threshold
24     threshold = (int)math.min(newcapacity * loadfactor, maximum_capacity + 1);
25 }

 ​　　通过调试可知holder.alternative_hashing_threshold为integer.max_value

​　　因此默认情况下rehash为false，扩容过程中不会对key值重新计算hash。下一节将详细探究hashmap扩容的键值对迁移过程，多线程并发执行transfer()方法是如何产生环形链表的。