JDK1.8ConcurrentHashMap源码解析第三部分（红黑树TreeNode的封装类TreeBin）_concurrenthashmap 1.8 红黑树 lockroot

TreeBin是红黑树TreeNode的封装类，和TreeNode的区别是有一个成员变量lockState表示锁的状态，还有waiter表示等待的线程，多了几个和锁有关的方法，其他都和TreeNode大致一样

 static final class TreeBin<K,V> extends Node<K,V> {
        TreeNode<K,V> root; //根节点
        volatile TreeNode<K,V> first; //链表头结点
        volatile Thread waiter; // 等待者线程（当前lockState是读锁状态）
        volatile int lockState; //锁的状态 写锁是独占状态 写的时候其他线程不能读或写 读锁是共享状态 其他线程可以读不能写 等待者状态 写线程要等其他线程读完才能写 把lockState最后两位设为2
        // values for lockState
        static final int WRITER = 1; // 锁处于写状态
        static final int WAITER = 2; // 锁处于等待获取写锁状态
        static final int READER = 4; // 锁处于读状态
}

//构造方法，通过一个TreeNode构造红黑树
TreeBin(TreeNode<K,V> b) {
            super(TREEBIN, null, null, null); //设置当前节点hash为-2表示当前节点是树节点
            this.first = b; //设置链表头结点
            TreeNode<K,V> r = null; //树根节点引用
            for (TreeNode<K,V> x = b, next; x != null; x = next) { // x表示遍历的当前节点
                next = (TreeNode<K,V>)x.next; //下一节点
                x.left = x.right = null; // 强制设置当前插入节点的左右子树为null
                if (r == null) { //当前红黑树是一个空树，那么设置插入元素为根节点 第一次循环，r一定是null
                    x.parent = null; // 根节点的父节点 一定为 null
                    x.red = false;  //根节点一定是黑色
                    r = x; //当前节点给树根节点引用
                }
                else { //第二次循环来到这里
                    K k = x.key; //节点的key
                    int h = x.hash; //节点的hash
                    Class<?> kc = null; //节点的class类型
                    for (TreeNode<K,V> p = r;;) { //p是根节点的临时节点 这个节点最后会变成插入节点的父节点 2754行被赋值
                        int dir, ph; //查找方向 临时节点hash值
                        K pk = p.key; //临时节点的key
                        if ((ph = p.hash) > h) //插入节点hash小于临时节点
                            dir = -1;   // 插入节点可能需要插入到当前节点的左子节点 或者 继续在左子树上查找
                        else if (ph < h) //插入节点hash大于临时节点
                            dir = 1;    // 插入节点可能需要插入到当前节点的右子节点 或者 继续在右子树上查找
                        else if ((kc == null && //来到这里说明临时节点和插入节点的hash一样然后就开始查找插入位置
                                  (kc = comparableClassFor(k)) == null) ||
                                  //key没有实现comparable接口就用compareTo比较大小 如果还是比较不了就用tieBreakOrder比较，tieBreakOrder比较的是原始的hash值
                                 (dir = compareComparables(kc, k, pk)) == 0) 
                            dir = tieBreakOrder(k, pk); //直接使用hash值比较大小不会返回0
                            TreeNode<K,V> xp = p; //插入节点的父节点
                        if ((p = (dir <= 0) ? p.left : p.right) == null) { //在这里p会被重新赋值
                            x.parent = xp; // 设置插入节点的父节点 为 当前节点
                            if (dir <= 0)
                                xp.left = x; //插入到左节点
                            else
                                xp.right = x; //插入到右节点
                            r = balanceInsertion(r, x); //进行插入后的调整
                            break;
                        }
                    }
                }
            }
            this.root = r;
            assert checkInvariants(root);
        }


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

整体流程：
通过TreeNode的链表来构建红黑树，红黑树为空就当前节点作为红黑树的根节点，红黑树不为空就看插入节点hash值比根节点大还是小，小的话就插入根节点的左边，大的话就插入根节点的右边，每插入一个节点就要进行红黑树的插入平衡

加锁解锁和抢锁的相关方法

  /**
   * cas更新LOCKSTATE的值 0更新成1 表示为写锁状态
  */
        private final void lockRoot() {
            if (!U.compareAndSwapInt(this, LOCKSTATE, 0, WRITER))
                contendedLock(); //更新失败表明有其他读线程在读数据 然后就要竞争锁
        }

        /**
         * 解锁头结点
         */
        private final void unlockRoot() {
            lockState = 0;
        }

        /**
         * Possibly blocks awaiting root lock.
         */
        private final void contendedLock() {
            boolean waiting = false;
            for (int s;;) { //锁的状态值
                if (((s = lockState) & ~WAITER) == 0) { // ~WAITER是11111~01 为true表明没线程访问红黑树 lockState为0或waiter状态10这个条件才成立，没有线程读或写红黑树，只有线程在等待
                    if (U.compareAndSwapInt(this, LOCKSTATE, s, WRITER)) { //cas更新lockState为WRITER状态，更新成功就把waiter状态清空
                        if (waiting) //若当前线程注册过waiter状态，则清除，返回写锁
                            waiter = null; //抢锁成功就不用等待了
                        return;
                    }
                }
                else if ((s & WAITER) == 0) { // lockState为READER状态时这里才成立 要挂起当前线程
                    if (U.compareAndSwapInt(this, LOCKSTATE, s, s | WAITER)) { //cas更新lockState为WAITER状态
                        waiting = true;
                        waiter = Thread.currentThread(); //设置waiter线程
                    }
                }
                else if (waiting)
                    LockSupport.park(this); //挂起当前线程
            }
        }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

