文档章节

谈谈HashMap线程不安全的体现

清尘V
 清尘V
发布于 2016/05/11 21:45
字数 1567
阅读 233
收藏 2

阿里云携手百名商业领袖、技术大咖,带您一探行进中的数字新基建!>>>

HashMap的原理以及如何实现,之前在JDK7与JDK8中HashMap的实现中已经说明了。

那么,为什么说HashMap是线程不安全的呢?它在多线程环境下,会发生什么情况呢?

1. resize死循环

我们都知道HashMap初始容量大小为16,一般来说,当有数据要插入时,都会检查容量有没有超过设定的thredhold,如果超过,需要增大Hash表的尺寸,但是这样一来,整个Hash表里的元素都需要被重算一遍。这叫rehash,这个成本相当的大。

void resize(int newCapacity) {
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;
        if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return;
        }

        Entry[] newTable = new Entry[newCapacity];
        transfer(newTable, initHashSeedAsNeeded(newCapacity));
        table = newTable;
        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
void transfer(Entry[] newTable, boolean rehash) {
        int newCapacity = newTable.length;
        for (Entry<K,V> e : table) {
            while(null != e) {
                Entry<K,V> next = e.next;
                if (rehash) {
                    e.hash = null == e.key ? 0 : hash(e.key);
                }
                int i = indexFor(e.hash, newCapacity);
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            }
        }
}

大概看下transfer:

  1. 对索引数组中的元素遍历
  2. 对链表上的每一个节点遍历:用 next 取得要转移那个元素的下一个,将 e 转移到新 Hash 表的头部,使用头插法插入节点。
  3. 循环2,直到链表节点全部转移
  4. 循环1,直到所有索引数组全部转移

经过这几步,我们会发现转移的时候是逆序的。假如转移前链表顺序是1->2->3,那么转移后就会变成3->2->1。这时候就有点头绪了,死锁问题不就是因为1->2的同时2->1造成的吗?所以,HashMap 的死锁问题就出在这个transfer()函数上。

1.1 单线程 rehash 详细演示

单线程情况下,rehash 不会出现任何问题:

  • 假设hash算法就是最简单的 key mod table.length(也就是数组的长度)。
  • 最上面的是old hash 表,其中的Hash表的 size = 2, 所以 key = 3, 7, 5,在 mod 2以后碰撞发生在 table[1]
  • 接下来的三个步骤是 Hash表 resize 到4,并将所有的 <key,value> 重新rehash到新 Hash 表的过程

如图所示:

1.2 多线程 rehash 详细演示

为了思路更清晰,我们只将关键代码展示出来

while(null != e) {
    Entry<K,V> next = e.next;
    e.next = newTable[i];
    newTable[i] = e;
    e = next;
}
  1. Entry<K,V> next = e.next;——因为是单链表,如果要转移头指针,一定要保存下一个结点,不然转移后链表就丢了
  2. e.next = newTable[i];——e 要插入到链表的头部,所以要先用 e.next 指向新的 Hash 表第一个元素(为什么不加到新链表最后?因为复杂度是 O(N))
  3. newTable[i] = e;——现在新 Hash 表的头指针仍然指向 e 没转移前的第一个元素,所以需要将新 Hash 表的头指针指向 e
  4. e = next——转移 e 的下一个结点

假设这里有两个线程同时执行了put()操作,并进入了transfer()环节

while(null != e) {
    Entry<K,V> next = e.next; //线程1执行到这里被调度挂起了
    e.next = newTable[i];
    newTable[i] = e;
    e = next;
}

那么现在的状态为:

从上面的图我们可以看到,因为线程1的 e 指向了 key(3),而 next 指向了 key(7),在线程2 rehash 后,就指向了线程2 rehash 后的链表。

然后线程1被唤醒了:

  1. 执行e.next = newTable[i],于是 key(3)的 next 指向了线程1的新 Hash 表,因为新 Hash 表为空,所以e.next = null
  2. 执行newTable[i] = e,所以线程1的新 Hash 表第一个元素指向了线程2新 Hash 表的 key(3)。好了,e 处理完毕。
  3. 执行e = next,将 e 指向 next,所以新的 e 是 key(7)

然后该执行 key(3)的 next 节点 key(7)了:

  1. 现在的 e 节点是 key(7),首先执行Entry<K,V> next = e.next,那么 next 就是 key(3)了
  2. 执行e.next = newTable[i],于是key(7) 的 next 就成了 key(3)
  3. 执行newTable[i] = e,那么线程1的新 Hash 表第一个元素变成了 key(7)
  4. 执行e = next,将 e 指向 next,所以新的 e 是 key(3)

这时候的状态图为:

然后又该执行 key(7)的 next 节点 key(3)了:

  1. 现在的 e 节点是 key(3),首先执行Entry<K,V> next = e.next,那么 next 就是 null
  2. 执行e.next = newTable[i],于是key(3) 的 next 就成了 key(7)
  3. 执行newTable[i] = e,那么线程1的新 Hash 表第一个元素变成了 key(3)
  4. 执行e = next,将 e 指向 next,所以新的 e 是 key(7)

这时候的状态如图所示:

