什么是HashMap容器

Implementation notes.
实现注意事项

This map usually acts as a binned (bucketed) hash table, 
but when bins get too large, they are transformed into bins of TreeNodes, 
each structured similarly to those in  java.util.TreeMap. 
Most methods try to use normal bins, but  relay to TreeNode methods when applicable (simply by checking instanceof a node).  
Bins of TreeNodes may be traversed and used like any others, but additionally support faster lookup when overpopulated. 
However, since the vast majority of bins in normal use are not overpopulated, checking for existence of tree bins may be delayed in the course of table methods.
这个映射通常充当一个分箱(桶)哈希表，但是当容器太大时，它们被转换为TreeNodes的容器，每个容器的结构类似于java.util.TreeMap中的容器。
大多数方法尝试使用普通的bin，但在适用的情况下中继到TreeNode方法(简单地通过检查节点的实例)。
TreeNodes的容器可以像其他容器一样被遍历和使用，但是在过度填充时还支持更快的查找。
然而，由于正常使用的绝大多数容器都没有过度填充，所以在表方法的过程中可能会延迟检查树容器的存在。

....

Because TreeNodes are about twice the size of regular nodes, we use them only when bins contain enough nodes to warrant use (see TREEIFY_THRESHOLD). 
And when they become too small (due to removal or resizing) they are converted back to plain bins.  
In usages with well-distributed user hashCodes, tree bins are rarely used.  
Ideally, under random hashCodes, the frequency of nodes in bins follows a Poisson distribution (http://en.wikipedia.org/wiki/Poisson_distribution) 
with a  parameter of about 0.5 on average for the default resizing threshold of 0.75,
although with a large variance because of resizing granularity. 
Ignoring variance, the expected  occurrences of list size k are (exp(-0.5) * pow(0.5, k) /  factorial(k)). 
The first values are:
因为TreeNodes大约是常规节点的两倍大，所以我们只在容器包含足够的节点以保证使用时才使用它们(参见TREEIFY_THRESHOLD)。
当它们变得太小(由于删除或调整大小)时，它们会被转换回普通的容器。
在分布良好的用户hashCodes的用法中，很少使用树容器。
理想情况下，在随机hashCodes下，容器中节点的频率遵循泊松分布(http://en.wikipedia.org/wiki/Poisson_distribution)，
对于默认的调整大小阈值0.75，该分布的参数平均约为0.5，尽管由于调整大小粒度的差异很大。
忽略方差，列表大小k的期望出现次数为(exp(-0.5) * pow(0.5, k) / factorial(k))。第一个值是:

0:    0.60653066
1:    0.30326533
2:    0.07581633
3:    0.01263606
4:    0.00157952
5:    0.00015795
6:    0.00001316
7:    0.00000094
8:    0.00000006  千万分之6
more: less than 1 in ten million
如果是更多的话，会低于千万分之一

...

主要原因是在于为了扩容时候的数据迁移，因为在源码中，HashMap是一个一个槽位的将数据迁移。
如果限制了是2的倍数是怎么样的呢？
如4个槽位各有四个数据
【1】 5，9，13，17
【2】 6，10，14，18
【3】 7，11，15，19
【4】 8，12，16，20
扩容成了8个槽位，则数据必然散落在原本的槽位和与之倍数的槽位上
【1】 9，17
【2】 10，18
【3】 11，19
【4】 12，20
【5】 5，13
【6】 6，14
【7】 7，15
【8】 8，16
这也是为什么扩容的时候只用设置两个链表结构的原因：
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;

反之如果是1.5倍，那么散落在的槽位就不确定了，那么我们就要面对更复杂的情况，必然要按照槽位设置多个链表结构
如8个槽位就要8个链表结构，槽位越多，对应的花销更多，所以显得不划算

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable

//明显是单链表的节点
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;
   }

   public final K getKey()        { return key; }
   public final V getValue()      { return value; }
   public final String toString() { return key + "=" + value; }

   public final int hashCode() {
       return Objects.hashCode(key) ^ Objects.hashCode(value);
   }

   public final V setValue(V newValue) {
       V oldValue = value;
       value = newValue;
       return oldValue;
   }

   public final boolean equals(Object o) {
       if (o == this)
           return true;
       if (o instanceof Map.Entry) {
           Map.Entry<?,?> e = (Map.Entry<?,?>)o;
           if (Objects.equals(key, e.getKey()) &&
               Objects.equals(value, e.getValue()))
               return true;
       }
       return false;
   }
}

