数据结构

1. Node数组+链表
2. 当链表长度大于8并且数组长度大于64时，链表转变为红黑树。
3. 树退化成链表时机
   1. resize()扩容时，红黑树拆分的树节点小于等于6则退化成链表
   2. remove()移除元素时，如果红黑树根 root 为空，或者 root 的左子树/右子树为空，root.left.left 根的左子树的左子树为空，都会发生红黑树退化成链表

Node节点

 static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;

        Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

Tree节点

static final class TreeNode<K,V> extends LinkedHashMap.Entry<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(int hash, K key, V val, Node<K,V> next) {
            super(hash, key, val, next);
        }

        /**
         * Returns root of tree containing this node.
         */
        final TreeNode<K,V> root() {
            for (TreeNode<K,V> r = this, p;;) {
                if ((p = r.parent) == null)
                    return r;
                r = p;
            }
        }

红黑树

性质

1. 节点要么是红色要么是黑色
2. 根结点是黑色
3. 所有叶子结点都是黑色（叶子是Nil结点）
4. 每个红色结点必须有两个黑色子结点（每个路径上不能存在连续的红色结点）
5. 从任意结点到其每个叶子结点都包含相同数目的黑色结点

插入逻辑

新插入节点默认是红色，如果是黑色的话那么当前分支上就会多出一个黑色节点出来,从而破坏了黑色平衡。

1. 如果插入的是第一个节点(根节点)，红色变黑色。
2. 如果父节点为黑色，则直接插入，不需要变色。
3. 如果父节点是红色，没有叔叔节点或者叔叔节点是黑色，则以爷爷节点为支点旋转，旋转之后原来的爷爷节点变红色,原来的父节点变黑色。
4. 如果父节点为红色，叔叔节点也是红色（此种情況爷爷节点一定是黑色），则父节点和叔叔节点变黑色,爷爷节点变红色（如果爷爷节点是根节点,则再变成黑色），爷爷节点此时需要递归（把爷爷节点当做新插入的节点再次进行比较）。

小结

• 无论一个红黑树的节点多少，深度多大，当它新增节点的时候，发生颜色冲突，如果符合节点新增原理的第四条那就无需旋转，只要变色就可以成为新的红黑树。其它需要旋转才能解决的场景都是以上四种情况的变形。
• 红黑树的形成有两个阶段：成为二叉搜索树和旋转变色。

put方法

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
          //创建hashMap时并不会初始化数组，在执行第一次put时会进行扩容
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
          //通过&运算得到的数组元素如果时null，直接新建一个Node放进去
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                // 如果hash与key相同，则更新当前节点的value
                e = p;
            else if (p instanceof TreeNode)
              // 如果定位的节点时treeNode，说明已经树化了。往树中添加元素
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
              // 说明还是链表
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                      // 说明到链表末尾了
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                          // 如果追加完node之后，达到了树化的标准（长度大于等于8），就进行树化
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                      // 如果hash与key相同，则更新当前节点的value。与上面在数组中一样
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);// hashmap中空实现
                return oldValue;
            }
        }
        ++modCount;// 修改次数，并发修改异常与此相关
        if (++size > threshold)
          // 追加完元素如果大于阈值（负载因子 * 当前数组容量），扩容
            resize();
        afterNodeInsertion(evict);// hashmap中空实现
        return null;
    }

链表树化

final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
      // 当node数组大于64时才会进行树化，否则先进行扩容
        resize();
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        TreeNode<K,V> hd = null, tl = null;
      // hd： 头节点
      // tl: 尾指针
        do {
          // 把链表中的node转换为TreeNode形成半成品树
            TreeNode<K,V> p = replacementTreeNode(e, null);
            if (tl == null)
                hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        if ((tab[index] = hd) != null)
          // 树化
            hd.treeify(tab);
    }
}

生成二叉搜索树

先生成二叉搜索树，再使用balanceInsertion进行染色+旋转

