Debug HashMap

• 2020 年 7 月 30 日
• 筆記
• Debug集合源碼, Java基礎

最近跟兩個正在找工作的同學聊天，說起集合，都是面試的重災區，必問的選項，而且在實際的面試中並不會單獨提問某一個問題，而是圍繞核心知識連環炮提問。所以背面試題治標不治本，還是得讀一讀源碼。誰讓這是個面試造火箭，工作擰螺絲的市場氛圍，就連CSDN的首頁第二張輪播圖都在蹭這個熱點：

本文主要包括兩部分：

• HashMap面試必問（總結了一些常見面試題）

• JDK1.7 & JDK1.8 關於HashMap原理分析

  這部分主要是通過斷點debug來分析HashMap中常見操作的過程，但由於步驟繁多，只記錄了關鍵步驟，建議讀者也在自己電腦上debug一遍，了解詳細流程。（計算機是一門實踐性很強的學科，看的再多也不如自己親自操作一遍，當然理論也同樣重要）

長文警告！！！

1，HashMap面試必問

這是筆者在一篇博客中找出來的，很有代表性，實際的面試提問中不會按部就班的問，而是千變萬化，所以除了把面試題背住之外，一定要花點時間看看源碼具體實現，雖然不會360度無死角，但對源碼總體有個大概的把握，回答起來就知道哪些知道哪些不知道，一來方便查漏補缺，二來也能更加靈活的回答問題。

示例性提問（真實場景下）：

• 你看過JDK的源碼嗎？

  看過。

• HashMap是如何通過put添加元素的？

  根據key計算hash值，再將hash值轉換為數組下標。

• 底層數組默認的長度為多少？

  默認為16。

• 什麼時候會觸發擴容機制？

  元素個數超過閾值就會觸發擴容機制，並且是在新增元素髮生hash衝突的情況下。

• 擴容時，直接將數據從原數組平移到新數組可以嗎？

  不行，需要重新計算hash值（更正，是重新計算index值，而不是重新計算hash值，hash值只與key相關，index與table.length相關）

• 為什麼需要重新計算hash值？

  因為數組擴容了，從hash值轉換為數組下標這個過程就發生了變化，同時，獲取value這個過程也會發生變化。所以必須重新計算，不然之前保存的元素就無法訪問。

一般性問題（建議背住，而後融會貫通）：

• 什麼是HashMap？

  HashMap是基於Map接口的實現，主要用於存儲鍵值對（1.7通過Entry對象封裝鍵值對，1.8通過Node封裝鍵值對）

• HashMap採用了什麼數據結構？

  1.7：數組+鏈表

  1.8：數組+鏈表+紅黑樹

• HashMap是如何解決hash衝突的問題的？

  鏈表。

• hash衝突和index衝突的關係？

  hash衝突就會導致index衝突，indexFor方法的兩個參數一個是hash值，另外一個是table.length。

• HashMap的put方法是如何實現的？

  先通過key計算hash值，再通過indexFor方法轉換為數組下標。

• HashMap的擴容機制是什麼樣的？

  HashMap默認初始容量為16，加載因子為0.75，實際存儲大小為12。hashMap容量達到12並且當前加入的元素產生hash衝突時時，進行初始容量的2倍擴容

  • 為什麼初始容量為16？

    HashMap重寫的hash採用的是位運算，目的是使key到index的映射分佈更加均勻

    	static final int hash(Object key) {
            int h;
            return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
        }
        
        也解釋了為什麼hash允許空值，實際上當key為null時，自動轉換為0
    

• 為什麼鏈表使用頭插法?

  HashMap的發明者認為，後插入的Entry被查找的可能性更大。

• hashMap中的鏈表是單鏈表還是雙鏈表？

  單鏈表

   		final int hash;
          final K key;
          V value;
          Node<K,V> next;
  

