第8篇:C++哈希表-开放寻址原理

承接上篇，在阅读本篇时你需要搞清如下几个问题

• 什么是哈希表(Hash Table)?
• 什么是键值对(Key-Value Pair)?
• 什么是散列函数(或叫哈希函数/Hash Function)?
• 什么是散列冲突(Hash Collision)?

如果没有任何概念，请先看我上一篇《第7篇:C++ 哈希表--散列函数》，OK，现在马上切入正题吧

开放寻址是其中一种缓解散列冲突的编程技术，当使用开放寻址作为冲突解决技术时，键值对存储在表（数组）中，而不是像单独链表那样的数据结构中。这意味着我们需要时刻留意哈希表的尺寸以及当前表中已有的元素数量。因为一旦哈希表中有太多元素，也将很难找到可用的位置来存放我们新插入的元素，因此这里我们需要引入一个重要的术语，负载系数(Load Factor)

负载系数

其实就是表中已有元素个数和表尺寸的比例，我们要密切关注这个系数的是因为哈希表的O(1)恒定时间行为假设负载因子k保持一定的固定值，这意味着一旦k>阈值，我们就需要增加表的大小（理想情况下是指数增长，例如，两倍）
ss8.png
在上图中，你会看到有两种缓解冲突的方法，即单独链表和线性探测(Linear Probing),在开放寻址(线性探测)技术看来，一旦达到某个阀值，它的时间复杂度就会呈现指数级恶化的趋势

当我们想要将键值对插入哈希表时，我们对键进行哈希处理并获得该键值对所属位置的原始位置。如果我们的键被散列到的位置被占用(此时出现了冲突)，对于开放寻址来说，同一个位置中不允许有两个键的，这不是数组的工作方式，我们要做的是使用一个探测序列函数(Probing Seque Function) 这里简称p(x)，因为我们已从散列函数获取了冲突点的所在位置，现在我们使用p(x)进行探测直到在沿途发现一个空闲的位置为止

探测函数

您可以提出无限数量的探测序列，这里仅提及一些常见的探测函数：

• 线性探测(Linear Probing)：p(x)= kx + b其中a，b是常数

• 二次探测(Quaratic Probing):p(x)= ax ^ 2 + bx + c，其中a，b，c是常数

• 双重散列(Double Hashing):p(k，x)= x * h(k），其中h(k)是辅助s散列函数

• 伪随机数发生器(Pseudo Random Number Generator):
  p(k，x)= x*RNG(h(k),x）其中RNG是以H（k）作为种子的随机数生成器函数

本篇仅介绍线性探测函数进行线性探测，因此给定输入参数x,当我们进行探测时，我们通常会将变量x初始化为0或1作为一个起点,如果我们找不到空闲的位置，会依次将x增加1,对以上所有这些探测函数都是一样的

开放寻址的通用算法

接下来，这是一个通用的开放寻址插入算法，假设我们有一个表的尺寸为n,开放寻址算法首先会初始化变量x=1,因为x是一个变量，我们要用它来探测，每当我们未能到达闲置的位置时，都需要递增x，然后我们通过散列函数获得keyHash,而实际上我们首先要查看表的索引，当表索引被占用意味着它不为空，那么新索引就是我们散列的最初位置(keyHash所指向的起始索引)加上探测函数的总和再于表尺寸N取模运算得到整数，由于我们总是回到表里，在循环中要递增x。下一次当我们在不同的位置探测时，在while循环中，最终我们会找到一个空闲的位置

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

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

insert(k,v,index) 

死循环地狱（Chaos with Cycle）

由于我们知道负载系数被控制在一定的范围内，所以这里有个问题，就是开放寻址中的探测函数存在缺陷--死循环地狱,以表尺寸N为模的大多数随机选择的探测序列将产生比表大小N更短的循环。当您尝试插入一个键-值对并且循环中的所有存储桶都被占用时，这将成为灾难性问题，因为您将陷入无限循环,这在一些老外谈及哈希表的相关文章中有一个非常有趣的昵称叫死循环地狱(Chaos with Cycle)

为了生动说明什么叫死循环地狱,我们这里看一个例子，这里有一个尺寸为12的哈希表，并且使用开放寻址插入了一些键值对，，该哈希表已经部分填充。 占用的单元格填充有键值对（Ki，Vi）和带有空令牌Φ的空单元格，如下图所示

假设我们使用探测序列函数p(x)=4x，并且在表中插入一个新的键值对，并且该键值对的散列值为8,即h(x)=8这意味着我们会在索引8的位置插入该键值对，但是该位置已被占用，因为这里已经有简直对(k5,v5)，所以我们该怎么办呢？接下来，我们需要进行探测，所以我们计算：
index=h(k)+p(1)=8+4 mod 12=0

此时，如下图，此时探测函数会跳转到索引为0的位置，糟糕的是索引1的位置也被占用了，因为(k1,v1)已经存在.

• 当x=2时，即index=h(k)+p(2)=(8+8) mod 12=4，探测函数会跳跃到索引4的位置，同样这里也是被占用的，如此类推
• 当x=3时,即index=h(k)+p(3)=(8+12) mod 12=8,p(x)跳跃到索引8的位置,该位置被占用
• 当x=4时,即index=h(k)+p(4)=(8+16) mod 12=0,p(x)跳跃到索引0的位置,该位置被占用
• 当x=5时,即index=h(k)+p(5)=(8+20) mod 12=4,p(x)跳跃到索引4的位置,该位置被占用
  .....

这样尽管我们具有探测函数，但这种特定的情况下它一直在一个死循环里面一直做一些毫无意义的事情。

由这个例子我们可知探测函数存在缺陷，他们产生的周期短于表的尺寸，因此，我们要如何处理产生小于表大小的周期的探测功能？一般来说，一致的看法是我们不处理这个问题，相反，我们通过将探测函数的范围限制在那些产生长度为N的循环的函数上来避免这个问题，我们选择的那些产生的周期正好为N的探测函数，并且这些探测函数确实存在。

线性探测、二次探测和双重散列等技术都受到死循环地狱问题的影响，这就是为什么与这些方法一起使用的探测函数非常特殊的原因。这是一个很大的话题，将是接下来几篇文章会重点讲述这些，我们目前需要做的是重新定义非常具体的探测函数，这些函数会产生一个循环长度为表尺寸N，并且避免无法插入元素或陷入无限循环

注意，开放寻址对使用的哈希函数和探测函数非常敏感。如果使用单独的链接作为冲突解决方法，则不必担心此问题。

小结

我们本篇用一个反例生动地介绍了开放寻址插入算法的底层是由探测函数和散列函数相互作用的结果，同时我们也介绍了一些探测函数的固有缺陷，就是死循环地狱,下一篇我们会详细讨论线性探测函数的原理，敬请期待。