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

前言：

在 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，接著下一輪回圈，

從 b 開始下一輪回圈，重復 1、2、3，注意此時 e 是 b 了，而 newTable[i] 的值已經不是空了，已經是 a 了，所以 1，2，3 行代碼執行下來，b 就會插入到 a 的前面，如下圖 3 的位置：

重點來了，假設執行緒 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 是如何保證執行緒安全的么？想要學習跟多的Java后端、架構知識嗎？我這整理有大量的學習資料，有需要的可以點擊進入，暗號：csll，大量的資料免費領取！

Java各方面的面試題資料

Java學習資料，資料很多，這只是其中一點，

最后祝大家都能作業順利，有需要上述資料的可以點擊進入，暗號：csll