//LinkedHashMap类的Entry结构，将单链表节点包装之后具备双向链表节点的功能
static class Entry<K,V> extends HashMap.Node<K,V> {
   Entry<K,V> before, after;
   Entry(int hash, K key, V value, Node<K,V> next) {
       super(hash, key, value, next);
   }
}
//所以TreeNode其实只是在Node节点上做了包装，所以这个树节点其实是包含了树和双向链表节点两者的功能
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;
       }
   }
...
}

//默认初始容量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//默认最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;//即536,870,912
//默认加载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//默认转成树结构的阈值
static final int TREEIFY_THRESHOLD = 8;
//由树转回为链表结构的阈值
static final int UNTREEIFY_THRESHOLD = 6;
//默认转成树时候数组的最小容量
static final int MIN_TREEIFY_CAPACITY = 64;

/* ---------------- Fields -------------- */
//存放数据的集合
transient Node<K,V>[] table;
//用于迭代器使用的
transient Set<Map.Entry<K,V>> entrySet;
//数据个数
transient int size;
//修改次数记录
transient int modCount;
//扩容的阈值，默认是（容量*加载因子）
int threshold;
//哈希表的加载因子
final float loadFactor;

//指定容量和负载因子
public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException(...);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException(...);
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);
}

//这个方法保证得出来的容量是2的N次方，把不足2的N次方的向上取到2的N次方
//如3得4，5得8,10得16
//设计的巧妙点在于使用了>>>表示无符号右移，也叫逻辑右移与异或方法
//减1，是为了让二进制尽可能多的出现1，如1000000，减一后变为0111111。当然如果是1000001，这种会变为1000000【但影响并不大】。
//就以1000001为例子，减一后为1000000
//其次当右移一位之后再异或就会保证前两位是1，即1000000|100000=1100000
//所以第二次直接右移两位再异或，即1100000|11000=1111000
//第三次就右移四位，即1111000|111=1111111
//所以最后+1，是会变成10000000即128
static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

//指定容量，默认负载因子为0.75
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

//容量使用默认值16，负载因子也为默认值0.75
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

//传入有数据的Map
public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}

final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
    int s = m.size();
    if (s > 0) {
        //初始化容器
        if (table == null) { // pre-size
            //使得计算出来的容量不大于阈值，+1是为了向上取整，因为整除是会舍弃小数点后面的
            float ft = ((float)s / loadFactor) + 1.0F;
            //限制不大于最大容量
            int t = ((ft < (float)MAXIMUM_CAPACITY) ? (int)ft : MAXIMUM_CAPACITY);
            //因为有可能是上面那种设置了容量但是没有初始化table的情况
            if (t > threshold)
                threshold = tableSizeFor(t);
        }
        //说明table已经初始化过了；判断传入map的size是否大于当前map的threshold，如果是，必须要resize，预先扩大容量，再put元素
        else if (s > threshold)
            resize();
        for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
            K key = e.getKey();
            V value = e.getValue();
            //塞入数据
            putVal(hash(key), key, value, false, evict);
        }
    }
}

//加入元素
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