很明显,环形链表出现了!!当然,现在还没有事情,因为下一个节点是 null,所以transfer()就完成了,等put()的其余过程搞定后,HashMap 的底层实现就是线程1的新 Hash 表了。

2. fail-fast

如果在使用迭代器的过程中有其他线程修改了map,那么将抛出ConcurrentModificationException,这就是所谓fail-fast策略。

这个异常意在提醒开发者及早意识到线程安全问题,具体原因请查看ConcurrentModificationException的原因以及解决措施

 

顺便再记录一个HashMap的问题:

为什么String, Interger这样的wrapper类适合作为键? String, Interger这样的wrapper类作为HashMap的键是再适合不过了,而且String最为常用。因为String是不可变的,也是final的,而且已经重写了equals()和hashCode()方法了。其他的wrapper类也有这个特点。不可变性是必要的,因为为了要计算hashCode(),就要防止键值改变,如果键值在放入时和获取时返回不同的hashcode的话,那么就不能从HashMap中找到你想要的对象。不可变性还有其他的优点如线程安全。如果你可以仅仅通过将某个field声明成final就能保证hashCode是不变的,那么请这么做吧。因为获取对象的时候要用到equals()和hashCode()方法,那么键对象正确的重写这两个方法是非常重要的。如果两个不相等的对象返回不同的hashcode的话,那么碰撞的几率就会小些,这样就能提高HashMap的性能。

Reference:

1. http://hwl-sz.iteye.com/blog/1897468?utm_source=tuicool&utm_medium=referral

2. http://github.thinkingbar.com/hashmap-infinite-loop/

3. http://www.importnew.com/7099.html

本文转载自:http://my.oschina.net/hosee/blog/673521

下一篇: java的NIO
清尘V

清尘V

粉丝 41
博文 107
码字总数 47780
作品 0
青岛
程序员
私信 提问
加载中

评论(0)

谈谈HashMap线程不安全的体现

HashMap的原理以及如何实现,之前在JDK7与JDK8中HashMap的实现中已经说明了。 那么,为什么说HashMap是线程不安全的呢?它在多线程环境下,会发生什么情况呢? 1. resize死循环 我们都知道H...

Hosee
2016/05/11
3.9K
1
大数据技术之_31_Java 面试题_02_== 和 equals 有什么区别 + String 相关 + 多态 + 传值 + static 加载机制 + 线程

1、== 和 equals 有什么区别?2、为什么需要同时覆写 hashCode 和 equals 方法?3、为什么用 eclipse 重写 hashCode 方法,有 31 这个数字?4、String 相关5、多态6、传值7、static 加载机制...

黑泽君
2019/06/17
0
0
2019最新初级JAVA面试问题

首先我们需要明白一个事实,招聘的一个很关键的因素是在给自己找未来的同事,同级别下要找比自己优秀的人,面试是一个双向选择的过程,也是一个将心比心去沟通的过程。 就像我们有的人感觉自...

osc_44jaxl0s
2019/02/14
12
0
并发编程(二):非线程安全集合类

前言 线程不安全的集合类 ArrayList: 结果一: 结果二: 抛出异常:ArrayIndexOutofBoundsException异常; 现象:出现null值; 出现输出不全的现象; 抛出异常; 原因: ArrayList中的add方...

mengdonghui123456
2017/08/14
0
0
HashMap线程不安全的体现

1、多线程put操作后,get操作导致死循环。 2、多线程put非NULL元素后,get操作得到NULL值。 3、多线程put操作,导致元素丢失。 参考:多线程下HashMap的死循环问题 比如一个 ArrayList 类,在...

osc_2xb14pj9
2019/09/03
5
0

没有更多内容

加载失败,请刷新页面

加载更多

.NET中小数,浮点数和双精度之间的区别? - Difference between decimal, float and double in .NET?

问题: What is the difference between decimal , float and double in .NET? .NET中的decimal , float和double float什么区别? When would someone use one of these? 有人什么时候会使用......

fyin1314
今天
22
0
如何找出Windows上正在侦听端口的进程? - How can you find out which process is listening on a port on Windows?

问题: 如何找出Windows上正在侦听端口的进程? 解决方案: 参考一: https://stackoom.com/question/CXO/如何找出Windows上正在侦听端口的进程 参考二: https://oldbug.net/q/CXO/How-can...

技术盛宴
今天
10
0
OSChina 周三乱弹 —— 一家动物都快饿成标本了~

@黑觉非常君 :前天晚上9点开始睡觉,睡到昨天上午8点起床,昨天下午2点又睡,睡到下午7点多,晚上10点又困了,又睡,睡到今天上午8点,中途没醒过,怎么这么能睡,是不是快挂了。 能睡不是好...

小小编辑
今天
15
0
神剧推荐全剧最污片段精剪

神剧推荐,全剧最污片段精剪 豆瓣评分最高,脑洞最大,脑回路最曲折,恶搞无数经典,没有一条差评的神剧 整个系列完整版 到这里观看

a57571735
今天
22
0
pingan.

职位诱惑:金融,技术研发,技术攻关,大舞台大作为职位描述:职位诱惑:立志打造一支国内一流实盘量化交易框架开发团队职位描述:职位描述:负责实盘低时延量化交易框架及附属行...

MtrS
今天
15
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部