Java HashMap基于哈希表实现，平均O(1)时间复杂度完成K-V操作；底层采用数组+链表+红黑树结构，JDK 8起链表≥8且数组≥64时树化；通过hash()扰动提升散列均匀性，(n-1)&hash定位下标；扩容时长度翻倍并按原索引或原索引+oldCap拆分迁移；key需不可变且重写equals/hashCode以保证一致性。
Java HashMap 是基于哈希表实现的键值对（K-V）集合，核心目标是用 O(1) 平均时间复杂度 完成插入、查找和删除操作。它不是线程安全的，底层靠数组 + 链表 + 红黑树协同工作，JDK 8 是关键分水岭。
数组 + 链表 + 红黑树：三段式存储结构
HashMap 底层是一个Nodetable），每个数组元素是一个“桶（bucket）”。新节点根据 key 的 hashCode() 计算索引位置，存入对应桶中：
- 如果桶为空 → 直接新建 Node 放进去
- 如果桶已有节点 → 先比 hash 值，再比
equals()；相同则覆盖 value；不同则链表尾插（JDK 7 是头插，有死循环风险） - 当链表长度 ≥ 8 且 数组长度 ≥ 64 → 触发树化，转为红黑树（避免长链表退化成 O(n) 查找）
- 红黑树节点数 ≤ 6 时，会退化回链表（减少小数据量下的树维护开销）
hash() 方法：让散列更均匀
直接用 key.hashCode() 不够安全——高位信息容易丢失，导致大量哈希冲突。HashMap 自己做了扰动：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}把高16位异或到低16位，让低位也参与索引计算，大幅降低碰撞概率。真正定位数组下标用的是：(n - 1) & hash（n 是数组长度，必须是 2 的幂），等价于取模但更快。
立即学习“Java免费学习笔记（深入）”；
扩容机制：resize() 是性能关键点
初始容量默认是 16，负载因子（loadFactor）默认 0.75。当 size > capacity × loadFactor（即元素数超 12）就触发扩容：
- 新数组长度 = 原长度 × 2（保持 2 的幂）
- 所有旧节点要重新计算索引，搬进新数组（rehash）
- JDK 8 优化了迁移过程：每个桶内节点按 “原索引” 或 “原索引 + oldCap” 拆成两组，不用全部重新 hash，提升效率
- 注意：扩容是耗时操作，建议预估大小，用带 initialCapacity 构造函数避免频繁 resize
key 为什么推荐不可变 & 要重写 equals/hashCode
HashMap 依赖 key 的 hashCode() 定位桶、用 equals() 判等。如果 key 可变（比如用了普通可变对象且改了影响 hash 的字段）：
- put 时存在某桶 A，get 时 hash 变了去桶 B 找 → 找不到（逻辑丢失）
- 所以 String、Integer 等不可变类天然适合做 key
- 自定义类作 key，必须重写
hashCode()和equals()，且保证：相等对象 hashCode 一定相同；hashCode 相同不一定要 equals
基本上就这些。理解数组定位、扰动 hash、链表树化、扩容拆分这四点，就抓住了 HashMap 的骨架。它不是黑盒，而是一套精巧平衡时间与空间的设计。
