Java HashMap采用数组+链表+红黑树结构，旨在平衡查询效率、内存占用与扩容成本：数组实现O(1)寻址，链表处理常规哈希冲突，红黑树在链表≥8且数组≥64时转为O(log n)查询以兜底极端冲突。
Java HashMap 用数组 + 链表 + 红黑树，核心是为了在查询效率、内存占用、扩容成本三者之间取得最佳平衡。
数组是高效寻址的基础
数组支持 O(1) 随机访问，只要知道索引就能直接定位元素。HashMap 把 key 的哈希值通过 (n - 1) & hash（n 是数组长度，必为 2 的幂）快速算出下标，实现近乎常数时间的存取。
但数组容量固定，无法动态伸缩；而且哈希函数再好，也无法完全避免不同 key 映射到同一位置——这就是哈希冲突。
链表解决哈希冲突，兼顾简单与空间效率
当多个 key 落入同一个桶（数组位置）时，用链表把它们串起来：
立即学习“Java免费学习笔记（深入）”；
- 插入只需在链表尾部追加，时间复杂度 O(1)（平均）
- 不预先分配大量空间，按需增长，节省内存
- 结构简单，维护成本低，适合冲突不严重的情况
但如果所有 key 都撞进同一个桶，链表会越来越长，查找退化成 O(n)，性能急剧下降。
红黑树应对极端哈希冲突，保障最坏性能
当某个桶的链表长度 ≥ 8 且 数组长度 ≥ 64 时，链表自动转为红黑树：
- 查询、插入、删除最坏时间复杂度从 O(n) 降到 O(log n)
- 红黑树自平衡，能稳定应对大量冲突数据（比如恶意构造的 key）
- 但只在“又长又满”的桶中启用，避免小数据量下树结构的额外开销
反过来，当树中节点数 ≤ 6 时，又会退化回链表——这是为了防止频繁树化/退化带来的扰动，也减少轻量级场景下的内存和逻辑负担。
这个组合不是堆砌，而是分层响应
数组负责宏观定位，链表处理日常碰撞，红黑树兜底极端情况。它既没选纯哈希表（无法容错），也没选纯树结构（失去 O(1) 优势），是在真实工程约束下演化出的成熟方案。
