红黑树：

基于BST(平衡二叉树）产生
旋转操作： 保持高度在logN

  1. 每个节点或是红色，或是黑色
  2. 根节点是黑色
  3. 每个叶子节点是黑色
  4. 如果一个节点是红色，那么他的两个子节点都是黑的

  5. 对每个节点，从该节点到其个叶子节点的所有路径上包含相同数目的黑节点


    就是父子节点之间不能出现两个连续的红节点
    查找复杂度：logN

插入数据：

  1. 新节点赋为红色，如果未黑色，会导致根到叶子路径上有一条路上，多一个额外黑色节点
  2. 设要插入的节点未N 父为 P ，

    处理方式一

    新结点N的叔叔结点U是红色的

    处理： 只是变色
    image.png
    新节点N 叔叔节点是黑色，N 是左子
    处理方式，对祖父节点右旋
    这时会修改父指针的指向

image.png

N s是右子

先选择父， 在右旋根
image.png

数据机构

数组+ 单项链表 + 红黑树
image.png
节点较少是：数组+ 单向链表
节点较多是 大于8 ： 数组 +红黑树

基本属性

  1.  /**
  2.      * 默认容量
  3.      */
  4.     static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
  6.     /**
  7.      * 最大容量
  8.      */
  9.     static final int MAXIMUM_CAPACITY = 1 << 30;
  11.     /**
  12.      * 负载因子
  13.      */
  14.     static final float DEFAULT_LOAD_FACTOR = 0.75f;
  16.     /**
  17.     转向红黑树的阈值
  18.      */
  19.     static final int TREEIFY_THRESHOLD = 8;
  21.     /**
  22.      * 红黑树转链表的阈值
  23.      */
  24.     static final int UNTREEIFY_THRESHOLD = 6;
  26.     /**
  27.      * 转红黑树时，ｔａｂｌｅ最小长度
  28.      */
  29.     static final int MIN_TREEIFY_CAPACITY = 64;

1.7死循环的问题：

1.7会造成循环链表
1.8 采用尾插法，避免死循环

HashMap红黑树插入操作

  1. static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
  2.                                             TreeNode<K,V> x) {
  3.     // 新节点默认为红色
  4.     x.red = true;
  5.     // xp表示x的父结点，xpp表示x的祖父结点，xppl表示xpp的左孩子结点，xppr表示xpp的右孩子结点
  6.     for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
  7.         // 如果x没有父结点，则表示x是第一个结点，自动为根节点，根节点为黑色
  8.         if ((xp = x.parent) == null) {
  9.             x.red = false;
  10.             return x;
  11.         }
  12.         // 如果父结点不是红色（就是黑色），或者x没有祖父节点，那么就证明x是第二层节点，父节点为根节点
  13.         // 这种情况无需就行操作
  14.         else if (!xp.red || (xpp = xp.parent) == null)
  15.             return root;
  17.         // 进入到这里，表示x的父节点为红色
  19.         // 如果x的父节点是祖父结点的左孩子
  20.         if (xp == (xppl = xpp.left)) {
  21.             // 祖父结点的右孩子，也就是x的叔叔节点不为空，且为红色
  22.             if ((xppr = xpp.right) != null && xppr.red) {
  23.                 // 父节点和叔叔节点都为红色，只需要变色，且将x替换为祖父节点然后进行递归
  24.                 xppr.red = false;
  25.                 xp.red = false;
  26.                 xpp.red = true;
  27.                 x = xpp;
  28.             }
  29.             // 如果叔叔节点为空，或者为黑色
  30.             else {
  31.                 // 如果x节点为xp的右孩子
  32.                 if (x == xp.right) {
  33.                     // 先进行左旋，并且把x替换为xp进行递归，在左旋的过程中产生了新的root节点
  34.                     root = rotateLeft(root, x = xp);
  35.                     // x替换后，修改xp和xpp
  36.                     xpp = (xp = x.parent) == null ? null : xp.parent;
  37.                 }
  38.                 // 如果x本来是左孩子，或者已经经过了上面的左旋之后，进行变色加右旋
  39.                 if (xp != null) {
  40.                     xp.red = false;
  41.                     if (xpp != null) {
  42.                         xpp.red = true;
  43.                         root = rotateRight(root, xpp);
  44.                     }
  45.                 }
  46.             }
  47.         }
  48.         // 如果x的父节点是祖父结点的右孩子
  49.         else {
  50.             if (xppl != null && xppl.red) {
  51.                 xppl.red = false;
  52.                 xp.red = false;
  53.                 xpp.red = true;
  54.                 x = xpp;
  55.             }
  56.             else {
  57.                 if (x == xp.left) {
  58.                     root = rotateRight(root, x = xp);
  59.                     xpp = (xp = x.parent) == null ? null : xp.parent;
  60.                 }
  61.                 if (xp != null) {
  62.                     xp.red = false;
  63.                     if (xpp != null) {
  64.                         xpp.red = true;
  65.                         root = rotateLeft(root, xpp);
  66.                     }
  67.                 }
  68.             }
  69.         }
  70.     }
  71. }

