HashMap連結清單轉紅黑樹源碼解析

HashMap連結清單轉紅黑樹需要同時滿足兩個條件：

1.table數組長度>=64

2.連結清單長度>8

當調用put方法添加元素到map時，連結清單轉紅黑樹的入口是treeifyBin(tab, hash)方法。為了讓元素集中添加到某個桶bucket中，簡單粗暴的做法是寫一個類，重寫hashCode和equals方法

/**
 * 想要HasMap都配置設定到同一個桶上，就要保證hashCode一樣，是以本類重寫了hashCode方法，并且都傳回1111
 * HashMap判斷key是否相等，是用==号，比較的是記憶體位址。是以new兩個User對象，用==号比較肯定是false
 * 重寫equals方法，永遠傳回false，這樣HashMap就不會認為key是一樣的了。就會往同一個桶插入user對象，
 * 直到連結清單長度超過8，就可以示範連結清單轉紅黑樹的現象。
 *
 * HashMap是這樣判斷key相等的，相等就把舊值替換為新值
 * 這裡key不等(都是new出來的，是以==号結果是false)
 * equals也不等，因為重寫了傳回為false
 * if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))    // p是連結清單表頭
 *     e = p;
 *
 * @author: lbj
 * @create: 2020-07-31 23:56
 */
public class User {
    @Override
    public boolean equals(Object o) {
        return false;   // 故意
    }

    @Override
    public int hashCode() {
        return 1111;    // 故意
    }
}
           

寫個demo，for循環100次往map裡添加元素，當添加到第9個元素的時候，才進入到treeifyBin方法

public class HashMapTest {
    public static void main(String[] args) {
        HashMap map = new HashMap<>();
        for (Integer i=0;i<100;i++) {
            System.out.println("i==="+i);
            map.put(new User(),1);
        }
    }
}
           

運作效果如下圖：

在treeifyBin方法會首先判斷table數組的長度，如果小于64的話，就擴容，容量為原來的2倍。

final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    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;
        do {// while循環，把Node節點轉成TreeNode節點
            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);
        if ((tab[index] = hd) != null)
            hd.treeify(tab);
    }
}

// For treeifyBin
TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
    return new TreeNode<>(p.hash, p.key, p.value, next);
}
           

變成紅黑樹之後，再往map添加元素，就走putVal方法的這個分支

else if (p instanceof TreeNode)
    e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
           

附上TreeNode的結構

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent;  // red-black tree links
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    TreeNode<K,V> prev;    // needed to unlink next upon deletion
    boolean red;
    TreeNode(int hash, K key, V val, Node<K,V> next) {
        super(hash, key, val, next);
    }
}