解析ConcurrentHashMap: 紅黑樹的代理類(TreeBin)

前一章是get、remove方法分析,喜歡的朋友點擊查看。本篇為ConcurrentHashMap源碼系列的最後一篇,來分析一下TreeBin 紅黑樹代理節點的源碼:

1、TreeBin內部類分析

TreeBin是紅黑樹的代理,對紅黑樹不太瞭解的,可以參考:

static final class TreeBin<K,V> extends Node<K,V> {
    // 紅黑樹根節點
    TreeNode<K,V> root;
    // 鏈表的頭節點
    volatile TreeNode<K,V> first;
    // 等待者線程(當前lockState是讀鎖狀態)
    volatile Thread waiter;
    /**
     * 鎖的狀態:
     * 1.寫鎖狀態 寫是獨占狀態,以散列表來看,真正進入到TreeBin中的寫線程 同一時刻隻能有一個線程。 
     * 2.讀鎖狀態 讀鎖是共享,同一時刻可以有多個線程 同時進入到 TreeBin對象中獲取數據。 每一個線程 都會給 lockStat + 4
     * 3.等待者狀態(寫線程在等待),當TreeBin中有讀線程目前正在讀取數據時,寫線程無法修改數據,那麼就將lockState的最低2位設置為 0b 10 :即,換算成十進制就是WAITER = 2;
     */
    volatile int lockState;
    // values for lockState(lockstate的值)
    static final int WRITER = 1; // set while holding write lock 寫鎖狀態
    static final int WAITER = 2; // set when waiting for write lock 等待者狀態(寫線程在等待)
    static final int READER = 4; // increment value for setting read lock 讀鎖狀態
    /**
     * TreeBin構造方法:
     */
    TreeBin(TreeNode<K,V> b) {
        // 設置當前節點hash為-2 表示此節點是TreeBin節點
        super(TREEBIN, null, null, null);
        // 使用first 引用 treeNode鏈表
        this.first = b;
        // r 紅黑樹的根節點引用
        TreeNode<K,V> r = null;
        // x表示遍歷的當前節點
        for (TreeNode<K,V> x = b, next; x != null; x = next) {
            next = (TreeNode<K,V>)x.next;
            // 強制設置當前插入節點的左右子樹為null
            x.left = x.right = null;
            // ----------------------------------------------------------------------
            // CASE1:
            // 條件成立:說明當前紅黑樹是一個空樹,那麼設置插入元素為根節點
            // 第一次循環,r一定是null
            if (r == null) {
                // 根節點的父節點 一定為 null
                x.parent = null;
                // 顏色改為黑色
                x.red = false;
                // 讓r引用x所指向的對象。
                r = x;
            }
			// ----------------------------------------------------------------------
            // CASE2:r != null	
            else {
                // 非第一次循環,都會來帶else分支,此時紅黑樹根節點已經有數據瞭
                // k 表示 插入節點的key
                K k = x.key;
                // h 表示 插入節點的hash
                int h = x.hash;
                // kc 表示 插入節點key的class類型
                Class<?> kc = null;
                // p 表示 為查找插入節點的父節點的一個臨時節點
                TreeNode<K,V> p = r;
                // 這裡的for循環,就是一個查找並插入的過程
                for (;;) {
                    // dir (-1, 1)
                    // -1 表示插入節點的hash值大於 當前p節點的hash
                    // 1 表示插入節點的hash值 小於 當前p節點的hash
                    // ph p表示 為查找插入節點的父節點的一個臨時節點的hash
                    int dir, ph;
                    // 臨時節點 key
                    K pk = p.key;
                    // 插入節點的hash值 小於 當前節點
                    if ((ph = p.hash) > h)
                        // 插入節點可能需要插入到當前節點的左子節點 或者 繼續在左子樹上查找
                        dir = -1;
                    // 插入節點的hash值 大於 當前節點
                    else if (ph < h)
                        // 插入節點可能需要插入到當前節點的右子節點 或者 繼續在右子樹上查找
                        dir = 1;
                    // 如果執行到 CASE3,說明當前插入節點的hash 與 當前節點的hash一致,會在case3 做出最終排序。最終
                    // 拿到的dir 一定不是0,(-1, 1)
                    else if ((kc == null &&
                              (kc = comparableClassFor(k)) == null) ||
                             (dir = compareComparables(kc, k, pk)) == 0)
                        dir = tieBreakOrder(k, pk);
                    // xp 想要表示的是 插入節點的 父節點
                    TreeNode<K,V> xp = p;
                    // 條件成立:說明當前p節點 即為插入節點的父節點
                    // 條件不成立:說明p節點 底下還有層次,需要將p指向 p的左子節點 或者 右子節點,表示繼續向下搜索。
                    if ((p = (dir <= 0) ? p.left : p.right) == null) {
                        // 設置插入節點的父節點 為 當前節點
                        x.parent = xp;
                        // 小於P節點,需要插入到P節點的左子節點
                        if (dir <= 0)
                            xp.left = x;
                            // 大於P節點,需要插入到P節點的右子節點
                        else
                            xp.right = x;
                        // 插入節點後,紅黑樹性質 可能會被破壞,所以需要調用 平衡方法
                        r = balanceInsertion(r, x);
                        break;
                    }
                }
            }
        }
        // 將r 賦值給 TreeBin對象的 root引用。
        this.root = r;
        assert checkInvariants(root);
    }
    /**
     * Acquires write lock for tree restructuring.
     * 加鎖:基於CAS的方式更新LOCKSTATE的值,期望值是0,更新值是WRITER(1,寫鎖)
     */
    private final void lockRoot() {
        // 條件成立:說明lockState 並不是 0,說明此時有其它讀線程在treeBin紅黑樹中讀取數據。
        if (!U.compareAndSwapInt(this, LOCKSTATE, 0, WRITER))
            // 競爭鎖的過程
            contendedLock(); // offload to separate method
    }
    /**
     * Releases write lock for tree restructuring.
     * 釋放鎖
     */
    private final void unlockRoot() {
        // lockstate置為0
        lockState = 0;
    }
    /**
     * Possibly blocks awaiting root lock.
     */
    private final void contendedLock() {
        boolean waiting = false;
        // 表示lock值
        int s;
        for (;;) {
            // ~WAITER = 11111....01
            // 條件成立:說明目前TreeBin中沒有讀線程在訪問 紅黑樹
            // 條件不成立:有線程在訪問紅黑樹
            if (((s = lockState) & ~WAITER) == 0) {
                // 條件成立:說明寫線程 搶占鎖成功
                if (U.compareAndSwapInt(this, LOCKSTATE, s, WRITER)) {
                    if (waiting)
                        // 設置TreeBin對象waiter 引用為null
                        waiter = null;
                    return;
                }
            }
            // lock & 0000...10 = 0, 條件成立:說明lock 中 waiter 標志位 為0,此時當前線程可以設置為1瞭,然後將當前線程掛起。
            else if ((s & WAITER) == 0) {
                if (U.compareAndSwapInt(this, LOCKSTATE, s, s | WAITER)) {
                    waiting = true;
                    waiter = Thread.currentThread();
                }
            }
            // 條件成立:說明當前線程在CASE2中已經將 treeBin.waiter 設置為瞭當前線程,並且將lockState 中表示 等待者標記位的地方 設置為瞭1
            // 這個時候,就讓當前線程 掛起。。
            else if (waiting)
                LockSupport.park(this);
        }
    }
    /**
     * Finds or adds a node.
     * @return null if added
     */
    final TreeNode<K,V> putTreeVal(int h, K k, V v) {
        Class<?> kc = null;
        boolean searched = false;
        for (TreeNode<K,V> p = root;;) {
            int dir, ph; K pk;
            if (p == null) {
                first = root = new TreeNode<K,V>(h, k, v, null, null);
                break;
            }
            else if ((ph = p.hash) > h)
                dir = -1;
            else if (ph < h)
                dir = 1;
            else if ((pk = p.key) == k || (pk != null && k.equals(pk)))
                return p;
            else if ((kc == null &&
                      (kc = comparableClassFor(k)) == null) ||
                     (dir = compareComparables(kc, k, pk)) == 0) {
                if (!searched) {
                    TreeNode<K,V> q, ch;
                    searched = true;
                    if (((ch = p.left) != null &&
                         (q = ch.findTreeNode(h, k, kc)) != null) ||
                        ((ch = p.right) != null &&
                         (q = ch.findTreeNode(h, k, kc)) != null))
                        return q;
                }
                dir = tieBreakOrder(k, pk);
            }
            TreeNode<K,V> xp = p;
            if ((p = (dir <= 0) ? p.left : p.right) == null) {
                // 當前循環節點xp 即為 x 節點的爸爸
                // x 表示插入節點
                // f 老的頭結點
                TreeNode<K,V> x, f = first;
                first = x = new TreeNode<K,V>(h, k, v, f, xp);
                // 條件成立:說明鏈表有數據
                if (f != null)
                    // 設置老的頭結點的前置引用為 當前的頭結點。
                    f.prev = x;
                if (dir <= 0)
                    xp.left = x;
                else
                    xp.right = x;

                if (!xp.red)
                    x.red = true;
                else {
                    // 表示 當前新插入節點後,新插入節點 與 父節點 形成 “紅紅相連”
                    lockRoot();
                    try {
                        // 平衡紅黑樹,使其再次符合規范。
                        root = balanceInsertion(root, x);
                    } finally {
                        unlockRoot();
                    }
                }
                break;
            }
        }
        assert checkInvariants(root);
        return null;
    }
}