//生成的hash是key的hashCode的高16位与低16位相与
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

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)
        n = (tab = resize()).length;
    //如果存在数组，利用相与的方式获得下标【二进制中相与是不可能大于最小值的】
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        //如果数组中已经有节点了
        Node<K,V> e; K k;
        //如果key是相等的
        if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        //如果节点是树节点，就用树节点的方式存入
        else if (p instanceof 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);
                    //判断是否满足转成树节点的条件【链表长度为8】
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                //如果当前遍历到的数据和要插入的数据的 key 是一样,和上面之前的一样,赋值给变量 e,下面替换内容
                if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        //进行内容的替换
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e); //扩展方法
            return oldValue;
        }
    }
    ++modCount;
    //达到阈值便要扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict); //扩展方法
    return null;
}

//这里就涉及到了Node节点的创建了
Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
    return new Node<>(hash, key, value, next);
}

final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    //限制了数组最少是64的长度
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    //满足数组长度64，链表长度8，就开始转为树结构
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        TreeNode<K,V> hd = null, tl = null;
        //先将单链表转为双向链表
        do {
            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);
    }
}

final Node<K,V>[] resize() {
   Node<K,V>[] oldTab = table;
   int oldCap = (oldTab == null) ? 0 : oldTab.length;
   int oldThr = threshold;
   int newCap, newThr = 0;
   //第一阶段：计算出新的newCap(扩容后的容量)和newThr(扩容后阈值)
   if (oldCap > 0) {
       if (oldCap >= MAXIMUM_CAPACITY) {
           threshold = Integer.MAX_VALUE;
           return oldTab;
       }
       //新容量为旧容量的2倍
       else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
           newThr = oldThr << 1; // double threshold
   }
   else if (oldThr > 0) // initial capacity was placed in threshold
       newCap = oldThr;
   else {      //如果数组还没有则将默认值设置进去，默认容量16，阈值为16*0.75=12
       newCap = DEFAULT_INITIAL_CAPACITY;
       newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
   }
   if (newThr == 0) {
       float ft = (float)newCap * loadFactor;
       newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE);
   }
   threshold = newThr;

   //第二阶段：根据newCap和newThr构造出新的newTab
   @SuppressWarnings({"rawtypes","unchecked"})
   Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
   //这里其实是线程不安全的，因为table的引用此时指向了新数组【而新数组还没有被赋值】
   table = newTab;
   if (oldTab != null) {
       for (int j = 0; j < oldCap; ++j) {
           Node<K,V> e;
           if ((e = oldTab[j]) != null) {
               oldTab[j] = null;
               //第一种情况，如果是单节点，直接存入数组槽位
               if (e.next == null)
                   newTab[e.hash & (newCap - 1)] = e;
               //如果是树节点，则开始割裂成两个子树
               else if (e instanceof TreeNode)
                   ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
               //如果是链表
               else { 
                   //构建两个链表结构【这就是为什么要进行两倍扩容的原因：因为假设是4个槽位，扩容到8个槽位，那么原本在第3槽位的数据散列之后的落点必然是在3与7两者之一】
                   Node<K,V> loHead = null, loTail = null;
                   Node<K,V> hiHead = null, hiTail = null;
                   Node<K,V> next;
                   do {
                       next = e.next;
                       if ((e.hash & oldCap) == 0) {
                           if (loTail == null)
                               loHead = e;
                           else
                               loTail.next = e;
                           loTail = e;
                       }
                       else {
                           if (hiTail == null)
                               hiHead = e;
                           else
                               hiTail.next = e;
                           hiTail = e;
                       }
                   } while ((e = next) != null);
                   if (loTail != null) {
                       loTail.next = null;
                       newTab[j] = loHead;
                   }
                   if (hiTail != null) {
                       hiTail.next = null;
                       newTab[j + oldCap] = hiHead;
                   }
               }
           }
       }
   }
   return newTab;
}

