并发编程专题八-hashMap死循环分析
一、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当中,链表扩容转为红黑树,没有相关的问题。
其他阅读 并发编程专题,大家有问题可以加我微信哈~

低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
Rancher发布Rio:为Kubernetes打造极简MicroPaaS平台
Rio已于近日正式发布!一个结合了Istio、Knative和Kubernetes的力量,且拥有像Docker一样的极简使用体验的MicroPaaS平台。 2019年5月21日,业界领先的容器管理软件提供商Rancher Labs(以下简称Rancher)宣布推出Rio,一个可以在任何符合标准的Kubernetes集群上使用的MicroPaaS平台。Rio由一些Kubernetes自定义资源和一个可选的CLI构成,用户可以轻松地将服务部署到Kubernetes,自动获得持续交付、DNS、HTTPS、路由、监控、自动扩缩容、金丝雀部署、git触发构建等功能。 “Rancher所有的产品,自始至终不变的理念都是致力于让Kubernetes简单易用。但我们团队深切感受到,如今业界现有的产品或解决方案,并没有解决管理Istio和Knative等工具所需的大量工作量的问题。”Rancher首席架构师及联合创始人Darren Shepherd表示:“正是出于这种考量,我们构建了Rio,让开发人员可以使用单个命令,就能部署、管理、扩展和编译应用程序。” Rio是2019年Rancher推出的第三个全...
- 下一篇
持续集成与持续交付之间的联系和区别
作者 | Rebecca Pruess 编译 | 毛智伟 随着DevOps理念的普及与扩散,大家经常会看到持续集成(Continuous Integration)与持续交付(Continuous Delivery)这样的字眼,而怎样使用与选择这些方法成了大多数IT团队必须面对的问题。在讨论更加深入地讨论问题之前,首先需要清楚这两者之间的主要区别是什么,以及用什么方法可以更好改善工作流程,从而在更短的时间内为目标用户提供更高质量的软件。 持续集成(CI)和持续交付(CD)都体现了如今快节奏市场中的文化和发展原则,旨在缩短开发周期、提高软件交付效率以及实现全流程的自动化。同时,两者都有着共同的目标:让软件开发更少地依赖于手动执行的任务,在此基础上使得软件的发布更加频繁、更加安全可靠。由于有着相同的目标,因此持续集成和持续交付并非相互排斥的。只是它们的应用范围有所不同。 那下面就来看下CI与CD之间的联系与区别。 什么是持续集成 如上所述,CI和CD是相互关联的。持续集成是指软件个人研发的部分向软件整体部分交付,频繁进行集成以便更快地发现其中的错误。由此可见,CI专注于定期地让开发人员构建小...
相关文章
文章评论
共有0条评论来说两句吧...