Appearance
哈希表：开放定址法
为什么需要哈希表：开放定址法
哈希表通过哈希函数将关键字映射到存储位置，理想情况下可以 O(1) 时间完成查找。但不同关键字可能映射到同一位置，产生冲突（碰撞）。
开放定址法是解决冲突的一种方式：当发生冲突时，按照某种探测序列在哈希表中寻找下一个空闲位置，将元素直接存入表中。与拉链法不同，开放定址法不需要额外的链表空间，所有元素都存储在哈希表本身中。
408 考研中，开放定址法是散列表章节的核心考点，尤其是线性探测法的 ASL 计算几乎年年出现。
核心思想
开放定址法的通用公式：
H_i = (H(key) + d_i) % m, i = 1, 2, 3, ...其中 H(key) 是哈希函数，m 是表长，d_i 是第 i 次探测的增量，不同的 d_i 取法对应不同的探测方法：
- 线性探测法：d_i = 1, 2, 3, ...
- 二次探测法：d_i = 1², -1², 2², -2², ...
- 双散列法：d_i = i × H₂(key)
核心数据结构定义：
c
#define EMPTY -1 // 空位标记
#define DELETED -2 // 已删除标记（墓碑）
typedef struct {
int *data; // 存储数组
int size; // 表长 m
int count; // 当前元素个数
} HashTable;交互可视化
通过下方的交互动画，你可以逐步观察哈希表：开放定址法的执行过程：
操作详解
线性探测法
当发生冲突时，依次探测下一个位置，增量序列为 d = 1, 2, 3, ...
c
// 线性探测法——插入
int linearInsert(HashTable *ht, int key) {
int pos = key % ht->size; // 初始哈希地址
int i = 0;
while (i < ht->size) {
int cur = (pos + i) % ht->size;
if (ht->data[cur] == EMPTY || ht->data[cur] == DELETED) {
ht->data[cur] = key;
ht->count++;
return cur; // 插入成功，返回位置
}
i++;
}
return -1; // 表满，插入失败
}
// 线性探测法——查找
int linearSearch(HashTable *ht, int key) {
int pos = key % ht->size;
int i = 0;
while (i < ht->size) {
int cur = (pos + i) % ht->size;
if (ht->data[cur] == EMPTY)
return -1; // 遇到空位，查找失败
if (ht->data[cur] == key)
return cur; // 查找成功
i++; // 遇到 DELETED 或其他值，继续探测
}
return -1;
}举例：哈希表长 m = 11，H(key) = key % 11，依次插入 19, 1, 23, 14, 55：
| 关键字 | H(key) | 探测序列 | 最终位置 |
|---|---|---|---|
| 19 | 8 | 8 | 8 |
| 1 | 1 | 1 | 1 |
| 23 | 1 | 1→2 | 2 |
| 14 | 3 | 3 | 3 |
| 55 | 0 | 0 | 0 |
堆积问题（聚集/Clustering）：线性探测法的最大缺陷。同义词（哈希值相同的关键字）和非同义词都可能争夺同一段连续区域，导致大量元素聚集在一起，探测次数急剧增加，查找效率下降。
二次探测法
增量序列为 d = 1², -1², 2², -2², 3², -3², ...，即交替探测哈希地址两侧的位置，可以有效缓解堆积问题。
c
// 二次探测法——查找
int quadraticSearch(HashTable *ht, int key) {
int pos = key % ht->size;
int i = 0;
while (i <= ht->size / 2) {
// 正方向探测 +i²
int cur = (pos + i * i) % ht->size;
if (ht->data[cur] == EMPTY) return -1;
if (ht->data[cur] == key) return cur;
// 负方向探测 -i²
cur = ((pos - i * i) % ht->size + ht->size) % ht->size;
if (ht->data[cur] == EMPTY) return -1;
if (ht->data[cur] == key) return cur;
i++;
}
return -1;
}注意：二次探测法要求表长 m 为4k + 3 形式的素数（如 7, 11, 19, 23, 43...），才能保证探测到所有位置。
双散列法：使用第二个哈希函数计算增量，d_i = i × H₂(key)。H₂(key) 的选取要求与 m 互素，常见做法是取 H₂(key) = p - (key % p)，其中 p 是小于 m 的最大素数。双散列法能更均匀地分散探测位置，聚集问题最轻。
冲突处理对比
| 对比项 | 线性探测 | 二次探测 | 双散列 | 拉链法 |
|---|---|---|---|---|
| 堆积问题 | 严重（一次聚集） | 较轻（二次聚集） | 最轻 | 无 |
| 删除操作 | 需要墓碑标记 | 需要墓碑标记 | 需要墓碑标记 | 直接删除 |
| 空间利用 | 无额外指针 | 无额外指针 | 无额外指针 | 需要指针域 |
| 表长要求 | 无特殊要求 | m 为 4k+3 素数 | 需互素条件 | 无特殊要求 |
| 适用场景 | 表规模小、装填因子低 | 通用 | 通用 | 频繁插入删除 |
删除问题：开放定址法不能直接删除元素。如果直接将位置置空，会导致后续探测到此位置时误认为查找失败，中断探测链。解决方案是使用墓碑标记（Tombstone / 懒删除）：将被删除的位置标记为 DELETED 状态，查找时跳过，插入时可复用。
ASL 分析
**ASL（平均查找长度）**是衡量哈希表性能的关键指标，分为查找成功和查找失败两种情况。
查找成功 ASL：对表中每个元素，统计找到它所需的比较次数，再求平均值。
查找失败 ASL：对每个可能的哈希地址（0 ~ m-1），统计从该地址出发探测到空位所需的比较次数，再对所有哈希地址求平均值。
举例：m = 11，H(key) = key % 11，依次插入 19, 1, 23, 14, 55，最终哈希表状态：
下标: 0 1 2 3 4 5 6 7 8 9 10
元素: 55 1 23 14 - - - - 19 - -查找成功 ASL = (1 + 1 + 2 + 1 + 1) / 5 = 6/5 = 1.2
查找失败 ASL：从每个哈希地址出发探测到空位的次数：
| 地址 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 比较次数 | 5 | 4 | 3 | 2 | 1 | 1 | 1 | 1 | 2 | 1 | 1 |
查找失败 ASL = (5 + 4 + 3 + 2 + 1 + 1 + 1 + 1 + 2 + 1 + 1) / 11 = 22/11 = 2.0
装填因子 α = 已存元素数 / 表长，α 越大冲突越多，ASL 越大。一般建议 α ≤ 0.75。
复杂度分析
| 操作 | 平均时间复杂度 | 最坏时间复杂度 | 说明 |
|---|---|---|---|
| 查找 | O(1/(1-α)) | O(n) | 取决于装填因子 α |
| 插入 | O(1/(1-α)) | O(n) | 需先查找空位 |
| 删除 | O(1/(1-α)) | O(n) | 懒删除，标记墓碑 |
空间复杂度：O(m)，m 为表长，不需要额外链表空间。
考研高频考点
- ⭐ 给定哈希函数和关键字序列，画出哈希表并计算 ASL（选择/填空/大题必考）
- ⭐ 线性探测法查找成功与查找失败的 ASL 计算（重中之重）
- ⭐ 开放定址法不能直接删除元素的原因及墓碑标记方案（简答题高频）
- ⭐ 堆积问题的含义：同义词和非同义词共同引起的聚集现象（概念辨析）
- ⭐ 开放定址法 vs 拉链法的优缺点对比（简答题/选择题）
- 装填因子 α 对查找效率的影响（概念题）
- 二次探测法对表长的要求（4k + 3 形式的素数）