哈希表是一种高效的数据结构，它能让我们通过“键”快速找到对应的“值”。想象一下，哈希表就像一个巨大的抽屉集合，每个抽屉有唯一的编号（数组位置），我们通过一个“钥匙规则”（哈希函数）把每个“物品”（键）放进对应的抽屉，这样找东西时直接打开抽屉就能拿到，不需要翻遍所有抽屉。但这个“钥匙规则”可能会出问题——不同的物品（键）可能被塞进同一个抽屉（数组位置），这就是“哈希冲突”。
一、哈希冲突是什么？¶
当两个不同的键（比如学号101和201）通过哈希函数计算后，映射到了哈希表的同一个数组位置（比如第5个抽屉），就发生了哈希冲突。就像两个同学用不同的名字（键），但因为某种规则（哈希函数）被分到了同一个教室座位（数组位置），这时就需要想办法让他们“各就各位”。
二、为什么会冲突？¶
哈希冲突的本质是 “键的数量远大于数组容量”，或者 “哈希函数设计得不够均匀”。
举个简单的例子：如果哈希表的数组长度是10（抽屉有10个），但我们有100个不同的键（比如1到100的学号），那么根据“取模10”的哈希函数（即 键 % 10），键1、11、21…91都会被放进第1个抽屉，键2、12、22…92放进第2个抽屉，以此类推。但10个抽屉只能装10个不同的余数（0-9），当键的数量超过10时，必然有多个键会被塞进同一个抽屉，冲突就发生了。
三、如何解决哈希冲突？¶
解决冲突的核心思路是：当冲突发生时，想办法让冲突的键“各占一个位置”。常见方法有以下几种：
1. 链地址法（拉链法）——最常用的方法¶
原理：每个数组位置（抽屉）不再是单个“空抽屉”，而是一个“链表”（小链条）。当多个键冲突时，把它们按顺序“挂”在对应的链表后面。
举个例子：
- 数组有4个位置（抽屉0-3），哈希函数是 键 % 4。
- 插入键5（5%4=1）→ 抽屉1的链表：[5]
- 插入键1（1%4=1，冲突）→ 抽屉1的链表变成：5 → 1
- 插入键9（9%4=1，冲突）→ 抽屉1的链表变成：5 → 1 → 9
- 插入键3（3%4=3）→ 抽屉3的链表：[3]
- 插入键13（13%4=1，冲突）→ 抽屉1的链表变成：5 → 1 → 9 → 13
查找时：先根据键计算数组位置（抽屉1），再遍历该位置的链表找到目标键（比如找13，就在链表中从5开始往后找）。
优点：实现简单，空间利用率高，不会出现“空位浪费”，是大多数编程语言（如Java的HashMap）的底层实现方式。
2. 开放定址法——从冲突位置往后找空位置¶
原理：当发生冲突时，从冲突位置的下一个位置开始，依次寻找空位置。
线性探测（最简单的开放定址法）：
- 冲突时，步长为1，即 i+1, i+2, i+3...（i为冲突位置）。
举个例子：
- 数组位置1有键5，插入键1（冲突）→ 尝试位置2（空），放入位置2。
- 插入键2（2%4=2，冲突）→ 尝试位置3（空），放入位置3。
- 插入键6（6%4=2，冲突）→ 位置2已被占，尝试位置3（已被占），尝试位置4（空，假设数组长度为5），放入位置4。
缺点：容易形成“聚集”（多个冲突键连续占用多个位置），比如连续插入10个冲突键，会占用10个位置，影响后续效率。
3. 二次探测——步长变大，减少聚集¶
原理：冲突时，步长不是1，而是平方数（1², 2², 3²…），比如 i+1², i+2², i+3²...。
举个例子：
- 冲突位置i=1，步长1²=1 → 位置2；若冲突，步长2²=4 → 位置1+4=5；若还冲突，步长3²=9 → 位置1+9=10…
优点：相比线性探测，能减少聚集，但步长设计不当仍可能聚集，实现稍复杂。
4. 双重哈希法——用多个哈希函数¶
原理：当第一个哈希函数冲突时，用第二个哈希函数计算新位置。
举个例子：
- 第一个哈希函数：h1(k) = k % 4（冲突位置1）。
- 第二个哈希函数：h2(k) = (k // 10) % 5（另一种映射规则）。
- 冲突时，新位置 = h1(k) + h2(k)，直到找到空位置。
优点：通过多个哈希函数分散冲突，减少聚集，但需要维护多个哈希函数，实现较复杂。
5. 公共溢出区——主区+溢出区¶
原理：主数组存“不冲突的键”，冲突的键统一放进“溢出区”数组。
查找时：先在主数组找，没找到再去溢出区找。
缺点：溢出区大小难确定，可能因空间不足导致插入失败。
四、总结¶
哈希冲突是哈希表的“天生问题”，因为键的数量永远可能超过数组容量，而哈希函数无法做到绝对均匀。解决方法中，链地址法（拉链法） 最直观、最常用，它通过“链表挂接”解决冲突，实现简单且效率高；开放定址法（线性/二次/双重）通过“往后找位置”解决冲突，但可能有聚集问题。实际使用中，需根据场景选择合适的方法。
理解哈希冲突和解决方法，能帮助你更好地设计和优化哈希表，写出高效的代码~