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

来源：cnblogs　　作者：比脚更长的路　　时间：2018/9/30 11:07:12　　对本文有异议

内容

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

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

适合人群

　　?Java进阶

参考

? 　　1、https://www.toutiao.com/i6544826418210013700/ HashMap底层数据结构原理

? 　　2、https://www.toutiao.com/i6545790064104833539/ 为什么HashMap非线程安全

?　　 3、https://blog.csdn.net/qq_32182461/article/details/81152025 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 }