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

look_w

红黑树构造注意：如果链表结构中元素超过TREEIFY_THRESHOLD阈值，默认为8个，则把链表转化为红黑树，提高遍历查询效率。
if (binCount != 0) {    if (binCount >= TREEIFY_THRESHOLD)        treeifyBin(tab, i);    if (oldVal != null)        return oldVal;    break;}接下来我们看看如何构造树结构，代码如下：
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));                }            }        }    }}可以看出，生成树节点的代码块是同步的，进入同步代码块之后，再次验证table中index位置元素是否被修改过。
1、根据table中index位置Node链表，重新生成一个hd为头结点的TreeNode链表。
2、根据hd头结点，生成TreeBin树结构，并把树结构的root节点写到table的index位置的内存中，具体实现如下：
TreeBin(TreeNode<K,V> b) {    super(TREEBIN, null, null, null);    this.first = b;    TreeNode<K,V> r = null;    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;        }        else {            K k = x.key;            int h = x.hash;            Class<?> kc = null;            for (TreeNode<K,V> p = r;;) {                int dir, ph;                K pk = p.key;                if ((ph = p.hash) > h)                    dir = -1;                else if (ph < h)                    dir = 1;                else if ((kc == null &&                          (kc = comparableClassFor(k)) == null) ||                         (dir = compareComparables(kc, k, pk)) == 0)                    dir = tieBreakOrder(k, pk);                    TreeNode<K,V> xp = p;                if ((p = (dir <= 0) ? p.left : p.right) == null) {                    x.parent = xp;                    if (dir <= 0)                        xp.left = x;                    else                        xp.right = x;                    r = balanceInsertion(r, x);                    break;                }            }        }    }    this.root = r;    assert checkInvariants(root);}主要根据Node节点的hash值大小构建二叉树。这个红黑树的构造过程实在有点复杂，感兴趣的同学可以看看源码。