HashMap红黑树拆分后的两个链表

在 HashMap 的树化与反树化过程中，“两个链表”具体指以下两种结构： ### **1. 原红黑树拆分后的两个链表** 当 HashMap 发生扩容（resize）时，原有的红黑树会根据新的哈希值分布被拆分为 **两个独立的链表**： • **高位链表**（hi-head）：哈希值与新数组容量按位与后非零的节点； • **低位链表**（lo-head）：哈希值与新数组容量按位与后为零的节点。 ### **2. 拆分后的处理逻辑** HashMap 会分别检查这两个链表的长度： 1. **长度 ≤6**：将链表退化为普通链表（`Node` 结构），取消树化； 2. **长度 >6**：重新将链表转换为红黑树（`TreeNode` 结构），保持高效查询性能。 --- ### **技术细节与设计意义** 1. **拆分目的** • 扩容后哈希分布改变，原红黑树可能不再适合新数组的哈希槽分布，需重新组织数据结构； • 拆分后按链表处理可减少不必要的树结构维护开销。 2. **阈值设定（6与8）** • **树化阈值（8）**：链表长度超过 8 时转为红黑树，避免极端哈希冲突导致查询性能退化； • **反树化阈值（6）**：树节点减少到 6 以下时退化为链表，防止小规模数据下树节点的内存浪费。 3. **性能优化** • 红黑树拆分后若仍较长，保留树结构可维持 O(log n) 的查询效率； • 若拆分后链表较短，退化为链表可减少内存占用和指针操作开销。 --- ### **总结** | **链表类型** | **触发场景** | **处理逻辑** | |--------------------|---------------------------|---------------------------------| | 高位链表（hi-head） | 扩容后哈希值高位分布 | 检查长度，决定是否反树化或重树化 | | 低位链表（lo-head） | 扩容后哈希值低位分布 | 同上 | 该机制通过动态调整数据结构，在时间（查询性能）与空间（内存占用）之间实现了高效平衡。