Java HashMap底层是“数组+链表+红黑树”结构：数组实现O(1)定位，链表解决哈希冲突，当链表长度≥8且数组长度≥64时转为红黑树以优化查询至O(log n)。
Java 中 HashMap 的“数组加链表”结构，本质是为兼顾查找速度和空间利用率而设计的哈希表实现方式。它不是两种结构简单拼凑，而是有明确分工：数组负责快速定位，链表负责容错处理。
数组是主干，每个位置叫一个“桶”
HashMap 底层维护一个 Node[] 类型的数组（JDK 8 起叫 table），默认长度 16，且必须是 2 的幂。每个数组元素就是一个“桶（bucket）”，代表一个哈希值对应的位置。当你 put 一个键值对时，系统先算 key 的 hash 值，再通过 (n - 1) & hash（n 是数组长度）快速算出它该落在哪个下标上——这个运算比取模快，且能均匀分布。
- 如果那个位置还是 null，直接把新节点放进去
- 如果已有节点，说明发生哈希冲突，就进入链表处理逻辑
链表解决哈希冲突，串起同桶的多个键值对
哈希冲突不可避免：不同 key 可能算出相同数组下标。这时，HashMap 不覆盖旧数据，而是把新节点以头插法（JDK 7）或尾插法（JDK 8+）接在已有链表后面。每个链表节点（Node）包含 key、value、hash 和 next 指针，形成单向链表。
- get 时先定位到桶，再遍历链表，用 == 或 equals() 判断 key 是否匹配
- 链表越长，查找越慢（最坏 O(n)），所以不能任其无限增长
链表不是终点，红黑树是性能兜底方案
JDK 8 引入了红黑树优化，但前提是两个条件同时满足：
立即学习“Java免费学习笔记（深入）”；
- 链表长度 ≥ 8
- 数组长度 ≥ 64
不满足任一条件，优先选择扩容（resize）而不是树化。因为小数组配红黑树反而更耗资源；而链表短时，遍历比树操作更快。树化后，查找从 O(n) 降到 O(log n)，大幅缓解极端哈希分布下的性能退化。
为什么不用纯链表或纯数组？
纯数组无法处理冲突，空间浪费大（要极大容量才减少碰撞）；纯链表失去 O(1) 定位能力，所有操作退化为遍历。数组 + 链表（+ 红黑树）是在时间与空间之间做的务实平衡：日常场景靠数组直达，冲突少时链表够用，极端情况由红黑树托底。
