HashMap添加元素時發生hash沖突，最大連結清單長度是多少？

疑問：往HashMap添加元素時發生hash沖突，最大連結清單長度是多少？

答案：往HashMap中添加元素時，如果key的hash值都是一樣的情況下，那麼連結清單最大長度可以達到10

HashMap添加元素發生Hash沖突時源碼如下

static final int TREEIFY_THRESHOLD = 8;
           

注意點一：這裡的binCount是從0開始，計算的是添加新元素之前連結清單的長度；TREEIFY_THRESHOLD的常量值為8，if(binCount >= TREEIFY_THRESHOLD - 1) 等價于if(binCount >= 7)，即原連結清單長度達到8時(添加第九個元素時，原連結清單長度就是8)，才會執行treeifyBin()方法

注意點二：執行treeifyBin()方法時，如果數組的大小<64，則會進行擴容，是不會轉為紅黑樹的

 測試代碼：

public class TestHashMap1 {
    
    public static void main(String[] args) {
        HashMap<Object, Object> hasMap = new HashMap<>();
        
        // 重點代碼：
        // 先添加七個元素，由于key的哈希值一樣，是以會形成長度為7的連結清單
        for (int i = 1; i <= 7; i++) {
            hasMap.put(new MyKey("zs_" + i, "age_" + i), "value_" + i);
        }
        
        /**
         * 添加第八個元素
         * 疑問一，添加第八個元素之後，連結清單會轉為紅黑樹嗎？
         * 答案：通過debug查詢執行情況，添加第8個元素時，不會轉為紅黑樹的，也不會執行treeifyBin()方法
         *
         * 執行完該方法後數組長度為16，連結清單長度為8
         */
        hasMap.put(new MyKey("zs_" + 8, "age_" + 8), "value_" + 8);  // 這裡還不會擴容，執行完後連結清單長度為8，數組長度為16
        
        /**
         * 添加第九個元素
         *
         * 執行完該方法後數組長度擴容到32，連結清單長度為9，會執行treeifyBin方法，但是不會将連結清單轉為紅黑樹，因為轉為紅黑樹的條件之一是需要table的長度>=64，是以這裡隻會擴容數組長度
         */
        hasMap.put(new MyKey("zs_" + 9, "age_" + 9), "value_" + 9);  // 執行完該方法後數組擴容到32，連結清單長度為9
        
        /**
         * 添加第十個元素
         *
         * 執行完該方法後數組長度擴容到64，連結清單長度為10，會執行treeifyBin方法，也隻會擴容數組，不會将連結清單轉為紅黑樹
         */
        hasMap.put(new MyKey("zs_" + 10, "age_" + 10), "value_" + 10);
        
        /**
         * 添加第十一個元素，連結清單轉紅黑樹
         * 在該方法運作的過程中，連結清單長度會達到11，但是之後會立馬轉為紅黑樹
         * 執行完該方法後數組長度還是64
         */
        hasMap.put(new MyKey("zs_" + 11, "age_" + 11), "value_" + 11);
        
        /**
         * 添加第十二個元素
         *
         * 往紅黑樹中添加元素
         * 執行完該方法後數組長度還是64
         */
        hasMap.put(new MyKey("zs_" + 12, "age_" + 12), "value_" + 12);
        
        /**
         * 添加第十三個元素
         *
         * 往紅黑樹中添加元素
         * 執行完該方法後數組長度還是64
         */
        hasMap.put(new MyKey("zs_" + 13, "age_" + 13), "value_" + 13);
        
        System.out.println(hasMap.get(new MyKey("zs_1", "age_1")));
    }
    
    /**
     * 自定義key，重寫hashCode方法時，傳回固定值，目的為了往HashMap添加元素時發生哈希沖突
     */
    static class MyKey {
        String name;
        String age;
        
        public MyKey(String name, String age) {
            this.name = name;
            this.age = age;
        }
        
        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            MyKey myKey = (MyKey) o;
            return Objects.equals(name, myKey.name) &&
                Objects.equals(age, myKey.age);
        }
        
        @Override
        public int hashCode() {
            // 傳回固定值
            return 97;
        }
    }
}
           

添加第11個元素時，debug代碼運作效果如下

運作完 p.next = newNode(hash, key, value, null);   檢視長度為11的連結清單

可以看到，HashMap中數組的長度為64，連結清單的長度達到了11，但是會立馬将連結清單轉為紅黑樹

不過執行完如下代碼之後，裡面就變為紅黑樹了

檢視數組存儲的對象,發現已經變為了紅黑樹