哈希冲突是哈希表设计中必然现象，源于哈希函数输出空间有限而键值无限；Java HashMap 采用链地址法，JDK 8 起链表≥8且数组≥64时转红黑树，删除≤6节点退化回链表。
哈希冲突不是 bug，而是哈希表设计中必然发生的现象：不同键算出相同的数组下标，导致它们要挤进同一个“桶”里。
哈希冲突是怎么产生的
根本原因就两条：哈希函数输出空间有限（比如数组长度是 16，索引只能是 0~15），而键的可能取值几乎是无限的。哪怕 hashCode() 返回值再分散，经过 index = hashCode & (table.length - 1)（JDK 8+ 的位运算取模）后，也大概率会撞车。
- 比如
"Aa"和"BB"的hashCode()都是 2112，若数组长度为 16，两者都落到索引0 - 只要元素数量超过数组容量 × 装载因子（默认 0.75），冲突概率就急剧上升
- 糟糕的
hashCode()实现（如所有对象都返回 1）会让冲突变成“全塞进第一个桶”
Java HashMap 怎么解决哈希冲突
它用的是链地址法（Chaining），但不是一成不变的链表——JDK 8 起做了关键升级：链表过长时自动转红黑树。
- 插入时，先计算
hash得到桶索引；如果该位置已有节点，就遍历链表比对equals() - 当链表长度 ≥ 8 且
table.length >= 64时，触发树化：链表转为TreeNode构成的红黑树 - 扩容或删除后，若树中节点 ≤ 6，则退化回链表（避免小树维护开销）
- 注意：
TreeNode不是java.util.TreeMap，而是 HashMap 自定义的、带树形结构的 Node 子类
为什么不用开放寻址法（比如线性探测）
因为链地址法更适合 Java 的通用场景，尤其在高负载、大对象、动态伸缩时更稳健。
立即学习“Java免费学习笔记（深入）”；
- 开放寻址法（如
ThreadLocalMap用的线性探测）要求装载因子必须远低于 1（通常 ≤ 0.7），否则探测链暴涨，性能断崖下跌 - 链表/红黑树允许装载因子 > 1（比如 2.0），内存利用率更高，也更容易支持
null键值（开放寻址法需特殊标记“已删除”，null就没法区分） - 链地址法删除简单（直接 unlink），而开放寻址法删除后必须打删除标记，否则会截断后续探测路径
- 不过代价是：每个节点多存一个指针（链表）或多个字段（红黑树），小对象场景有内存冗余
实战中容易踩的坑
很多看似奇怪的行为，其实都源于对哈希冲突处理机制的误判。
-
key的hashCode()和equals()没一起重写 → 冲突时无法正确识别重复键，导致“明明 put 了却 get 不到” - 自定义 key 类忘了让
hashCode()对字段变化敏感 → 同一个对象修改后，get()找不到自己（因为 hash 值变了，去错桶了） - 把可变对象（如
ArrayList）当 key 用 → 一旦 list 内容改变，hashCode()变，原桶里找不到了，也放不进新桶（因为HashMap不会自动 rehash） - 盲目调大初始容量（如
new HashMap(1000)）却不设装载因子 → 内存浪费，且没解决本质冲突分布问题；不如优先优化 key 的hashCode()
真正影响性能的，从来不是“有没有冲突”，而是“冲突是否集中”。一个设计不良的 hashCode() 比任何扩容策略都致命。
