今天再聊一件事：HashMap的扩容机制

大家好，我是阿清，上一期聊完HashMap的put过程后，

这一期我们乘胜追击，继续聊一下HashMap的扩容机制。

针对扩容，一个重要问题:

如何进行扩容？

我们直接看源码吧

先来看看官方文档对resize方法的解释：

/**
 * Initializes or doubles table size.  If null, allocates in
 * accord with initial capacity target held in field threshold.
 * Otherwise, because we are using power-of-two expansion, the
 * elements from each bin must either stay at same index, or move
 * with a power of two offset in the new table.
 *
 * @return the table
 */

正好可以练下英语，翻译如下：

初始化或将table扩大两倍。如果table为空，则按照字段threshold保存的初始化容量目标进行分配，如果table不为空，因为我们使用二次幂对 table进行扩张，因此原来每个桶（即链表）中的元素在新的table中，要么留在同样的索引位置，要么在原位置的基础上，偏移原来的长度。

源码大致可分为两个部分：确定HashMap的新容量，确定旧元素的新位置

我再次逐行注释源码：

final Node<K,V>[] resize() {
    // 第一部分：
    // 声明一个oldTab变量 保存旧的table
    Node<K,V>[] oldTab = table;
    // 再次声明oldCap变量， 保存旧的table的长度
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    // 声明一个oldThr变量， 保存旧的阈值，（阈值即当HashMap的 节点数 超过 阈值时，将会进行扩容）
    int oldThr = threshold;
    // 声明新的capcity 与 新的 threshold
    int newCap, newThr = 0;
    // 首先判断oldCap
    if (oldCap > 0) {
        // 若oldCap大于0，则判断是否超过 HashMap的最大容量 ，即Integer.MAX_VALUE;
        if (oldCap >= MAXIMUM_CAPACITY) { 
            // 更新 threshold 为 Integer.MAX_VALUE;
            threshold = Integer.MAX_VALUE;
            // 直接返回旧table
            return oldTab;
        }
        // 首先初始化newCap为oldCap的两倍，同时判断oldCap是否大于 默认初始化容量
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            // 若满足，则初始化newThr 也为 oldThr 的两倍
            newThr = oldThr << 1; // double threshold
    }
    // 若oldCap 等于 0 或 小于0  且 oldThr已被初始化
    else if (oldThr > 0) // initial capacity was placed in threshold
        // 则将新的容量更新为 oldThr
        newCap = oldThr;
    // 若oldCap 等于 0 或 小于0  且 oldThr未被初始化
    else {               // zero initial threshold signifies using defaults
        // 则newCap 与 newThr 直接使用默认的容量 与 默认的阈值（默认容量 * 默认的负载因子）即可
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    // 若代码到此时，发现newThr仍未被更新
    if (newThr == 0) {
        // 则计算出newThr
        float ft = (float)newCap * loadFactor;
        // 并更新newThr, 不过要保证所有的结果，都应当小于最大容量
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    // 同时更新字段threshold 为 newThr
    threshold = newThr;
    
    
    @SuppressWarnings({"rawtypes","unchecked"})
    // 第二部分：
    // 按照新容量，构建一个newTab
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    // 并更新字段 table
    table = newTab;
    // 首先判断oldTab是否为空
    if (oldTab != null) {
        // 若oldTab不为空，按照oldTab的长度即oldCap 进行遍历，
        for (int j = 0; j < oldCap; ++j) {
            // 声明一个节点变量e, 作为遍历该位置链表的变量
            Node<K,V> e;
            // 若该位置的链表不为空
            if ((e = oldTab[j]) != null) {
                // 首先删除 原table中 该位置的链表
                oldTab[j] = null;
                if (e.next == null)
                    // 若当前结点是最后一个节点，按照 e的hash值 和 新table长度-1 进行 与 运算 获得在 新table中的位置
                    // 并将e储存在该位置
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    // 若 e 是 树节点，会将树节点拆分成更低的树容器或更高的树容器, 或转成链表，这里不多赘述
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // preserve order
                    // 若 e 的下一个节点不为空, 即链表中包含多个节点
                    // 首先声明5个变量
                    // 低位的头节点 与 尾节点
                    Node<K,V> loHead = null, loTail = null;
                    // 高位的头节点与 尾节点
                    Node<K,V> hiHead = null, hiTail = null;
                    // 下一个节点
                    Node<K,V> next;
                    do {
                        // 将next更新为 e的下一个节点
                        next = e.next;
                        // 判断e的hash值 和 oldCap进行与运算后是否为0
                        if ((e.hash & oldCap) == 0) {
                            // 若为0，
                            if (loTail == null)
                                // 且低位为节点为空，则将低位头节点 更新为e
                                loHead = e;
                            else
                                // 若低位尾节点不为空，则更新loTail的下一个节点
                                loTail.next = e;
                            // 同时 更新 loTail为
                            loTail = e;
                        }
                        else {
                            // 若 不为0
                            // 则对高位节点进行相同的操作，参照 低位节点 的注释
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    // 判断loTail节点是否为空
                    if (loTail != null) {
                        // 若不为空，将loTail的下一个节点置为null
                        loTail.next = null;
                        // 则更新旧的位置j处的链表为loHead
                        newTab[j] = loHead;
                    }
                     // 判断hiTail节点是否为空
                    if (hiTail != null) {
                        // 若不为空，将hiTail的下一个节点置为null
                        hiTail.next = null;
                        // 则更新j + oldCap处的链表为hiHead
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}