高并发下的HashMap

HashMap不是一个线程安全的类,在并发下可能会出现死循环(JDK1.7),今天我们来聊聊这个死循环是如何形成的

本文基于 jdk-7u76 进行分析

温馨提示

本文对照着源码看并在纸上画画效果会更佳

代码回顾

师傅,我常常听别人说,不要在并发情况下使用HashMap,可能会出现死循环,这个死循环是怎么形成的呢?

一尘

慧能

这个听为师慢慢道来

我们都知道,HashMap的底层是由数组加链表来实现的

对HashMap底层不了解的可先看:

什么是HashMap?(讲了HashMap的底层原理)

神速Hash上(讲了Hash函数的设计)

神速Hash下(讲了链表法解决冲突及扩容)

当往HashMap中put一个键值对时,如果HashMap中的键值对数量 size 大于或等于阈值(threshold) 并且null != table[bucketIndex] 时会进行扩容

bucketIndex为该键值对最后被散列到hash表table的位置

比如 table的初始容量为4,加载因子为0.75,此时阈值为3,table已有三个元素,现在put一个元素<1,"A">,<1,"A">被散列到table[1]处,而table[1] != null,此时满足扩容条件

阈值 = 容量 * 加载因子

threshold = capacity * loadFactor

扩容时先生成一个是table大小2倍的newTable,然后把table中的元素迁移到newTable中,迁移的工作就由 transfer方法来完成,这个方法就是引起死循环的原因所在

环的形成

现在我们来模拟一下环是如何形成的,设HashMap的初始容量为4,先往HashMap中依次put三个元素<5,"B">、<9,"C">、<1,"A">,它们都被散列到table[1]处,形成了链

假设此时有两个线程并发对该HashMap进行put,线程1 put <13,"D">时,这个键值对被散列到table[1]处,满足扩容条件,进行扩容(生成newTable并进行迁移)

此时,线程1用 transfer 方法将 table中的元素迁移到 newTable 中,假设线程1执行完 transfer 方法中的 Entry<K,V> next = e.next 语句后时间片用完,挂起

此时,线程1内的 e 指向 <1,“A”>,next指向<9,"C">

然后线程2 put <16,"E">,同样这个键值对被散列到table[1]处,满足扩容条件,进行扩容

生成完newTable后用transfer方法进行迁移,执行完Entry<K,V> next = e.next;后与线程1一样,e指向<1,"A">,next指向<9,"C">

线程2 然后执行循环体下面的语句

线程2执行完之后为下图

然后线程2按照同样的逻辑进行第二次循环(while循环),下面是第二遍循环后的结果

下面是第三遍循环后的结果

此时,线程2时间片用完,线程1得到时间片,开始执行

注意,此时线程1的e指向<1,A>,next指向<9,C>,在线程2操作链表的时候,线程1 中的e,next指向的元素没变(一直是红色的e和next)

线程一和线程二整体图为:

然后线程1开始执行循环内剩下的代码

执行完后为下图

线程1继续执行第二遍循环

执行完为下图

线程1继续第三遍循环(注意:此次循环会形成环)

先执行 Entry<K,V> next = <1,A>.next

然后执行 <1,A>.next = newTable[1]

此时环已经形成

然后执行剩余的两行代码

执行完,e 为 null,退出循环

死循环的发生

当形成环后,当给HashMap中put元素的时候,这个元素恰巧落在了table[1](不管有没有更新table),而这个元素的Key不在table[1]这条链上,此时会发生死循环

或者在get元素的时候,该元素恰巧落在table[1]上,并且该元素的Key不在该链上,会发生死循环

原来死循环是这样形成的

一尘

慧能

对,核心就是线程2修改了原来的链表结构,而线程1却以原来的逻辑执行迁移

那并发下我还想使用散列表这种数据结构怎么办呢

一尘

慧能

用ConcurrentHashMap

推荐阅读:

什么是HashMap?

神速Hash

神速Hash

后记

想深入研究的伙伴可以用代码调试跑一遍

原文发布于微信公众号 - 趣谈编程(gh_51e791ad9174)

原文发表时间:2018-04-26

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏北京马哥教育

面试分享系列:从现在开始,准备加入BAT!

程序员是一项技术工种,个人的技术水平决定薪资。 程序员需要在面试的过程中展示自己的技术水平,通过有说服力的表现拿到自己理想的薪资。 面试中,面试题是招聘方对...

3176
来自专栏java技术学习之道

百度"Java面试题"前200页都在这里了

1392
来自专栏微信公众号:Java团长

Java面试题:百度前200页都在这里了

transient变量有什么特点 super什么时候使用 public static void 写成 static public void会怎样 说明一下pub...

1202
来自专栏程序员的知识天地

Python两步实现网页天气爬虫程序

说道爬虫大家或许感觉非常神秘,其实它没有我们想象的那么神奇,今天我们就来揭开它神秘的面纱。呵呵,简单两步就可以实现一个网页天气爬虫程序。。。

1841
来自专栏MyBlog

Effective Java 读书笔记(7)避免finalizer

对于Finalizers他们的使用可能会造成错误的产生,糟糕的性能以及移植性的问题,当然Finalizers有着一些有用的优点,我们会在后续介绍这些,但是作为首...

1102
来自专栏安恒网络空间安全讲武堂

​CTF逆向——常规逆向篇(下)

CTF逆向——常规逆向篇(下) 题目: CrackMe.exe(NSCTF reverse第一题) WHCTF2017 reverse HCTF reverse...

5275
来自专栏Python绿色通道

Python入门三部曲(三)

在函数greet_user()中,变量username是一个形参—-函数完成其工作所需要的一项信息.在代码greet_user(‘kobe’)中,值’kobe’...

1463
来自专栏风中追风

高效编程之HashMap的entryset和keyset比较

最近看了一点spring的源码,甚是苦涩;对spring稍微有了点整体的认识,但对很多细节的地方还是懵逼啊。。。太多不懂了的,只能慢慢去读,先把简单的不懂的解决...

37710
来自专栏贾老师の博客

C/C++ 中的异常处理

1412
来自专栏Zephery

工厂模式

工厂模式 目录 何为工厂模式 工厂方法与抽象工厂 如何在Java EE中通过@Producers与@Inject注解实现工厂模式 如何创建自定义注解以及通过@Q...

42711

扫码关注云+社区

领取腾讯云代金券