个人中心
gpt4 book ai didi

浅谈HashMap在高并发下的问题

转载 作者：qq735679552 更新时间：2022-09-27 22:32:09 25 4
gpt4 key购买 nike

CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.

这篇CFSDN的博客文章浅谈HashMap在高并发下的问题由作者收集整理，如果你对这篇文章有兴趣，记得点赞哟.

前言

总所周知，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 。

最后此篇关于浅谈HashMap在高并发下的问题的文章就讲到这里了,如果你想了解更多关于浅谈HashMap在高并发下的问题的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。

25 4 0
文章推荐： SpringBoot如何自动生成API文档详解
文章推荐： yii2使用gridView实现下拉列表筛选数据
文章推荐： 光遇8.4任务攻略 光遇8.4每日任务是什么
文章推荐： 在IIS下安装PHP扩展的方法（超简单）
qq735679552
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
全站热门文章
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com