面试考察点
- 是否理解哈希表的桶、哈希函数和冲突处理。
- 是否能说清 JDK 8 中链表、红黑树和扩容的关系。
- 是否知道容量、负载因子对空间和性能的影响。
- 是否清楚 HashMap 的线程安全边界，而不是只背“线程不安全”。
核心答案
**一句话回答：**HashMap 是基于哈希表的 Map 实现，底层使用数组定位桶，冲突元素使用链表或红黑树保存；当元素数量超过容量与负载因子的乘积时，哈希表会扩容并重新分布元素。
JDK 8 的典型结构可以抽象为 Node<K,V>[] table。数组长度通常保持为 2 的幂，这样可以使用 (n - 1) & hash 快速计算索引。
put 的执行流程
- 对 key 的
hashCode()做扰动，减少高位信息丢失。 - 根据数组长度计算桶下标。
- 桶为空时创建节点。
- 桶不为空时，先比较 hash 和 key；相同则替换 value。
- key 不同则沿链表查找，或在红黑树中查找。
- 新节点插入后检查树化和扩容条件。
Map<String, Integer> counts = new HashMap<>();
counts.merge("java", 1, Integer::sum);
为什么需要扰动 hash？
数组定位只使用 hash 的一部分位。当数组较小时，高位信息可能没有参与定位，很多不同的 hash 可能落入同一个桶。JDK 8 使用 h ^ (h >>> 16) 将高位混入低位，在不增加太多成本的情况下改善分布。
链表为什么会树化？
哈希冲突严重时，链表查找接近 O(n)。JDK 8 在链表长度达到树化阈值、且数组容量达到最小树化容量时，将链表转换为红黑树；如果数组还很小，优先扩容而不是树化。这样可以避免小表因为偶然冲突就承担红黑树成本。
扩容与负载因子
容量是桶的数量，负载因子表示允许的装载程度。默认负载因子为 0.75，阈值约等于 capacity * loadFactor。超过阈值后，容量通常扩大为两倍。
扩容的成本包括创建新数组和迁移节点。提前估算数据量并设置合适的初始容量，可以减少多次扩容；但初始容量过大又会增加遍历空桶的成本。
时间复杂度与边界
在哈希分布良好的情况下，get 和 put 的平均时间复杂度接近 O(1)。大量 key 使用相同 hash、或者 key 的 equals / hashCode 实现不正确，都会破坏这个假设。
HashMap 允许一个 null key 和多个 null value，不保证遍历顺序。官方 API 明确说明它不是同步容器；多个线程并发访问且至少一个线程结构性修改时，必须在外部同步，或者改用并发容器。
高频追问
为什么 key 要同时重写 equals 和 hashCode？
HashMap 先用 hash 定位桶，再用 equals 判断是否是同一个 key。只重写 equals 会让相等对象拥有不同 hash，直接落入不同桶。
为什么不建议依赖 ConcurrentModificationException？
HashMap 视图迭代器是 fail-fast 的，但官方只保证“尽力而为”。它用于尽早发现 bug，而不是作为并发正确性的控制手段。
参考资料
- Oracle Java SE 21 HashMap API
- OpenJDK 8
HashMap源码与注释
核心考点清单
- JDK 8 使用数组、链表和红黑树处理哈希冲突。
- 容量为 2 的幂便于位运算定位和扩容拆分。
- 树化不仅看链表长度，还要求数组达到一定容量。
- HashMap 非线程安全，fail-fast 也不是并发安全保证。
高频追问与参考回答
追问：为什么 ConcurrentHashMap 不允许 null？
并发环境中 get 返回 null 无法区分“键不存在”与“值就是 null”，会让原子语义产生歧义，因此键和值都禁止 null。
追问：扩容后元素如何迁移？
容量翻倍时，元素根据哈希中对应新增位分成原位置与“原位置 + 旧容量”两组，无需重新计算完整取模。
机制全景图
下面把「HashMap 的底层原理是什么？」从输入到结果压缩成一条可复述的主链路。面试时先用图建立全局坐标，再进入局部实现，能避免只背零散结论。
flowchart LR
A["计算键哈希"]
A --> B["扰动并定位桶"]
B --> C["检查首节点"]
C --> D["遍历链表或红黑树"]
D --> E["命中更新或插入扩容"]
完整链路：从输入到结果
沿着「计算键哈希 → 扰动并定位桶 → 检查首节点 → 遍历链表或红黑树 → 命中更新或插入扩容」观察输入、状态与输出，下面每个阶段都对应一个可以在源码、日志或系统表中验证的位置。
1. 计算键哈希
HashMap 先取得 hashCode 并做高低位扰动，让容量为 2 的幂时高位也参与桶索引。
2. 扰动并定位桶
索引通过 (n-1)&hash 计算，容量为 2 的幂可以用位运算并保持分布规律。
3. 检查首节点
桶首节点若哈希与键相等即可命中，否则才进入冲突结构，null 键固定落在特定桶。
4. 遍历链表或红黑树
冲突较多且容量达到阈值时链表可树化；删除或容量条件变化时也可能退回链表。
5. 命中更新或插入扩容
size 超过 capacity*loadFactor 会扩容，节点根据旧容量对应位拆到原位置或原位置+oldCap。
源码与实现定位
| 入口 | 阅读重点 |
|---|---|
| java.util.HashMap#putVal | 桶插入、树化和 resize 触发 |
| java.util.HashMap#resize | 低位/高位拆分迁移 |
源码或系统表应按上表顺序追踪：先确认入口实际走到哪条路径，再用运行时数据验证，而不是仅凭类名或配置推测。
参数配置与可复现实验
int expected = 1_000_000;
int capacity = (int) Math.ceil(expected / 0.75d);
Map<Key, Value> map = new HashMap<>(capacity);
用 100 万个均匀键、低位重复键和常量哈希键压测，记录 get/put P99、树桶数量和扩容前后分配峰值。
验证步骤与预期结果
1. 固定输入和基线
先在没有故障注入的环境执行上述配置，固定数据规模、并发度、运行时版本和预热时间。以「装载因子」为主基线，记录值应满足「默认 0.75」；同时保存 桶冲突分布、集合尺寸与扩容次数，使后续变化能够回到同一时间轴比较。
2. 从实现入口确认路径
在「java.util.HashMap#putVal」确认请求确实进入「桶插入、树化和 resize 触发」对应的实现，再沿「java.util.HashMap#resize」观察「低位/高位拆分迁移」。如果入口路径都未命中，就不应继续调整下游参数，而应先检查调用条件、版本或路由是否与假设一致。
3. 注入本文特有的失败模式
优先复现「可变字段参与 hashCode 后修改键」，并把单一变量逐级放大，直到「装载因子」越过「size 超阈值触发 resize」。随后再分别验证「初始容量过小触发多次扩容」和「低质量哈希造成热点桶」，三类故障分开执行，避免多个变量同时变化而无法归因。
4. 执行止损和根因修复
第一轮只应用「修复键哈希而非依赖树化兜底」，确认它能控制影响范围；第二轮应用「键字段设为不可变」，验证核心链路恢复；最后落实「按预计元素数和装载因子计算容量」，消除同类问题再次出现的条件。每一步都保留变更前后数据，不用“感觉变快了”替代测量。
5. 通过退出条件
实验只有同时满足三项才算通过：「装载因子」回到「默认 0.75」、「树化阈值」回到「链长达到 8 且容量>=64」、「resize 峰值」回到「应不进入请求 P99」，并且业务结果差异为零。若性能恢复但结果不一致，仍应视为失败；若指标恢复后很快再次越线，则说明只完成了临时止损，没有消除根因。
量化基线
| 指标 | 样例基线/口径 | 风险线 | 结论 |
|---|---|---|---|
| 装载因子 | 默认 0.75 | size 超阈值触发 resize | 预估容量 |
| 树化阈值 | 链长达到 8 且容量>=64 | 热点桶频繁树化 | 修复 hashCode |
| resize 峰值 | 应不进入请求 P99 | 复制与 GC 同时上升 | 启动/批量阶段完成扩容 |
这些数值是实验口径或示例告警线，不是可复制到所有系统的固定答案；上线阈值应由本系统稳态、峰值和故障演练共同确定。
事故复盘：缓存键分布倾斜导致 CPU 突增
自定义键把 hashCode 固定为地区编号，百万用户只有几十个哈希值，大量元素聚集在少数桶。即使红黑树限制最坏查找，比较与对象访问仍很重。重新组合稳定且高区分度的用户标识，并在写入前确认键不可变后，冲突和 CPU 都恢复正常。
| 失败模式 | 首要证据 | 第一处置动作 |
|---|---|---|
| 可变字段参与 hashCode 后修改键 | 桶冲突分布 | 修复键哈希而非依赖树化兜底 |
| 初始容量过小触发多次扩容 | 集合尺寸与扩容次数 | 键字段设为不可变 |
| 低质量哈希造成热点桶 | get/put 尾延迟 | 按预计元素数和装载因子计算容量 |
发布与回滚检查点
- 发布前：确认「java.util.HashMap#putVal」对应实现和上述配置在目标版本仍然有效，并保存「装载因子」基线。
- 灰度中：同时观察 桶冲突分布、集合尺寸与扩容次数、get/put 尾延迟；任一指标越过表中风险线，就停止继续扩量。
- 回滚时：先执行「修复键哈希而非依赖树化兜底」控制影响，再回退代码或参数；涉及持久状态时必须额外核对结果差异。
- 发布后：至少覆盖一个完整峰值周期，确认「可变字段参与 hashCode 后修改键」没有再次出现，才关闭变更观察窗口。
方案对比与选型
| 方案 | 更适合的场景 | 主要收益 | 代价与边界 |
|---|---|---|---|
| HashMap | 单线程或外部同步的一般键值映射 | 均摊 O(1)、API 通用 | 非线程安全且扩容有瞬时成本 |
| LinkedHashMap | 需要插入顺序或访问顺序 | 可实现 LRU 语义 | 额外双向链表开销 |
| TreeMap | 需要有序遍历和范围查询 | 稳定 O(log n)、支持导航 | 比较成本高且键顺序契约更严格 |
选型至少带上 元素数量、读写比例、遍历方式、并发度和内存预算，并用上面的量化基线验证；未知数据应明确为待测假设。
设计边界与工程取舍
HashMap 的 O(1) 是良好哈希与合理负载因子下的均摊结论；它不保证遍历顺序，也不能通过“读多写少”自然获得线程安全。
工程落地遵循：先保证数据结构语义正确，再依据访问模式选择实现。回答时直接引用「java.util.HashMap#putVal」、配置实验和事故数据，比复述固定模板更有说服力。