• 擴容閾值threshold被賦值了幾次？

  • 調用構造函數被賦值，初始化容量大小（默認為16）
  • 數組為空，初始化數組時，被賦值為初始化容量*加載因子（默認為12）

• hash衝突插入鏈表的方式？

  1.7：採用頭插法：作者認為，後插入的會被優先訪問

  1.8：採用尾插法：避免鏈表死循環

• hashMap允許key為null值嗎？

  允許一個key為null，會轉換為數組下標0。當出現第二個key為null，其value會自動覆蓋第一個null的值。

• hashMap中鏈表過長會導致什麼問題？

  查詢效率降低。時間複雜度為O(n)【需要遍歷鏈表】

• jdk7中的HashMap存在哪些問題？

  • 鏈表過長導致查詢效率降低

  • 擴容導致的死循環

  • 線程不安全（個人認為這不是問題，而是在設計上就沒有考慮這個，線程安全就會導致效率降低，本質上是效率和安全之間的取捨）

• jdk7和jdk8處理hash衝突的區別？為什麼？

  jdk7計算hash值的運算是非常複雜的，因為如果產生了hash衝突是用鏈表來進行存儲的，效率比較慢，所以在設計上要儘可能避免衝突。

  jdk8計算hash值的方法相對簡單，因為採用了紅黑樹的結構，即使發生了hash衝突，也可以通過轉換為紅黑樹來提高效率。

• 為什麼加載因子是0.75而不是其他值？

  因為加載因子參與indexFor數組下標的計算，return h & (length-1);

  其數值會影響index是否發生衝突，同時也會影響空間利用率，默認情況下table長度為16，但只能存12個值。

  所以這個加載因子是在index衝突和空間利用率之間尋求的一個平衡點。

• HashMap是否可以存放自定義對象？

  可以，因為HashMap使用了泛型。

• 為什麼JDK8引入紅黑樹？

  由於hash衝突導致鏈表查詢非常慢，時間複雜度為O（n），引入紅黑樹後鏈表長度為8時會自動轉換為紅黑樹，以提高查詢效率O(logn)。

• Java集合中ArrayList，LinkedList，HashMap的時間複雜度分別為多少？

  ArrayList基於數組實現，基於下標查詢的話時間複雜度為O(1)，如果基於內容查找需要遍歷的話，時間複雜度為O(n)。

  LinkedList基於鏈表實現，查詢效率為O(n)

  HashMap在不考慮Hash衝突沒有形成鏈表的情況下時間複雜度為O(1)，形成鏈表後時間複雜度為O(n)

2，Debug源碼的心得體會

【關注核心步驟，選擇性忽略】

JDK是一個相當龐大的系統，把所有的類和原理全部弄清楚是相當有難度的，所以在debug源碼的時候，如果遇見了不相關的類，忽略就是了。

然而單看HashMap源碼（2300行）也是一個較為龐大的代碼量，所以對其中不重要或者不常用的方法，最好先選擇性忽略。比如計算hash值的各種位運算，研究起來還是得廢一些功夫的，這個可以在把握了HashMap的大致框架後再做精細化的研究。

總的來說，先重點關注核心步驟，選擇性忽略更加具體的實現，逐個擊破，從而提高閱讀效率。

ps：建議把1.7和1.8的jdk都裝上，切換着分析。

3，JDK 1.7

3.1 用debug分析一個元素是如何加入到HashMap中的【jdk1.7】

創建一個Main.java類

 		HashMap<String,String> hashMap = new HashMap<>(16);
        
        hashMap.put("x","x");
        hashMap.put("y","y");

在創建HashMap對象上打上斷點：

debug運行，強制進入方法內部（Alt+Shift+F7）：

調用構造函數：

this方法，初始值判空異常（初始值不能小於0大於最大值），加載因子判空異常，

threshold被初始化容量賦值（threshold為擴容閾值）

在插入第一個元素上打上斷點：

