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，但是会立马将链表转为红黑树

不过执行完如下代码之后，里面就变为红黑树了

查看数组存储的对象,发现已经变为了红黑树