第11篇:C++哈希表-开放寻址--双重散列

如果你阅读前面两篇的开放寻址，我们已经详细底介绍了开放寻址的其中一种缓解散列冲突的策略--线性探测(Leanar)和二次探测，那么这篇我们会再讨论第三种冲突解决方案--双重散列(Double hashing)

那么双重散列的处理方法是如何的呢？
双重散列和前面提到的开放寻址的两外两种解决方案的算法逻辑是一样的，差别在于，双重散列用到的探测函数即P(x,k)的具体实现和其他的解决方案不一样，它的特殊之处是，我们可以根据另外一个散列函数得到散列值的x倍进行探测。即我们将常量k和变量x作为键的变量传递到探测如下探测函数

需要注意的是上面定义的双重散列方案定义的探测函数的简约表达式，因为上面的表达式没有说清楚探测过程中回避死循环的条件，下文谈到死循环问题会给出完整的P(x,k)探测函数

• hash1(k)是一个主散列函数(Primary Hash Function):就是跟之前其他冲突解决方案一样，用于计算被插入键值对的初始化散列值，即未与其他已插入元素发生冲突情况下，它本应的在哈希表的索引位置
• hash2(x)是一个辅助散列函数(Secodary Hash Function):就是被插入键值对与其他已插入元素发生冲突后，该散列函数用于计算探测的偏移量，即重算用于被插入键值对的索引值

这里的需要注意的是hash2(k)和hash1(k)具备相同的类型的键。例如传入散列函数hash1(k)的k是string类型，那么hash2(k)的k也必须是string类型

算法中的索引表达式是

双重散列的优缺点

双重散列的目地是最大限度减少线性探测的次数，这个线性探测和二次探测无法比拟的，因为双重散列继承了前两种探方案的优点。缺点是代码实现的比线性探测和二次探测复杂得多。

死循环问题

双重散列是为了在运行时减少线性探测的次数，但如果选择的辅助散列函数不恰当的，并且哈系表的尺寸N,即会产生死循环的问题，例如在P(x)=3x,我们的辅助散列函数在运行时计算出的常数的值为3，假设hash1(k)=4,表的尺寸是9，那么下面的例子我们在探测过程中就会陷入死循环了。

ss8.png

因为在循环中，index重算只徘徊在{4，7，1},且在第2次循环中{4，7，1}这些位置已经被占用了，重算的index无法不可能达到{0,2,3,5,6,8}任何一个存储桶,即无法在{4,7,1}之外的位置插入键值对，正如上面的列出的一样，这是一个典型的死循环问题。