Java并发进阶系列：jdk1.8 ConcurrentHashMap的TreeBin读写锁竞争机制讨论

本文接前面ConcurrentHashMap文章的内容，继续深入到TreeBin这个特殊节点的读写锁竞争机制。

7、TreeBin类设计原理

对TreeBin类深入分析，不仅能够理解为何CHM能支持并发读的底层实现，而且也能加深jk1.8的ConcurrentHashMap整体设计原理。本文将详细深入地解析TreeBin优秀的读写锁控制设计，此部分内容在全网的相关文章很少涉及。

7.1 保证加锁对象不改变的设计思想

首先看其源码的注释说明：

TreeNodes used at the heads of bins. TreeBins do not hold user keys or values, but instead point to list of TreeNodes and their root. They also maintain a parasitic read-write lock forcing writers (who hold bin lock) to wait for readers (who do not) to complete before tree restructuring operations.

TreeBins节点不是用于放置key和value，而是用于指向TreeNodes和TreeNodes的根节点。TreeBins内部会维护一把读写锁，用于保证在树重构前，持有锁的写线程被强制等待无锁读线程完成。

当然这注释也未能回答这样核心问题：为何对于桶位是红黑树的情况下，CHM放置的一个TreeBin节点，而不像HashMap那样放置一个TreeNode节点？

首先看看TreeBin的使用场景，在put场景下：

synchronized(f){if(tabAt(tab,i)==f){//if(fh>=0){// ..}//elseif(finstanceofTreeBin){Node<K,V>p;binCount=2;if((p=((TreeBin<K,V>)f).putTreeVal(hash,key,value))!=null){oldVal=p.val;if(!onlyIfAbsent)p.val=value;}}}}

当key所在桶位可以放入key时，先对头节点加锁synchronized (f)，注意这是独占锁，要求头节点对象在锁期间不会改变，否则就不能锁住同一对象。

为论证f头节点是TreeNode类型不适用并发的CHM场景，不妨假设CHM使用TreeNode作为CHM桶位上红黑树的头节点，于是在put场景下：

// ① 假设当前头节点f是一个TreeNode节点，则执行流会进入②分支synchronized(f){if(tabAt(tab,i)==f){//if(fh>=0){// ..}// ② 这里已经将TreeBin换成TreeNode类型elseif(finstanceofTreeNode){Node<K,V>p;binCount=2;// ③ 将key和value插入到红黑树当中if((p=((TreeBin<K,V>)f).putTreeVal(hash,key,value))!=null){oldVal=p.val;if(!onlyIfAbsent)p.val=value;}}}}

这里关键是第③步逻辑：将key和value插入到红黑树当中，会发生什么事情？

我们知道，在HashMap节点，将一个节点put入红黑树后，需要做插入平衡处理和将红黑树root节点移到双向链表的头节点位置，目的是为了保证桶位上的头节点即是红黑树的根节点也是双向链表的头结点，下面就是HashMap对应的操作

finalTreeNode<K,V>putTreeVal(HashMap<K,V>map,Node<K,V>[]tab,inth,Kk,Vv){// 插入平衡处理和将红黑树root节点移到双向链表的头节点位置moveRootToFront(tab,balanceInsertion(root,x));returnnull;}}

但对于并发CHM来说，红黑树的插入平衡处理会导致root节点发生了改变（例如插入平衡前根节点是treeNodeA，插入平衡后根节点是treeNodeB）而不是位于桶位头节点上，如果CHM桶位头节点还是TreeNode，那么就会出现以下图示的不能保证写线程独占操作的线程不安全情况。

如何解决以上遇到的问题？

Doug Lea为此设计了TreeBin类（节点），该节点只放在桶位头节点上，它内部“包装”一棵红黑树（有些文章会跟你说TreeBin是 TreeNode的代理结点，其实意思都一样）。加锁时，对桶位头节点上TreeBin节点进行加锁，内部的红黑树根节点root在调整平衡后不管如何变化，当前桶位的加锁对象——TreeBin节点保持不变，也即保证写操作独占性，如下图所示。此外TreeBin还支持高级特性：并发环境下的读写锁控制机制。

而且这样设计的TreeBin还有另外一个收益：无需进行类似HashMap的moveRootToFront操作，因为桶头节点不再要求是

红黑树的根节点root，也不是链表的first头节点，而是一个包装了TreeNodes的TreeBin节点。

以下是HashMap的插入节点后需要做moveRootToFront操作的源码片段：

// putVal方法内部代码片段elseif(pinstanceofTreeNode)e=((TreeNode<K,V>)p).putTreeVal(this,tab,hash,key,value);// putTreeVal方法内部代码片段moveRootToFront(tab,balanceInsertion(root,x));

以下是CHM插入新节点后的插入平衡操作：在插入平衡操作前，采用cas加锁机制，显然不同于HashMap，这个加锁机制有点复杂，目的是什么呢？在后面7.3小节会提到。

else{lockRoot();try{// 仅有插入平衡操作，没有moveRootToFront操作，因为桶位头节点一直都是TreeBin节点，这个节点的hash值为-2，没有key和valueroot=balanceInsertion(root,x);}finally{unlockRoot();}}break;

此外，在源码中的lockRoot等地方的注释中，有个短语：tree restructuring，表示：红黑树重新调整结构。

而tree restructuring operations则表示：红黑树重新调整结构操作，具体来说是以下两个方法

put方面内部的putTreeVal方法以及remove方法内部的removeTreeNode方法，也即红黑树插入一个新节点需要触发tree restructuring 操作，红黑树删除一个节点需要触发tree restructuring 操作：执行tree restructuring操作前需要使用lockRoot()获取写锁，调整完后使用unlockRoot()释放写锁。

7.2 TreeBin类

TreeBin作为CHM内部类，有部分设计是新设计，用于解决高并发条件下的读写竞争问题，而另外一部分设计则沿用HashMap红黑树部分操作方法：如rotateLeft、rotateRight、balanceInsertion、balanceDeletion等，这几个方法是在synchronized(f)独占锁条件系进行的，因此跟HashMap原来的执行机制类似，此处不再累赘。本章重点放在新的设计上。

7.2.1 基本的成员变量

基本成员变量具体使用在7.3小节的读写竞争设计给出，waiter、lockState以及lockState对应的三个标记值，再结合位运算方式，非常巧妙的实现了TreeBin读写锁竞争！

staticfinalclassTreeBin<K,V>extendsNode<K,V>{TreeNode<K,V>root;// 桶位上红黑树根节点的引用volatileTreeNode<K,V>first;// 因为TreeNode节点还有next属性，因此红黑树本身也是一条链表，first就是该链表的头节点，常常用在需要线性遍历节点的场景volatileThreadwaiter;// 参考7.3.1小节内容volatileintlockState;// 直译：锁状态，用于表征TreeBin对象当前的锁状态是什么，对应以下三种状态// values for lockStatestaticfinalintWRITER=1;// set while holding write lock 写线程给lockState进行cas设1以此获得写锁：0001staticfinalintWAITER=