debug運行，強制進入方法內部（Alt+Shift+F7）：

	public V put(K key, V value) {
		//判斷數組是否為空，如果為空進行初始化，inflateTable初始化方法見下文①
		//threshold：擴容的閾值（當前元素個數超過這個數值就會進行擴容）
        if (table == EMPTY_TABLE) {
            inflateTable(threshold);
        }
        
        //判斷key是否為空
        if (key == null)
        	//hashMap處理空值的方法②
            return putForNullKey(value);
            
        //計算key的hash值（主要是各種位運算）
        int hash = hash(key);
        
        //i就是將key的hash值再進行一次轉換得出的數組下標
        int i = indexFor(hash, table.length);
        //同樣是個處理hash衝突的頭插算法
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }

        modCount++;
        
        //添加元素③
        addEntry(hash, key, value, i);
        return null;
    }

①inflateTable初始化容量方法：

private void inflateTable(int toSize) {
        //向上舍入為2的冪
        int capacity = roundUpToPowerOf2(toSize);

	    //重點：threshold在初始化構造函數時默認為16，在初始化數組時，乘以加載因子被二次賦值
        threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
        //初始化數組容量
        table = new Entry[capacity];
        initHashSeedAsNeeded(capacity);
    }

②hashMap處理空值的方法

private V putForNullKey(V value) {

		//處理key為null值的hash衝突，採用頭插法（null會自動轉為0）
        for (Entry<K,V> e = table[0]; e != null; e = e.next) {
            if (e.key == null) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
        modCount++;
        addEntry(0, null, value, 0);
        return null;
    }

③addEntry添加元素

void addEntry(int hash, K key, V value, int bucketIndex) {
		//hash擴容（size代表元素個數，如果元素大於threshold【默認是12】，則會進行擴容）
        if ((size >= threshold) && (null != table[bucketIndex])) {
            resize(2 * table.length);
            hash = (null != key) ? hash(key) : 0;
            bucketIndex = indexFor(hash, table.length);
        }
		//④
        createEntry(hash, key, value, bucketIndex);
    }

④

void createEntry(int hash, K key, V value, int bucketIndex) {

		//bucketIndex就是put方法中計算出的數組下標i
		//難點：如果未發生hash衝突，table[bucketIndex]則為空，e也為空，table[bucketIndex]等於最新插入的元素
		//如果發生了hash衝突，也就是table[bucketIndex]並不為空，table[bucketIndex]就頭插到鏈表中
        Entry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<>(hash, key, value, e);
        size++;
    }

3.2 用debug分析HashMap是如何get到一個元素的【jdk1.7】

還是先編寫測試用例：

ps：測試的代碼都不複雜，關鍵是要關注底層是如何實現的

  		HashMap<String,String> hashMap = new HashMap<String, String>(3);

        hashMap.put("x","x");
        hashMap.put("y","y");
        hashMap.put("z","z");
        hashMap.get("z");

打上斷點：

debug運行，強制進入方法內部（Alt+Shift+F7）：

public V get(Object key) {
        if (key == null)     //判空
            return getForNullKey();
        Entry<K,V> entry = getEntry(key);  

		//判空，否則返回value
        return null == entry ? null : entry.getValue();
    }

final Entry<K,V> getEntry(Object key) {
		//判斷數組是否為空
        if (size == 0) {
            return null;
        }

		//判斷key是否為空，為空則返回0，否則計算hash值
        int hash = (key == null) ? 0 : hash(key);
        
        //遍歷鏈表，獲取Entry對象
        for (Entry<K,V> e = table[indexFor(hash, table.length)];e != null;e = e.next) {
            Object k;
            
            //核心：hash相等並且key相等才能返回entry，否則繼續遍歷
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k))))
                return e;
        }
        return null;
    }

3.3 用debug分析HashMap是如何擴容的？【jdk1.7】

