ConcurrentHashMap: 红黑树代理类的示例分析

小编给大家分享一下ConcurrentHashMap: 红黑树代理类的示例分析，相信大部分人都还不怎么了解，因此分享这篇文章给大家参考一下，希望大家阅读完这篇文章后大有收获，下面让我们一起去了解一下吧！

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;        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(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);    }        private final void lockRoot() {        // 条件成立：说明lockState 并不是 0，说明此时有其它读线程在treeBin红黑树中读取数据。        if (!U.compareAndSwapint(this, LOCKSTATE, 0, WRITER))            // 竞争锁的过程            contendedLock(); // offload to separate method    }        private final void unlockRoot() {        // lockstate置为0        lockState = 0;    }        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);        }    }        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: 红黑树代理类的示例分析”这篇文章的所有内容，感谢各位的阅读！相信大家都有了一定的了解，希望分享的内容对大家有所帮助，如果还想学习更多知识，欢迎关注编程网精选频道！