JDK8中HashMap底层结构升级为“数组+链表/红黑树”，链表长度≥8且数组容量≥64时树化，退化阈值为6，通过动态切换将最坏查询复杂度从O(n)降至O(log n)。

Java 中 HashMap 的底层结构在 JDK 8 及之后，从“数组 + 链表”升级为“数组 + 链表/红黑树”，这个演变不是一蹴而就的，而是基于性能优化的渐进式策略：当链表过长导致查找退化为 O(n) 时，就把它转成红黑树，把查找降到 O(log n)。

触发树化的两个核心条件

一个桶（bucket）中的链表要变成红黑树，必须同时满足：

• 链表长度 ≥ TREEIFY_THRESHOLD（默认是 8）：这是硬性长度门槛；
• 整个哈希表的容量 ≥ MIN_TREEIFY_CAPACITY（默认是 64）：防止在表还很小、只是局部哈希冲突严重时盲目树化（此时更应优先扩容）。

为什么不是一超过 8 就立刻转？

因为链表长度达到 8 是概率事件。在均匀哈希的前提下，链表长度服从泊松分布，长度 ≥ 8 的概率约 0.00000006，非常低。所以出现长度 8，往往说明：

• 哈希函数不够好（比如 key 的 hashCode 实现有问题）；
• 数据本身存在大量哈希冲突（如 key 是固定字符串或简单整数）；
• 当前容量太小，还没来得及扩容。

这时如果容量又小于 64，HashMap 会优先选择 resize（扩容），而不是树化——因为扩容后重新散列，大概率能自然缓解冲突。

java-api-doc-generator

分析 Java Spring Boot 后端 Controller 代码，自动生成 Markdown 格式的接口文档。当用户说“生成 Java 接口文档”、“生成 API 文档”、“从 Spring 代码生成文档”时触发。

下载

立即学习“Java免费学习笔记（深入）”；

树化过程做了什么？

当两个条件都满足，HashMap 会把该桶里的 Node 链表，逐个构造成 TreeNode（红黑树节点），再调用 treeifyBin() 完成树化：

• TreeNode 是 Node 的子类，额外携带 parent、left、right、red 等字段；
• 树化时会根据 key 的 hashCode 和 Comparable 接口（或使用 tieBreakOrder 比较）确定顺序；
• 构造完成后，原链表头节点被替换为树的根节点，但数组槽位（table[i]）引用不变，仍是同一个地址。

红黑树也会退化回链表？

会。当执行 remove 或 resize 后，如果某棵树的节点数 ≤ UNTREEIFY_THRESHOLD（默认是 6），就会被拆解为普通链表：

• 这不是“降级”，而是权衡：少量节点下，链表遍历比红黑树维护（旋转、着色）更轻量；
• 退化只发生在 resize 或删除后检查时，不会在 put 过程中动态降级。