編寫測試用例：給的初始值為3，根據2的冪計算，HashMap初始化容量為4，擴容閾值為3，也就是在執行 hashMap.put(“m”,”n”);時會發生擴容：

		HashMap<String,String> hashMap = new HashMap<String, String>(3);

        hashMap.put("x","x");
        hashMap.put("y","y");
        hashMap.put("z","z");
        hashMap.put("m","n");

打上斷點：

debug運行，強制進入方法內部（Alt+Shift+F7）：

判斷數組是否為空。false

。。。（此處省去一些步驟）

運行到addEntry方法對size和threshold進行判斷，此時size為3，滿足條件。(ps：除了當前大小大於等於閾值之外，當前元素計算出的數組下標也必須與之前的元素產生hash衝突才能擴容)

【坑點】：size是元素總個數，而不是數組佔用個數，比如只佔用了一個數組位置，但是鏈表長12，還是會擴容，其目的是使得hash分佈的更均勻

resize方法對數組table進行兩倍擴容，當前table.length = 4.

resize方法：

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

⑤將數據移至新數組

/**
     * 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;
            }
        }
    }

3.4 HashMap 1.7 中多線程下擴容的死循環問題

問題描述：jdk1.7在多線程並發的情況下會由於鏈表的頭插法導致擴容的死循環問題，在1.8中已經被解決。

問題代碼：

void transfer(Entry[] newTable, boolean rehash) {
        int newCapacity = newTable.length;
        
        //table是全局變量，多線程的情況下，由於沒有任何鎖的機制，多個線程可以同時獲取到table
        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);
                }
                //重新計算hash值
                int i = indexFor(e.hash, newCapacity);
                //頭插法插入鏈表
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            }
        }
    }

圖片描述：假設有A，B，C，D四個元素組成的鏈表，在擴容的時候，遍歷鏈表A最先被移過去，其次是B，C，D，假設在進行擴容前，同時有兩個線程獲取到了全局變量table，T1線程擴容進行到了如圖所示的步驟，正準備移動D過去。T2線程此時獲取到的table的仍然擴容前的指向。所以T2讀取到的table可能是A指向B，B同時指向A，這種情況下，遍歷鏈表就會導致死循環。

			   e.next = newTable[i];
                newTable[i] = e;
                e = next;
                
                一個元素的移動過程（index衝突），newTable[i]是已經移到新table中的數組下標對應的元素，如下圖所示，C這個時候就是newTable[i],e
               就是D，那麼過程就是D指向了C，然後把e也就是D元素賦給newTable[i]，此時這個鏈表的頭結點就是D。最後一行代碼相當與e = e.next。繼續遍歷鏈表。

4，JDK1.8

1.8相對於1.7有很多改進，比如採用了新的數據結構紅黑樹，鏈表改為尾插法等等。相對來說，1.8的代碼量較1.7更多，故下文會部分省略代碼，只展示程序運行過的步驟。

4.1 用debug分析第一個元素是如何加入到HashMap中的【jdk1.8】

切換到jdk1.8，繼續debug

計算hash函數：hash(key)，1.8中同樣允許null值，會自動轉換為0

jdk1.7中計算hash的方法
final int hash(Object k) {
        int h = hashSeed;
        if (0 != h && k instanceof String) {
            return sun.misc.Hashing.stringHash32((String) k);
        }
        h ^= k.hashCode();
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

jdk1.8中計算hash的方法
static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
    
jdk1.7中計算hash值的方法相對比較複雜，主要是因為要儘可能的避免hash衝突，因為鏈表的遍歷是很慢的。但jdk1.8中因為引入了紅黑樹，即使hash衝突很高，也可以通過轉換紅黑樹來提高查詢效率。（所以hash的運算就相對簡單，畢竟運算也是要耗費資源的）

核心方法：putVal：由於分支過多，部分注釋在下文中補充

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        
        //初始化擴容 ，resize方法見下文
        if ((tab = table) == null || (n = tab.length) == 0)
       		//n為擴容後的容量，本次情況下為4，上文中HashMap的初始化容量設為3，根據hashMap規則，容量只能為2^n
            n = (tab = resize()).length;
        //&優先級高於=，看了半天沒明白啥意思，1.7中將hash轉換為index的過程用indexFor方法封裝起來了，其實是一樣的：h&(length-1)
        //如果當前位置是空的，直接賦值給數組
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
         //這裡包括轉換為鏈表或紅黑樹，下文再分析
        else {
            **************
        }
        //修改次數+1
        ++modCount;
        
        //若當前size+1後的值大於擴容閾值，執行擴容
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

//hashMap擴容方法
final Node<K,V>[] resize() {
		//獲取到當前table，table是全局變量
        Node<K,V>[] oldTab = table;
        //計算當前table的長度
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        //獲取當前擴容閾值（threshold=capacity*loadFactor）
        int oldThr = threshold;
        //初始化新的容量和擴容閾值
        int newCap, newThr = 0;
        if (oldCap > 0) {
        //若當前容量大於最大容量(10億多)
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            //左移運算符優先級高於賦值運算符，左移1位相當於乘以2，newCap相當於舊容量2倍擴容
            //另外一個判斷條件：當前容量大於默認容量16
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                     //新的擴容閾值翻倍
                newThr = oldThr << 1; // double threshold
        }
        //若當前擴容閾值大於0
        else if (oldThr > 0) // initial capacity was placed in threshold
        //將當前擴容閾值賦值給新容量
            newCap = oldThr;
            
        //若當前容量為0且擴容閾值為0，這種情況是在沒有給hashmap任何初始值的時候發生的
        else {               // zero initial threshold signifies using defaults
            //默認容量為16
            newCap = DEFAULT_INITIAL_CAPACITY;
            //默認的擴容閾值為默認的負載因子乘以默認初始化容量
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        //若新的擴容閾值為0
        if (newThr == 0) {
        	//計算新的擴容閾值：在新容量小於最大容量且計算後的擴容閾值小於最大容量的情況下，新的擴容閾值為新容量乘以負載因子，否則為最大容量
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        //賦值給擴容閾值
        threshold = newThr;
        @SuppressWarnings({"rawtypes","unchecked"})
   		//初始化一個新的鍵值對數組，初始化新的容量
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        賦值給全局變量table
        table = newTab;
        
        //在為空初始化容量時，並不會進入分支，下文再補充注釋
        if (oldTab != null) {
            *******
        }
        //返回新的鍵值對數組
        return newTab;
    }

ps：1.8中使用Node代替Entry，換了個名，然後hash加上了final修飾

4.2 用debug分析HashMap擴容情況【jdk1.8】

測試用例如下：HashMap的初始容量給到3，實際容量為4，擴容閾值為3，在添加第四個元素的時候進行擴容

進入方法內部：

重點關注putVal方法：

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        //table為空時初始化的擴容操作
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
            
        //若當前數組下標並未有元素，直接賦值
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
            
            //形成鏈表
        else {
        
            Node<K,V> e; K k;
            //若key衝突，直接替換value（key相同，hash值一定相同）
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            //判斷是否形成紅黑樹
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
                
            //判斷是否形成鏈表
            else {
            	//遍歷當前table[i]所在的鏈表
                for (int binCount = 0; ; ++binCount) {
                *******
                }
            }
        }
        ++modCount;
        //當前size為3，加1後大於擴容閾值，進行擴容操作
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

resize（）擴容：

final Node<K,V>[] resize() {
		//獲取到當前table，table是全局變量
        Node<K,V>[] oldTab = table;
        //計算當前table的長度
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        //獲取當前擴容閾值（threshold=capacity*loadFactor）
        int oldThr = threshold;
        //初始化新的容量和擴容閾值
        int newCap, newThr = 0;
        if (oldCap > 0) {
        //若當前容量大於最大容量(10億多)
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            //左移運算符優先級高於賦值運算符，左移1位相當於乘以2，newCap相當於舊容量2倍擴容
            //另外一個判斷條件：當前容量大於默認容量16
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                     //新的擴容閾值翻倍
                newThr = oldThr << 1; // double threshold
        }
        //若當前擴容閾值大於0
        else if (oldThr > 0) // initial capacity was placed in threshold
        //將當前擴容閾值賦值給新容量
            newCap = oldThr;
            
        //若當前容量為0且擴容閾值為0，這種情況是在沒有給hashmap任何初始值的時候發生的
        else {               // zero initial threshold signifies using defaults
            //默認容量為16
            newCap = DEFAULT_INITIAL_CAPACITY;
            //默認的擴容閾值為默認的負載因子乘以默認初始化容量
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        //若新的擴容閾值為0
        if (newThr == 0) {
        	//計算新的擴容閾值：在新容量小於最大容量且計算後的擴容閾值小於最大容量的情況下，新的擴容閾值為新容量乘以負載因子，否則為最大容量
            float ft = (float)newCap * loadFactor;
            
            //此時新的擴容閾值為6，容量為8
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        //賦值給擴容閾值
        threshold = newThr;
        @SuppressWarnings({"rawtypes","unchecked"})
   		//初始化一個新的鍵值對數組，初始化新的容量
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        賦值給全局變量table
        table = newTab;
        
        //上文補充，此時舊數組並不為空 ***************************************************************************//
         if (oldTab != null) {
         	//遍歷舊數組，遍歷計算下標放入新數組中
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                //null會直接轉化為0，所以不需要計算
                if ((e = oldTab[j]) != null) {
                	//舊數組置空
                    oldTab[j] = null;
                    //判斷當前節點是否形成了鏈表，若未形成鏈表，計算下標將節點重新賦值給數組
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;
                    //判斷是否為紅黑樹節點
                    else if (e instanceof TreeNode)
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else { // preserve order
                    
                    //為鏈表節點，需要進行重hash分佈（就是數組下標的重新計算，一天天的，就不整個人話）
                        Node<K,V> loHead = null, loTail = null;   //用於數組下標為0的節點
                        Node<K,V> hiHead = null, hiTail = null;   //用於數組下標發生變化的節點
                        Node<K,V> next;
                        do {
                            next = e.next;
                            //將當前元素的hash值與老表的容量進行與運算，相當於計算數組下標，若等於0，則擴容後的下標仍然是0
                            if ((e.hash & oldCap) == 0) {
                            	//若loTail為空，表示該節點為鏈表上的第一個節點（loTail表示鏈表尾），將節點賦給loHead
                                if (loTail == null)
                                    loHead = e;
                               //若loTail不為空，表示當前節點並非是鏈表的第一個節點，可將e賦給鏈表尾loTail的下一個指向，此時表尾lotail後連接的是e
                                else
                                    loTail.next = e;
                                    
                                //將e賦給鏈表尾，1.8中使用了尾插法，而1.7中使用的是頭插法
                                loTail = e;
                            }
                            //處理數組下標非0的節點
                            else {
                            //同理：使用尾插法連接節點
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);    //這個循環就是遍歷鏈表，直到下一個為null
                        
                        //如果loTail不為空，說明老數組中的數組下標在新數組中也有使用
                        if (loTail != null) {
                        	//將鏈表尾的下一個指向置為空
                            loTail.next = null;
                            //將鏈表頭賦值給新數組的元素
                            newTab[j] = loHead;
                        }
                        
                        //如果hiTail不為空，說明這是非0的數組下標，
                        if (hiTail != null) {
                        	//將鏈表尾的下一個指向置為空
                            hiTail.next = null;
                            //新數組下標為原來的數組下標+舊容量（666）
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        //返回新的鍵值對數組
        return newTab;
    }

4.3 用debug分析鏈表的形成過程【jdk1.8】

編寫測試用例，（？？？如何模擬更多的hash衝突？？？）

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        //table為空時初始化的擴容操作
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
            
        //若當前數組下標並未有元素，直接賦值
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
            
        //形成鏈表**************************************************
        else {
      
            Node<K,V> e; K k;
            //若key衝突，直接替換value（key相同，hash值一定相同）
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            //判斷是否形成紅黑樹
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
                
            //排除了key覆蓋和紅黑樹，剩下的就是鏈表了
            else {
            	//遍歷當前table[i]所在的鏈表
                for (int binCount = 0; ; ++binCount) {
                	//若鏈表當前節點的下一個節點為空，說明已到鏈表尾，break退出循環
                    if ((e = p.next) == null) {
                    	//退出循環前，把新元素加到鏈表尾部
                        p.next = newNode(hash, key, value, null);
                        //若鏈表節點數量大於等於8，轉換為紅黑樹（binCount從0開始計算，到7的時候已經是第8節點了）
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
         
        }
        ++modCount;
        //當前size為3，加1後大於擴容閾值，進行擴容操作
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

4.4 用debug分析get元素的過程【jdk1.8】

getNode()

final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
            
            //判斷第一個節點的hash值和key是否相等，若相等，直接返回，否則進入鏈表遍歷
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            //遍歷鏈表
            if ((e = first.next) != null) {
            	//判斷鏈表是否形成了紅黑樹
                if (first instanceof TreeNode)
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                //若未形成紅黑樹，則挨個遍歷
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

4.5 用debug分析刪除元素的過程【jdk1.8】

removeNode（）

final Node<K,V> removeNode(int hash, Object key, Object value,
                               boolean matchValue, boolean movable) {
        Node<K,V>[] tab; Node<K,V> p; int n, index;
        //一個if看得都費勁，p節點是根據hash和key計算出的待刪除的節點
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (p = tab[index = (n - 1) & hash]) != null) {
            Node<K,V> node = null, e; K k; V v;
            //若p的hash和key都吻合，直接賦值節點node
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                node = p;
                
            //說明p所在節點為一個鏈表
            else if ((e = p.next) != null) {
            	//判斷鏈表是否轉換成了紅黑樹
                if (p instanceof TreeNode)
                    node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
                //若未轉換為紅黑樹，則遍歷鏈表，直到key和hash都吻合，賦值給node
                else {
                    do {
                        if (e.hash == hash &&
                            ((k = e.key) == key ||
                             (key != null && key.equals(k)))) {
                            node = e;
                            break;
                        }
                        p = e;
                    } while ((e = e.next) != null);
                }
            }
            
            //刪除node
            if (node != null && (!matchValue || (v = node.value) == value ||
                                 (value != null && value.equals(v)))) {
               //判斷node是否為紅黑樹節點
                if (node instanceof TreeNode)
                    ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
                //判斷node節點是否為鏈表的第一個節點，若是，將當前鏈表的下一個節點指向賦給數組
                else if (node == p)
                    tab[index] = node.next;
                //最後一種情況就是node節點在鏈表中間，將頭節點的下一個節點指向node的下一個節點。
                else
                    p.next = node.next;
                ++modCount;
                --size;
                afterNodeRemoval(node);
                //返回node
                return node;
            }
        }
        return null;
    }

get和remove的思路

兩者大體思路相同，先根據傳入的key計算hash，再依次通過：第一個元素是否命中，鏈表是否為紅黑樹，遍歷鏈表的思路尋找對應的節點元素刪除或返回。

4.6 關於紅黑樹。核心就是自平衡！

紅黑樹基於二叉查找樹實現，在此基礎上做了優化。

二叉查找樹又稱二叉搜索樹，二叉排序樹

關鍵規則如下：左子樹的值=<根節點=<右子樹的值，左右子樹遵守同樣的規則

二叉查找樹的平衡問題：

紅黑樹的核心功能就是自平衡。

紅黑樹的規則：

• 節點為紅色或黑色

• 根節點是黑色

• 葉子節點（NIL）是黑色

• 如果一個節點是紅色的，則它的子節點必須是黑色的。

• 任一節點到其子樹的葉子節點的路徑都包含相同的黑色節點

新插入的節點是這樣的：

若向當前樹中插入14，則為：並不會引起紅黑樹的變化

但若插入節點為21：違反了紅黑樹的紅色節點的子節點都為黑色

與規則發生衝突時，紅黑樹需要進行調整，調整有兩種方式：變色和自旋（自旋又分為左旋和右旋）

變色：比如新添加一個紅色節點到一個紅色節點下就會產生變色的情況。

左旋：當前節點變為左節點，當前節點的右節點變為父節點（把右節點的子樹的左節點往左子樹挪）

右旋：當前節點變為右節點，當前節點的左節點變為父節點（把左節點的子樹的右節點往右子樹挪）

4.7 hashMap樹化原理

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
                
            //若當前已經是紅黑樹，直接向樹中添加元素
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        //若鏈表長度大於8，轉換為紅黑樹
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

樹化方法 treeifyBin(tab, hash);

final void treeifyBin(Node<K,V>[] tab, int hash) {
        int n, index; Node<K,V> e;
        
        //若table為空或者tab的長度小於樹化最小長度，優先擴容
        if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
            resize();
            
        //獲取當前鏈表的位置
        else if ((e = tab[index = (n - 1) & hash]) != null) {
            TreeNode<K,V> hd = null, tl = null;   //定義紅黑樹的頭結點和尾結點
            //遍歷鏈表，最終結果：hd為表頭，tl為表尾
            do {
                TreeNode<K,V> p = replacementTreeNode(e, null);
                if (tl == null)
                    hd = p;
                else {
                    p.prev = tl;
                    tl.next = p;
                }
                tl = p;
            } while ((e = e.next) != null);
            //將hd賦給數組
            if ((tab[index] = hd) != null)
            	//樹化方法
                hd.treeify(tab);
        }
    }

treeify

final void treeify(Node<K,V>[] tab) {
            TreeNode<K,V> root = null;
            //遍歷鏈表，this在第一次循環代表hd
            for (TreeNode<K,V> x = this, next; x != null; x = next) {
                next = (TreeNode<K,V>)x.next;
                x.left = x.right = null;
                //初始化根節點
                if (root == null) {
                    x.parent = null;
                    x.red = false;
                    root = x;
                }
                else {
                    K k = x.key;
                    int h = x.hash;
                    Class<?> kc = null;
                    //遍歷根節點
                    for (TreeNode<K,V> p = root;;) {
                        int dir, ph;
                        K pk = p.key;
                        if ((ph = p.hash) > h)
                            dir = -1;   //為p的左子樹
                        else if (ph < h)
                            dir = 1;   //為p的右子樹
                        else if ((kc == null &&
                                  (kc = comparableClassFor(k)) == null) ||
                                 (dir = compareComparables(kc, k, pk)) == 0)
                            dir = tieBreakOrder(k, pk);

                        TreeNode<K,V> xp = p;
                        //判斷p的子樹是否為空（賦值和判斷同時進行，666），若不為空，則在其子樹下繼續循環。最後到達葉子節點，插入節點
                        if ((p = (dir <= 0) ? p.left : p.right) == null) {
                            x.parent = xp;
                            if (dir <= 0)
                                xp.left = x;
                            else
                                xp.right = x;
                            root = balanceInsertion(root, x); //自平衡
                            break;
                        }
                    }
                }
            }
            moveRootToFront(tab, root);
        }

本文篇幅已經過長，關於紅黑樹，之後會專門寫一篇文章研究1.8中的實現。