HashMap 底层原理 （回答样本）

面试官您好，关于 HashMap 的底层实现，我是按照以下三个维度来理解的：

1. 宏观结构 (Overview)

从宏观上看，HashMap 的底层结构在 JDK 1.8 中是 “数组 + 链表 + 红黑树”。它的主体是一个 Node 数组（源码中叫 table），数组的每个位置我们称之为“桶”（Bucket）。

• 常规情况：当没有任何冲突时，数据直接存在数组里。
• Hash 冲突：当发生哈希冲突时，早期的 JDK 1.7 采用的是单纯的链表（头插法）。
• JDK 1.8 改进：为了解决哈希冲突导致链表过长、查询效率退化为 的问题，JDK 1.8 引入了红黑树。 转换机制：当链表长度 > 8 且 数组长度 >= 64 时，链表会自动转换为红黑树，将查询复杂度优化为 。

2. 核心流程：Put 数据的过程 (The Flow)

当我们调用 put(key, value) 时，内部主要经历了四个步骤：

1. 计算 Hash： 它不直接使用 key 的 hashCode()，而是做了一次扰动运算（key.hashCode() ^ (h >>> 16)）。这样做是为了让 Hash 值的高位也参与运算，使散列更加均匀，减少碰撞。
2. 定位索引： 通过 (n - 1) & hash 公式计算下标。这里利用了位运算代替取模，效率更高，这也解释了为什么 HashMap 的容量必须是 2 的幂次方。
3. 冲突处理： 如果该位置为空，直接 CAS 或插入新节点。如果该位置有数据（Hash 冲突），会调用 equals 对比 Key。 Key 相等：直接覆盖 Value。Key 不等（红黑树节点）：调用树的插入方法。Key 不等（链表节点）：遍历插入到尾部（尾插法）。插入后会检查是否需要转红黑树。
4. 扩容检查： 插入成功后，如果当前 size > 阈值 (Capacity * 0.75)，就会触发 resize() 扩容。

3. 关键细节与设计哲学 (Deep Dive)

在阅读源码时，我有两个设计细节印象深刻，这也是体现对底层理解的地方：

• 关于扩容 (Resize) 的优化：JDK 1.8 做了一个非常巧妙的优化。因为数组长度翻倍了（比如 16 -> 32），元素的新位置要么在原下标，要么在原下标 + 旧数组长度的位置。Java 只需要判断 Hash 值中新增的那一位比特位是 0 还是 1，就能直接定位。这意味着不需要像 1.7 那样重新计算 Hash，极大提升了扩容性能。
• 关于线程安全：HashMap 是线程不安全的。在 JDK 1.7 中，并发扩容会导致环形链表（死循环）。虽然 JDK 1.8 改用了尾插法解决了死循环问题，但在并发 put 时依然会发生数据覆盖的问题。结论：在多线程场景下，我会坚决使用 ConcurrentHashMap，而不是 HashMap。