我前一篇已经深入介绍了开放寻址技术的其中一种缓解散列冲突的策略，那就是线性探测(Linear Probing)的工作原理，我们本篇会继续介绍二次探测函数，事实上只要涉及到开放寻址，你不论使用什么探测函数，算法的逻辑主体是不会变，只是索引表达式中使用到P(x)不同而已。
为什么需要二次探测策略呢？那么我们需要了解线性探测的缺点。现在我们通过一个具体的例子来说明一切。我们有一个长度为10的哈希表，在线性探测操作后，该表插入了8个键值对，如下图
线性探测函数P(x)=x
ss8.png
这种线性探测带来的问题是已插入的元素开始出现堆积(clustering),即多个元素将开始在哈希表的某个区域多个元素项逐个挨着，这会带来什么问题呢？假设我想插入一个散列值为0的键值对(12,"Mandy")，那么线性探测函数P(x)就必须探测堆积区域中的索引0,1,2,3,4,5，直到探测到索引为6的存储桶为空才能插入散列值为0的键值对(12,"Mandy"),显然对于这种情况，线性探测的时间复杂度为O(n)
我前一篇已经深入介绍了开放寻址技术的其中一种缓解散列冲突的策略，那就是线性探测(Linear Probing)的工...
本篇我们将深入讨论哈希表的冲突缓解技术之一 开放寻址中的其中一种策略-线性探测(Linear Probing)在开...
哈希表ThreadLocal用的是开放寻址方法hashmap用链表法
承接上篇，在阅读本篇时你需要搞清如下几个问题 什么是哈希表(Hash Table)? 什么是键值对(Key-Val...
哈希表： 特点： 数组(顺序表)：寻址容易 链表：插入与删除容易 哈希表：寻址容易，插入删除也容易的数据结构，也就...
哈希表 特点 数组(顺序表)：寻址容易 链表：插入与删除容易 哈希表：寻址容易，插入删除也容易的数据结构 Hash...
哈希表 是由数组跟链表组合而成的产物特点： 数组（顺序表）寻址容易 链表：插入删除容易 哈希表：寻址容易，插入删除...
如果你阅读前面两篇的开放寻址，我们已经详细底介绍了开放寻址的其中一种缓解散列冲突的策略--线性探测(Leanar)...
HashMap 必备知识——哈希表 哈希表 哈希函数 哈希碰撞 解决办法 1. 拉链法 2. 线性探测法 Hash...
哈希算法处理冲突的机制： 1．开放寻址法2． 再散列法3． 链地址法(拉链法)4． 建立一个公共溢出区参考：哈希表...
本文标题：第10篇:C++哈希表-开放寻址--二次探测
本文链接：https://www.haomeiwen.com/subject/nlxnuhtx.html
网友评论