JDK8中HashMap底层升级为“数组+链表+红黑树”，旨在解决高哈希冲突下的O(n)查询退化问题；当链表≥8且数组长度≥64时树化，≤6时退化回链表，并通过扰动函数与2的幂数组优化分布。

JDK8 中 HashMap 的底层结构从“数组 + 链表”升级为“数组 + 链表 + 红黑树”，核心目标是解决高哈希冲突下的查询性能退化问题。

为什么需要红黑树

链表在冲突严重时会退化成线性查找，时间复杂度升至 O(n)。当某个桶中链表长度持续增长，尤其在恶意构造哈希值或数据分布不均的场景下，get/put 性能明显下降。红黑树将最坏查找复杂度优化到 O(log n)，大幅缓解长链表瓶颈。

• 单链表适合小规模冲突（元素少、操作快）
• 红黑树适合大规模冲突（查询稳、结构平衡）
• 引入过渡阈值，避免频繁切换带来的开销

链表转红黑树的两个硬性条件

不是链表一满8个就树化，而是必须同时满足：

• 链表节点数 ≥ 8（TREEIFY_THRESHOLD = 8）
• 哈希表数组长度 ≥ 64（MIN_TREEIFY_CAPACITY = 64）

若数组太小（比如刚初始化为16），即使某链表已达8，也会优先触发扩容而非树化——因为扩容后桶增多，冲突自然分散，比建树更轻量高效。

红黑树退化回链表的时机

树结构维护成本高于链表，所以当元素减少时会主动降级：

• 红黑树节点数 ≤ 6（UNTREEIFY_THRESHOLD = 6）时，自动转回链表
• 这个阈值（6）比树化阈值（8）低2，形成“滞后区间”，防止增删抖动引发反复树化/退化
• 退化只发生在 resize 或 remove 过程中，由 treeifyBin / untreeify 方法触发

数组与扰动函数的关键作用

数组是定位基础，其长度始终为 2 的幂，配合 (n - 1) & hash 实现快速取模；而 key.hashCode() 经过扰动函数（高16位异或低16位）后再参与寻址，显著提升低位离散性，降低桶分布倾斜概率。

• 初始容量默认 16，负载因子 0.75，阈值为 12
• 扩容时容量翻倍，所有元素 rehash 重分配，保证平均桶长可控
• 延迟初始化：table 数组首次 put 才创建，节省空 map 内存