⭐ 题目日期：

美团 - 2025/4/4

📝 题解：

HashMap的put流程步骤如下：

1. 计算哈希值：
   对键key调用hashCode()，并通过扰动函数（高16位与低16位异或）降低哈希冲突，得到最终哈希值hash。

2. 初始化数组：
   若数组table为空或长度为0，调用resize()进行初始化（默认容量16，负载因子0.75）。

3. 确定桶位置：
   计算索引i = (n - 1) & hash（等价于取模运算，n为数组长度）。

4. 处理空桶：
   若table[i]为空，直接创建新节点Node并放入该位置。

5. 处理哈希冲突：
   若table[i]非空，分情况处理：

   • 首节点匹配：若首节点的hash和key均相同，直接替换值。
   • 红黑树节点：若节点为TreeNode，调用红黑树的插入方法。
   • 链表遍历：遍历链表，若找到相同key则替换值；否则在尾部插入新节点。插入后若链表长度≥8，触发树化检查。

6. 树化检查：
   若链表长度≥8且数组长度≥64，将链表转为红黑树；若数组长度不足64，则优先扩容。

7. 触发扩容：
   若元素总数超过阈值（容量×负载因子），调用resize()扩容至2倍旧容量，并重新分配节点。

详细说明：

• 扰动函数：通过(h = key.hashCode()) ^ (h >>> 16)混合高位与低位，提升哈希分布性。
• 索引计算：(n-1) & hash利用位运算高效替代取模，要求n为2的幂。
• 树化条件：链表长度≥8且数组容量≥64，否则仅扩容。
• 尾插法：Java 8后链表插入改用尾插，避免并发扩容死循环。
• 扩容优化：无需重新计算哈希，通过判断新增位（原哈希值对应位置）决定节点在新数组中的位置（原位置或原位置+旧容量）。

示例：

map.put("key", "value");

1. 计算"key"的哈希值。
2. 若数组未初始化，创建容量16的数组。
3. 确定索引位置，假设为5。
4. 若位置5为空，直接插入新节点。
5. 若冲突且链表长度达到8，检查数组长度决定树化或扩容。
6. 最终若元素数超过12（16×0.75），数组扩容至32。

此流程确保了HashMap的高效插入、动态扩容及冲突处理。