第10篇:C++哈希表-开放寻址--二次探测

我前一篇已经深入介绍了开放寻址技术的其中一种缓解散列冲突的策略，那就是线性探测(Linear Probing)的工作原理，我们本篇会继续介绍二次探测函数，事实上只要涉及到开放寻址，你不论使用什么探测函数，算法的逻辑主体是不会变，只是索引表达式中使用到P(x)不同而已。

二次探测函数 VS 线性探测

为什么需要二次探测策略呢？那么我们需要了解线性探测的缺点。现在我们通过一个具体的例子来说明一切。我们有一个长度为10的哈希表，在线性探测操作后，该表插入了8个键值对，如下图

• 哈系表尺寸N=10

• 线性探测函数P(x)=x

  
  ss8.png

这种线性探测带来的问题是已插入的元素开始出现堆积(clustering),即多个元素将开始在哈希表的某个区域多个元素项逐个挨着，这会带来什么问题呢？假设我想插入一个散列值为0的键值对(12,"Mandy")，那么线性探测函数P(x)就必须探测堆积区域中的索引0,1,2,3,4,5，直到探测到索引为6的存储桶为空才能插入散列值为0的键值对(12,"Mandy"),显然对于这种情况，线性探测的时间复杂度为O(n)