final void treeify(Node<K,V>[] tab) {
    TreeNode<K,V> root = null;
    for (TreeNode<K,V> x = this, next; x != null; x = next) {// 链表循环
        next = (TreeNode<K,V>)x.next;
        x.left = x.right = null;
      // 当没有根节点的时候，创建根节点，设置为黑色
        if (root == null) {
            x.parent = null;
            x.red = false;
            root = x;
        }
        else {
          // 生成普通的二叉搜索树
            K k = x.key;
            int h = x.hash;
            Class<?> kc = null;
            for (TreeNode<K,V> p = root;;) {// 树内循环
                int dir, ph;
                K pk = p.key;
              // 当前节点hash大于插入节点hash，向左遍历，往左子树放
                if ((ph = p.hash) > h)
                    dir = -1;
              // 当前节点hash大于插入节点hash，向右遍历，往右子树放
                else if (ph < h)
                    dir = 1;
                else if ((kc == null &&
                          (kc = comparableClassFor(k)) == null) ||
                         (dir = compareComparables(kc, k, pk)) == 0)
                  // HashMap不使用comparable作为是否替换旧的value的条件，只会使用hash与equals
                  // 此处使用compareComparables判断插入节点往左子树插入还是往右子树插入
                   // hash值相同时，但又无法比较时，判断插入节点是左还是右
                  // tieBreakOrder 如果两个对象的className一样 返回0，hash一样，返回-1。按照下面dir<=0判断，都是往左差。
                  // 没发判断的时候，只要用一个统一的判断方法即可。
                    dir = tieBreakOrder(k, pk);

                TreeNode<K,V> xp = p;
              // 如果当前节点的左或右节点是空，说明找到插入位置了
                if ((p = (dir <= 0) ? p.left : p.right) == null) {
                  // 插入节点指向父节点
                    x.parent = xp;
                  // dir<=0 插入到左边
                    if (dir <= 0)
                        xp.left = x;
                    else
                      // dir>0 插入到右边
                        xp.right = x;
                    // 变色与旋转
                    root = balanceInsertion(root, x);
                    break;
                }
            }
        }
    }
  // 确保root是根节点
    moveRootToFront(tab, root);
}

变色与旋转

static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
                                            TreeNode<K,V> x) {
  // 默认时红色
    x.red = true;
  // 从x节点开始遍历整棵树
    for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
      // xp：父亲
      // xpp: 爷爷
      // xxpl: 爷爷的左子节点
      // xxpr: 爷爷的右子节点
        if ((xp = x.parent) == null) {
          // 如果被处理的节点没有父节点，说明是根节点
            x.red = false;
            return x;
        }
        else if (!xp.red || (xpp = xp.parent) == null)
          // 如果父节点是黑（参考插入逻辑第二条）的或者爷爷节点是null（说明父节点根节点）。不需要处理（只要x.red=true就行）
          // 正常情况下“根节点”一定为黑色。？
            return root;
        if (xp == (xppl = xpp.left)) {// 进入这个if时父节点是红色，那么爷爷节点是黑色的（如果存在）
          // 如果父节点是爷爷节点的左孩子
            if ((xppr = xpp.right) != null && xppr.red) {
              // 如果爷爷节点的右孩子存在且是红色，此时，父节点与叔叔节点都是红色，此时需要父叔节点变为黑色，爷爷节点变为红色。
              // 然后红色的爷爷节点作为接下来要处理的节点进行递归处理
                xppr.red = false;
                xp.red = false;
                xpp.red = true;
                x = xpp;
            }
            else {
              // 如果叔叔节点不是红色或者不存在，如果这个节点时右节点，则为下面两种情况
                        //       xpp                                    xpp
              //      /                                             / \ 
              //       xp(red)    或者     (red)xp xppr(black)
              //         \                                          \
              //        x(red)                               x(red)
                if (x == xp.right) {
                    root = rotateLeft(root, x = xp);//先以xp节点左旋
                    xpp = (xp = x.parent) == null ? null : xp.parent;
                }
                if (xp != null) {// 上面左旋完之后
              //       xpp                                  xpp
              //      /                                             / \ 
           // （原x）xp(red)    或者     (red)xp xppr(black)
              //      /                                             /
              //   x（原xp）(red)              x（原xp）(red)  
                    xp.red = false;
                    if (xpp != null) {
                        xpp.red = true;
                      // 以xpp节点进行右旋
                        root = rotateRight(root, xpp);
                    }
                }
            }
        }
        else { // 与上面镜像
            if (xppl != null && xppl.red) {
                xppl.red = false;
                xp.red = false;
                xpp.red = true;
                x = xpp;
            }
            else {
                if (x == xp.left) {
                    root = rotateRight(root, x = xp);
                    xpp = (xp = x.parent) == null ? null : xp.parent;
                }
                if (xp != null) {
                    xp.red = false;
                    if (xpp != null) {
                        xpp.red = true;
                        root = rotateLeft(root, xpp);
                    }
                }
            }
        }
    }
}

左旋

