开放寻址法

Open addressing

开放寻址法

前面学习了一种最简单的冲突解决方法：链接法，现介绍另一种冲突解决方法：开放寻址法

开放寻址法关键在于计算探查序列（probe sequence）

• 对于每一个要插入的关键字k，显然需要连续地检查散列表以找到一个空槽，这个过程称为探查（probe）
• 一个探查序列其实就是m个插槽号的一次排列（permutation）
• 每个关键字的探查序列不同（哈希函数h接收两个参数：关键字 k 和探查号 trial count ）
• 显然探查序列包括了所有插槽，因此只要表中还有空槽就一定能被找到

tips：对于同一个关键字k而言，其插入/搜索/删除的探查序列均一致

Insert

• 要插入关键字k，沿着k的探查序列寻找
• 当找到一个空槽，插入k
• 如果遍历结束 i==m，说明表满，插入失败

Search

• 对于搜索k而言，同样沿着探查序列搜索
• 如果k在表中，就一定能顺着探查序列找到它
• 否则，如果找到空槽或者遍历结束 i==m，这均说明k根本就没有被插入到表中（不考虑插入后又删除的情况），搜索失败

Delete

• 同理沿着探查序列查找k

• 如果没有找到，返回错误

• 当找到k所在槽 i 时，注意这时不能直接将槽 i 置为NIL，因为这会导致上面的搜索算法出错；

  正确的做法是：为槽 i 设定一个特定的值DELETED替代NIL来标记这个槽的内容被删除了，这样只需要对insert操作稍加修改，让其知道DELETED意味着槽为空，而对于search操作则无需再做什么改动

Uniform Hashing Assumption

均匀哈希假设：对于每一个关键字 k，在其对应的 m！个探查序列中，每个探查序列的生成概率相同

（Double Hashing时可以这么假设）

Analysis：

假设已经插入了n个元素至m个插槽中，那么下一次插入预计的probe次数将<=1/（1-α）

Proof：

当插入一个新的元素时，记 p = (m-n)/m

• 一次成功的概率为 p

• 第一次失败的概率为 n/m

• 第二次失败的概率为 （n-1）/（m-1）

• 第三次失败的概率为 （n-2）/（m-2）

  ...

• 以此类推，总共需要的探测次数为：
  $$
  Probes = 1+n/m(1+(n-1)/(m-1)(1+(n-2)/(m-2)(..(1+1/n-m+1)..))
  ≤1+α^2+α3+....
  =sum_{i=0}^∞αi
  =1/(1-a)

  $$

  根据上述推导过程，可以得出在均匀哈希假设下，搜索/插入/删除的时间复杂度均为 O(1/(1-α))

  

参考：https://www.cnblogs.com/soyscut/p/3390032.html