Java 容器源码分析之ConcurrentHashMap（10）

look_w

ConcurrentHashMap的红黑树实现分析知止而后有定，定而后能静，静而后能安，安而后能虑，虑而后能得
红黑树红黑树是一种特殊的二叉树，主要用它存储有序的数据，提供高效的数据检索，时间复杂度为O(lgn)，每个节点都有一个标识位表示颜色，红色或黑色，有如下5种特性：
1、每个节点要么红色，要么是黑色；
2、根节点一定是黑色的；
3、每个空叶子节点必须是黑色的；
4、如果一个节点是红色的，那么它的子节点必须是黑色的；
5、从一个节点到该节点的子孙节点的所有路径包含相同个数的黑色节点；
结构示意图
只要满足以上5个特性的二叉树都是红黑树，当有新的节点加入时，有可能会破坏其中一些特性，需要通过左旋或右旋操作调整树结构，重新着色，使之重新满足所有特性。
ConcurrentHashMap红黑树实现《谈谈ConcurrentHashMap1.7和1.8的不同实现》一文中已经提到，在1.8的实现中，当一个链表中的元素达到8个时，会调用treeifyBin()方法把链表结构转化成红黑树结构，实现如下：
/** * Replaces all linked nodes in bin at given index unless table is * too small, in which case resizes instead. */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)            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);                        if ((p.prev = tl) == null)                            hd = p;                        else                            tl.next = p;                        tl = p;                    }                    setTabAt(tab, index, new TreeBin<K,V>(hd));                }            }        }    }}从上述实现可以看出：并非一开始就创建红黑树结构，如果当前Node数组长度小于阈值MIN_TREEIFY_CAPACITY，默认为64，先通过扩大数组容量为原来的两倍以缓解单个链表元素过大的性能问题。
红黑树构造过程下面对红黑树的构造过程进行分析：
1、通过遍历Node链表，生成对应的TreeNode链表，其中TreeNode在实现上继承了Node类；
class TreeNode<K,V> extends Node<K,V> {    TreeNode<K,V> parent;  // red-black tree links    TreeNode<K,V> left;    TreeNode<K,V> right;    TreeNode<K,V> prev;        // needed to unlink next upon deletion    boolean red;}假设TreeNode链表如下，其中节点中的数值代表hash值：

2、根据TreeNode链表初始化TreeBin类对象，TreeBin在实现上同样继承了Node类，所以初始化完成的TreeBin类对象可以保持在Node数组中；
class TreeBin<K,V> extends Node<K,V> {    TreeNode<K,V> root;    volatile TreeNode<K,V> first;    volatile Thread waiter;    volatile int lockState;    // values for lockState    // set while holding write lock    static final int WRITER = 1;    // set when waiting for write lock    static final int WAITER = 2;     // increment value for setting read lock    static final int READER = 4; }3、遍历TreeNode链表生成红黑树，一开始二叉树的根节点root为空，则设置链表中的第一个节点80为root，并设置其red属性为false，因为在红黑树的特性1中，明确规定根节点必须是黑色的；
for (TreeNode<K,V> x = b, next; x != null; x = next) {    next = (TreeNode<K,V>)x.next;    x.left = x.right = null;    if (r == null) {        x.parent = null;        x.red = false;        r = x;    }    ...