為了賬號安全,請及時綁定郵箱和手機立即綁定

大多數人不知道的:HashMap鏈表成環的原因和解決方案

2019.09.10 10:34 7531瀏覽

引導語

在 JDK7 版本下,很多人都知道 HashMap 會有鏈表成環的問題,但大多數人只知道,是多線程引起的,至于具體細節的原因,和 JDK8 中如何解決這個問題,很少有人說的清楚,百度也幾乎看不懂,本文就和大家聊清楚兩個問題:1:JDK7 中 HashMap 成環原因,2:JDK8 中是如何解決的。

JDK7 中 HashMap 成環原因

成環的時機

1:HashMap 擴容時。
2:多線程環境下。

成環的具體代碼位置

在擴容的 transfer 方法里面,有三行關鍵的代碼,如下:

    void transfer(Entry[] newTable, boolean rehash) {
        int newCapacity = newTable.length;
        for (Entry<K,V> e : table) {
            //e為空時循環結束
            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;
            }
        }
    }

假設原來在數組 1 的下標位置有個鏈表,鏈表元素是 a->b->null,現在有兩個線程同時執行這個方法,我們先來根據線程 1 的執行情況來分別分析下這三行代碼:

  1. e.next = newTable[i];
    newTable 表示新的數組,newTable[i] 表示新數組下標為 i 的值,第一次循環的時候為 null,e 表示原來鏈表位置的頭一個元素,是 a,e.next 是 b,
    e.next = newTable[i] 的意思就是拿出 a 來,并且使 a 的后一個節點是 null,如下圖 1 的位置:
    圖片描述

  2. newTable[i] = e;
    就是把 a 賦值給新數組下標為 1 的地方,如下圖 2 的位置:
    圖片描述

  3. e = next;
    next 的值在 while 循環一開始就有了,為:Entry<K,V> next = e.next; 在此處 next 的值就是 b,把 b 賦值給 e,接著下一輪循環。

  4. 從 b 開始下一輪循環,重復 1、2、3,注意此時 e 是 b 了,而 newTable[i] 的值已經不是空了,已經是 a 了,所以 1,2,3 行代碼執行下來,b 就會插入到 a 的前面,如下圖 3 的位置:
    圖片描述
    這個就是線程 1 的插入節奏。

重點來了,假設線程 1 執行到現在的時候,線程 2 也開始執行,線程 2 是從 a 開始執行 1、2、3、4 步,此時數組上面鏈表已經形成了 b->a->null,線程 2 拿出 a 再次執行 1、2、3、4,就會把 a 放到 b 的前面,大家可以想象一下,結果是如下圖的:
圖片描述
從圖中可以看出,有兩個相同的 a 和兩個相同的 b,這就是大家說的成環,自己經過不斷 next 最終指向自己。

注意?。?!這種解釋看似好像很有道理,但實際上是不正確的,網上很多這種解釋,這種解釋最致命的地方在于 newTable 不是共享的,線程 2 是無法在線程 1 newTable 的基礎上再進行遷移數據的,1、2、3 都沒有問題,但 4 有問題,最后的結論也是有問題的

因為 newTable 是在擴容方法中新建的局部變量,方法的局部變量線程之間肯定是無法共享的,所以以上解釋是有問題的,是錯誤的。

那么真正的問題出現在那里呢,其實線程 1 完成 1、2、3、4 步后就出現問題了,如下圖:
圖片描述

總結一下產生這個問題的原因:

  1. 插入的時候和平時我們追加到尾部的思路是不一致的,是鏈表的頭結點開始循環插入,導致插入的順序和原來鏈表的順序相反的。
  2. table 是共享的,table 里面的元素也是共享的,while 循環都直接修改 table 里面的元素的 next 指向,導致指向混亂。

接下來我們來看下 JDK8 是怎么解決這個問題。

JDK8 中解決方案

JDK 8 中擴容時,已經沒有 JDK7 中的 transfer 方法了,而是自己重新寫了擴容方法,叫做 resize,鏈表從老數組拷貝到新數組時的代碼如下:

                    //規避了8版本以下的成環問題
                    else { // preserve order
                        // loHead 表示老值,老值的意思是擴容后,該鏈表中計算出索引位置不變的元素
                        // hiHead 表示新值,新值的意思是擴容后,計算出索引位置發生變化的元素
                        // 舉個例子,數組大小是 8 ,在數組索引位置是 1 的地方掛著一個鏈表,鏈表有兩個值,兩個值的 hashcode 分別是是9和33。
                        // 當數組發生擴容時,新數組的大小是 16,此時 hashcode 是 33 的值計算出來的數組索引位置仍然是 1,我們稱為老值
                        // hashcode 是 9 的值計算出來的數組索引位置是 9,就發生了變化,我們稱為新值。
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        // java 7 是在 while 循環里面,單個計算好數組索引位置后,單個的插入數組中,在多線程情況下,會有成環問題
                        // java 8 是等鏈表整個 while 循環結束后,才給數組賦值,所以多線程情況下,也不會成環
                        do {
                            next = e.next;
                            // (e.hash & oldCap) == 0 表示老值鏈表
                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            // (e.hash & oldCap) == 0 表示新值鏈表
                            else {
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        // 老值鏈表賦值給原來的數組索引位置
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        // 新值鏈表賦值到新的數組索引位置
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }

解決辦法其實代碼中的注釋已經說的很清楚了,我們總結一下:

  1. JDK8 是等鏈表整個 while 循環結束后,才給數組賦值,此時使用局部變量 loHead 和 hiHead 來保存鏈表的值,因為是局部變量,所以多線程的情況下,肯定是沒有問題的。

  2. 為什么有 loHead 和 hiHead 兩個新老值來保存鏈表呢,主要是因為擴容后,鏈表中的元素的索引位置是可能發生變化的,代碼注釋中舉了一個例子:
    數組大小是 8 ,在數組索引位置是 1 的地方掛著一個鏈表,鏈表有兩個值,兩個值的 hashcode 分別是是 9 和 33。當數組發生擴容時,新數組的大小是 16,此時 hashcode 是 33 的值計算出來的數組索引位置仍然是 1,我們稱為老值(loHead),而 hashcode 是 9 的值計算出來的數組索引位置卻是 9,不是 1 了,索引位置就發生了變化,我們稱為新值(hiHead)。
    大家可以仔細看一下這幾行代碼,非常巧妙。

總結

本文主要分析了 HashMap 鏈表成環的原因和解決方案,你學會了嗎?
想知道 HashMap 底層數據結構是什么樣的么?想了解 ConcurrentHashMap 是如何保證線程安全的么?想閱讀更多 JUC 的源碼么,請關注我的新課:面試官系統精講Java源碼及大廠真題,帶你一起閱讀 Java 核心源碼,了解更多使用場景,為升職加薪做好準備。

點擊查看更多內容

本文原創發布于慕課網 ,轉載請注明出處,謝謝合作

8人點贊

若覺得本文不錯,就分享一下吧!

評論

相關文章推薦

正在加載中
意見反饋 幫助中心 APP下載
官方微信

舉報

0/150
提交
取消
开奖号码