HashMap 的底层实现是什么？为什么链表会转成红黑树？红黑树的时间复杂度是多少？

# 1）HashMap 底层实现（JDK 8 视角） * **主体结构**：`Node<K,V>[] table`（数组）。每个桶（bucket）里是**链表或红黑树**。 * **寻址**：先算 `hash = spread(key.hashCode())`（常见实现是 `h ^ (h >>> 16)` 做高低位扰动），再 `index = (n - 1) & hash` 定位到桶。 * **冲突解决**：同桶冲突先挂**链表**；当链表“过长”并且表容量足够大时转为**红黑树**（TreeBin）。 * **扩容**：负载因子 `loadFactor`（默认 `0.75`），阈值 `threshold = capacity * loadFactor`。超过则容量**翻倍**。 扩容时采用 **位迁移拆分**：老桶链表按 `(hash & oldCap)` 分成 **low**（索引不变）和 **high**（索引 + oldCap）两条链，**保持相对顺序**，减少重哈希成本。 * **链/树的互相转换**： * 链表节点数 ≥ `TREEIFY_THRESHOLD`（默认 **8**），且整体表容量 ≥ `MIN_TREEIFY_CAPACITY`（默认 **64**）→ **树化**。 * 树中节点数 ≤ `UNTREEIFY_THRESHOLD`（默认 **6**）→ **退化回链表**（例如扩容后冲突减少）。 * **其它关键点**： * `Node` 使用 `final int hash` + `K key` + `V value` + `Node next`。 * `equals/hashCode` 契约必须正确，否则定位/去重都会出问题。 * 树化后用 `TreeNode`（红黑树节点），树内排序**先按 hash，再按 key 的可比较性（Comparable），否则用身份哈希做 tie-break**，保证有序性与可定位。 # 2）为什么链表会转成红黑树？ * **避免最坏 O(n)**：当大量键**哈希冲突**（比如被恶意构造）时，链表查找/插入会退化为 O(n)，性能灾难（曾有 DoS 攻击利用这一点）。 * **红黑树保证 O(log n)**：用红黑树替换“长链表”，将桶内操作（search/insert/delete）稳定在 O(log n)，显著降低最坏时延。 * **阈值策略的考量**： * **下限 8**：实践中链表长度达到 8 已经非常罕见，且树的常数因子与内存开销更大，只有“足够长”才值得树化。 * **表容量至少 64**：当表很小且冲突多时，与其树化不如**先扩容**把冲突摊薄，更省内存也更快。 * **上/下翻门槛（8/6）**：设滞回区避免频繁在链表与树之间抖动。 # 3）红黑树的时间复杂度 * **查找 / 插入 / 删除：O(log n)**（最坏也保持平衡）。 * **空间**：每个节点多存颜色、父子指针等，**常数开销大于链表**。 * **在 HashMap 中的“n”** 指的是**同一个桶内**的元素数（不是整个表的元素数）。表本身寻址是 O(1)，所以总体为 **O(1) 平均，O(log k) 最坏（k 为冲突桶大小）**。 # 小结（面试直答版） * **底层**：数组 +（链表 / 红黑树），拉链法解决冲突；负载因子 0.75，扩容翻倍并用高位拆分优化迁移。 * **树化原因**：防止哈希冲突导致链表 O(n) 退化，提升到 O(log n) 的稳定最坏性能，抗恶意输入。 * **红黑树复杂度**：桶内操作最坏 **O(log n)**；平均情况下 HashMap 查找/插入仍可视为 **O(1)**。