[数据结构与算法]HashMap

前言

HashMap的整体结构是由Node<K, V>形成的数组table，table中每个下标对应的位置被称为bin。每个bin保存的结果只有三种，分别是null，链表和红黑树。而且每个下标中都是相互独立的，比如下标为0的是null，下标为1的是链表，下标为2的是红黑树。

每个节点(Node<K, V>)中保存着key，由hash(key)对table长度取余就知道保存的下标位置。如果有多个节点的保存地址出现了重复，那么就会出现链表的结构。

当某个bin中链表的长度大于了TREEIFY_THRESHOLD，并且table的总长度大于了MIN_TREEIFY_CAPACITY，才会出现树化操作，否则都是扩容。

扩容操作的时候可能出现原先在一个bin中的内容分裂到了别的bin上。注意，这里分裂出去只可能分裂到一个新的bin上，新下标 = 旧下标 + 旧长度。也就是有的方法中定义loHead, loTail, hiHead, hiTail的原因。

1.HashMap

public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}

2.putMapEntries

final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
    int s = m.size();
    if (s > 0) {
        if (table == null) {
            float ft = ((float)s / loadFactor) + 1.0F;
            int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                     (int)ft : MAXIMUM_CAPACITY);
            if (t > threshold)
                threshold = tableSizeFor(t);
        }
        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);
        }
    }
}

3.tableSizeFor

// 很简单的原理，你随便将一个数字转化为二进制数，然后只管盯住最高位的1。
// 通过下面的>>>1操作，可以得到将这个1往右移一位的结果，与原先的值做按位或运算，那么1就多了一个。
// 而第二次右移2位的时候，相当于把原始最高位的1往后移动2位，第一次新得到的1往右移动两位，就是和原来最高位的结果相差了三位。
// 可以发现，从最高位开始的1，右边的每一位数都会变成1，最终返回结果加上1以后不断进位，就变成了大于等于cap的最小二次幂。
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;
}

4.resize

/** 
这里的hash & oldCap的原理如下
从putVal的方法中，我们可以知道原先我们是通过hash值对总长度取余得出的结果。
而我们现在的总长度已经扩展为了原先的两倍，那么取余以后的结果是否会发生变化，只要看对应位是0还是1.
举例：hash是25，原先长度是16，resize以后长度是32.
25 & (16 - 1)		25 & (32 - 1)
 00011001		    00011001
&00001111		   &00011111
 00001001		    00011001
因为长度翻倍了，所以转为二进制时，末尾连续的1长度加了1，只要观察增加的那位1上面是不是也是1就能得出是否发生了变化。也就知道位置是否发生变化了。
*/
final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    // oldCap:当前table的总容量.
    // oldThr:当前table重构的阈值。
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
  	// newCap:重构以后的总容量.
    // newThr:重构以后想要再次的阈值。
    int newCap, newThr = 0;
    if (oldCap > 0) {
        // 如果已经超过了最大的容量，那么就改变一下重构的阈值，并直接返回，因为已经无法扩容了。
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // 没有到达最大容量且容量大于等于原始的默认值，就将newCap和newThr设置为原始的两倍，双倍扩容。
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1;
    }
    // oldCap == 0，即没有指定容量，但是指定了threshold，所以newCap = oldThr即可。
    else if (oldThr > 0)
        newCap = oldThr;
    // oldCap和oldThr都没有指定，那就直接使用默认的，这里newCap = 10,newThr = 12.
    else {
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    // 以上的三种情况，保证了newCap一定是有内容的。
    // 计算出newThr, 如果是大于最大容量了，就只取Integer.Max.MAX_VALUE
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    // 保证了threshold一定有内容
    threshold = newThr;
    @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;
            // 如果复制出来的table中下标为j的位置上内容不为空，即要复制到新的table中去
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                // 说明这个节点的内容只有一个Node，可以直接复制走
                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 {
                    // 没有发生位移使用的链表
                    Node<K,V> loHead = null, loTail = null;
                    // 发生位移以后使用的链表
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    // 一直循环下去，可以按序的取出下标为j中的链表，并且这个链表中每个节点的哈希都是一样的。
                    do {
                        next = e.next;
                        // 说明从老的table中复制到新的table中下标位置没有发生变化
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        // 说明从老的table中复制到新的table中下标位置发生变化
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    // 简单的链接到新的table中，位置不变
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    // 位置发生了变化，扩大了oldCap，也就是增加的容量数量。
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

5.split

final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
    // 这里this指的是调用者Node，也即某个下标为index的位置上保存的链表头
    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) {
            // 第一次：e就是头节点，所以e.prev为空，并令尾巴指向e。
            // 后续循环时，每次e先主动往后移动，e.prev指向了loTail，并将loTail.nexr指向e,最后再将loTail往后移动。
            // 最终形成了一条链表
            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) {
        // 如果达不到非树化标准，将index下标中的所有节点，重新替换为只有next指针的节点。
        if (lc <= UNTREEIFY_THRESHOLD)
            tab[index] = loHead.untreeify(map);
        else {
            // 否则，将头节点保存到index下标位置上
            tab[index] = loHead;
            // 如果有一部分的节点被分走了，那么需要重新生成红黑树。
            if (hiHead != null)
                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);
        }
    }
}

