解析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的源码分析就告一段落了,祝大家变得更强~也希望大家多多关注我们的其他内容!

(0)

相关推荐

  • 解析ConcurrentHashMap: put方法源码分析

    上一章:预热(内部一些小方法分析) put()方法是并发HashMap源码分析的重点方法,这里涉及到并发扩容,桶位寻址等等- JDK1.8 ConcurrentHashMap结构图: 1.put方法源码解析 // 向并发Map中put一个数据 public V put(K key, V value) { return putVal(key, value, false); } // 向并发Map中put一个数据 // Key: 数据的键 // value:数据的值 // onlyIfAbsent:

  • 解析ConcurrentHashMap: 预热(内部一些小方法分析)

    前面一篇文章中介绍了并发HashMap的主要成员属性,内部类和构造函数,下面在正式分析并发HashMap成员方法之前,先分析一些内部类中的字方法函数: 首先来看下ConcurrentHashMap内部类Node中的hash成员属性值的计算方法spread(int h): static class Node<K,V> implements Map.Entry<K,V> { final int hash;// 该属性是通过spread(int h)方法计算得到~ final K key

  • 解析ConcurrentHashMap: get、remove方法分析

    前面几篇文章分析了并发HashMap的put方法及其相关方法,transfer方法,那么接下来本篇文章相对之前几篇难度会小一些. 本篇文章介绍ConcurrentHashMap的get方法和remove方法. 1.get方法 get方法:获取元素,根据目标key所在桶的第一个元素的不同采用不同的方式获取元素,关键点在于find()方法的重写. public V get(Object key) { // tab 引用map.table // e 当前元素(用于循环遍历) // p 目标节点 //

  • 解析ConcurrentHashMap:成员属性、内部类、构造方法分析

    1.简介 ConcurrentHashMap是HashMap的线程安全版本,内部也是使用(数组 + 链表 + 红黑树)的结构来存储元素.相比于同样线程安全的HashTable来说,效率等各方面都有极大地提高. 在学习ConcurrentHashMap源码之前,这里默认大家已经读过HashMap源码,了解LongAdder原子类.红黑树.先简单介绍下 ConcurrentHashMap的整体流程: 整体流程跟HashMap比较类似,大致是以下几步: (1)如果桶数组未初始化,则初始化: (2)如果

  • 解析ConcurrentHashMap: transfer方法源码分析(难点)

    上一篇文章介绍过put方法以及其相关的方法,接下来,本篇就介绍一下transfer这个方法(比较难),最好能动手结合着源码进行分析,并仔细理解前面几篇文章的内容~ 注:代码分析的注释中的CASE0.CASE1- ,这些并没有直接关联关系,只是为了给每个if逻辑判断加一个标识,方便在其他逻辑判断的地方进行引用而已. 再复习一下并发Map的结构图: 1.transfer方法 transfer方法的作用是:迁移元素,扩容时table容量变为原来的两倍,并把部分元素迁移到其它桶nextTable中.该方

  • 解析ConcurrentHashMap: 红黑树的代理类(TreeBin)

    前一章是get.remove方法分析,喜欢的朋友点击查看.本篇为ConcurrentHashMap源码系列的最后一篇,来分析一下TreeBin 红黑树代理节点的源码: 1.TreeBin内部类分析 TreeBin是红黑树的代理,对红黑树不太了解的,可以参考: static final class TreeBin<K,V> extends Node<K,V> { // 红黑树根节点 TreeNode<K,V> root; // 链表的头节点 volatile TreeNo

  • 解析ConcurrentHashMap:成员属性、内部类、构造方法

    目录 1.简介 2.JDK1.8 ConcurrentHashMap结构图 3.成员属性 4.静态属性 5.静态代码块 6.内部类 6.1 Node节点 6.2 ForwardingNode节点 6.3 TreeNode节点 7.构造方法 8.总结 1.简介 ConcurrentHashMap是HashMap的线程安全版本,内部也是使用(数组 + 链表 + 红黑树)的结构来存储元素.相比于同样线程安全的HashTable来说,效率等各方面都有极大地提高. 在学习ConcurrentHashMap

  • HashMap红黑树入门(实现一个简单的红黑树)

    目录 1.树结构入门 1.1 什么是树? 1.2 树结构常用术语 1.3 二叉搜索树 2.红黑树原理讲解 2.1 红黑树的性质: 2.2 红黑树案例分析 3.手写红黑树 4. HashMap底层的红黑树 5 将链表转换为红黑树 treeifyBin() 总结: JDK集合源码之HashMap解析 1.树结构入门 1.1 什么是树? 树(tree)是一种抽象数据类型(ADT),用来模拟具有树状结构性质的数据集合.它是由n(n>0)个有限节点通过连接它们的边组成一个具有层次关系的集合. 把它叫做&quo

  • JDK动态代理之ProxyGenerator生成代理类的字节码文件解析

    通过前面几篇的分析,我们知道代理类是通过Proxy类的ProxyClassFactory工厂生成的,这个工厂类会去调用ProxyGenerator类的generateProxyClass()方法来生成代理类的字节码.ProxyGenerator这个类存放在sun.misc包下,我们可以通过OpenJDK源码来找到这个类,该类的generateProxyClass()静态方法的核心内容就是去调用generateClassFile()实例方法来生成Class文件.我们直接来看generateClas

  • 解析利用wsdl.exe生成webservice代理类的详解

    利用wsdl.exe生成webservice代理类:根据提供的wsdl生成webservice代理类1.开始->程序->Visual Studio 2005 命令提示2.输入如下红色标记部分D:/Program Files/Microsoft Visual Studio 8/VC>wsdl /language:c# /n:TestDemo /out:d:/Temp/TestService.cs D:/Temp/TestService.wsdl在d:/Temp下就会产生一个TestServ

  • Java红黑树的数据结构与算法解析

    目录 红黑树的介绍 红黑树的实现 1.节点 2.查找 3.平衡化 颜色反转 插入的实现 红黑树的复杂度– 总结 红黑树的介绍 红黑树(Red-Black Tree,简称R-B Tree),它一种特殊的二叉查找树. 红黑树是特殊的二叉查找树,意味着它满足二叉查找树的特征:任意一个节点所包含的键值,大于等于左孩子的键值,小于等于右孩子的键值. 除了具备该特性之外,红黑树还包括许多额外的信息. 红黑树的每个节点上都有存储位表示节点的颜色,颜色是红(Red)或黑(Black). 红黑树的特性: (1)

随机推荐