Java 源码系列 4——HashMap 扩容时究竟对链表和红黑树做了什么?

// 把原有链表拆成两个链表
// 链表1存放在低位（原索引位置）
Node<K,V> loHead = null, loTail = null;
// 链表2存放在高位（原索引 + 旧数组长度）
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
    next = e.next;
    // 链表1
    if ((e.hash & oldCap) == 0) {
        if (loTail == null)
            loHead = e;
        else
            loTail.next = e;
        loTail = e;
    }
    // 链表2
    else {
        if (hiTail == null)
            hiHead = e;
        else
            hiTail.next = e;
        hiTail = e;
    }
} while ((e = next) != null);
// 链表1存放于原索引位置
if (loTail != null) {
    loTail.next = null;
    newTab[j] = loHead;
}
// 链表2存放原索引加上旧数组长度的偏移量
if (hiTail != null) {
    hiTail.next = null;
    newTab[j + oldCap] = hiHead;
}

// 红黑树转链表阈值
static final int UNTREEIFY_THRESHOLD = 6;
// 扩容操作
final Node<K,V>[] resize() {
    // ....
    else if (e instanceof TreeNode)
       ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
    // ...
}
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
    TreeNode<K,V> b = this;
    // Relink into lo and hi lists, preserving order
    // 和链表同样的套路，分成高位和低位
    TreeNode<K,V> loHead = null, loTail = null;
    TreeNode<K,V> hiHead = null, hiTail = null;
    int lc = 0, hc = 0;
    /**
      * TreeNode 是间接继承于 Node，保留了 next，可以像链表一样遍历
      * 这里的操作和链表的一毛一样
      */
    for (TreeNode<K,V> e = b, next; e != null; e = next) {
        next = (TreeNode<K,V>)e.next;
        e.next = null;
        // bit 就是 oldCap
        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) {
        // 如果 loHead 不为空，且链表长度小于等于 6，则将红黑树转成链表
        if (lc <= UNTREEIFY_THRESHOLD)
            tab[index] = loHead.untreeify(map);
        else {
            /**
              * hiHead == null 时，表明扩容后，
              * 所有节点仍在原位置，树结构不变，无需重新树化
              */
            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);
        }
    }
}