Java中HashMap底层是“数组+链表+红黑树”三层协作结构：数组为骨架实现O(1)定位；链表处理哈希冲突，轻量高效；当桶中链表长度≥8且数组容量≥64时升级为红黑树以优化查询至O(log n)，节点≤6时退化回链表。
Java 中 HashMap 的底层结构不是固定不变的，而是一种“按需升级”的三层协作机制：数组是骨架，链表是默认冲突应对方式，红黑树是长链表的性能优化手段。理解它，关键不是死记结构，而是看清三者分工和触发条件。
数组是定位基础，靠哈希值快速找“桶”
HashMap 内部维护一个 Node<K,V>[] table 数组，每个位置叫一个“桶”（bucket）。当你调用 put(key, value) 时，系统先对 key 计算哈希值，再通过位运算 (n - 1) & hash（n 是数组长度，必为 2 的幂）快速映射到某个下标——这比取模快得多，也保证了索引均匀分布。
数组本身不存数据，只存指向第一个节点的引用。如果该位置是 null，说明没冲突，直接放进去；如果不为空，就说明有哈希冲突，得往下查。
链表解决多数冲突，轻量又够用
当多个 key 映射到同一个桶时，新节点会以头插或尾插（JDK 1.8 改为尾插）方式加入链表。每个 Node 包含 hash、key、value 和 next 引用。
立即学习“Java免费学习笔记（深入）”；
在 Java 中初始化和管理阿里云 SDK客户端。包括单例模式、线程安全、endpoint 与 region 配置、VPC 终端节点、同步与异步等。
- 链表结构简单，内存开销小（一个 Node 约 32 字节）
- 在冲突不严重时（比如平均链长 ≤3），遍历成本低，O(1) 平均查找仍成立
- 插入、删除只需调整指针，无需平衡操作
红黑树是链表的“升级开关”，不是一上来就上树
链表变红黑树有两个硬性条件，缺一不可：
- 当前桶中链表长度 ≥ 8
- 整个数组长度 ≥ 64
为什么设这两个阈值？
- 长度 ≥8 是统计结果：基于泊松分布，哈希均匀时，链长达到 8 的概率低于千万分之一，说明大概率是哈希设计差或数据异常，需要优化查询
- 数组 ≥64 才转树：避免小数组频繁树化——小数组意味着整体数据少，即使链长 8，总元素也不多，树化反而增加空间和维护成本（TreeNode 比 Node 大近一倍）
反过来，当红黑树节点数 ≤6 时，会退化回链表。这个“缓冲区间”（6 和 8 不相等）防止在临界点反复转换，减少开销。
扩容是维持效率的关键调节器
数组长度固定，但数据不断增长。当元素总数超过 容量 × 负载因子（默认 16×0.75=12） 时，触发扩容：新建一个 2 倍大小的数组（如 16→32），所有旧节点重新计算索引，搬入新桶。
注意：扩容后，原来链表里的节点可能被拆散到两个不同桶中（因为新数组长度变了，(n-1)&hash 结果可能不同），这客观上缓解了局部冲突。
