Java HashMap底层是数组+链表+红黑树结构：数组通过扰动哈希与位运算定位桶，链表解决哈希冲突，链表长度≥8且数组长度≥64时转红黑树优化查询，扩容机制维持O(1)平均性能。
Java 中的 HashMap 底层是基于**数组 + 链表 + 红黑树**（JDK 8+）的哈希表实现，核心目标是用 O(1) 平均时间复杂度完成 key 的插入、查找和删除。
哈希函数与数组索引计算
HashMap 内部维护一个 Node[] table 数组，每个元素是一个链表或红黑树的头节点。当 put 一个键值对时：
- 先调用 key 的
hashCode()得到原始哈希值； - 再通过扰动函数（
(h = key.hashCode()) ^ (h >>> 16)）降低哈希冲突概率； - 最后用
(n - 1) & hash（n 是数组长度，必须是 2 的幂）代替取模运算，快速定位数组下标。
处理哈希冲突：拉链法
多个 key 经哈希后映射到同一数组位置（即“哈希碰撞”），HashMap 采用**链地址法（拉链法）**解决：
- 该位置的
Node节点形成单向链表； - 新节点默认头插（JDK 7）或尾插（JDK 8+），避免多线程扩容死循环问题；
- 查找时先定位数组下标，再遍历链表，用
equals()比较 key 是否相等。
链表转红黑树的阈值与条件
为防止极端哈希碰撞导致链表过长（退化为 O(n) 查找），JDK 8 引入红黑树优化：
立即学习“Java免费学习笔记（深入）”；
- 当链表长度 ≥ 8 且 数组长度 ≥ 64 时，链表转换为红黑树；
- 若数组扩容后某桶中红黑树节点数 ≤ 6，则退化回链表；
- 红黑树节点继承自
Node，但额外维护 parent/child/color 等字段，支持 O(log n) 查找。
动态扩容机制
当元素数量超过 threshold = capacity × loadFactor（默认负载因子 0.75）时触发扩容：
- 创建容量翻倍（×2）的新数组；
- 原数组中每个桶的节点重新计算索引（仅需判断原 hash 的高位是否为 1，决定是否加原容量）；
- 链表或红黑树整体迁移，保持结构有序性（红黑树会重新平衡）。
整个设计在空间与时间之间做了权衡：数组提供快速寻址，链表应对碰撞，红黑树兜底长链，扩容保证平均性能稳定。
