开放寻址法

概述

开放寻址法（Open Addressing） 是一种处理 散列表 冲突的方法，其核心思想是：所有元素都直接存储在散列表数组 $T[\mathrm{0..}m-1]$ 内，不使用额外的链表或指针。当插入关键字 $k$ 时，如果槽位 $h(k)$ 已被占用，就按照某个探测序列（probe sequence）依次检查后续槽位，直到找到一个空槽为止。开放寻址法的装载因子 $\alpha$ 必须严格小于 1。

定义

开放寻址法

在开放寻址法中，散列表 $T[\mathrm{0..}m-1]$ 的每个槽位要么存储一个元素，要么为空（NIL）。对于关键字 $k$，探测序列为： $⟨h(k,0),h(k,1),h(k,2),\dots ,h(k,m-1)⟩$ 这是一个对 $\{0,1,\dots ,m-1\}$ 的排列（permutation），保证每个槽位恰好被探测一次。

伪代码

搜索：

HASH-SEARCH(T, k)
    for i = 0 to m - 1
        j = h(k, i)
        if T[j] == NIL
            return NIL                    // 搜索失败
        if T[j].key == k
            return T[j]                   // 搜索成功
    error "hash table overflow"           // 表已满

插入：

HASH-INSERT(T, k)
    for i = 0 to m - 1
        j = h(k, i)
        if T[j] == NIL
            T[j] = k
            return j
    error "hash table overflow"           // 表已满

删除（惰性删除）：

HASH-DELETE(T, k)
    j = HASH-SEARCH(T, k)
    if j != NIL
        T[j] = DELETED                    // 标记为已删除，而非 NIL

删除的特殊处理

开放寻址法中不能简单地将槽位置为 NIL，否则会截断后续元素的探测链，导致搜索失败。必须使用特殊标记 DELETED（惰性删除），使搜索时能跳过已删除的槽位继续探测。

核心性质

三种经典探测方法

1. 线性探测（Linear Probing）

$h(k,i)=(h^{\prime }(k)+i)\mathrm{mod}m$

其中 $h^{\prime }(k)$ 是一个辅助散列函数。

• 优点：实现简单，缓存友好（探测的内存位置相邻）
• 缺点：存在一次聚类（primary clustering）问题——连续被占用的槽位会越来越长，形成”聚集块”，新插入的元素更容易落入聚集块，导致聚集块进一步增长

2. 二次探测（Quadratic Probing）

$h(k,i)=(h^{\prime }(k)+c_{1}i+c_2{i}^2)\mathrm{mod}m$

其中 $c_1,c_2$ 为常数（$c_2\ne 0$）。

• 优点：缓解了一次聚类问题
• 缺点：可能存在二次聚类（secondary clustering）——初始探测位置相同的关键字会遵循相同的探测序列
• 探测序列的完整性：要保证探测序列覆盖所有槽位，表大小 $m$ 必须是素数，且对某些 $c_1,c_2$ 组合有额外要求

3. 双重散列（Double Hashing）

$h(k,i)=(h_1(k)+i\cdot h_2(k))\mathrm{mod}m$

其中 $h_1(k)$ 和 $h_2(k)$ 是两个独立的散列函数。

• 优点：探测序列由关键字完全决定，几乎消除了聚类问题，是开放寻址法中性能最好的方案
• 关键要求：$h_2(k)$ 必须与 $m$ 互素，以保证探测序列覆盖所有槽位
  • 常用做法：取 $m$ 为素数，$h_2(k)=1+(k\mathrm{mod}(m-1))$，确保 $h_2(k)\in \{1,2,\dots ,m-1\}$

三种探测方法对比

特性	线性探测	二次探测	双重散列
探测公式	$h^{\prime }+i$	$h^{\prime }+c_{1}i+c_2{i}^2$	$h_1+i\cdot h_2$
聚类问题	一次聚类	二次聚类	几乎无聚类
缓存性能	最好	中等	较差
实现复杂度	最简单	中等	较复杂
推荐程度	适合小表	中等	通用推荐

时间复杂度分析

在均匀散列假设（Uniform Hashing）下——每个未被查看过的槽位等概率地成为下一个被探测的槽位：

给定装载因子 $\alpha =n/m<1$：

操作	期望探测次数
不成功搜索	$\le \frac{1}{1-\alpha }$
成功搜索	$\le \frac{1}{\alpha }\ln \frac{1}{1-\alpha }$

直观理解：

• $\alpha =0.5$ 时：不成功搜索期望探测 $\le 2$ 次，成功搜索期望探测 $\le 1.39$ 次
• $\alpha =0.9$ 时：不成功搜索期望探测 $\le 10$ 次，成功搜索期望探测 $\le 2.56$ 次
• $\alpha \to 1$ 时：期望探测次数急剧增大，性能严重退化

装载因子的约束

与 链地址法 不同，开放寻址法严格要求 $\alpha <1$：

• 当 $\alpha \ge 1$ 时，表中没有空槽，插入操作必然失败
• 实际应用中，通常保持 $\alpha \le 0.7$（或更低），以保证良好的性能
• 当 $\alpha$ 超过阈值时，需要进行扩容（分配更大的表并重新散列所有元素）

章节扩展

开放寻址法 vs. 链地址法

特性	开放寻址法	链地址法
存储方式	全部在表内	表 + 外部链表
装载因子	必须 $\alpha <1$	$\alpha$ 可 $>1$
缓存性能	好（数据连续）	差（链表节点分散）
删除操作	复杂（需惰性删除）	简单（直接删除节点）
指针开销	无	每个节点需要指针
对 $\alpha$ 的敏感度	高（$\alpha$ 接近 1 时急剧退化）	低（性能线性退化）

均匀散列假设 vs. 简单均匀散列

• 简单均匀散列（用于链地址法分析）：每个关键字独立等概率地映射到每个槽位
• 均匀散列（用于开放寻址法分析）：探测序列等价于从 $\{0,1,\dots ,m-1\}$ 的随机排列中均匀选取
• 均匀散列是比简单均匀散列更强的假设，实际中双重散列最接近这一假设

参见

• 散列表 —— 开放寻址法所服务的散列表结构
• 散列函数 —— 提供探测所需的辅助散列函数
• 链地址法 —— 另一种冲突处理方法，与开放寻址法互补
• 直接寻址表 —— 无冲突的简单字典实现