HashMap 的原理是什么？

核心回答

以 OpenJDK 25 的 java.util.HashMap 为例，它用“数组定位桶、桶内比较键、随负载扩容”实现键值映射。桶中的冲突节点通常组成链表，符合条件时可转换为红黑树。

1. 定位桶：取键的 hashCode()，将高位与低位混合得到内部 hash，再用 hash & (容量 - 1) 定位数组下标。数组容量保持为 2 的幂，便于定位和扩容迁移。
2. 处理冲突：落在同一桶不代表是同一个键，还要比较保存的 hash 及键的引用或 equals()。相同键更新值，不同键继续在链表或树中查找、插入。
3. 查询：按同样方式定位桶，再找匹配的键。哈希分布良好时，get、put 通常具有平均常数时间的表现；冲突严重时会变慢。
4. 扩容：新增映射超过容量与负载因子对应的阈值后，通常把数组扩为两倍并重新分配桶内节点，降低拥挤程度。

HashMap 允许一个 null 键和多个 null 值，不保证遍历顺序，也不提供并发修改的线程安全保证。树化改善冲突严重时的查找，不能替代正确的哈希设计和并发控制。

为什么既要 hash，又要 equals？

hash 用来缩小查找范围，equals() 才决定两个不同对象在业务上是否代表同一个键。两个键的 hash 相同，可能只是哈希碰撞；即使内部 hash 不同，也可能因数组只取其中部分位而进入同一个桶。

因此，自定义键需要遵守 equals() 与 hashCode() 的约定：相等的对象必须具有相同的 hashCode，不相等的对象允许碰撞。 只重写 equals() 而没有相应重写 hashCode()，可能使逻辑相等的键落入不同位置，破坏预期的查找和去重行为。

键存入后，也不应再修改参与这两个方法判断的字段。节点保存的是插入时算出的 hash，后来字段变化可能使查询去另一个桶查找；对象还在 Map 中，却不能按原来的预期找到。扩容也不会替应用修复可变键的语义。

链表、红黑树和扩容各解决什么？

链表让多个不同键能够共存在同一桶中，但查找可能要逐个比较。冲突链较长时，实现会尝试树化：表较小时优先扩容，让节点有机会分散到更多桶；表已经足够大，才把相应桶转成红黑树，以控制长链带来的查找开销。树节点结构更复杂，所以不会从一开始就把所有桶都建成树。

扩容关注整个表的负载，树化关注某一个桶的严重冲突，两者不是同一个触发条件。默认负载因子是 0.75；例如数组容量为 16 时，常见阈值是 12。这里的容量指桶数，size 指键值映射数量，不是数组里非空桶的数量；默认构造也通常将实际数组分配留到首次插入时。

容量翻倍后，链表节点利用已保存的 hash 拆成两组，不必重新调用每个键的 hashCode()：节点要么保留在原下标，要么移动到“原下标 + 旧容量”。决定因素是 hash 中与旧容量对应的那一位。

例如旧容量为 16，内部 hash 为 3 和 19 的两个键都在下标 3；扩到 32 后，前者仍在 3，后者移到 19。扩容减少了这两个键的桶冲突，但仍要迁移节点并分配新数组，所以已知规模时可以合理预估初始容量，减少反复扩容，也避免过度预分配。

常见追问

变成红黑树后就一定很快吗？ 仍依赖键的 hash 和比较性质。树结构有助于处理长链，但大量相同 hash、键又难以区分等情况仍可能增加搜索工作，不能把任何输入下的查询都保证为常数或对数时间。

为什么不能直接让多个线程同时写？ HashMap 的节点连接、数组替换、计数等操作没有统一的并发协调，可能出现覆盖、丢失更新或遍历异常。需要并发访问时，可使用合适的并发 Map 或外部同步；涉及“先判断再更新”的复合业务操作，还要明确整体的原子性。

遍历抛出 ConcurrentModificationException 就算并发保护吗？ 不是。fail-fast 是尽力发现不合规结构修改的诊断机制，不保证每次都能检测到，也不能用它建立线程安全。

参考资料