从 key 到桶#

存入 key 时，HashMap 会计算 hash 并定位数组下标。没有冲突时直接放入；有冲突时在链表或红黑树中继续比较 key。链表查找最坏为 $O(n)$，树化通常改善冲突严重时的查找成本；对于 hash 相同且无法有效比较的特殊 key，不能保证所有查找都严格为 $O(\log n)$。

以 JDK 8 为例，先把 hashCode 的高低位进行扰动，再通过 (n - 1) & hash 定位桶。桶内匹配时先判断 hash，再判断引用是否相同或 equals 是否相等。找到已有 key 就替换 value，没有找到才增加节点。

什么时候树化#

JDK 8 的树化阈值为 8，最小树化数组容量为 64；数组太小时优先扩容。普通 put 路径中，向已有 8 个节点的链表追加新节点时可能触发树化判断，不要死记“放入第 8 个一定树化”。扩容拆分后树桶节点数不超过 6 时转为链表；普通删除路径还会根据树结构判断是否退化。

null key#

HashMap 允许一个 null key，其 hash 按 0 处理，落在数组下标 0，也允许 null value。ConcurrentHashMap 禁止 null key 和 null value，让 null 能明确表达查询没有对应映射；禁止 null value 尤其避免了并发查询中的歧义。

HashMap 为什么不线程安全？#

多个线程同时 put、扩容或修改节点时，没有统一的并发协调，可能丢失更新或产生不一致状态。JDK 8 改善了迁移实现，但并没有把 HashMap 变成线程安全集合；有并发写入时使用合适的同步策略或 ConcurrentHashMap。

面试回答模板#

HashMap 在 JDK 8 中使用桶数组、链表和红黑树。通过扰动后的 hash 定位桶，再通过 equals 等判断 key，已有 key 替换 value，新 key 增加节点。容量不足会扩容，冲突集中时可能树化。平均查询通常接近 O(1)，但受哈希分布影响。HashMap 支持 null，不保证遍历顺序，也不保证并发修改安全。