一、什么是哈希碰撞？
你可以把 哈希函数 想象成一个“数字打印机”，它能把任意输入（比如字符串、对象）变成一个固定长度的数字（哈希值）。
比如：
输入“苹果”，得到哈希值 123；输入“香蕉”，得到哈希值 456；但如果输入“西瓜”和“菠萝”，都得到了 789，这就叫 哈希碰撞（两个不同的输入，算出了相同的哈希值）。
为什么会碰撞？
因为哈希值的范围是有限的（比如4字节的哈希值只有约42亿种可能），但输入的可能性是无限的，所以 碰撞无法完全避免，只能尽量减少。
二、如何解决哈希碰撞？
虽然碰撞无法杜绝，但我们可以用一些方法来“处理”碰撞，让数据依然能正确存储和查找。下面是几种常见的解决方案：
1. 链地址法（拉链法）—— 最常用！
原理：在哈希表的每个位置（桶）上，维护一个 链表（或树结构）。当多个元素碰撞到同一个桶时，把它们按顺序串起来。例子：
比如哈希表有10个桶（编号0-9），元素A的哈希值对应桶3，元素B的哈希值也对应桶3。
这时，桶3里会有一个链表：A → B。
查找时，先找到桶3，再逐个对比链表中的元素是否相等。Java中的应用：
Java的 HashMap 在JDK1.8之前用纯链表处理碰撞，JDK1.8之后，当链表长度超过阈值（默认8）时，会升级为 红黑树（查找效率从O(n)变成O(logn)），进一步优化性能。
2. 开放寻址法 —— 找下一个“空位”
原理：当碰撞发生时，不使用链表，而是在哈希表中寻找下一个 空闲的位置 存放元素。寻找下一个位置的方法：
线性探测：从当前位置开始，逐个往后找空位（比如当前位置是3，就依次检查4、5、6…）。二次探测：用公式（当前位置 + k²）找空位（k=1, -1, 2, -2…），避免“扎堆”。
缺点：可能导致元素“聚集”，影响查找效率，所以实际应用不如链地址法广泛。
3. 再哈希法 —— 换个哈希函数再算一次
原理：准备多个哈希函数，当第一个函数算出的位置碰撞时，用第二个函数重新计算哈希值，直到找到不冲突的位置。例子：
第一次用 hash1(key) 得到位置3（碰撞），第二次用 hash2(key) 得到位置5（若空闲则存入）。优点：减少聚集问题；缺点：每次碰撞都要计算新的哈希值，增加计算成本。
4. 建立公共溢出区 —— 专门存“撞车”的元素
原理：把哈希表分为两部分：
主表：存放正常的元素；溢出区：专门存放所有碰撞的元素。
缺点：查找时需要先查主表，再查溢出区，效率较低，现在很少使用。
5. 优化哈希函数 —— 从源头减少碰撞
虽然无法完全避免碰撞，但可以让哈希值分布更均匀：
合理设计哈希函数：比如Java中 String 的哈希函数，会混合每个字符的ASCII码，减少碰撞概率。重写自定义类的 hashCode() 和 equals()：
如果用自定义对象作为HashMap的键，必须正确重写这两个方法，让相似的对象哈希值差异大。class Student {
private String id;
private String name;
@Override
public int hashCode() {
return id.hashCode() + name.hashCode(); // 混合多个属性的哈希值
}
@Override
public boolean equals(Object o) {
if (o == this) return true;
if (o == null || getClass() != o.getClass()) return false;
Student s = (Student) o;
return id.equals(s.id) && name.equals(s.name);
}
}
三、总结：碰撞不可怕，方法很重要！
哈希碰撞：不同输入算出相同哈希值，无法避免但能处理。主流解决方案：
链地址法（HashMap的选择，链表+红黑树）；优化哈希函数（减少碰撞概率）；其他方法（开放寻址、再哈希等，按需选择）。
理解哈希碰撞和解决方法，能帮你更好地使用哈希表（如HashMap），写出高效的代码~ 如果有疑问，欢迎留言讨论！ 😊