java中hashmap底层是“数组+链表+红黑树”动态组合结构：数组为哈希桶主干，通过(n-1)&hash快速寻址；冲突时用链表挂载，长度≥8且数组容量≥64时树化为红黑树，节点≤6时退化回链表；扩容时翻倍并重哈希，兼顾o(1)平均性能与o(log n)最坏查询。

Java 中 HashMap 的底层结构是“数组 + 链表 + 红黑树”的组合，核心目标是在不同数据规模下兼顾查询效率和内存开销。它不是静态固定结构，而是动态演化的：初始只有数组；冲突多时链表生长；链表过长（默认 ≥8）且数组够大（≥64）时转为红黑树；扩容或删除后还可能退化回链表。

数组是哈希桶的主干

HashMap 底层维护一个 Node[] table 数组，每个元素叫一个“桶（bucket）”。key 经过 hash() 方法扰动计算（高16位异或低16位），再用 (n-1) & hash（n 是数组长度，2的幂）快速定位下标——这比取模 % 更快，也保证分布更均匀。

数组长度总是 2 的幂（如 16、32、64…），初始为 16，触发扩容（load factor = 0.75）时翻倍。扩容会重新哈希所有已有元素，分配到新数组中。

链表解决哈希冲突

当多个 key 的 hash 值映射到同一个数组下标时，发生哈希冲突。HashMap 用链表把它们串起来，头插法（JDK 7）改为尾插法（JDK 8+），避免多线程扩容死循环问题。

Java Maven Code Review

审查Java Maven项目（ZIP压缩包或GitLab仓库URL），检查代码规范、命名、模块边界、可维护性问题以及重复代码。

下载

• 插入：先计算下标，若桶为空直接放入；否则遍历链表，key 相等则覆盖 value，否则尾部追加新节点
• 查找：定位桶后，顺序遍历链表，用 equals() 比较 key（不是 ==）
• 删除：同样先定位再遍历，找到后断开前后指针

红黑树优化长链表查询

链表查找最坏 O(n)，当某个桶中节点数 ≥8 且数组长度 ≥64 时，该链表会树化（treeify）为红黑树。反之，如果删除后节点数 ≤6，又会反树化（untreeify）回链表。

树化条件两个缺一不可：防止小数组下频繁树化浪费空间；也避免极小容量时红黑树结构开销反而大于链表。

• 红黑树节点是 TreeNode，继承自 Node，额外包含 parent/child/red 字段
• 比较 key 仍依赖 hashCode 和 equals，但排序靠 compareTo（若实现 Comparable）或 System.identityHashCode
• 树化后查找、插入、删除都稳定在 O(log n)

扩容与树化/反树化的协同机制

扩容时，每个桶里的元素要重新分配到新数组的两个位置（原下标 or 原下标+oldCap）。链表和红黑树都会被拆分：

• 链表：按“hash & oldCap”是否为 0 分成两条，分别插入新桶的头或尾
• 红黑树：同样拆成两棵子树；若某棵子树节点太少（≤6），直接转成链表

这个过程确保扩容后结构依然合理，不会残留过长链表或无效红黑树。

Java免费学习笔记：立即使用
解锁 Java 大师之旅：从入门到精通的终极指南