（数据结构）哈希碰撞：线性探测法 vs 拉链法
一、哈希碰撞背景
哈希表（Hash Table）是一种通过 哈希函数（Hash Function）将 key 映射到数组下标的数据结构。
但由于数组长度有限，不同的 key 可能映射到同一个位置，这种情况称为 哈希碰撞。
为了解决碰撞问题，常用的方法有：
开放地址法（Open Addressing）：典型代表 → 线性探测法
链地址法（Chaining）：典型代表 → 拉链法
二、线性探测法（Linear Probing）
基本思想：
当一个位置冲突时，就往后一个一个找，直到找到空位为止。
例子：
hash(key) = i
if table[i] 被占用-> 检查 table[(i+1) % tablesize]-> 再检查 table[(i+2) % tablesize]-> 直到找到空位
优点：
实现简单，只需要数组结构。
空间利用率高。
缺点：
容易产生 聚集问题（Primary Clustering）：连续的空位被占用后，新元素容易集中到一块区域，查找效率下降。
删除操作复杂，需要“删除标记”来避免断链。
三、拉链法（Chaining）
基本思想：
哈希表的每个位置存放的是一个 链表（或红黑树）。发生冲突时，新元素插入到该位置的链表中。
例子：
table[i] -> 链表（存放所有哈希值为 i 的元素）
优点：
插入方便，直接挂到链表上。
删除简单，只需要操作链表。
装填因子（α）高时，性能也较稳定。
缺点：
需要额外的链表/指针空间。
最坏情况下查找效率 O(n)（链表过长）。
优化方案：Java HashMap 在链表长度超过阈值时，会转为红黑树，提高效率到 O(log n)。
四、装填因子：datasize 与 tablesize
datasize：哈希表中存放的元素个数
tablesize：哈希表数组的容量
装填因子 α = datasize / tablesize
装填因子 α 的大小直接影响效率：
1. 线性探测法的限制
必须保证 tablesize > datasize，否则可能没有空位可插入，甚至陷入死循环。
当 α → 1（接近满表）时，冲突严重，查找/插入效率急剧下降。
实际工程中一般保持：
α≤0.7α ≤ 0.7α≤0.7当超过该值时，通常会 扩容（rehash）。
2. 拉链法的特点
允许 datasize > tablesize，因为每个槽位可以存放一个链表（或树）。
但 α 太大时，链表会变长，查找效率下降。
五、对比总结
| 特点 | 线性探测法 | 拉链法 |
|---|---|---|
| 存储结构 | 纯数组 | 数组 + 链表（或树） |
| 插入效率 | 可能多次探测 | 插到链表尾即可 |
| 查找效率 | 受聚集影响大 | 平均 O(1)，最坏 O(n) |
| 删除操作 | 复杂，需要标记 | 简单，直接删节点 |
| 空间利用 | 节省指针开销 | 链表需要额外空间 |
| tablesize 要求 | 必须大于 datasize | 允许 datasize > tablesize |
| 适用场景 | 小数据量、低 α | 大数据量、α 较高 |
六、结论
如果 数据量较小，装填因子 α 较低 → 用 线性探测法 更合适，简单高效。
如果 数据量较大，冲突不可避免 → 用 拉链法 更稳定，插入删除也方便。