探究HashMap线性不安全(三)——死循环的产生 – 比脚更长的路

内容

  网上很多资料都详细地讲解了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对象查找一个不为空的Key时,会执行getEntry(key)方法。

1 public V get(Object key) {
2         //key为null时,从index为0的链表中查找数据
3         if (key == null)
4             return getForNullKey();
5         //key不为null是查找数据    
6         Entry<K,V> entry = getEntry(key);
7         //如果未查找到key对应的值,那么entry为null,get方法会返回null。
8         return null == entry ? null : entry.getValue();
9     }

1538216304142

​  getEntry(key)方法会计算Key的hash值,然后通过indexFor(hash, table.length)对hash值取模求得key对应table数组的下标index。如果这个Key对应的table数组下标为3,那么线程会在下标3处的环形链表上遍历检索目标key对应的值。当key对应的键值对不存在,线程将进入死循环,代码如下所示:

 1 final Entry<K,V> getEntry(Object key) {
 2     //计算key的hash值
 3     int hash = (key == null) ? 0 : hash(key);
 4     //通过indexFor(hash, table.length)求得key对应的index,然后遍历index下表的链表
 5     for (Entry<K,V> e = table[indexFor(hash, table.length)];
 6          e != null;
 7          e = e.next) {
 8         Object k;
 9         //如果链表中不存在对应key的键值对,且链表为环形,那么当前线程将在for语句中产生死循环。
10         if (e.hash == hash &&
11             ((k = e.key) == key || (key != null && key.equals(k))))
12             return e;
13     }
14     return null;
15 }

​  至此,JDK1.7中HashMap的线性不安全特性已经论证完毕。下一节,将探究JDK1.8中HashMap的线性不安全特性。



You must enable javascript to see captcha here!

Copyright © All Rights Reserved · Green Hope Theme by Sivan & schiy · Proudly powered by WordPress

无觅相关文章插件,快速提升流量