static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,
                                              TreeNode<K,V> p) {
            TreeNode<K,V> r, pp, rl;
                    // rl：右节点的左孩子
                    // pp：p的父节点
                    // r：p的右节点
            //       p
            //        \
            //         r
            //        /
            //       rl
            if (p != null && (r = p.right) != null) {
              // 既然是左旋，那么旋转节点的右节点就不能为null
                if ((rl = p.right = r.left) != null)
                    rl.parent = p;
              //       r
              //      /
              //     p
              //      \
              //       r1
                if ((pp = r.parent = p.parent) == null)
                  // 说明p是根节点。旋转之后r就是根节点
                    (root = r).red = false;
                else if (pp.left == p)
                  // 说明p节点是父节点的左节点，旋转后r为p的父节点，父节点的左子节点为r
                    pp.left = r;
                else
                  // 说明p节点是父节点的右节点，旋转后r为p的父节点，父节点的右子节点为r
                    pp.right = r;
                r.left = p;
                p.parent = r;
              //    r
              //   /
              //  p
              //   \
              //    r1
            }
            return root;
        }

右旋

与左旋镜像

static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root,
                                               TreeNode<K,V> p) {
            TreeNode<K,V> l, pp, lr;
            if (p != null && (l = p.left) != null) {
                if ((lr = p.left = l.right) != null)
                    lr.parent = p;
                if ((pp = l.parent = p.parent) == null)
                    (root = l).red = false;
                else if (pp.right == p)
                    pp.right = l;
                else
                    pp.left = l;
                l.right = p;
                p.parent = l;
            }
            return root;
        }

往树中添加元素

插入新节点从root节点往下遍历分为4种情况：

1. 要插入的节点hash值小于遍历所在节点hash，遍历左子树
2. 要插入的节点hash值大于遍历所在节点hash，遍历右子树
3. 要插入的节点hash值等于遍历所在节点hash，并且key值相等返回该节点
4. 要插入的节点hash值等于遍历所在节点hash，但是key不等时，发生hash冲突。此时又分为两种情况。
   遍历该节点的左右子节点是否存在hash相等，并且key也相等的节点，有则返回该节点
   如果没有则调用tieBreakOrder(k, pk)方法，比较key值，确定是遍历左子树还是右子树

final TreeNode putTreeVal(HashMap map, Node[] tab,
                                       int h, K k, V v) {
            Class kc = null;// key（HashMap中的key-valule的key）的class
            boolean searched = false;
            TreeNode root = (parent != null) ? root() : this;
            for (TreeNode p = root;;) {
                int dir, ph; K pk;
                // dir：-1表示添加的元素小于当前节点，往左子树上放；1表示添加的元素大于当前节点，往右子树上放。
                // ph：当前节点的hash值
                // pk：当前节点的key
                if ((ph = p.hash) > h)// 与当前元素比较hash大小
                    dir = -1;
                else if (ph < h)// 与当前元素比较hash大小
                    dir = 1;
                else if ((pk = p.key) == k || (k != null && k.equals(pk)))// 如果key相等，则更新当前元素。与putVal中一样
                    return p;
                else if ((kc == null && 
                          (kc = comparableClassFor(k)) == null) ||
                         (dir = compareComparables(kc, k, pk)) == 0) {
                  // comparableClassFor 判断key有没有实现compareble接口。有个话返回Class，null就是没有实现
                  // compareComparables 如果当前节点的key与添加元素Class相同，则用compareTo比较大小(判断往左子树还是右子树插)
                  // 当hash相同但是key不同 &&（添加的元素没有实现comparable接口 || 实现了comparable接口但是compareTo相等）进入此方法。
                    if (!searched) {
                        TreeNode q, ch;
                      // q：当前树中与添加元素key相同的元素
                      // ch: 子节点
                        searched = true;
                        if (((ch = p.left) != null &&
                             (q = ch.find(h, k, kc)) != null) ||
                            ((ch = p.right) != null &&
                             (q = ch.find(h, k, kc)) != null))
                          // find()为从左右子树中寻找key与hash相同的节点（二叉树遍历），找到则更新当前元素。与putVal中一样
                            return q;
                    }
                  // 说明没有一样的，那就区分一下谁大谁小
                    dir = tieBreakOrder(k, pk);
                }

                TreeNode xp = p;
                if ((p = (dir <= 0) ? p.left : p.right) == null) {
                  // 如果p的左或者右节点是null，则说明找到插入位置
                    Node xpn = xp.next;
                  // 新建一个节点
                    TreeNode x = map.newTreeNode(h, k, v, xpn);
                    if (dir <= 0)
                        xp.left = x;
                    else
                        xp.right = x;
                    xp.next = x;
                    x.parent = x.prev = xp;
                    if (xpn != null)
                        ((TreeNode)xpn).prev = x;
                  // 染色&旋转
                    moveRootToFront(tab, balanceInsertion(root, x));
                    return null;
                }
            }
        }