Java HashMap核心底层结构是数组+链表+红黑树：数组为Node[] table，容量为2的幂，默认16；哈希冲突时用链表（尾插法）解决；链表长度≥8且数组容量≥64时树化为红黑树，节点数≤6时退化回链表。
Java HashMap 的核心底层数据结构是“数组 + 链表 + 红黑树”的复合结构，不是单一容器，而是为兼顾性能与空间效率做的分层设计。
数组作为哈希桶的主干容器
HashMap 内部维护一个 Node
- 数组本身不存键值对，只存链表头节点或红黑树根节点
- 空桶对应数组元素为 null；非空桶指向链表第一个 Node 或 TreeNode
- 扩容时数组长度翻倍，所有已有元素需重新哈希、再分配到新桶中
链表用于处理低频哈希冲突
当多个 key 经过扰动哈希后落到同一数组下标，就发生哈希冲突。此时 HashMap 用单向链表把冲突节点串起来：
- 每个 Node 包含 hash、key、value 和 next 引用
- JDK 8 改为尾插法（JDK 7 是头插法），避免多线程扩容时形成环形链表导致死循环
- 链表查找需遍历，最坏时间复杂度 O(n)，但平均很短（依赖哈希分布）
红黑树优化高频冲突场景
当某个桶中链表长度 ≥ 8 且当前数组长度 ≥ 64 时，该链表会树化为红黑树；反之，若树中节点数 ≤ 6，则退化回链表：
立即学习“Java免费学习笔记（深入）”；
- TreeNode 继承自 Node，额外包含 parent、left、right、red 等字段
- 树化后查找/插入/删除降为 O(log n)，显著优于长链表的 O(n)
- 阈值设为 8 是经验值：泊松分布表明，哈希均匀时链表长度 ≥ 8 的概率已低于千万分之一
哈希计算与扰动机制保障分布质量
Key 的 hashCode() 原始值不直接用于寻址，而是经过扰动函数处理：
- 先调用 key.hashCode() 获取 32 位整数 h
- 执行 h ^ (h >>> 16)：让高 16 位参与低位运算，减少低位相同导致的聚集
- 再通过 (n - 1) & hash 得到最终数组索引
- 这个过程确保即使 hashCode() 设计不佳（如只变动低位），也能提升散列均匀性
不复杂但容易忽略
