高并发环境下,HashMap可能出现的致命问题!

JAVA herman 1713浏览
公告:“业余草”微信公众号提供免费CSDN下载服务(只下Java资源),关注业余草微信公众号,添加作者微信:codedq,发送下载链接帮助你免费下载!
本博客日IP超过2000,PV 3000 左右,急需赞助商。
极客时间所有课程通过我的二维码购买后返现24元微信红包,请加博主新的微信号:codedq,之前的微信号好友位已满,备注:返现
饿了么大量招人,我内推!Java 方向!薪资不设上限,工作年龄不限!工作地点限魔都,可电话面试!简历,发我微信:codedq
所有面试题(java、前端、数据库、springboot等)一网打尽,请关注文末小程序
视频教程免费领

高并发环境下,HashMap可能出现的致命问题!注意:是在 jdk8 以下版本发生!

我们先来看看 Rehash 的概念。

Rehash 是 HashMap 在扩容时候的一个步骤。

HashMap 的容量是有限的。当经过多次元素插入,使得 HashMap 达到一定饱和度时,Key 映射位置发生冲突的几率会逐渐提高。

这时候,HashMap 需要扩展它的长度,也就是进行 Resize。

影响发生 Resize 的因素有两个:

  • Capacity(HashMap 的当前长度–容量)

HashMap 的当前长度。上一期曾经说过,HashMap 的长度是 2 的幂。

  • LoadFactor(负载因子)

HashMap 负载因子,默认值为 0.75f。

衡量 HashMap 是否进行 Resize 的条件如下:

HashMap.Size >= Capacity * LoadFactor (默认情况下是 == 原来长度 * 0.75)

HashMap 的 Resize 方法具体做了什么事情?

  • 扩容

创建一个新的Entry空数组,长度是原数组的2倍。

  • ReHash

遍历原 Entry 数组,把所有的 Entry 重新 Hash 到新数组。为什么要重新 Hash 呢?因为长度扩大以后,Hash 的规则也随之改变。

让我们回顾一下Hash公式:

index = HashCode(Key) & (Length - 1)

当原数组长度为 8 时,Hash 运算是和 111B(代表二进制的 7)做与运算;新数组长度为16,Hash 运算是和 1111B(代表二进制的 15)做与运算。Hash 结果显然不同

ReHash 的 Java 代码如下:

/**
 * Transfers all entries from current table to newTable.
 */
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;
        }
    }
}

注意 HashMap 在多线程下的 Rehash 可能会出现什么样的问题呢?

现在假设一个 HashMap 已经到了 Resize 的临界点。此时有两个线程 A 和 B,在同一时刻对 HashMap 进行 Put 操作:

此时达到 Resize 条件,两个线程各自进行 Rezie 的第一步,也就是扩容。

这时候,两个线程都走到了 ReHash 的步骤。让我们回顾一下 ReHash 的代码:

假如此时线程 B 遍历到 Entry3 对象,刚执行完红框里的这行代码,线程就被挂起。

对于线程 B 来说:e = Entry3 next =Entry2 这时候线程 A 畅通无阻地进行着 Rehash,当 ReHash 完成后,结果如下(图中的 e 和 next,代表线程 B 的两个引用):

直到这一步,看起来没什么毛病。接下来线程 B 恢复,继续执行属于它自己的 ReHash。 线程 B 刚才的状态是:e = Entry3 next = Entry2

当执行到上面这一行时,显然 i = 3,因为刚才线程 A 对于 Entry3 的 hash 结果也是3。

我们继续执行到这两行,Entry3 放入了线程 B 的数组下标为 3 的位置,并且 e 指向了 Entry2。

此时 e 和 next 的指向关系:e =Entry2 next = Entry2 整体情况如下图所示:

接着是新一轮循环,又执行到红框内的代码行:

e = Entry2

next = Entry3

整体情况如图所示:

接下来执行下面的三行,用头插法把 Entry2 插入到了线程 B 的数组的头结点:

整体情况如图所示:

第三次循环开始,又执行到红框的代码:

e = Entry3

next = Entry3.next = null

最后一步,当我们执行下面这一行的时候,见证奇迹的时刻来临了。

newTable[i] = Entry2
e = Entry3
Entry2.next = Entry3
Entry3.next = Entry2

链表出现了环形!整体情况如图所示:

此时,问题还没有直接产生。当调用 Get 查找一个不存在的 Key,而这个 Key 的 Hash 结果恰好等于 3 的时候,由于位置 3 带有环形链表,所以程序将会进入死循环!

这种情况,不禁让人联想到一道经典的面试题:如何判断链表有环?

如何杜绝这种情况?

最后总结如下:

  • Hashmap 在插入元素过多的时候需要进行 Resize。

Resize 的条件是 HashMap.Size >= Capacity * LoadFactor

  • Hashmap 的 Resize 包含扩容和 ReHash 两个步骤,ReHash 在并发的情况下可能会形成链表环。

链表头插法的会颠倒原来一个散列桶里面链表的顺序。在并发的时候原来的顺序被另外一个线程 a 颠倒了,而被挂起线程 b 恢复后拿扩容前的节点和顺序继续完成第一次循环后,又遵循 a 线程扩容后的链表顺序重新排列链表中的顺序,最终形成了环。

这也是为什么后来 HashMap 改为尾插法的原因之一。

业余草公众号

最后,欢迎关注我的个人微信公众号:业余草(yyucao)!可加作者微信号1:xmtxtt(5000人已满),微信号2:xttblog(5000人已满),微信号3:codedq(超3800)。备注:“1”,添加博主微信拉你进微信群。备注错误不会同意好友申请。再次感谢您的关注!后续有精彩内容会第一时间发给您!原创文章投稿请发送至532009913@qq.com邮箱。商务合作也可添加作者微信进行联系!

本文原文出处:业余草: » 高并发环境下,HashMap可能出现的致命问题!