2、treeifyBin方法分析

treeifyBin:TreeBin的成員方法,轉換鏈表為紅黑樹的方法:

/**
 * 將鏈表轉換成紅黑樹
 */
private final void treeifyBin(Node<K,V>[] tab, int index) {
    // b:
    // n: tab的長度
    // sc: sizeCtl
    Node<K,V> b; int n, sc;
    if (tab != null) {
        // ---------------------------------------------------------------------------
        // CASE1:
        // 條件成立:說明當前table數組長度未達到 64,此時不進行樹化操作,而進行擴容操作。
        if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
            // table進行擴容
            tryPresize(n << 1);
        // ---------------------------------------------------------------------------
        // CASE2:
        // 條件成立:說明當前桶位有數據,且是普通node數據。
        else if ((b = tabAt(tab, index)) != null && b.hash >= 0) {
			// 給頭元素b加鎖
            synchronized (b) {
                // 條件成立:表示加鎖沒問題,b沒有被其他線程修改過
                if (tabAt(tab, index) == b) {
                    // 下面的for循環邏輯,目的就是把桶位中的單鏈表轉換成雙向鏈表,便於樹化~
					// hd指向雙向列表的頭部,tl指向雙向鏈表的尾部
                    TreeNode<K,V> hd = null, tl = null;
                    for (Node<K,V> e = b; e != null; e = e.next) {
                        TreeNode<K,V> p =
                            new TreeNode<K,V>(e.hash, e.key, e.val,
                                              null, null);
                        if ((p.prev = tl) == null)
                            hd = p;
                        else
                            tl.next = p;
                        tl = p;
                    }
					// 把node單鏈表轉換的雙向鏈表轉換成TreeBin對象
                    setTabAt(tab, index, new TreeBin<K,V>(hd));
                }
            }
        }
    }
}

