ConcurrentHashMap(JDK1.8)中红黑树的实现

ConcurrentHashMap(JDK1.8)中红黑树的实现

本文只介绍红黑树的实现 不对并发容器ConcurrentHashMap进行介绍。

红黑树的理论和基础试下可以阅读红黑树与JAVA实现

红黑树特性

1. 每个结点的或是黑色或是红色
2. 根结点是黑色
3. 每个叶子结点都是黑色（NIL）
4. 如果一个结点是红色，那么它的子结点必须是黑色
5. 对任意一结点，该结点到其叶结点树尾端NIL指针的每一条路径都包含相同数目的黑结点

ConcurrentHashMap数据结构示意图

代码实现分析 结点组成

Node

        // key的hash值
        final int hash;
        // 关键字
        final K key;
        // 存储值
        volatile V val;
        // 下一个结点
        volatile Node next;

TreeNode 作为红黑树结构的存储结构，比一般红黑树存储结构出来的next和prev，可以将这些结点变成双向的链表结构，是为了方便从链表变为红黑树，在从红黑树变成链表。在ConcurrentHashMap中，链表与红黑树的转变是依据链表中的结点数量，默认变成红黑树的链表结点个数需要大于8。

hashkeyvalnextprevparentleftrightred

static final class TreeNode extends Node {
    TreeNode parent;  // red-black tree links
    TreeNode left;
    TreeNode right;
    TreeNode prev;    // needed to unlink next upon deletion
    boolean red;

    TreeNode(int hash, K key, V val, Node next,
             TreeNode parent) {
        super(hash, key, val, next);
        this.parent = parent;
    }

    Node find(int h, Object k) {
        return findTreeNode(h, k, null);
    }

    /**
     * Returns the TreeNode (or null if not found) for the given key
     * starting at given root.
     */
    final TreeNode findTreeNode(int h, Object k, Class kc) {
        if (k != null) {
            TreeNode p = this;
            do  {
                int ph, dir; K pk; TreeNode q;
                TreeNode pl = p.left, pr = p.right;
                if ((ph = p.hash) > h)
                    p = pl;
                else if (ph