哈希表的冲突解决策略：开放定址法

一、知识点描述
开放定址法是哈希表中解决冲突的一种重要策略。当发生哈希冲突时（即不同关键字映射到同一位置），该方法会在哈希表中系统地寻找下一个可用的空槽位来存放冲突元素，而不是像链地址法那样使用链表存储。核心思想是：当目标位置被占用时，按照某种预定的探测序列继续查找，直到找到空位或满足停止条件。

二、核心概念解析

1. 哈希冲突

   • 定义：两个或多个不同的关键字通过哈希函数计算后得到相同的数组索引
   • 示例：关键字"apple"和"banana"都映射到索引5

2. 探测序列

   • 定义：当发生冲突时，决定下一个检查位置的规则序列
   • 公式：h(k, i) = (h'(k) + f(i)) mod m
     • h'(k)：初始哈希函数
     • f(i)：探测函数，决定第i次探测的偏移量
     • m：哈希表大小

三、常见探测方法详解

1. 线性探测

• 原理：按固定步长（通常为1）顺序查找下一个空位

• 探测函数：f(i) = i

• 操作过程：

  1. 计算初始位置h0 = h'(k) mod m
  2. 如果位置h0被占用，检查h0+1 mod m
  3. 如果仍被占用，继续检查h0+2 mod m，依此类推

• 示例：

  • 插入关键字k，h'(k)=5，表大小m=10
  • 探测序列：5→6→7→8...（遇到空位停止）

• 缺点：容易产生"一次聚集"现象，即元素形成连续块，增加查找时间

2. 平方探测

• 原理：使用平方增量避免线性探测的聚集问题

• 探测函数：f(i) = i² 或 f(i) = (-1)^i * (i/2)²

• 操作过程：

  1. 计算h0 = h'(k) mod m
  2. 依次检查：h0+1², h0-1², h0+2², h0-2²...（取模运算）

• 示例：

  • h'(k)=5，m=10
  • 探测序列：5→6→4→9→1→...

• 优点：减少聚集现象

• 注意：需保证表大小为质数且装载因子≤0.5，以确保能找到空位

3. 双重哈希

• 原理：使用第二个哈希函数作为步长

• 探测函数：f(i) = i * h₂(k)

• 操作过程：

  1. 计算h1 = h₁(k) mod m
  2. 计算步长s = h₂(k) mod m（通常s≠0）
  3. 探测序列：h1, h1+s, h1+2s...（取模）

• 示例：

  • h₁(k)=5, h₂(k)=3, m=10
  • 探测序列：5→8→1→4→7...

• 优点：提供最好的分布性，最接近理想均匀哈希

四、完整操作流程

插入操作：

1. 计算初始哈希值pos = h'(key)
2. 设置探测次数i=0
3. while 表位置pos被占用：
   • if 当前位置的key与插入key相同：更新值并返回
   • else: i++，计算新位置pos = (h'(key) + f(i)) mod m
4. 在空位pos处插入键值对

查找操作：

1. 计算初始位置pos = h'(key)
2. i=0
3. while 位置pos不为空：
   • if 当前位置key等于目标key：返回对应值
   • else: i++，计算新位置继续查找
4. 返回"未找到"

五、重要注意事项

1. 装载因子：开放定址法的性能与装载因子α密切相关

   • 当α接近1时，操作时间急剧增加
   • 通常需要维持α < 0.7-0.8

2. 删除操作的特殊处理

   • 不能简单将位置置空，否则会中断后续查找
   • 应采用"墓碑标记"法：标记删除但保持位置特殊状态

3. 聚类问题

   • 线性探测易产生主聚类（连续占用区域）
   • 平方探测和双重哈希能有效缓解此问题

这种冲突解决方法在内存受限或需要连续存储的场景中特别有用，但需要合理选择探测策略和控制装载因子以保证性能。