您现在的位置是:首页 > 文章详情

并发编程专题八-hashMap死循环分析

日期:2019-05-28点击:348

一、hashMap并发中存在的问题

在我们开发程序过程中,hashMap算是我们最常用的数据结构了,那么如果我们在高并发下使用hashMap可能会出现什么问题呢?

1、拿到的结果不是我们想要的。(非线程安全)

2、扩容而导致程序死循环。致使CPU100%;(JDK1.7版本扩容,1.8暂无此问题。严重

为什么会出现死循环,接下来我们进行分析一下。首先我们了解下hashMap的源码,以及put操作。

1.1 1.7HashMap源码简析

1.1.1 构造函数解析

hashMap代价都比较熟悉了,这里就简单介绍HashMap几个关键点。HashMap的数据结构就是数组+链表的数据结构,如下

static class Entry<K,V> implements Map.Entry<K,V> { final K key; V value; Entry<K,V> next;//存储指向下一个Entry的引用,单链表结构 int hash;//对key的hashcode值进行hash运算后得到的值,存储在Entry,避免重复计算 /** * Creates new entry. */ Entry(int h, K k, V v, Entry<K,V> n) { value = v; next = n; key = k; hash = h; } 

当实例化一个HashMap时,系统会创建一个长度为Capacity的Entry数组,这个长度被称为容量(Capacity),在这个数组中可以存放元素的位置我们称之为“桶”(bucket),每个bucket都有自己的索引,系统可以根据索引快速的查找bucket中的元素。 每个bucket中存储一个元素,即一个Entry对象,但每一个Entry对象可以带一个引用变量,用于指向下一个元素,因此,在一个桶中,就有可能生成一个Entry链。 Entry是HashMap的基本组成单元,每一个Entry包含一个key-value键值对。 

一个长度为16的数组中,每个元素存储的是一个链表的头结点。那么这些元素是按照什么样的规则存储到数组中呢。一般情况是通过hash(key)%len获得,也就是元素的key的哈希值对数组长度取模得到。比如上述哈希表中,12%16=12,28%16=12,108%16=12,140%16=12。所以12、28、108以及140都存储在数组下标为12的位置。

在存储一对值时(Key—->Value对),实际上是存储在一个Entry的对象e中,程序通过key计算出Entry对象的存储位置。换句话说,Key—->Value的对应关系是通过key—-Entry—-value这个过程实现的,所以就有我们表面上知道的key存在哪里,value就存在哪里。

构造函数里的参数值

//默认初始化化容量,即16 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; //最大容量,即2的30次方 static final int MAXIMUM_CAPACITY = 1 << 30; //默认装载因子 static final float DEFAULT_LOAD_FACTOR = 0.75f; //HashMap内部的存储结构是一个数组,此处数组为空,即没有初始化之前的状态 static final Entry<?,?>[] EMPTY_TABLE = {}; //空的存储实体 transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE; //实际存储的key-value键值对的个数 transient int size; //阈值,当table == {}时,该值为初始容量(初始容量默认为16);当table被填充了,也就是为table分配内存空间后,threshold一般为 capacity*loadFactory。HashMap在进行扩容时需要参考threshold int threshold; //负载因子,代表了table的填充度有多少,默认是0.75,当超过容量*负载因子时会进行扩容 final float loadFactor; //用于快速失败,由于HashMap非线程安全,在对HashMap进行迭代时,如果期间其他线程的参与导致HashMap的结构发生变化了(比如put,remove等操作),需要抛出异常ConcurrentModificationException transient int modCount; 

1.2.2 put源码分析

1、当我们将一个元素放入hashMap中,首先判断map是否为空,如果是空,对数组进行填充

2、如果Key为null,则将值存储在table[0]的位置或table[0]的链表冲突连上

3、对key值再进行hash散列,使其散列均匀,然后通过indexFor进行确定table的位置,该方法为h & (length-1);就是拿当前hash的值如table长度-1做与运算,其实本质等于hash值除table长度取余。

4、然后循环遍历链表,查看链表里的key是否存在,存在的话替换旧值。然后return 老的值

5、如果不存在,则在尾部添加新的entry节点。

public V put(K key, V value) { //如果table数组为空数组{},进行数据填充 if (table == EMPTY_TABLE) { inflateTable(threshold);//分配数组空间 } //如果key为null,存储位置为table[0]或table[0]的冲突链上 if (key == null) return putForNullKey(value); int hash = hash(key);//对key的hashcode进一步hash计算,确保散列均匀 int i = indexFor(hash, table.length);//获取在table中的实际位置 for (Entry<K,V> e = table[i]; e != null; e = e.next) { //如果该对应数据已存在,执行覆盖操作。用新value替换旧value,并返回旧value Object k; if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; e.value = value; e.recordAccess(this);//调用value的回调函数,其实这个函数也为空实现 return oldValue; } } modCount++;//保证并发访问时,若HashMap内部结构发生变化,快速响应失败 addEntry(hash, key, value, i);//新增一个entry return null; }

1.2.3 addEntry节点方法以及扩容

void addEntry(int hash, K key, V value, int bucketIndex) { if ((size >= threshold) && (null != table[bucketIndex])) { resize(2 * table.length);//当size超过临界阈值threshold,并且即将发生哈希冲突时进行扩容,新容量为旧容量的2倍 hash = (null != key) ? hash(key) : 0; bucketIndex = indexFor(hash, table.length);//扩容后重新计算插入的位置下标 } //把元素放入HashMap的桶的对应位置 createEntry(hash, key, value, bucketIndex); } //创建元素 void createEntry(int hash, K key, V value, int bucketIndex) { Entry<K,V> e = table[bucketIndex]; //获取待插入位置元素 table[bucketIndex] = new Entry<>(hash, key, value, e);//这里执行链接操作,使得新插入的元素指向原有元素。 //这保证了新插入的元素总是在链表的头 size++;//元素个数+1 } 

1、当我们对要插入的元素定好位置之后,则需要对当前链表进行判断是否需要扩容

2、当前table数组长度大于threashold(表默认长度*负载因子)的时候,则需要对数组进行扩容,扩容方式为当前的数组长度的两倍

3、当数组扩容完毕,需要重新计算所有的元素的位置,然后插入对应的位置当中。扩容方法主要为resize以及resize中的transfer方法,不在细说

如图

扩容前,3,7,5对数组长度2取摩都是值1,所以都是在1的位置.

扩容后数组table长度为4,7,3取摩后为位置为3,5取摩为位置为1

4、最后执行createEntry方法,将生成的节点插入对应位置的头部。

1.3、HashMap死循环分析

了解了hashMap中put以及扩容操作之后,我们模拟一个场景。有原hashMap如下

在多线程环境下有线程一和线程二,同时对该map进行扩容执行扩容。

当线程一执行到如下代码时被挂起

此时线程1的数据结构为,table已经扩容完毕,重新计算每个元素位置时被挂起,此时key为3的还在1位置,3.next为7。

这时,线程2完成扩容,扩容后的数据结构为

当线程1被调度回来执行之后,因为线程一执行的e.next =newTable[i];将key3插入到3号位置,同时3.next=key7。此时e=key3,next=key7;

当执行到e=next的时候,e=key7,next=key7;

然后开始下一轮while。但此时因为线程二已经将key=7的next设置为key3(问题就在这里,线程二执行的时候,key7.next已经是null了,但这里线程一去执行的时候key7.next却是key3)。所以当第二轮循环开始,执行next=e.next后,next = key3。

之后通过头插法,将key7插入key3之前。在执行完next=e.next 之后,e=key3,next=key3;

然后开始第三轮循环。e和next都是key3。所以根据头插法。key3又要插入key7之前,这就导致了key3.next为key7,key7.next为key3

所以当我们去get值得时候,当定位到3的时候,就会产生死循环。导致永远拿不到数据。

总结

HashMap之所以在并发下的扩容造成死循环,是因为,多个线程并发进行时,因为一个线程先期完成了扩容,将原Map的链表重新散列到自己的表中,并且链表变成了倒序,后一个线程再扩容时,又进行自己的散列,再次将倒序链表变为正序链表。于是形成了一个环形链表,当get表中不存在的元素时,造成死循环。在1.8当中,链表扩容转为红黑树,没有相关的问题。

其他阅读   并发编程专题,大家有问题可以加我微信哈~

481021518c4b8fa00ba60ef9609c53b2b5f.jpg

原文链接:https://my.oschina.net/u/3694479/blog/3054837
关注公众号

低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。

持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。

转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。

文章评论

共有0条评论来说两句吧...

文章二维码

扫描即可查看该文章

点击排行

推荐阅读

最新文章