Java HashMap：哈希、碰撞、扩容与键的合同

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 区分 Map API 保证与特定 OpenJDK 实现细节；没有指定版本时不把桶树化阈值当通用语言规范。

解题路线

1. hashCode 把键映射到散列值，再定位桶；碰撞时仍要用 equals 区分键。相等键必须同 hash，否则检索合同被破坏。
2. 底层数组结合桶内节点；常见 OpenJDK 在特定条件下树化碰撞桶。扩容重新组织桶，单次操作可能线性，平均常数依赖合理散列。
3. 容量和负载因子权衡内存与碰撞，预估规模可减少扩容。HashMap 不提供线程安全，也不承诺迭代顺序。
4. 插入后修改参与 hash/equals 的字段会使键落在旧桶、查找定位新桶。优先不可变键，不能靠再次 put 修复所有情况。

手动走一遍

插入 key(id=7)，随后把 id 改为8，get 使用新 hash 可能找不到原项；size 却仍计入它。读取含 null 值的映射时，get 返回 null 不区分缺失与已存 null，需 containsKey。

规模与取舍

良好散列下 get/put 平均 O(1)，扩容 O(n)；迭代成本与 capacity+size 有关。容量过大也会拖慢遍历。

易错点与追问

容易失分的边界

• 所有情形都承诺 O(1)。
• 把 fail-fast 迭代器当并发安全保证。
• 用 mutable key 作为长期索引。

继续深挖

• 攻击性碰撞如何影响系统？
• 什么时候使用 ConcurrentHashMap 或不可变快照？