服务器之家

服务器之家 > 正文

浅谈HashMap在高并发下的问题

时间:2021-11-01 10:41     来源/作者:梧桐和风

前言

总所周知,HashMap不是线程安全的,在高并发情况下会出现问题。特别是,在java1.7中,多线程的HashMap会出现CPU 100%的严重问题。这个问题是怎样产生的,后续版本还会有这个问题吗(指java8及后续版本)?下面就来用通俗的语言讲解下。

解析

关于这个问题,是由于java7多线程扩容机制下链表变为循环链表,再获取该链表导致的。

看下java7中扩容的代码。java7中HashMap的实现为数组+链表的形式,没有红黑树。

java7扩容的原则很简单,新数组长度为原数组2倍。遍历原数组,将数组每个位置(有可能为空,有可能只有一个数组,有可能是一个链表)重新哈希,放到对应的新数组上。全部遍历完后更改数组指针,指向新数组。需要注意的是,这里重哈希将链表元素放到新数组,使用的是头插法。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// 扩容核心方法,基本思想就是遍历数据,使用头插法将旧数组元素移到新数组。
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]; // 头插法,新节点next指向该位置首节点
               newTable[i] = e; // 新元素归位
               e = next; // 指向下一个节点,继续遍历
           }
       }
   }
  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);
   }

这里处理的话,如果单线程情况下不会有问题。如果在多线程情况下,会导致链表在扩容过程中形成循环链表。

形成循环链表的原因在于多线程和头插法。试想,两个线程在添加元素时,同时发现该扩容了,然后同时发起扩容过程。由上述代码可知,扩容完成之前是在自己的线程里创建一个新数组。等扩容完成后(也就是将原数组元素迁移到新数组后)再更改指针指向新扩容数组。

举例初始HashMap是这样的

浅谈HashMap在高并发下的问题

假设两个线程同时扩容,一个线程扩容到一半后被挂起。(标识了某链表的e和next),另一个线程执行扩容,且完成了扩容。

浅谈HashMap在高并发下的问题

红色的数组和元素表示线程1,也就是扩容一半挂起的线程,而线程二已完成扩容。观察完成扩容的线程二,在3的位置,该链表的位置顺序已经改变(原数组顺讯为3->7,现在反过来了,这是使用头插法的效果,你也可以对着代码试试)。从图中也可以看出,线程1,2分别创建了自己的新数组,并在自己的新数组中完成扩容。

这时线程1开始执行。熟悉下它即将执行的代码。

?
1
2
3
4
5
6
7
8
9
10
11
// transfer 方法循环部分
  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]; // 头插法,新节点next指向该位置首节点
         newTable[i] = e; // 新元素归位
         e = next; // 指向下一个节点,继续遍历
     }

下面线程1将使用头插法将元素插入线程1新建的数组中去。注意此时e指向的是Key3,next指向的是Key7。不用想也知道后面操作会有问题。因为现在的next指针指的不是e的下一个元素,而是它的前一个元素!

如果继续走代码的话,把Key3(当前e指向元素)放入新数组后,再把Key7放入新数组,后面会放哪个元素?当然又是Key3了,因为Key7next是Key3,这样就形成了死循环。

浅谈HashMap在高并发下的问题

java8的改进

  • 添加了红黑树,当链表长度大于8时,会将链表转为红黑树。
  • 扩容后,新数组中的链表顺序依然与旧数组中的链表顺序保持一致。具体JDK8是用 head 和 tail 来保证链表的顺序和之前一样,这样就不会产生循环引用。也就没有死循环了。
  • 虽然修复了死循环的BUG,但是HashMap 还是非线程安全类,仍然会产生数据丢失等问题。

以上为个人经验,希望能给大家一个参考,也希望大家多多支持服务器之家。

原文链接:https://blog.csdn.net/wthfeng/article/details/88972137

标签:

相关文章

热门资讯

yue是什么意思 网络流行语yue了是什么梗
yue是什么意思 网络流行语yue了是什么梗 2020-10-11
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全 2019-12-26
背刺什么意思 网络词语背刺是什么梗
背刺什么意思 网络词语背刺是什么梗 2020-05-22
2021年耽改剧名单 2021要播出的59部耽改剧列表
2021年耽改剧名单 2021要播出的59部耽改剧列表 2021-03-05
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总 2020-11-13
返回顶部