//本质上也是先弄成两个链表
//然后判断存入槽位的该是链表还是树
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
       TreeNode<K,V> b = this;
       //也是创建了两个链表结构
       TreeNode<K,V> loHead = null, loTail = null;
       TreeNode<K,V> hiHead = null, hiTail = null;
       int lc = 0, hc = 0;
       //这里的操作本质上与链表结构的操作没什么不同
       for (TreeNode<K,V> e = b, next; e != null; e = next) {
           next = (TreeNode<K,V>)e.next;
           e.next = null;
           if ((e.hash & bit) == 0) {
               if ((e.prev = loTail) == null)
                   loHead = e;
               else
                   loTail.next = e;
               loTail = e;
               ++lc;
           }
           else {
               if ((e.prev = hiTail) == null)
                   hiHead = e;
               else
                   hiTail.next = e;
               hiTail = e;
               ++hc;
           }
       }

       //对生成的链表进行判断
       if (loHead != null) {
           //要么不满足条件，将退化成为链表，即将TreeNode结构转回为Node
           if (lc <= UNTREEIFY_THRESHOLD)
               tab[index] = loHead.untreeify(map);
           else {
               //如果还是树的话，针对新链表再次树化一遍
               tab[index] = loHead;
               if (hiHead != null) // (else is already treeified)
                   loHead.treeify(tab);
           }
       }
       if (hiHead != null) {
           if (hc <= UNTREEIFY_THRESHOLD)
               tab[index + bit] = hiHead.untreeify(map);
           else {
               tab[index + bit] = hiHead;
               if (loHead != null)
                   hiHead.treeify(tab);
           }
       }
   }

final Node<K,V> untreeify(HashMap<K,V> map) {
  Node<K,V> hd = null, tl = null;
  for (Node<K,V> q = this; q != null; q = q.next) {
      //重新转为Node节点
      Node<K,V> p = map.replacementNode(q, null);
      if (tl == null)
          hd = p;
      else
          tl.next = p;
      tl = p;
  }
  return hd;
}

Node<K,V> replacementNode(Node<K,V> p, Node<K,V> next) {
   return new Node<>(p.hash, p.key, p.value, next);
}

final void treeify(Node<K,V>[] tab) {
  TreeNode<K,V> root = null;  // 定义树的根节点
  for (TreeNode<K,V> x = this, next; x != null; x = next) {  // 遍历链表，x指向当前节点、next指向下一个节点
      next = (TreeNode<K,V>)x.next;
      x.left = x.right = null;  // 设置当前节点的左右节点为空
      if (root == null) {  // 如果还没有根节点
          x.parent = null;  // 当前节点的父节点设为空
          x.red = false; // 当前节点的红色属性设为false（把当前节点设为黑色）
          root = x;  // 根节点指向到当前节点
      }
      else {  // 如果已经存在根节点了
          K k = x.key;  // 取得当前链表节点的key
          int h = x.hash;  // 取得当前链表节点的hash值
          Class<?> kc = null;
          for (TreeNode<K,V> p = root;;) {  // 从根节点开始遍历，此遍历没有设置边界，只能从内部跳出
              int dir, ph;
              K pk = p.key;  // 当前树节点的key
              if ((ph = p.hash) > h)  // 如果当前树节点hash值 大于 当前链表节点的hash值
                  dir = -1;  // 标识当前链表节点会放到当前树节点的左侧
              else if (ph < h)
                  dir = 1;  // 标识当前链表节点会放到当前树节点的右侧

              //如果两个节点的key的hash值相等，那么还要通过其他方式再进行比较，
              //如果当前链表节点的key实现了comparable接口，并且当前树节点和链表节点是相同Class的实例，那么通过comparable的方式再比较两者。
              //如果还是相等，最后再通过tieBreakOrder比较一次
              else if ((kc == null && (kc = comparableClassFor(k)) == null) || (dir = compareComparables(kc, k, pk)) == 0)
                  dir = tieBreakOrder(k, pk);

              TreeNode<K,V> xp = p;
              //挂载之后，还需要重新把树进行平衡。平衡之后，就可以针对下一个链表节点进行处理了。
              //为什么需要再平衡，基于红黑树的定义【红黑树（Red Black Tree） 是一种自平衡二叉查找树】：
              //性质1. 结点是红色或黑色。 
              //性质2. 根结点是黑色。 
              //性质3. 所有叶子都是黑色。（叶子是NIL结点）
              //性质4. 每个红色结点的两个子结点都是黑色。（从每个叶子到根的所有路径上不能有两个连续的红色结点）
              //性质5. 从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点。
              if ((p = (dir <= 0) ? p.left : p.right) == null) {
                  x.parent = xp;
                  if (dir <= 0)
                      xp.left = x;
                  else
                      xp.right = x;
                  root = balanceInsertion(root, x);  // 重新平衡
                  break;
              }
          }
      }
  }
  // 把所有的链表节点都遍历完之后，最终构造出来的树可能经历多个平衡操作，根节点目前到底是链表的哪一个节点是不确定的
  // 因为我们要基于树来做查找，所以就应该把 tab[N] 得到的对象一定根节点对象，而目前只是链表的第一个节点对象，所以要做相应的处理。
  moveRootToFront(tab, root);
}

