哈希冲突是怎么产生的？有哪些解决方法？
简化版
不同的键经过哈希函数算出了同一个下标，就叫哈希冲突。因为键的数量远多于桶的数量（鸽巢原理），冲突不可避免。主流解决方法两大类：拉链法（每个桶挂一条链表/红黑树，冲突元素串起来）和开放寻址法（冲突了就按规则去找下一个空桶）。Java 的 HashMap 用的是拉链法。
详细版
冲突的来源：哈希函数把无限（或很大）的键空间压缩到有限的桶数组里，压缩必然有多个键落到同一格。这是数学上注定的，只能缓解不能消除。
四种经典解法：
| 方法 | 思路 | 代表 |
|---|---|---|
| 拉链法（链地址法） | 每个桶存一条链表，冲突的都挂在后面 | Java HashMap、大多数语言 |
| 开放寻址法 | 冲突就在数组里另找空位（线性/二次探测、双重哈希） | Python dict、ThreadLocalMap |
| 再哈希法 | 冲突时换一个哈希函数再算，直到不冲突 | 较少用 |
| 建立公共溢出区 | 冲突元素统一放到另一个溢出表 | 教学概念为主 |
实际工程里以拉链法和开放寻址法为绝对主流。
完整版教学
一、为什么冲突必然发生（鸽巢原理）
哈希表的桶是有限的（比如 16 个），而可能的键是无限的（所有字符串）。把无限个「鸽子」放进有限个「笼子」，必然有笼子装了不止一只——这就是鸽巢原理。所以任何哈希表设计都必须自带冲突处理，不存在「永不冲突」的通用哈希表。
二、拉链法：给每个桶挂链表
桶数组的每个格子不直接存元素，而是存一条链表的头。冲突的元素都追加到对应桶的链表上。
- 查找：定位桶 → 沿链表逐个比较 key。
- 优点：实现简单；删除方便（改指针即可）；负载因子可以大于 1（链表能无限接）；对哈希函数要求相对宽松。
- 缺点：额外的指针内存开销；链表节点内存分散、缓存不友好；冲突严重时链表变长，查找退化 O(n)。
Java 8 起，当某个桶链表长度 ≥ 8 且数组容量 ≥ 64 时，链表会转成红黑树，把最坏查找从 O(n) 降到 O(log n)，防止被恶意构造的哈希碰撞攻击。
三、开放寻址法：所有元素都住在数组里
不挂链表，冲突了就在同一个数组里往后找空位。常见探测方式：
-
线性探测：
(hash + 1) % cap, (hash + 2) % cap, ...逐格往后找。简单，但容易形成「一堆连续占用」的聚集（clustering），降低效率。 -
二次探测：步长按
1², 2², 3²...增长，缓解一次聚集。 -
双重哈希：用第二个哈希函数决定步长，分布更均匀。
-
优点：没有链表指针开销，全部数据连续在数组里，缓存友好。
-
缺点：负载因子必须 < 1（数组会满）；删除麻烦（不能直接清空，否则会中断探测链，需用「墓碑标记」）；对哈希函数和负载因子更敏感。
四、两类方法怎么对比记
- 拉链法：桶外挂链表，「纵向」延伸，容得下、删得动，但缓存差 —— 适合负载高、频繁增删。
- 开放寻址：都挤在数组里，「横向」找空位，缓存好、省内存，但删除烦、怕装满 —— 适合负载低、读多、追求缓存性能。
五、冲突越少越好，但根治靠「均匀 + 扩容」
冲突处理是「兜底」，真正让哈希表保持 O(1) 的是两点：哈希函数足够均匀（少产生冲突）+ 负载因子超标就扩容 rehash（桶不够了就加桶，把扎堆的元素重新打散）。冲突解决方法只是让「已经发生的冲突」不至于崩，而不是让冲突消失。
六、常见误区与追问
| 冲突解决方式 | 插入位置 | 删除难度 | 典型特点 |
|---|---|---|---|
| 拉链法 | 桶内链表/树 | 较简单 | 负载弹性大 |
| 线性探测 | 下一个空槽 | 较复杂 | 缓存友好但易聚集 |
| 二次探测 | 按平方步长探测 | 较复杂 | 缓解一次聚集 |
| 双重哈希 | 用第二个哈希决定步长 | 较复杂 | 分布更灵活 |
capacity=5
keyA -> index 2
keyB -> index 2 发生冲突
拉链法: bucket[2] -> keyA -> keyB
开放寻址: bucket[2]=keyA, bucket[3]=keyB易错点：哈希冲突不是异常情况，而是哈希表必须面对的常态。优秀实现靠均匀哈希、合理负载因子和扩容把冲突控制在可接受范围。
如果容量是 10，却要放 12 个不同 key，根据鸽巢原理至少有一个桶会冲突。即使容量大于元素数，哈希函数把多个 key 映射到同一下标时也会冲突。平均 O(1) 建立在冲突较少且桶长度可控的前提上。
- 误区：好的哈希函数可以彻底消灭冲突。 有限桶映射无限或大量 key，冲突不可避免，只能降低概率。
- 误区：发生冲突后哈希表就退化成 O(n)。 少量冲突仍然可控，严重扎堆才会让桶链或探测序列变长。
- 误区：开放寻址比拉链法一定更省事。 开放寻址删除和高负载探测更复杂，不能只看它不需要链表节点。
- 追问：为什么负载因子会影响冲突？ 元素越接近桶容量，空位越少，冲突和探测成本越高。
- 追问：Java HashMap 冲突严重时怎么处理？ 链表长度达到条件且容量足够时会树化，用红黑树降低桶内查找复杂度。
- 追问：如何减少冲突？ 改善 hash 分布、扩容、选择合适负载因子，并避免低质量 key 哈希。
七、加强记忆
不同键算到同一下标就是哈希冲突，由鸽巢原理注定不可避免。两大解法：拉链法（桶挂链表/红黑树，好删、负载可>1、缓存差，Java HashMap 用它）和开放寻址法（冲突就在数组里探测找空位，缓存好、省内存，但删除难、负载须<1）。真正保持 O(1) 靠均匀哈希 + 及时扩容，冲突处理只是兜底。