Java HashMap底层是“数组+链表+红黑树”混合结构：Node[] table数组初始容量16，扩容为2的幂；哈希计算用扰动函数提升分布均匀性；冲突时链表存储，长度≥8且数组≥64转红黑树；超负载因子0.75触发扩容并重哈希。
Java 中 HashMap 的底层哈希表结构，核心是“数组 + 链表 + 红黑树”的混合实现，JDK 8 及以后版本采用该设计，兼顾查询效率与空间利用率。
数组是哈希表的主干结构
HashMap 内部维护一个 Node<k>[] table</k> 数组，每个数组元素是一个桶（bucket），初始容量为 16，扩容时按 2 的幂次增长（如 32、64…）。键值对通过哈希值定位到具体桶：计算 hash(key) & (table.length - 1) 得到下标。这个位运算等价于取模，但更高效，前提是数组长度必须是 2 的幂。
哈希冲突用链表和红黑树解决
当多个键的哈希值映射到同一数组下标时，发生哈希冲突。HashMap 将冲突元素以链表形式挂在该桶上：
- 新节点头插或尾插（JDK 8 改为尾插，避免多线程扩容死链）
- 当链表长度 ≥ 8 且数组长度 ≥ 64 时，链表转为红黑树，提升最坏情况查找性能（从 O(n) 降到 O(log n)）
- 若红黑树节点数 ≤ 6，则退化回链表
哈希值计算做了扰动处理
为降低低位重复导致的聚集，HashMap 对 key 的原始 hashCode 做了高位参与运算的扰动：
立即学习“Java免费学习笔记（深入）”；
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}这使得高 16 位与低 16 位混合，让哈希分布更均匀，尤其在数组较小时能减少碰撞。
扩容机制保证负载均衡
当元素数量超过 threshold = capacity × loadFactor（默认负载因子 0.75）时触发扩容：
- 新建两倍容量的数组
- 所有已有节点重新计算桶位置（因数组长度变化，下标可能改变）
- 链表或红黑树中的节点被拆分到新数组的原位置或原位置 + 旧容量处（利用 2 的幂特性，仅需判断 hash 的某一位）
