HashMap底层是数组+链表+红黑树结构：数组为桶主体，哈希冲突时用链表解决；链表长度≥8且数组容量≥64时转红黑树优化查询，退化阈值为6；通过扰动函数和位运算（(n-1)&hash）高效定位索引；扩容触发条件为size>capacity×0.75，扩容后容量翻倍。
面试时讲 HashMap 底层原理，关键不是背定义，而是用清晰逻辑串起“结构—计算—冲突—优化—扩容”这条主线。回答要体现你真正理解它为什么这么设计，而不是只记住几个名词。
底层数据结构：数组 + 链表 + 红黑树
HashMap 的主干是一个 Node
当多个 key 的哈希值算出同一个数组下标（即哈希冲突），就用链表把它们串起来；链表节点是 Node 类型，含 hash、key、value 和 next 指针。
从 JDK 1.8 开始加了红黑树优化：
立即学习“Java免费学习笔记（深入）”；
- 某个桶里链表长度 ≥ 8 且 当前数组总长度 ≥ 64，链表会转成红黑树，把最坏查询从 O(n) 降到 O(log n)
- 如果树中节点数减少到 ≤ 6，又会自动退化回链表，避免小数据量时树的维护开销
哈希计算与索引定位：扰动函数 + 位运算
put 或 get 时，核心是把 key 映射到数组下标。过程分两步：
- 先调用 key.hashCode() 得到原始哈希值 h
- 再执行扰动：hash = h ^ (h >>> 16)，让高16位参与运算，减少低位重复导致的聚集冲突
- 最后用 (n - 1) & hash 替代取模（比如 n=16 → 15 & hash），因为 n 是 2 的幂，位运算更快更稳定
这个设计说明：HashMap 不依赖 key.hashCode() 的质量，自己做了二次加工来提升散列均匀性。
哈希冲突处理：链地址法是基础，红黑树是升级
冲突不可避免，HashMap 采用链地址法——相同桶位的元素挂成链表。但链表太长会拖慢查询，所以引入红黑树作为“性能兜底”。
注意两个转换条件必须同时满足：
- 链表长度 ≥ 8（阈值可调，但源码写死为 8）
- 数组容量 ≥ 64（防止小容量时频繁树化，得不偿失）
这反映出设计者权衡了空间、时间、实现复杂度——不是越早转树越好，而是看实际收益。
扩容机制：触发条件、过程与线程安全问题
当 size（当前键值对数量）超过 threshold（阈值 = 容量 × 负载因子），就会扩容。默认负载因子是 0.75，初始容量 16 → 阈值就是 12。
扩容过程：
- 新建一个容量翻倍的数组（比如 16 → 32）
- 把老数组里每个桶的元素重新 hash、重新计算下标，搬进新数组
- JDK 1.8 优化了搬迁逻辑：链表/树节点根据新数组长度的最高位是否为 1，直接拆成高低两个子链，不用全部 rehash
正因为扩容涉及数组重建和元素搬迁，且全程无锁，所以 HashMap 是非线程安全的。多线程 put 可能导致死循环（JDK 1.7）、数据覆盖或丢失（JDK 1.8），并发场景应选 ConcurrentHashMap。
