HashMap 的 put 完整流程和扩容条件是什么？

以 OpenJDK 8u412 的 HashMap 为例，put 的主线是计算 hash、定位桶、查重或插入、必要时调整桶结构，最后更新计数并检查扩容：

对键的 hashCode 做扰动；null 键的内部 hash 为 0。表尚未分配时，先通过 resize 完成初始化。
用“内部 hash 与数组长度减一按位与”定位桶。空桶直接放新节点。
桶非空时，先检查首节点是否为同一个键；是树桶则走树插入，否则遍历链表。找到相等键就更新值并返回旧值；没有相等键才追加新节点。
链表新增节点后达到相应条件，会尝试树化；表容量不足时优先扩容。
新增映射才增加 size 等计数；如果新增后的 size 大于 threshold，再执行扩容。已有键的普通值替换不会增加 size，也不会因此触发这一负载阈值检查。

因此，扩容既可能来自元素数量超过阈值，也可能来自长冲突链在小表上的处理；首次分配数组同样复用了 resize 方法，不能把这些情况都理解成“原表已经装满”。

HashMap 不是只比较桶位置，也不是只比较 hash。普通节点会先比较内部 hash，再检查键是否为同一引用，或满足 equals。不同键可能同桶，也可能具有相同 hash，所以仍要判断键的相等性。

查到已有键时替换的是值，键值映射数量不变。put 返回旧值；返回 null 既可能表示此前没有这个键，也可能表示旧值就是 null，因为 HashMap 允许 null 值。

键在存入后若改变了影响 hashCode、equals 的字段，可能无法按预期定位或匹配原节点。通常应选择等价关系稳定的键，不能指望扩容修复可变键造成的问题。

size 是映射条数，capacity 是桶数组长度，二者不同。threshold 通常与容量、负载因子有关；默认负载因子是 0.75。例如容量为 16 时，常规阈值为 12，在没有提前因冲突触发扩容的情况下，插入第 13 个不同键后超过阈值，扩为 32。

树化针对的是单个桶的冲突程度，不是全表的 size。长链达到尝试树化的条件时，如果桶数组还小，扩容可能先把冲突分散到两个桶，所以优先扩容；容量足够时才转换为树。不能把“链表长”和“全表装载率高”当成同一条件，也不应只背一个节点数就断言一定树化。

默认构造时还没有实际分配桶数组，第一次 put 才进行分配。容量达到实现的最大限制后，也不会无限翻倍。

resize 分配更大的桶数组，遍历旧桶并迁移节点。对容量翻倍时的普通链表，只需检查节点内部 hash 与旧容量按位与的结果：为 0 的留在原下标，非 0 的移动到“原下标加旧容量”；两个分组内部保持相对顺序。树桶则通过相应拆分逻辑处理，必要时恢复为链表。

例如内部 hash 为 3、19，在容量 16 时都落在下标 3；扩为 32 后分别落在 3、19。这是利用节点保存的 hash 重新定位，不是重新调用每个键的 hashCode。扩容仍要处理旧节点和桶数组，会有时间与空间成本，不能认为这条位运算让整个扩容变成 O(1)。

这些检查、指针修改、计数和迁移没有为多个线程建立完整同步协议。两个线程都发现同一桶为空后写入，就可能覆盖入口；替换值、遍历、扩容也要遵守同步要求。需要共享更新时使用适合的并发容器或统一外部同步，不能把尾插、红黑树或 fail-fast 当成线程安全机制。

参考答案