容量、负载因子与扩容
HashMap 的容量是桶数组长度，负载因子决定元素数量达到什么程度时扩容。当前默认值在空间占用、冲突概率和扩容次数之间取一个通用折中。
1. capacity、size 与 threshold
- capacity：当前桶数组长度。
- size：当前键值对数量。
- load factor：计算扩容阈值的比例。
- threshold：通常约为
capacity × loadFactor。
当前 OpenJDK 的默认初始容量是 16，默认负载因子是 0.75。默认构造的 HashMap 会延迟到首次写入时分配 table。
Map<Long, User> users = new HashMap<>();
这些默认值是 HashMap 实现约定，不是所有 Map 的统一规则。
2. 负载因子控制空间与冲突
负载因子较低：
- table 更稀疏，普通冲突概率降低。
- 更早扩容，空桶占用更多空间。
- 扩容次数可能增加。
负载因子较高：
- 空桶更少，空间利用率提高。
- 桶内冲突和比较可能增加。
- 到达同样 size 前扩容更少。
默认 0.75 适合一般用途，不是由业务数据推导出的万能最优值。除非有测量依据，通常通过合理初始容量减少扩容，比随意修改负载因子更稳妥。
3. 容量为什么使用 2 的幂
容量为 2 的幂时，可以使用：
index = (capacity - 1) & hash;
例如容量 16，掩码是二进制 1111，保留哈希低 4 位作为下标。容量翻倍到 32 后，只多使用一位哈希。
这个性质还简化了扩容迁移。节点新位置只由新增的那一位决定：
(hash & oldCapacity) == 0 -> 原索引
(hash & oldCapacity) != 0 -> 原索引 + oldCapacity
因此不需要为每个节点重新调用 key 的 hashCode()。
4. 构造参数会向上调整
Map<String, Order> orders = new HashMap<>(20);
参数 20 不是最终 table 长度，也不是“保证能放 20 个元素而不扩容”的直接声明。实现会把需要的容量调整到允许的 2 的幂，并结合负载因子计算阈值。
如果预计要保存 n 个映射，并希望减少扩容，容量至少要覆盖 ceil(n / loadFactor)，再由实现调整到合适桶数。现代 JDK 还提供 HashMap.newHashMap(expectedMappings)，用预计映射数量创建合适容量，避免手写公式和边界溢出。
HashMap<Long, User> users = HashMap.newHashMap(expectedUsers);
这个工厂从 Java 19 开始提供。需要支持更早 JDK 时，再按目标版本选择构造方式。
5. resize 怎样迁移节点
扩容通常把容量翻倍，并为新 table 分配数组。旧桶中的链或树会按哈希新增位拆成两组：
- 低位组保持原索引。
- 高位组移动到
原索引 + 旧容量。
这是 O(n) 的迁移，期间还会短暂同时持有新旧数组，并写入大量引用。大 Map 的扩容会造成分配峰值和延迟抖动。
扩容不是并发安全操作。多个线程无同步修改 HashMap，不能依赖实现迁移过程保持正确。
6. 初始容量应该怎样估算
适合预估的场景：
- 批量加载已知行数。
- 按固定上限建立短期索引。
- 性能剖析确认 resize 是热点。
不适合盲目预留的场景：
- 每个请求创建许多小 Map。
- 预计上限远大于常见值。
- Map 生命周期很长但实际稀疏。
可以记录元素数量分布和扩容事件，在 P50、P95 等实际规模上选择容量。预留的目标是减少有意义的扩容，而不是保证永不扩容。
7. 遍历成本也受容量影响
HashMap 的迭代需要扫描桶并访问节点，成本与 capacity 加 size 相关。过大的稀疏 table 不只浪费内存，也会增加遍历空桶的工作。
如果业务主要做有序全量遍历，LinkedHashMap 的迭代成本与 size 更直接，但它为每个节点增加顺序链接。选型仍需基于实际读写方式。
8. 常见问题
8.1 元素达到 threshold 就立即扩容吗
应按具体实现的插入判断理解：通常新增映射使 size 超过 threshold 后触发扩容。更新已有键不会增加 size，也不会因这次 put 单独触发相同路径。
8.2 负载因子越小查询越快吗
不一定。更大的数组会增加内存占用和遍历成本，缓存命中也可能变差；冲突原本很少时收益有限。只有数据与性能证据支持时才调整。
8.3 初始容量设置为元素数量就够了吗
默认负载因子 0.75 下，桶数达到 75% 左右就会扩容，所以直接传 n 可能仍在装入 n 个元素前扩容。使用 HashMap.newHashMap(n) 或按负载因子计算。
8.4 resize 会重新调用所有 key 的 hashCode 吗
当前 OpenJDK 保存了处理后的哈希，容量翻倍时通过旧容量对应的位拆分节点，不需要再次调用每个 key 的 hashCode。它仍要遍历并迁移所有节点链接。
9. 面试题
9.1 HashMap 为什么使用 2 的幂作为容量
出现公司：一嗨租车、上海卫瓴信息科技
考察重点
- 位掩码怎样把哈希映射到桶。
- 扰动函数为什么让高位参与低位。
- 容量翻倍后节点为什么只有两个候选位置。
相关内容：第 3 节“容量为什么使用 2 的幂”、第 5 节“resize 怎样迁移节点”。
参考回答
容量是 2 的幂时，capacity - 1 的低位全为 1，可以用按位与快速取得桶下标。HashMap 还把原始哈希高位混入低位，减少只看低位造成的部分冲突。
容量翻倍只增加一个参与定位的哈希位，因此旧桶中的节点要么留在原索引，要么移动到原索引加旧容量。实现可以直接检查这一位拆分，不必重新调用所有键的 hashCode。
9.2 怎样为预计一百万个映射设置初始容量
出现公司：上海卫瓴信息科技
考察重点
- 预计元素数不等于桶数组长度。
- 负载因子和向上取 2 的幂。
- 预留内存与减少扩容之间的取舍。
相关内容：第 4 节“构造参数会向上调整”、第 6 节“初始容量应该怎样估算”。
参考回答
目标是让扩容阈值至少覆盖预计映射数，而不是把构造参数直接写成一百万。默认负载因子下需要约 ceil(1_000_000 / 0.75) 个桶，再向上调整到实现允许的 2 的幂。
在支持的 JDK 上可以直接使用 HashMap.newHashMap(1_000_000)，让库处理计算和溢出边界。还要确认峰值并非远高于常见值，否则一次性预留很大的桶数组也会增加内存和遍历成本。