深入浅出HashMap扩容死循环问题

一.问题

众所周知,HashMap是线程不安全的,在并发使用HashMap时很容易出现一些问题,其中最典型的就是并发情况下扩容之后会发生死循环,导致CPU占用100%。同时,这也是一个高频面试题。因此,本文通过解读HashMap源码并结合实例,来具体分析HashMap扩容发生的死循环问题。

二.源码解读

下面这段代码是JDK 1.7中HashMap的resize方法,即扩容时调用的代码,作用是创建新的Entry数组newTable,然后调用transfer方法将原来的Entry数组中的节点都转移到newTable中,最后将HashMap的成员变量table指向newTable,所以扩容机制的核心代码在transfer方法中。

    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);
    }

下面这段代码是JDK1.7中HashMap的transfer方法,作用是遍历原来table中每个位置的链表,并对链表中的每个节点重新进行hash,在新的Entry数组newTable中找到归宿,并插入。

    void transfer(Entry[] newTable, boolean rehash) {
        int newCapacity = newTable.length;
        for (Entry<K,V> e : table) {
            //获取链表的头节点e
            while(null != e) {
                //获取要转移的下一个节点next
                Entry<K,V> next = e.next;
                if (rehash) {
                    e.hash = null == e.key ? 0 : hash(e.key);
                }
                //计算要转移的节点在新的Entry数组newTable中的位置
                int i = indexFor(e.hash, newCapacity);
                //使用头插法将要转移的节点插入到newTable原有的单链表中
                e.next = newTable[i];
                //将newTable的hash桶的指针指向要转移的节点
                newTable[i] = e;
               //转移下一个需要转移的节点e
                e = next;
            }
        }
    }

其中,transfer方法的核心代码分为以下四个步骤:
1.\color{red}{Entry<K,V> next = e.next;}获取要转移的下一个节点next;
2.\color{red}{e.next = newTable[i];}使用头插法将要转移的节点插入到newTable原有的单链表中;
3.\color{red}{newTable[i] = e;}将newTable的hash桶的指针指向要转移的节点;
4.\color{red}{e = next;}转移下一个需要转移的节点e。

三.实例分析

1.单线程扩容

假设单线程场景下要对下图中的table进行扩容:


HashMap原来的Entry数组oldTable

扩容初始情况如下:


扩容初始情况

转移A节点之后的情况如下:
转移A节点之后

为了便于理解,简化上图如下:


转移A节点之后

转移B节点之后的情况如下:
转移B节点之后

转移C节点之后,oldTable中的节点就都转移到newTable中了,HashMap成功完成了扩容的过程:
转移C节点之后

观察扩容之前的oldTable中的单链表和扩容之后的newTable中的单链表,不难发现,oldTable中的单链表和newTable中的单链表的节点的顺序是相反的。由于扩容过程中使用头插法将oldTable中的单链表中的节点插入到newTable的单链表中,所以newTable中的单链表会倒置oldTable中的单链表。

2.多线程扩容

假设有两个线程同时对HashMap进行扩容,在某一时刻这两个线程都进行到如下状态:


某一时刻两个线程扩容进行到同一状态

之后线程1执行了transfer方法的核心代码中的第1步和第2步,时间片就用完了,执行后的情况如下:


线程1执行完的情况

这时轮到线程2开始执行,执行transfer方法的核心代码中的第1步之后,情况如下:
线程2执行第1步之后

线程2执行第2,3,4步之后,情况如下:


线程2执行第2,3,4步之后

线程2执行下一轮循环的第1,2,3,4步之后,线程2的扩容过程成功结束:
线程2执行下一轮循环的第1,2,3,4步之后

可以看到,线程2扩容之后的newTable中的单链表形成了一个环,后续执行get操作的时候,会触发死循环,引起CPU的100%问题。

四.总结

通过解读HashMap源码并结合实例可以发现,HashMap扩容导致死循环的主要原因在于扩容过程中使用头插法将oldTable中的单链表中的节点插入到newTable的单链表中,所以newTable中的单链表会倒置oldTable中的单链表。那么在多个线程同时扩容的情况下就可能导致扩容后的HashMap中存在一个有环的单链表,从而导致后续执行get操作的时候,会触发死循环,引起CPU的100%问题。所以一定要避免在并发环境下使用HashMap。


参考:
HashMap扩容死循环问题
老生常谈,HashMap的死循环

©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 211,884评论 6 492
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 90,347评论 3 385
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 157,435评论 0 348
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 56,509评论 1 284
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 65,611评论 6 386
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 49,837评论 1 290
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,987评论 3 408
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 37,730评论 0 267
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 44,194评论 1 303
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,525评论 2 327
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,664评论 1 340
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 34,334评论 4 330
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,944评论 3 313
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,764评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,997评论 1 266
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 46,389评论 2 360
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 43,554评论 2 349

推荐阅读更多精彩内容