1. 首页
  2. 文章列表
  3. 漫画详解高并发下的HashMap

上一篇介绍了HashMap的基本原理,这一篇来讲解高并发环境下,HashMap可能出现的致命问题。

懒得勤快的博客_全栈开发者_互联网分享精神

懒得勤快的博客_全栈开发者_互联网分享精神

懒得勤快的博客_全栈开发者_互联网分享精神

懒得勤快的博客_全栈开发者_互联网分享精神

懒得勤快的博客_全栈开发者_互联网分享精神

懒得勤快的博客_全栈开发者_互联网分享精神

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

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

懒得勤快的博客_全栈开发者_互联网分享精神

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

1.Capacity

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

2.LoadFactor

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

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

HashMap.Size   >=  Capacity * LoadFactor

懒得勤快的博客_全栈开发者_互联网分享精神


1.扩容

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

2.ReHa" alt='懒得勤快的博客_全栈开发者_互联网分享精神' title='懒得勤快的博客_全栈开发者_互联网分享精神'/>

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

让我们回顾一下Hash公式:

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

当原数组长度为8时,Hash运算是和111B做与运算;新数组长度为16,Hash运算是和1111B做与运算。Hash结果显然不同。

Resize前的HashMap:

懒得勤快的博客_全栈开发者_互联网分享精神

Resize后的HashMap:

懒得勤快的博客_全栈开发者_互联网分享精神

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已经到了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带有环形链表,所以程序将会进入死循环!

懒得勤快的博客_全栈开发者_互联网分享精神

懒得勤快的博客_全栈开发者_互联网分享精神

懒得勤快的博客_全栈开发者_互联网分享精神

懒得勤快的博客_全栈开发者_互联网分享精神


1.Hash" alt='懒得勤快的博客_全栈开发者_互联网分享精神' title='懒得勤快的博客_全栈开发者_互联网分享精神'/>

HashMap.Size   >=  Capacity * LoadFactor。

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

—————END—————

漫画转自:玻璃猫

文章历史版本:

修改次数:1 次 查看历史版本

版权声明:

本文仅用于学习、研究和交流目的,欢迎非商业性质转载。本文链接:https://masuit.com/161

l  博主在此发文(包括但不限于汉字、拼音、拉丁字母)均为随意敲击键盘所出,用于检验本人电脑键盘录入、屏幕显示的机械、光电性能,并不代表本人局部或全部同意、支持或者反对观点。如需要详查请直接与键盘生产厂商法人代表联系。挖井挑水无水表,不会网购无快递。

l  文章内容部分来源于互联网,不代表本人的任何立场;涉及到的软件来源于互联网,仅供个人下载使用,请勿用于商业用途,版权归软件开发者所有,下载后请于24小时内删除,请支持正版!因下载本站任何资源造成的损失,全部责任由使用者本人承担!如果你是版权方,认为本文内容对您的权益有所侵犯,请联系博主,待博主进行严格地审查和背景调查后,情况属实的将在三天内将本文删除或修正。

l  博主的文章没有高度、深度和广度,只是凑字数。由于博主的水平不高(其实是个菜B),不足和错误之处在所难免,希望大家能够批评指出。

l  博主是利用读书、参考、引用、抄袭、复制和粘贴等多种方式打造成自己的纯镀 24k 文章,请原谅博主成为一个无耻的文档搬运工!

l  博主只是一名普通的互联网从业者,不懂修电脑,不会卖电脑,不会帮你盗号,不会破解开机密码,找不回你丢失的手机等,如有这样的想法请绕道!

相关推荐:

由double类型判等引发的一点小思考 一些常用的正则表达式大全
漫画详解什么是HashMap? IT职场:为什么你总是感觉打码很吃力,总是出低级bug?
java经典面试题——HashMap和HashTable有什么不同? 关于各种开源许可证的详解
这又是史上最丧心病狂的大数据时代的IT术语解读😂 简单说说State和Status两个单词的区别

评论区:

    还没有评论哦,赶紧来写评论吧

    分享按钮