Java中HashMap底层是“数组+链表+红黑树”动态组合结构：数组为哈希桶主干，通过(n-1)&hash快速寻址；冲突时用链表挂载，长度≥8且数组容量≥64时树化为红黑树，节点≤6时退化回链表；扩容时翻倍并重哈希，兼顾O(1)平均性能与O(log n)最坏查询。
Java 中 HashMap 的底层结构是“数组 + 链表 + 红黑树”的组合，核心目标是在不同数据规模下兼顾查询效率和内存开销。它不是静态固定结构，而是动态演化的：初始只有数组；冲突多时链表生长；链表过长（默认 ≥8）且数组够大（≥64）时转为红黑树；扩容或删除后还可能退化回链表。
数组是哈希桶的主干
HashMap 底层维护一个 Node<K,V>[] 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免费学习笔记（深入）”；
- 插入：先计算下标，若桶为空直接放入；否则遍历链表，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），直接转成链表
这个过程确保扩容后结构依然合理，不会残留过长链表或无效红黑树。
