• HashMap在多线程环境下的安全问题
  • 发布于 1周前
  • 77 热度
    1 评论
HashMap是最常用的数据结构之一,有着出色的查询效率,在上篇推文中提及了它的一些基本构成和处理碰撞的机制。但是在多线程环境中,它是不安全的,这也是面试喜欢问的问题之一。这篇是我对HashMap的线程不安全的一些理解,希望若有谬误之处,不吝赐教。

HashMap的初始容量是16,当长度超出12(16的3/4)时,Map需要扩容,每次扩容之后大小都是之前的两倍。

扩容时,需要将容器中的元素重新计算一遍,并且创建一个更长的新的数组,将元素复制进这个新数组。这个步骤很消耗性能,所以,在初始化map的时候,尽可能地按照需要指定其长度,尽量减少resize的次数,这是一个良好的习惯。

为什么采用两倍的扩容方式呢?

因为使用位运算比直接取模效率高很多,在JDK7中,采用的是 取模来计算桶的位置,在JDK8中采用了巧妙的位运算的方式: h&(length-1),h是元素的key的哈希值,length是数组的长度。这样的好处是首先降低了运算的难度,因为位运算对于计算机来说只要判断1或0;第二点好处是,由于这种方式,在hashMap扩容的时候,不需要重新对hash值进行取模。只需要判断当前元素是保持当前位置不变,还是需要移动长度为length个位置即可,这减少了运算的次数。

那么HashMap是具体是如何扩容的呢?

这里就不将源码贴出来了,确实有些晦涩,暂时大可不必“锱铢必较”,暂时由我口述这个流程即可。

1.对数组上的元素进行遍历
2.检查数组上每个索引位置上是否存在链表(或红黑树):若存在,重新计算该元素的index,并用头插法(为什么是头插法?因为如果使用尾插法,需要遍历链表,复杂度O(N),效率低)将其插入新的HashMap。
3.循环第二个步骤,直到旧数组当前索引下的元素全部转完成。

4.遍历数组的下一个位置,直到数组全部转移。


HashMap为什么线程不安全?

最著名的情况是两个线程同时执行 resize操作,先来演示一下假如在单线程情况下,正确的扩容流程的图解:

如果两个线程同时对一个HashMap进行操作:

1.线程A:愉快地开始对数组进行操作(参照上图步骤)当处理到第一步时,时间片用尽,线程A被挂起,将资源让给其他线程。此时e指向key(3),next指向key(7)。
2.线程B:获取时间片,开始对数组进行操作(参照上图步骤)比较幸运的是(对程序来说是不幸),线程B完成了上述三个步骤。此时key(7)指向key(3)。
3.线程A被再度唤醒,它不知道在他小憩了一瞬间的时候发生了什么事,开始继续完成自己的任务。
4.相比此时大家也看出来了,key(3),key(7)之间出现了一个死循环。
这就是最经典的HashMap线程不安全原因了

此外,在日常的put操作中,hashMap仍然存在着线程安全隐患。

先看一下put操作的流程:

在两个线程对数组进行插入时:

1.线程A将一个Node A的key计算出hash值,并且通过取模/位运算操作后,要插入到数组的一个桶中时,时间片耗尽。
2.线程B获取资源,顺利完成将一个Node B插入到数组或数组某索引下的链表之中。但是吴巧不成书,Node B的链表头与Node A的链表头是一样的,而这一切,A和B都不知晓。
3.发生灾难,线程A被唤醒,它不知道之前计算出来的链表头的位置已经被B占用了,所以仍然继续操作,于是将Node B的数据覆盖了。造成了数据的丢失。
用户评论