线性探查法（Linear Probing）
定义
线性探查法（Linear Probing）是一种开放寻址（Open Addressing）的哈希冲突解决方法。
核心思想：当发生哈希冲突时，从冲突位置开始线性向后探查（index+1, +2, +3, ...），直到找到空位或目标 key。
基本原理
冲突处理流程
插入键值对 (key, value):
1. 计算初始索引：index = hash(key)
2. 若 table[index] 为空 → 直接插入
3. 若 table[index] 不为空：
- 若 key 相同 → 更新值
- 若 key 不同 → index++，继续探查
4. 重复步骤 3，直到找到空位或相同 key
探查特性
| 特性 | 说明 |
|---|---|
| 探查序列 | hash(key), hash(key)+1, hash(key)+2, ... |
| 探查窗口 | 从初始哈希值到空位之间的连续区域 |
| 聚集问题 | 连续占用区域会形成"聚集"，导致后续冲突概率增加 |
| 缓存友好 | 数据存储在连续数组中，比链表的指针跳转更利于 CPU 缓存 |
核心操作伪代码
Put（插入/更新）
public void put(int key, int value) {
int index = hash(key);
// 向后探查，直到找到 key 或者找到空位
while (index < table.length
&& table[index] != null
&& table[index].key != key) {
index++;
}
// 找到空位或相同 key，插入/更新
table[index] = new KVNode(key, value);
}
Get（查找）
public int get(int key) {
int index = hash(key);
// 向后探查，直到找到 key 或者找到空位
while (index < table.length
&& table[index] != null
&& table[index].key != key) {
index++;
}
if (table[index] == null) {
return -1; // 未找到
}
return table[index].value;
}
Remove（删除）—— 核心难点
问题：不能直接置为 null！
错误示例：
table[index] = null; // ❌ 破坏探查链
后果：
- 后续元素依赖于这条探查链才能被找到
- 如果中间断开，后面的元素会"丢失"（查找时遇到空位就停止）
解决方案（常见方法）：
-
标记删除法：使用特殊标记（如
deleted）表示"曾有过但已删除"- 查找时：
deleted位置视为"非空"，继续探查 - 插入时：
deleted位置可以复用
- 查找时：
-
重新插入法：删除后，将后续元素重新插入哈希表
- 从删除位置开始，向后找到下一个空位
- 将中间的所有元素重新执行
put操作
线性探查法的两个难点
根据文章分析，实现线性探查法有两个主要难点：
难点 1：删除操作的特殊处理
- 问题：直接删除会破坏探查链，导致后续元素无法被查找
- 解决方案：使用
deleted标记或重新插入后续元素 - 权衡：标记法简单但会产生"幽灵"位置；重插法正确但开销大
难点 2：探查序列的边界处理
- 问题 1：如何处理数组末尾？需要循环回开头（环形缓冲区）
- 问题 2：如何检测表已满？避免无限循环
- 问题 3：负载因子控制与扩容时机
环形探查伪代码：
public void put(int key, int value) {
int startIndex = hash(key);
int index = startIndex;
do {
if (table[index] == null || table[index].key == key) {
table[index] = new KVNode(key, value);
return;
}
index = (index + 1) % table.length; // 环形探查
} while (index != startIndex); // 表满检测
// 表已满，需要扩容
resizeAndRehash();
}
与拉链法的对比
| 维度 | 线性探查法（开放寻址） | 拉链法（链地址法） |
|---|---|---|
| 存储方式 | 纯数组 | 数组 + 链表 |
| 冲突处理 | 向后找空位 | 同一桶内链表存储 |
| 缓存友好性 | ✅ 较好（连续内存） | ❌ 较差（指针跳转） |
| 删除操作 | ❌ 复杂（需保持探查链） | ✅ 简单（链表删除） |
| 负载因子 | 必须 <1（表不满） | 可以 >1（链表长度不限） |
| 聚集问题 | ❌ 有（Primary Clustering） | ✅ 无 |
| 空间开销 | ✅ 无需额外指针 | ❌ 链表指针开销 |
| 实现复杂度 | 中等（边界处理） | 简单 |
探查聚集（Primary Clustering）
现象：线性探查容易产生"聚集"——连续被占用的区域越来越长。
原因：
- 新元素哈希到聚集区时，会进一步延长聚集区
- 聚集区越长，后续元素冲突到该区域的概率越大
- 形成正反馈，导致性能下降
影响：平均查找长度增加，最坏情况退化为 O(n)。
改进方案（本文未详细涉及）：
- 二次探查：步长按平方增长
hash(key) + 1², +2², +3², ... - 双重哈希：使用第二个哈希函数计算步长，避免固定步长 1
时间复杂度
| 操作 | 平均情况 | 最坏情况 | 说明 |
|---|---|---|---|
| 查找 | O(1) | O(n) | 最坏情况为整个表都是聚集区 |
| 插入 | O(1) | O(n) | 可能触发扩容 |
| 删除 | O(1) | O(n) | 取决于探查链长度 |
注意：由于聚集问题，线性探查法的常数因子通常比拉链法大。
应用场景
- 缓存友好的场景：数据量不大，内存访问模式重要
- 负载因子较低的场景：冲突少，聚集问题不明显
- 实现简单的场景：不想处理链表指针的额外复杂度
相关概念
待补充
- 完整文章内容（"两个难点"的具体实现细节）
- 代码示例（Java/C++ 完整实现）
- 可视化示例（探查过程动画）
- 性能测试数据（与拉链法对比）