//将根结点放置于数组的槽位上，便于一开始就从树的头结点开始遍历
static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {
  int n;
  //红黑树根节点不能为空，table数组不能为空
  if (root != null && tab != null && (n = tab.length) > 0) {
      //获取红黑树根节点的应该放入的下标位置
      int index = (n - 1) & root.hash;
      TreeNode<K,V> first = (TreeNode<K,V>)tab[index];
      //如果当前的下标位置放得对象与需要验证的对象，不是同一个对象
      if (root != first) {
          Node<K,V> rn;
          //设置红黑树根节点的值为改下标位置的值
          tab[index] = root;
          TreeNode<K,V> rp = root.prev;
          //重置红黑树根节点的上下级关系，主要是调整root,root.prev,root.next,first;四者的关系
          if ((rn = root.next) != null)
              ((TreeNode<K,V>)rn).prev = rp;
          if (rp != null)
              rp.next = rn;
          if (first != null)
              first.prev = root;
          root.next = first;
          root.prev = null;
      }
      assert checkInvariants(root);
  }
}

static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root, TreeNode<K,V> x) {
  //默认是红色节点
  x.red = true;
  //循环当前节点的树结构
  for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
      //如果当前对象的父节点为空，则认为是根节点，根节点不能为红节点，返回该节点
      if ((xp = x.parent) == null) {
          x.red = false;
          return x;
      }
      //如果父节点是红色节点，以父节点的父节点为空，当前节点为根节点的孙子，设置该节点为红色，并返回
      else if (!xp.red || (xpp = xp.parent) == null)
          return root;
      //如果当前节点的父节点和父节点的父节点的左节点相等
      if (xp == (xppl = xpp.left)) {
          //如果当前节点的父节点的父节点的右节点是红色的
          if ((xppr = xpp.right) != null && xppr.red) {
              xppr.red = false;
              xp.red = false;
              xpp.red = true;
              x = xpp;
          }
          else {
              //如果当前节点与父节点的右节点相等，则进行左旋转
              if (x == xp.right) {
                  root = rotateLeft(root, x = xp);
                  xpp = (xp = x.parent) == null ? null : xp.parent;
              }
              //父节点不为空，设置父节点的颜色，及是否右旋转
              if (xp != null) {
                  xp.red = false;
                  if (xpp != null) {
                      xpp.red = true;
                      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;
  if (p != null && (r = p.right) != null) {
      if ((rl = p.right = r.left) != null)
          rl.parent = p;
      if ((pp = r.parent = p.parent) == null)
          (root = r).red = false;
      else if (pp.left == p)
          pp.left = r;
      else
          pp.right = r;
      r.left = p;
      p.parent = r;
  }
  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;
}