红黑树的左右选操作

  1. static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,
  2.                                       TreeNode<K,V> p) {
  3.     // pp是祖父结点
  4.     // p是待旋转结点
  5.     // r是p的右孩子结点
  6.     // rl是r的左孩子结点
  7.     TreeNode<K,V> r, pp, rl;
  8.     if (p != null && (r = p.right) != null) {
  9.         // 如果rl不为空，则设置p.right=rl
  10.         if ((rl = p.right = r.left) != null)
  11.             rl.parent = p;
  12.         // 如果祖父结点为null，那么r设置为黑色，r左旋之后即为root节点
  13.         if ((pp = r.parent = p.parent) == null)
  14.             (root = r).red = false;
  15.         // 如果待旋转结点是左孩子节点
  16.         else if (pp.left == p)
  17.             pp.left = r;
  18.         // 如果待旋转结点为右孩子
  19.         else
  20.             pp.right = r;
  21.         r.left = p;
  22.         p.parent = r;
  23.     }
  24.     return root;
  25. }
  27. static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root,
  28.                                        TreeNode<K,V> p) {
  29.     TreeNode<K,V> l, pp, lr;
  30.     if (p != null && (l = p.left) != null) {
  31.         if ((lr = p.left = l.right) != null)
  32.             lr.parent = p;
  33.         if ((pp = l.parent = p.parent) == null)
  34.             (root = l).red = false;
  35.         else if (pp.right == p)
  36.             pp.right = l;
  37.         else
  38.             pp.left = l;
  39.         l.right = p;
  40.         p.parent = l;
  41.     }
  42.     return root;
  43. }

HashMap的树话

  1. final void treeify(Node<K,V>[] tab) {
  2.     TreeNode<K,V> root = null;
  3.     // 遍历当前链表
  4.     for (TreeNode<K,V> x = this, next; x != null; x = next) {
  5.         next = (TreeNode<K,V>)x.next;
  6.         x.left = x.right = null;
  7.         if (root == null) {
  8.             x.parent = null;
  9.             x.red = false;
  10.             root = x;
  11.         }
  12.         else {
  13.             K k = x.key;
  14.             int h = x.hash;
  15.             Class<?> kc = null;
  16.             // 每遍历一个链表上的元素就插入到红黑树中
  17.             for (TreeNode<K,V> p = root;;) {
  18.                 int dir, ph;
  19.                 K pk = p.key;
  21.                 // 判断待插入结点应该插入在左子树还是右子树
  22.                 // 先比较hash值
  23.                 if ((ph = p.hash) > h)
  24.                     dir = -1;
  25.                 else if (ph < h)
  26.                     dir = 1;
  27.                 // 如果hash值相等，然后比较k.compareTo(pk)
  28.                 else if ((kc == null &&
  29.                           (kc = comparableClassFor(k)) == null) ||
  30.                          (dir = compareComparables(kc, k, pk)) == 0)
  31.                     // 如果还相等则再比较identityHashCode
  32.                     dir = tieBreakOrder(k, pk);
  34.                 // 根据dir的值就知道了待插入结点该插在左子树还是右子树了
  35.                 TreeNode<K,V> xp = p;
  36.                 if ((p = (dir <= 0) ? p.left : p.right) == null) {
  37.                     x.parent = xp;
  38.                     if (dir <= 0)
  39.                         xp.left = x;
  40.                     else
  41.                         xp.right = x;
  42.                     root = balanceInsertion(root, x);
  43.                     break;
  44.                 }
  45.             }
  46.         }
  47.     }
  48.     moveRootToFront(tab, root);
  49. }

PUT的过程

  1. 生成hashCode
  2. 判断数组是否为空，初始化数组
  3. 根据hashCode算出数组下表
  4. 判断当前数组元素是否为空

如果为空：封装node 对象
如果不为空：
如果当前类型是是treeNode, 就是红黑树，把key value插入红黑树中
如果不是treeNode类型，就是链表
链表方式查找，封装node插入尾部，
判断个数是不是大于8，如果是转成红黑树
5:. modeCount ++
6。 HashMap元素size +1
7：判断是否扩容

get的过程

  1. 根据key生成hashCode
  2. 如果数组为空，直接返回
  3. 计算数组下表
  4. 当前数组是否为空，空直接返回
  5. 判断该数组第一个位置上的key是否相同
  6. 如果不等，还没有下个节点就返回
  7. 有下个节点判断是链表，还是红黑树
    1. 遍历链表
    2. 遍历红黑树
  8. 找到返回