HashMap底層數據結構之鏈表轉紅黑樹的具體時機

前言

本文從三個部分去探究HashMap的鏈表轉紅黑樹的具體時機：

1、從HashMap中有關“鏈表轉紅黑樹”閾值的聲明；
2、【重點】解析HashMap.put(K key, V value)的源碼；
3、測試；

一、從HashMap中有關“鏈表轉紅黑樹”閾值的聲明，簡單了解HashMap的鏈表轉紅黑樹的時機

HashMap中有關“鏈表轉紅黑樹”閾值的聲明：

/**
    *  使用紅黑樹(而不是鏈表)來存放元素。當向至少具有這么多節點的鏈表再添加元素時，鏈表就將轉換為紅黑樹。
    * 該值必須大于2，并且應該至少為8，以便于刪除紅黑樹時轉回鏈表。
    */
    static final int TREEIFY_THRESHOLD = 8;

    /**
     *  當桶數組容量小于該值時，優先進行擴容，而不是樹化：
     */
    static final int MIN_TREEIFY_CAPACITY = 64;

二、【重點】解析HashMap.put(K key, V value)的源碼，去弄清楚鏈表轉紅黑樹的具體時機

　　通過查看HashMap的源碼可以發現，它的put(K key, V value)方法調用了putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)來實現元素的新增。所以我們實際要看的是putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)的源碼。

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); //直接放在散列表上的節點，并沒有特意標識其為頭節點，其實它就是"鏈表/紅黑樹.index(0)"
        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節點，找到該桶上的最后一個節點：
                        p.next = newNode(hash, key, value, null); //直接生成新節點，鏈在最后一個節點的后面；

                        //“binCount >= 7”：p從鏈表.index(0)開始，當binCount == 7時，p.index == 7,newNode.index == 8； 
                        //也就是說，當鏈表已經有8個節點了，此時再新鏈上第9個節點，在成功添加了這個新節點之后，立馬做鏈表轉紅黑樹。
                        if (binCount >= TREEIFY_THRESHOLD - 1)
　　　　　　　　　　　　　　　　treeifyBin(tab, hash); //鏈表轉紅黑樹 break; 
　　　　　　　　　　　　}
　　　　　　　　　　　　…… 
　　　　　　　　　　　　p = e; 
　　　　　　　　　　} 
　　　　　　 } 
　　　　　　　…… 
　　　　} 
　　　　…… 
}

通過源碼解析，我們已經很清楚HashMap是在“當鏈表已經有8個節點了，此時再新鏈上第9個節點，在成功添加了這個新節點之后，立馬做鏈表轉紅黑樹”。

三、通過debug，進一步理解鏈表轉紅黑樹的具體時機

　　1. 自定義一個類：該類中去重寫hashCode()，讓一組數據能得到同樣的哈希值，從而實現哈希碰撞。同時也重寫equals()方法。

public class A03Bean {
    protected int number;

    public A03Bean(int number) {
        this.number = number;
    }

    /**
     * 重寫hashCode()方法，只要是4的倍數，最后算出的哈希值都會是0.
     */
    @Override
    public int hashCode() {
        return number % 4;
    }

    /**
     * 也必須重寫equals()方法。當發生哈希沖突的時候，需要調用equals()方法比較兩個對象的實際內容是否相同。
     */
    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        A03Bean other = (A03Bean) obj;
        if (number != other.number)
            return false;
        return true;
    }
}

2. 將自定義類A03Bean的實例放到HashMap中：

public class A03Method_TreeifyBin2 {
    public static void main(String[] args) {
        HashMap<A03Bean, Integer> hashMap = new HashMap<>();
        hashMap.put(new A03Bean(4), 0);
        hashMap.put(new A03Bean(8), 1);
        hashMap.put(new A03Bean(12), 2);
        hashMap.put(new A03Bean(16), 3);
        hashMap.put(new A03Bean(20), 4);
        hashMap.put(new A03Bean(24), 5);
        hashMap.put(new A03Bean(28), 6);
        hashMap.put(new A03Bean(32), 7);
        hashMap.put(new A03Bean(36), 8);
        hashMap.put(new A03Bean(40), 9);
        hashMap.put(new A03Bean(44), 10);

        System.out.println("hashMap.size = " + hashMap.size());

        //查看是否所有對象都放到HashMap中了：
        for(A03Bean key : hashMap.keySet()) {
            System.out.println(key.number);
        }
    }
}

3.debug，斷點查看當同一個桶上的鏈表的長度達到多長時會做“鏈表轉紅黑樹”的操作。

　　　　斷點打在HashMap.putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)方法的“treeifyBin(tab, hash);”這里。

4.測試結果：

　　　　當put進第9個元素（hashMap.put(new A03Bean(36), 8);）時，HashMap做了鏈表轉紅黑樹的操作。

　　　　也就是說：當鏈表已經有8個元素了，此時put進第9個元素，先完成第9個元素的put，然后立刻做鏈表轉紅黑樹。這個結論和第2點中得到的結論一致。

　　　　最后的輸出結果也證明了所有的元素都成功put進了集合中，hashMap.size等于11。

　　到這里，有關“HashMap的鏈表轉紅黑樹的具體時機”算是解釋清楚了，有時間再探究“HashMap的紅黑樹轉回鏈表的具體時機”。