HashMap底层是数组+链表+红黑树：数组作主干（默认容量16，2的幂，位运算定位），链表解决哈希冲突（JDK8尾插法），链表≥8且数组≥64时转红黑树（O(log n)查询），节点≤6时退化回链表；超负载因子0.75触发2倍扩容。

Java 的 HashMap 底层是“数组 + 链表 + 红黑树”三者结合的结构，核心目标是在不同数据量和哈希冲突程度下，兼顾查询、插入、删除的效率（平均 O(1)，最坏 O(log n)）。

数组是主体存储容器

HashMap 内部维护一个 Node<k>[] table</k> 数组，每个元素叫“桶（bucket）”。初始容量默认是 16，扩容时按 2 倍增长（如 16 → 32 → 64），保证长度始终是 2 的幂。这样做是为了用位运算 (n - 1) & hash 替代取模 hash % n，更快定位元素该存到哪个桶里。

• 每个数组索引位置可能为空（null），也可能指向一个节点（单个元素）
• 如果多个键的哈希值对数组长度取模后结果相同，就发生哈希冲突，这些元素会链在一起

链表解决哈希冲突（JDK 8 之前的主要方式）

当多个键映射到同一个桶时，HashMap 用链表把它们串起来。新插入的节点采用头插法（JDK 7）或尾插法（JDK 8），避免多线程扩容时的死循环问题。

• 链表查找需遍历，最坏情况所有元素都在一个桶里，时间复杂度退化为 O(n)
• 当链表长度 ≥ 8 且数组长度 ≥ 64 时，触发树化：链表转为红黑树

红黑树优化高频冲突场景

链表过长影响性能，所以 JDK 8 引入了红黑树。满足两个条件就将链表转换成红黑树：

Java 接口排错助手

在调试 Java 后端 API 故障时使用此技能，尤其适用于以下任务：分析日志、跨 Controller、Service 和 Mapper 层追踪请求、定位异常根因、检查 SQL 执行或参数流转，以及生成简洁的诊断结论与修复方案。

下载

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

• 当前桶中链表节点数 ≥ 8
• 整个数组长度（table.length）≥ 64

红黑树是自平衡二叉搜索树，查找/插入/删除都是 O(log n)。它比链表快，又比普通二叉搜索树稳定（不会退化成链表）。当红黑树节点数 ≤ 6 时，还会退化回链表，减少小规模时的结构开销。

扩容机制让负载更均衡

当元素总数（size）超过阈值（capacity × loadFactor，默认负载因子 0.75），就会触发扩容。例如默认 16×0.75 = 12，第 13 个元素插入前先扩容为 32。

• 扩容要重新计算每个元素的 hash 在新数组中的位置
• JDK 8 中利用了“2 倍扩容”的特性：原索引位置要么不变，要么变为 原索引 + 旧数组长度，只需一次遍历完成迁移
• 红黑树在扩容时也会拆分，节点按新哈希值分散到高低两个位置