哈希表是数据结构里的“查找小能手”，它通过哈希函数把键快速映射到数组的某个位置，实现O(1)的平均查找效率。但如果两个不同的键通过哈希函数映射到同一个位置，就会发生哈希冲突。这时候，我们该怎么解决冲突呢？今天用最简单的方式聊聊几种常见的哈希冲突解决方法，让你轻松理解数据结构里的哈希逻辑。
一、哈希冲突是什么？¶
先回忆一下哈希表的基本原理：哈希表本质是一个数组，数组的每个位置叫做“槽位”（slot）。我们把键（比如学生的名字、商品的ID）通过哈希函数（比如key % 数组长度）计算出一个索引，这个索引就是键在数组里的“家”。
但问题来了：如果两个不同的键算出来的索引相同（比如键1和键6，数组长度是5，哈希函数都是key % 5，那么1%5=1，6%5=1，冲突！），这时候就会抢同一个“家”，这就是哈希冲突。
二、解决冲突的核心思路¶
冲突发生后，我们需要给冲突的元素找“新的家”。常见的思路有两种：
1. 把冲突的元素“挂”在同一个槽位（比如多个元素共用一个链表）；
2. 往其他空槽位“挤一挤”（比如顺着数组往后找空位置）。
三、最常用的两种解决方法¶
1. 链地址法（拉链法）：给冲突元素“建链表”¶
原理：每个槽位不是只存一个元素，而是存一个链表（或数组），所有冲突的元素都“挂”在这个链表上。
类比：就像快递柜，每个柜子（槽位）一开始是空的。如果两个快递的哈希值相同（比如都对应“柜子0”），就把它们放进这个柜子旁边的“临时货架”（链表）里，取件时先找柜子，再在货架上找。
举个例子：
假设哈希表数组长度是5（槽位0-4），哈希函数是key % 5。现在插入键1、6、11：
- 键1：1%5=1 → 槽位1是空的，直接放进去，链表[1] = [1]；
- 键6：6%5=1 → 槽位1已有元素，把6挂到链表末尾，链表[1] = [1,6]；
- 键11：11%5=1 → 同样挂到链表，链表[1] = [1,6,11]。
查找时：比如找键6，先算6%5=1，定位到槽位1，然后遍历链表[1,6,11]，找到6。
优点：实现简单，适合动态数据（随时增删），不会浪费空间（没冲突就不用建链表）。
缺点：需要额外空间存链表，查找时需要遍历链表（最坏O(n)时间，但平均还是O(1)）。
2. 开放寻址法：“挤一挤”找空槽位¶
原理：如果槽位i被占用，就从i开始往后找空槽位（或往前），直到找到空位。根据“找空槽位”的规则不同，分为：
- 线性探测：冲突时，依次探测i+1, i+2, ..., m-1, 0, 1,...（循环）；
- 二次探测：冲突时，探测i+1², i+2², i+3²,...（避免连续聚集）。
类比：排队买奶茶，第一个人（键）站在1号窗口（槽位1），第二个人（键）也站1号窗口冲突了，就站2号窗口（线性探测）；如果2号也冲突，就站4号（二次探测，1+1²=2，2+1²=3，3+1²=4）。
举个例子：
数组长度5，哈希函数key%5，插入键1（槽位1）、键6（槽位1冲突）：
- 键1：1%5=1 → 空槽位，放1；
- 键6：6%5=1 → 冲突，线性探测到1+1=2（空），放6。
再插入键11：11%5=1 → 冲突，线性探测到2（被6占），3（空），放11。
查找时：找键6，算6%5=1→槽位1，发现不是，线性探测到2（6），找到。
优点：空间利用率高（数组不用浪费额外空间），实现简单（不需要链表）。
缺点：线性探测会导致“聚集”（多个冲突元素挤在一起），可能填满数组；二次探测可以缓解聚集，但需要更大的数组空间（避免找不到空位）。
四、其他方法（简单了解）¶
- 再哈希法：冲突时用另一个哈希函数重新计算位置，直到找到空位。比如
f(key, i) = (f1(key) + i*f2(key)) % m，i=0,1,2…。适合冲突较少的场景，但需要多个哈希函数。 - 公共溢出区：把哈希表分为“基本表”和“溢出表”。基本表存无冲突的元素，冲突的元素全放溢出表。查找时先查基本表，没找到再查溢出表。适合冲突少的静态数据，但溢出表管理复杂。
五、总结：选哪种方法？¶
- 链地址法：Java的HashMap、Python的字典都用这种方法，实现简单，适合动态数据量大、冲突多的场景（比如数据量不固定时）。
- 开放寻址法：适合数组大小固定、冲突少的场景（比如已知数据范围时），线性探测简单但聚集多，二次探测更灵活。
- 其他方法：再哈希法适合冲突少且需严格避免聚集的场景，公共溢出区适合冲突极少的静态数据。
哈希冲突的解决方法本质是“如何给冲突元素找新位置”，理解这两种核心方法（链地址法和开放寻址法）就能应对大部分场景啦。下次写代码实现哈希表时，就知道该怎么处理冲突了～