说说 HashMap 的扩容机制？如何扩容的？

结论先行：当 size 超过 threshold（容量 × 负载因子）时触发扩容，容量翻倍、阈值同步翻倍。JDK 8 利用“容量是 2 的幂”这一性质，用 (e.hash & oldCap) 把每个桶拆成低位链和高位链：低位留在原下标 j，高位整体搬到 j + oldCap，不需要重新计算 hash，也不改变节点间的相对顺序。

1. 阈值与触发时机

默认构造的 HashMap 是懒初始化：第一次 put 时才 resize() 出长度 16 的数组，阈值 threshold = 16 × 0.75 = 12。putVal 末尾的判断是：

++modCount;
if (++size > threshold)
    resize();

也就是说，插入第 13 个元素后立刻扩容，稳态下 size 不会长期高于阈值。

2. 为什么可以“不重算 hash”

桶下标是 hash & (n - 1)。容量从 16 翻到 32 后，掩码从 0b1111 变成 0b11111，多出来的那一位正好是 oldCap = 16。于是每个节点只有两种去向：

扩容前（容量 16）：index = hash & 0b01111
扩容后（容量 32）：index = hash & 0b11111

若 hash & 16 == 0  →  新下标仍是 j        （低位链 lo）
若 hash & 16 != 0  →  新下标是 j + 16     （高位链 hi）

oldTab[j] = A -> B -> C -> D
              │
   按 hash & oldCap 分成两条链（JDK 8 用尾插，保持相对顺序）
              │
newTab[j]        = A -> C
newTab[j + 16]   = B -> D

3. 源码：resize 的骨架

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    if (oldCap > 0) {
        if (oldCap >= MAXIMUM_CAPACITY) {          // 到顶：不再扩容
            threshold = Integer.MAX_VALUE;
            return oldTab;
        } else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                   oldCap >= DEFAULT_INITIAL_CAPACITY) {
            newThr = oldThr << 1;                  // 阈值同步翻倍
        }
    } else if (oldThr > 0) {
        newCap = oldThr;                           // 构造时指定了初始容量
    } else {
        newCap = DEFAULT_INITIAL_CAPACITY;         // 默认 16
        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;
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    // 逐个桶迁移：单节点直接放、树桶调用 split、链表拆 lo/hi
    return newTab;
}

链表节点迁移的关键几行：

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;
}
// ...
if (loTail != null) { loTail.next = null; newTab[j] = loHead; }
if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; }

4. 代码：按预估容量一次性建表

import java.util.HashMap;
import java.util.Map;

public class ResizeDemo {
    public static void main(String[] args) {
        int expected = 1000;
        // 阈值 = 容量 × 0.75，要装下 expected 个元素，容量至少 expected / 0.75
        int cap = (int) (expected / 0.75f) + 1;
        Map<String, Integer> map = new HashMap<>(cap);
        for (int i = 0; i < expected; i++) {
            map.put("k" + i, i);
        }
        System.out.println(map.size()); // 输出：1000，全程没有扩容
    }
}

注意 new HashMap<>(1000) 的实际容量是 tableSizeFor(1000) = 1024，阈值 768——参数是“容量”而不是“能装多少个”，想装 1000 个应传 1000 / 0.75 + 1。

5. JDK 1.7 与 1.8 的迁移差异

常见追问

• 为什么容量必须是 2 的幂？ (n-1) & hash 等价于取模且更快；扩容时还能用一位判断新下标。
• 扩容时红黑树怎么处理？ TreeNode.split 按 hash & bit 拆成两棵树，某侧节点数 ≤ UNTREEIFY_THRESHOLD（6）就退回链表。
• 扩容的复杂度？ 单次 O(n) 拷贝，均摊到每次 put 是 O(1)；频繁扩容仍是性能杀手。
• 负载因子调大能减少扩容吗？ 能，但冲突率上升，查询变慢，通常不建议动。
• new HashMap<>(16) 会立刻分配数组吗？ 不会，构造只记录阈值，首次 put 才分配。
• 为什么 1.8 不再重新计算 hash？ 容量翻倍只多影响一位，用 hash & oldCap 就能判断归属，省掉一次 hash 计算。

小结

扩容的本质是“容量翻倍 + 按新增的那一位把桶一分为二”。记住三个数字：默认 16、负载因子 0.75、阈值 12；记住一个位运算：hash & oldCap 决定去 j 还是 j + oldCap；再记住一个结论：JDK 8 尾插保序，不会再出现 1.7 的扩容死循环。工程上最有用的一句是——能预估元素数量时，按 元素数 / 0.75 + 1 指定初始容量。