抢锁的整体流程：
（1）先看有没有线程在读或写红黑树，没有的话就把当前线程的锁状态更新为写状态，更新成功就把waiter状态清空
（2）如果有线程在读红黑树，就cas更新lockState为WAITER状态，表示当前线程等待获取锁
（3）如果当前线程在等待，就把当前线程挂起等待其他线程解锁

查找元素方法

final Node<K,V> find(int h, Object k) {
            if (k != null) {
                for (Node<K,V> e = first; e != null; ) {
                    int s; K ek;
                    if (((s = lockState) & (WAITER|WRITER)) != 0) { //当lockState为WAITER或WRITER状态时就用链表方式查找
                        if (e.hash == h &&                          //写状态时 读则采取遍历链表的方式 虽然查找复杂度提高，但读写不阻塞 红黑树写时会阻塞读
                            ((ek = e.key) == k || (ek != null && k.equals(ek))))
                            return e;
                        e = e.next;
                    } //cas设置LOCKSTATE为读锁
                    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 {
                            Thread w; //如果是最后一个读线程，并且有写线程因为读锁而阻塞 那么要通知它，告诉它可以尝试获取写锁了
                            //U.getAndAddInt(this, LOCKSTATE, -READER)释放一把读锁 LOCKSTATE-4
                            // 减完之后如果等于0110表示还有最后一个线程在读 并且还有一个线程在等（因为0110是6 4 + 2 4是读线程 2是等待线程）
                            // (w = waiter) != null 说明有一个写线程在等待读操作全部结束。
                            if (U.getAndAddInt(this, LOCKSTATE, -READER) == 
                                (READER|WAITER) && (w = waiter) != null)   
                                // 使用unpark 让等待最后一个读锁释放的线程 即写线程恢复运行状态。   
                                LockSupport.unpark(w);                        
                        }      
                        return p;
                    }
                }
            }
            return null;
        }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

整体流程：
（1）有线程在写红黑树，或有线程在等待就遍历链表查找，因为有线程在写红黑树时会对红黑树进行平衡调整而导致红黑树结构变化，所以不能根据红黑树的方式查找，链表不用进行平衡调整所以结构就不会改变可以遍历链表查找
（2）cas设置LOCKSTATE为读锁，lockState+4表示读锁多了一把，如果获取了读锁就用红黑树方式查找
（3）查找完之后就释放读锁，然后判断是否还有最后一个读锁和一个等待写锁的线程，是的话就唤醒这个等待写锁的线程让它准备去竞争
最后一个读锁解锁之后的锁

添加元素

 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) //插入元素hash小于p
                    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 && //hash相等但key不相等
                          (kc = comparableClassFor(k)) == null) ||
                         (dir = compareComparables(kc, k, pk)) == 0) { //key实现了Comparable接口就调用compareTo方法比较
                    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); //没找到会来到这里比较原始的hashcode决定插入左边还是右边
                }

                TreeNode<K,V> xp = p;//当前节点为插入节点的父节点
                if ((p = (dir <= 0) ? p.left : p.right) == null) {
                    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;
        }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

整体流程：
（1）先判断红黑树是否为空，空的话就直接添加然后返回
（2）判断插入节点hash值比根节点大还是小，小的话就插入根节点的左边，大的话就插入根节点的右边，插入节点本来在红黑树有就相当于查找操作，返回找到的目标节点
（3）没有找到就寻找插入位置，然后判断插入左边还是右边，把插入节点设置成链表的新的头结点，遍历链表时第一个节点为最后插入的节点
（4）如果插入节点的父节点为黑色，插入节点就为红色
（5）如果插入节点和父节点都为红色，就要锁红黑树的根节点阻塞其他线程读然后进行平衡调整，调整完之后就解锁

树化方法

 private final void treeifyBin(Node<K,V>[] tab, int index) {
        Node<K,V> b; int n, sc;
        if (tab != null) {
            if ((n = tab.length) < MIN_TREEIFY_CAPACITY) //table桶位还没达到树化要求的最小桶位就直接扩容
                tryPresize(n << 1);
            else if ((b = tabAt(tab, index)) != null && b.hash >= 0) { //对应桶位有元素 并且是链表节点
                synchronized (b) { //锁头结点
                    if (tabAt(tab, index) == b) { //再次判断防止头结点加锁前被修改
                        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); //使用当前节点实例化一个TreeNode节点
                            if ((p.prev = tl) == null) //当前节点没有前驱节点  当前节点的前驱节点指向尾节点
                                hd = p; //当前节点设置成头结点
                            else
                                tl.next = p; //尾节点的后继节点指向当前节点
                            tl = p;  //更新尾节点
                        }
                        setTabAt(tab, index, new TreeBin<K,V>(hd));// 把node单链表转换的双向链表转换成TreeBin对象 new TreeBin这个构造函数会初始化红黑树
                    }
                }
            }
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

整体流程：
（1）判断table大小是否达到了树化要求的最小桶位，是的话就可以树化，否的话就直接扩容
（2）对应桶位有元素，并且是链表节点
（3）锁桶位元素开始树化
（4）把单链表节点Node变成双向链表节点TreeNode
（5）最后使用双向链表节点TreeNode转换成TreeBin对象，是通过TreeBin的构造函数转换的

还有其他方法和HashMap的TreeNode一样，例如平衡插入，平衡删除，右旋左旋，remove方法和TreeNode的区别是删除前要加锁，删完后解锁