什么是哈希冲突？
在数据结构里，哈希冲突（Hash Collision）指的是不同的输入数据经过哈希函数计算后，得到了相同的哈希值（即数组索引）。因为哈希表容量有限，而输入数据理论上无限，所以冲突在实际应用中很难完全避免。
为什么会发生冲突？
- 哈希表大小固定：底层通常是数组，长度确定，但数据量可能远超容量。
- 分布不均匀：理想状态下哈希函数应均匀分布数据，但受限于算法特性或数据特征，某些桶位容易堆积。
常见的解决策略
- 链地址法（Chaining）：每个桶挂一个链表，冲突时追加到链表尾部。这是 Java
HashMap处理冲突的主流方式之一。 - 开放寻址法（Open Addressing）：冲突时探测下一个空闲位置，比如线性探测、二次探测。
- 双重哈希：利用第二个哈希函数计算偏移量。
- 扩容机制：当负载因子超过阈值，扩大数组并重新散列。
链地址法实战示例
下面是一个基于链表解决冲突的简易实现，重点看 insert 逻辑：
import java.util.LinkedList;
import java.util.List;
class HashTable {
private List<List<String>> table;
public HashTable(int size) {
table = new LinkedList<>();
for (int i = 0; i < size; i++) {
table.add(new LinkedList<>());
}
}
public void insert(String key, String value) {
int index = hashFunction(key);
// 冲突时直接追加到对应位置的链表中
table.get(index).add(value);
}
private int hashFunction(String key) {
return key.hashCode() % table.size();
}
}
