第9篇:C++哈希表-开放寻址--线性探测

本篇我们将深入讨论哈希表的冲突缓解技术之一 开放寻址中的其中一种策略-线性探测(Linear Probing)
在开始之前，我们先回顾以下伪代码开放寻址的插入算法，如下符号表示如下

• H(x)是散列函数
• keyHash是散列函数H(x)提供的散列值
• N是哈希表的尺寸
• x是一个遍历索引的自变量
• p(k,x)是线性探测函数

前言

从这篇开始往后的内容，笔者会选择性发布付费文章，之所以付费是笔者自己原创或经验的总结。

我们回顾一下开放寻址的工作原理，不论你使用什么探测函数，

1. 我们都需要一个自变量x记录在探测过程中的探测的次数，
2. 探测过程中，我要检测的索引就是键k初次H(k)返回的散列值指向的位置index
3. 在遍历整个表过程中table[index]!=NULL检测当前index位置是否被占用(即发生冲突)
   • 若当前index的位置已被占用，我们将通过如下表达式:index=keyHash+P(k,x) mod N 计算出新的index,并且变量x递增1，然后进入下一次的while循环的table[index]!=NULL检查.
   • 若当前index的位置未被占用,即忽略while循环,使用当前index作为当前键k的键值对的插入位置

x=1
keyHash=H(k)
index=keyHash

while table[index]!=NULL:
      index=(keyHash+p(k,x)) mod N
      x=x+1
end-while

insert(k,v,index) 

在每次检测table[index]!=NULL返回false的情况下,我们的探测函数都会将index推到一个新的位置，直到找到一个闲置的索引为止。所以有人会问什么是线性探测？