6.untreeify

final Node<K,V> untreeify(HashMap<K,V> map) {
    Node<K,V> hd = null, tl = null;
    // 从当前节点开始遍历，这个this指的是index下标的链表头
    for (Node<K,V> q = this; q != null; q = q.next) {
        // 重新创建节点，依次的替换整个链表中所有的节点,为了断开所有的left,right,parent
        Node<K,V> p = map.replacementNode(q, null);
        if (tl == null)
            hd = p;
        else
            tl.next = p;
        tl = p;
    }
    return hd;
}

7.putVal

/**
这里的hash是单纯通过key计算出来的。所以存在以下三种情况
1.两者的key不相同，计算出的hash不同。
2.两者的key不相同，计算出的hash相同。注意，即便是这中hash不相同的情况，也会出现在table中同一个下标出现的情况。因为两者都是对长度取余数，举例，长度是16的table，对于hash是9和25的内容，都是放到同一个bin中。
3.两者的key相同，hash必定相同。
保存下标的计算原理：hash值对最大容量取余数。
假设计算出来的hash值是25，长度为16，根据计算公式25 & (16-1)得到以下结果
 00011001
&00001111
 00001001
可以看出，因为长度已经是2的幂了，所以长度-1就会出现全1的二进制数，由&运算符的运算规律，可以得出结果就是hash转化为二进制以后末尾几位的值。注意，我这里前面加了这么多的前置0，是为了resize的时候可以由更清晰的感受。
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // 复制原先的table,并检测原先的table是不是为空，空的话重构一下并重新复制。
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 通过(n - 1) & hash计算出保存在tab的下标位置，并判断是否为空。空的话就可以直接插入一个Node进去。
    // 而n - 1是固定的，所以只要看hash即可，即hash相同，保存的下标位置就会相同。
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    // 说明该位置上已经有内容了，需要改成链表或者红黑树。
    else {
        Node<K,V> e; K k;
        // 如果是因为key一模一样导致的hash碰撞，那会覆盖前一个的内容。
        // 比如先put("李", "李白");再put("李", "李大白");只会剩下李大白那项。
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // key不同，但是也出现了hash碰撞的情况。
        // 如果该位置的内容已经是棵树了，按照树的方式插入。
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        // 按照链表的方式插入。
        else {
            // 计量，看看链表的长度是多长了，如果到达了一定长度，转化为树。
            for (int binCount = 0; ; ++binCount) {
                // 如果循环到末尾都没有发现key相同的，插入一个新的节点到尾部。
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    // 如果到了树化的界限，那么进行树化操作。
                    if (binCount >= TREEIFY_THRESHOLD - 1)
                        treeifyBin(tab, hash);
                    break;
                }
                // 检测链表中是否有key相同的部分，如果有直接掠过，而不是和上面举例的地方一样进行替换了。
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        // 循环到了链表中间，发现有key重复的部分，退出了循环。
        if (e != null) {
            // 取出重复节点的value
            V oldValue = e.value;
            // 根据一开始传入的参数，onlyIfAbsent:是否只有在没有的情况才存入?false代表有的时候也要替换掉。
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    // 判断是否到达了扩容重构的阈值。
    if (++size > threshold)
        resize();	
    afterNodeInsertion(evict);
    return null;
}

8.putTreeVal

final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab, int h, K k, V v) {
    Class<?> kc = null;
    boolean searched = false;
    // 这里的parent指的是调用这个方法的node的parent
    // 如果父节点确实存在，说明当前节点不是父节点，需要寻找根节点。
    // 否则当前节点就是根节点。
    TreeNode<K,V> root = (parent != null) ? root() : this;
    for (TreeNode<K,V> p = root;;) {
        int dir, ph; K pk;
        // 先根据hash值进行排序
        if ((ph = p.hash) > h)
            dir = -1;
        else if (ph < h)
            dir = 1;
        // 如果hash值比较不出来，对比两者的key是否相同，相同就直接返回p，如果出现了key相同的内容，需要在putVal中根据ifOnlyAbsent决定是否覆盖。
        else if ((pk = p.key) == k || (k != null && k.equals(pk)))
            return p;
        // 如果K类没有实现Comparable接口
        // 如果K类实现了Comparable<?>接口，但是两者的key实现的Comparable不可比或者比较结果为0，需要进一步比较
        else if ((kc == null &&
                  (kc = comparableClassFor(k)) == null) ||
                 (dir = compareComparables(kc, k, pk)) == 0) {
            if (!searched) {
                TreeNode<K,V> q, ch;
                searched = true;
                // 如果p拥有左子树，且左子树中包含目标，或者在右子树中同理，直接返回。返回的结果是hash和key完全相同的节点。说明已经存在了就不添加了。
                if (((ch = p.left) != null &&
                     (q = ch.find(h, k, kc)) != null) ||
                    ((ch = p.right) != null &&
                     (q = ch.find(h, k, kc)) != null))
                    return q;
            }
            // 将k和pk强行分出个高下。
            dir = tieBreakOrder(k, pk);
        }

        TreeNode<K,V> xp = p;
        if ((p = (dir <= 0) ? p.left : p.right) == null) {
            Node<K,V> xpn = xp.next;
            // 创建节点，并根据dir分出的结果，决定是左子树还是右子树。
            TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
            if (dir <= 0)
                xp.left = x;
            else
                xp.right = x;
            // 将xp的链表形态的next连接上
            xp.next = x;
            // 将x的树形态和x的链表形态都连接上
            x.parent = x.prev = xp;
            // 如果xpn本身是有内容的，那就改变链表的顺序，而不动树的样子。
            if (xpn != null)
                ((TreeNode<K,V>)xpn).prev = x;
            // 平衡树，顺带将链表和树的头节点标为一个。
            moveRootToFront(tab, balanceInsertion(root, x));
            return null;
        }
    }
}

9.find

// h是hash，k是key，kc是K类
final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
    TreeNode<K,V> p = this;
    do {
        int ph, dir; K pk;
        // 创建左右子树的节点
        TreeNode<K,V> pl = p.left, pr = p.right, q;
        // 根据hash的大小关系，决定是往左或右子树寻找
        if ((ph = p.hash) > h)
            p = pl;
        else if (ph < h)
            p = pr;
        // 如果找到了hash相同的，判断两者的key是否相同，如果key相同，返回节点p
        else if ((pk = p.key) == k || (k != null && k.equals(pk)))
            return p;
        // 如果hash相同，但是key不同。
        else if (pl == null)
            p = pr;
        else if (pr == null)
            p = pl;
        // 判断kc是否实现了comparable接口，如果实现了，判断k和pk是否可以比较，如果可以比较，将p更进一步
        else if ((kc != null ||
                  (kc = comparableClassFor(k)) != null) &&
                 (dir = compareComparables(kc, k, pk)) != 0)
            p = (dir < 0) ? pl : pr;
        // 如果实现了comparable接口，但是依然无法比较，则走右子树查询，如果没有查询结果，则走左子树。
        else if ((q = pr.find(h, k, kc)) != null)
            return q;
        else
            p = pl;
    } while (p != null);
    return null;
}

10.treeifyBin

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)
        resize();
    // 根据下标，取出对应的节点，并记录下标
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        TreeNode<K,V> hd = null, tl = null;
        do {
            /// 根据取出的节点e，生成一棵树的根root。其中hash，key，value都沿用原先的，next的值是null。
            TreeNode<K,V> p = replacementTreeNode(e, null);
            // 第一次执行循环，修改hd,这个hd是作为树的头部保存下来的，在本函数中不再修改了
            if (tl == null)
                hd = p;
            else {
                // 接下来的每次循环都会生成一个新的节点，新节点和上一个节点都会互相连接。
                p.prev = tl;
                tl.next = p;
            }
            // tl现在就后移，p是通过e的后移生成新节点实现后移的。
            tl = p;
        } while ((e = e.next) != null);
        // 执行结束以后就会得到一条新的链表，相邻的节点之间互相都有prev和next。
        // 将这个链表赋值到tab数组中，下标位置是之前记录的index = (n - 1) & hash
        if ((tab[index] = hd) != null)
            hd.treeify(tab);
    }
}

11.treeify

final void treeify(Node<K,V>[] tab) {
    TreeNode<K,V> root = null;
    // 这里的this指tab中某个需要树化的下标中所有的节点组成的链表
    for (TreeNode<K,V> x = this, next; x != null; x = next) {
        // 这里保证了，以下的代码不仅实现了树，而且还带有next，即还是个链表。
        next = (TreeNode<K,V>)x.next;
        x.left = x.right = null;
        // 如果是第一个节点，令parent为null，颜色为黑。
        if (root == null) {
            x.parent = null;
            x.red = false;
            root = x;
        }
        else {
            K k = x.key;
            int h = x.hash;
            Class<?> kc = null;
            // 用p从根节点开始遍历
            for (TreeNode<K,V> p = root;;) {
                int dir, ph;
                K pk = p.key;
                // 根据遍历节点的hash值和需要插入的哈希值作比较，判断是插在哪边。
                if ((ph = p.hash) > h)
                    dir = -1;
                else if (ph < h)
                    dir = 1;
                // kc本身就是空，这是上面赋值实现的。
                // 关键就是看comparableClassFor(k)返回值是什么。
                // 如果k的类实现了Comparable<?>接口，那么就会返回K类，否则就会返回null。
                // 1.如果K类没有实现Comparable，直接执行tieBreakOrder(k, pk);
                // 2.如果K类实现了Comparable,依据他们自己的规则进行要插入节点和循环节点的比较。如果比较出来的结果还是0，那就要再进行一轮比较。
                else if ((kc == null &&
                          (kc = comparableClassFor(k)) == null) ||
                         (dir = compareComparables(kc, k, pk)) == 0)
                    dir = tieBreakOrder(k, pk);

                TreeNode<K,V> xp = p;
                // 根据dir判断左右，x是要插入的节点，p是插入的位置，xp是父节点。
                // 简单的根据dir的值，连接父子节点。
                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;
                }
            }
        }
    }
    
    moveRootToFront(tab, root);
}

12.compareClassFor

static Class<?> comparableClassFor(Object x) {
    // 判断x是否是Comparable的实例，如果不是，说明没有实现Comparable<?>,直接返回null
    if (x instanceof Comparable) {
        Class<?> c; Type[] ts, as; Type t; ParameterizedType p;
        // 这是一种特殊情况，因为String.class实现了Comparable<String>，所以返回?就直接返回String即可。
        if ((c = x.getClass()) == String.class)
            return c;
        // 如果不是String，就需要获取实现的所有的interface，返回值是一个interface数组。
        if ((ts = c.getGenericInterfaces()) != null) {
            for (int i = 0; i < ts.length; ++i) {
                // 判断当前循环到的是不是参数化类型，即是不是带有泛型的接口。即A<B>这种接口。
                // getRawType()获取A的内容。
                // getActualTypeArguments()获取B的内容，并查看B的长度和内容是否符合条件。
                if (((t = ts[i]) instanceof ParameterizedType) &&
                    ((p = (ParameterizedType)t).getRawType() ==
                     Comparable.class) &&
                    (as = p.getActualTypeArguments()) != null &&
                    as.length == 1 && as[0] == c)
                    return c;
            }
        }
    }
    return null;
}

13.compareComparables

// k 和 x是比较的两内容
static int compareComparables(Class<?> kc, Object k, Object x) {
    // 如果x内容为空，或者x和k不是一个类，那就是没有办法比较的，所以返回0。
    // 如果可以比较，那么就使用compareTo比较这两个变量的内容大小。
    return (x == null || x.getClass() != kc ? 0 :
            ((Comparable)k).compareTo(x));
}

14.tieBreakOrder

static int tieBreakOrder(Object a, Object b) {
    int d;
    // 1.先判断这个两个是否为null
    // 2.判断两者的类名大小，并记录到d中，如果结果不是0就直接返回。
    // 3.如果2中记录的d是0，那么深入的判断a和b的哈希值，这里用上了<=，所以必定不会出现0的返回值。
    if (a == null || b == null ||
        (d = a.getClass().getName().
         compareTo(b.getClass().getName())) == 0)
        d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
             -1 : 1);
    return d;
}

15.balanceInserting

// root是根节点，x是插入的当前节点，返回最终的根节点。
// 函数的目的是使已经插入的节点，保持红黑树的颜色协调。
// 这里其实一共有三种旋转的情况:
// 1.叔父节点存在而且颜色是红色的。
// 2.叔父节点不存在或者颜色是黑色的，当前节点是右子树。
// 3.叔父节点不存在或者颜色是黑色的，当前节点是左子树。
static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
                                            TreeNode<K,V> x) {
    // 先假设颜色为red
    x.red = true;
    for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
        // 如果父亲节点是null，那么就说明这是一个根节点，直接令为黑色并返回
        if ((xp = x.parent) == null) {
            x.red = false;
            return x;
        }
        // 如果爷爷节点是空，说明xp就是根节点，那么xp一定是黑色，当前插入的节点颜色为红是允许的，所以直接返回root
        else if (!xp.red || (xpp = xp.parent) == null)
            return root;
        // 如果父节点是祖先节点的左子树
        if (xp == (xppl = xpp.left)) {
            // 叔父节点不为空且是红色的
            // 令叔父节点颜色为黑，父亲节点颜色为黑，祖先节点为红
            // 令x指向祖父节点，往上继续迭代查询是否有不合法的地方。
            if ((xppr = xpp.right) != null && xppr.red) {
                xppr.red = false;
                xp.red = false;
                xpp.red = true;
                x = xpp;
            }
            // 叔父节点不存在或者颜色为黑
            else {
                // 如果当前节点是右子树，先令x指向父节点，再进行左旋，往上迭代
                if (x == xp.right) {
                    root = rotateLeft(root, x = xp);
                    // 经过了左旋以后，x和xp变成左子树
                    // 重新记xp为父节点，xpp为祖父节点
                    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);
                    }
                }
            }
        }
    }
}

16.rotateLeft

// 左旋操作
static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,
                                      TreeNode<K,V> p) {
    TreeNode<K,V> r, pp, rl;
    // 记r为p的右子树
    // 如果p不是空节点，且存在右子树
    if (p != null && (r = p.right) != null) {
        // 记rl为r的左子树，并记为该左子树为p的新右子树
        // 如果该左子树存在，那么还要令该左子树的父亲为p
        if ((rl = p.right = r.left) != null)
            rl.parent = p;
        // 刷新p的父节点，并记为pp
        // 如果该父节点不存在，那么说明p原先是根节点
        // 那么左旋之后r就是根节点了，并令颜色为黑。
        if ((pp = r.parent = p.parent) == null)
            (root = r).red = false;
        // 如果原先p不是根节点，而且p是pp的左子树，那么r就代替了这个左子树位置，反之代替右子树。
        else if (pp.left == p)
            pp.left = r;
        else
            pp.right = r;
        // 记p为r的左子树
        r.left = p;
        // 记p的父节点为r
        p.parent = r;
    }
    // 返回根节点
    return root;
}

17.moveRootToFront

static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {
    int n;
    // 先确保不为null
    if (root != null && tab != null && (n = tab.length) > 0) {
        // 取出对应下标的节点内容
        int index = (n - 1) & root.hash;
        TreeNode<K,V> first = (TreeNode<K,V>)tab[index];
        // 发现树的根节点和保存在对应下标bin中的链表头不是同一个节点
        if (root != first) {
            Node<K,V> rn;
            // 先令对应下标的头节点为root
            tab[index] = root;
            // rp指向root的前置节点
            TreeNode<K,V> rp = root.prev;
            // 如果root有后置节点，就令后置节点指向前置节点。断开了和root的关系
            if ((rn = root.next) != null)
                ((TreeNode<K,V>)rn).prev = rp;
            // 如果前置节点确实存在，令原先root的前置和和后置节点彻底的建立连接关系
            if (rp != null)
                rp.next = rn;
            // 如果first也是存在的，令first的前置节点为root。
            if (first != null)
                first.prev = root;
            // root的后置节点为first，并令前置为null。
            // 至此，实现了树的结构没有发生变化，但是链表的结构发生了变化，将root从中间抽离出来，放到了first前面。虽然链表发生了顺序上的变化，但是这个影响实际上是不大的，因为HashMap中的table，对每个数组中每个下标谁开头是没有太大的要求的。
            root.next = first;
            root.prev = null;
        }
        assert checkInvariants(root);
    }
}