3、find方法分析

find:TreeBin中的查找方法。

final Node<K,V> find(int h, Object k) {
    if (k != null) {
        // e 表示循環迭代的當前節點:迭代的是first引用的鏈表
        for (Node<K,V> e = first; e != null; ) {
            // s 保存的是lock臨時狀態
            // ek 鏈表當前節點 的key
            int s; K ek;
            // ----------------------------------------------------------------------
            // CASE1:
            // (WAITER|WRITER) => 0010 | 0001 => 0011
            // lockState & 0011 != 0 條件成立:說明當前TreeBin有等待者線程 或者 目前有寫操作線程正在加鎖
            if (((s = lockState) & (WAITER|WRITER)) != 0) {
                if (e.hash == h &&
                    ((ek = e.key) == k || (ek != null && k.equals(ek))))
                    return e;
                e = e.next;
            }
            // ----------------------------------------------------------------------
            // CASE2:
            // 前置條件:當前TreeBin中 等待者線程 或者 寫線程 都沒有
            // 條件成立:說明添加讀鎖成功
            else if (U.compareAndSwapInt(this, LOCKSTATE, s,
                                         s + READER)) {
                TreeNode<K,V> r, p;
                try {
                    // 查詢操作
                    p = ((r = root) == null ? null :
                         r.findTreeNode(h, k, null));
                } finally {
                    // w 表示等待者線程
                    Thread w;
                    // U.getAndAddInt(this, LOCKSTATE, -READER) == (READER|WAITER)
                    // 1.當前線程查詢紅黑樹結束,釋放當前線程的讀鎖 就是讓 lockstate 值 - 4
                    // (READER|WAITER) = 0110 => 表示當前隻有一個線程在讀,且“有一個線程在等待”
                    // 當前讀線程為 TreeBin中的最後一個讀線程。
                    // 2.(w = waiter) != null 說明有一個寫線程在等待讀操作全部結束。
                    if (U.getAndAddInt(this, LOCKSTATE, -READER) ==
                        (READER|WAITER) && (w = waiter) != null)
                        // 使用unpark 讓 寫線程 恢復運行狀態。
                        LockSupport.unpark(w);
                }
                return p;
            }
        }
    }
    return null;
}

三、總結

到此為止,ConcurrentHashMap的源碼分析就告一段落瞭,祝大傢變得更強~也希望大傢多多關註WalkonNet的其他內容!

推薦閱讀: