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

tangjin

作者

前一章是get、remove方法分析，喜欢的朋友点击查看。本篇为ConcurrentHashMap源码系列的最后一篇，来分析一下TreeBin 红黑树代理节点的源码：

1、TreeBin内部类分析

TreeBin是红黑树的代理，对红黑树不太了解的，可以参考：

解析ConcurrentHashMap:,红黑树的代理类(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; }