C++八股文分享---数据结构其二---哈希表
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了C++八股文分享---数据结构其二---哈希表,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含3734字,纯文字阅读大概需要6分钟。
内容图文
C++八股文分享—数据结构其二—哈希表
前言
什么是哈希表?
搜索二叉树对值的查找是通过从根节点开始,逐个节点与目标值做比较,向下查找,直至找到目标值或是到达根节点未查找到,时间复杂度为O(logn)。而哈希表,则是通过将value与key成对绑定,将key带入哈希函数,即可得到目标值的存放地址,从而得到目标值,在不考虑哈希冲突的情况下,时间复杂度为O(1)。
哈希表其实可以理解为一个特殊的数组。我们通常使用的数组,通过下标0开始,直至数组长度len-1,依次存储数组元素,他们的地址是连续的。而哈希表是使用一段比原数据大一些的数组,通过哈希函数将key映射到数组中的某个地址上,存放是不连续的。
例如我们现在有int nums[20]一个整数数组,访问nums[3]的步骤为:
1、取到nums数组的首地址
2、根据首地址偏移sizeof(int)*3个字节,即可到达nums[3]的存储位置,得到其中元素
例如我们现在有一个哈希表hashmap(string, int) myhash,存储的是某人的身高。
myhash["张三"] = 175,myhash["李四"] = 180, 代表张三身高175cm,李四身高180。
现在获取张三身高myhash["张三"]的步骤为:
1、index = H("张三"),通过哈希函数H,得到哈希表内部对应数组的地址index
2、使用访问index指向的内存区域,得到张三的身高175
哈希函数的构造方法:
1、数字分析法 2、平方取中法 3、折叠法 4、除留余数法 。主要使用方法4.但无论使用哪一种方法,都会出现不同的key经过哈希函数计算出的地址是相同,这种情况就叫做哈希冲突。
哈希函数的注意事项:
1.计算散列地址所需要的时间(即hash函数本身不要太复杂)
2.关键字的长度,key过长就要考虑使用折叠法和除留余数法
3.哈希表的长度
4.关键字分布是否均匀,是否有规律可循
5.设计的hash函数在满足以上条件的情况下尽量减少冲突
关于构造方法的详解可参考:数据结构 Hash表(哈希表)
链接转自:CSDN-洌冰
哈希冲突的解决方法:
不管hash函数设计的如何巧妙,总会有特殊的key导致hash冲突,特别是对动态查找表来说。
hash函数解决冲突的方法有以下几个常用的方法
1.开放定制法:对于冲突的key,不断使用Hi?=(H(key)+di?)MODmm进行递归计算,直至不冲突。
2.链地址法:对于冲突的key,经过哈希函数计算后得到了相同的索引,那么直接在该索引构建链表,将冲突的数据全部链在该链表中。
3.公共溢出区法:建立一个特殊存储空间,专门存放冲突的数据。此种方法适用于数据和冲突较少的情况。
4.再散列法:准备若干个hash函数,如果使用第一个hash函数发生了冲突,就使用第二个hash函数,第二个也冲突,使用第三个……
重点了解一下1、开放定制法和2、链地址法
哈希表元素的插入和rehash
插入:
首先我们要知道一个概念,负载因子:负载因子 loadFactor=n/m,实际数据的长度除表长。
1、当loadFactor<=1时,hash表查找的期望复杂度为O(1).。因此,每次往哈希表中添加元素时,我们必须保证是在loadFactor<1的情况下,
才能够添加。
2、负载因子越大,平均查找长度越大,那么装载因子α越小越好?也不是,就像100的表长只存一个数据,查找时间很快,但空间浪费极大。通常
情况下,认为α=0.75是时间空间综合利用效率最高的情况。
rehash:
rehash,就是指当哈希表插入元素后其负载因子大于0.75时,需要对哈希表的空间和哈希函数进行调整的过程。
以C++中的hashmap为例,当负载因子大于等于0.75时,就需要进行rehash。rehash过程中,首先会开辟一个原来桶数组的两倍空间,称为新桶数组,然后把原来的桶数组中元素全部重新哈希到新的桶数组中。这个过程需要注意,因为新数组的大小变了,所以需要构造新的哈希函数,然后再将以前的key和value重新哈希到新数组中。
哈希表元素的删除:
当删除哈希表的一个元素时,如果处理哈希冲突使用的是链地址法可以直接删除。如果是开放定制法式肯定不行的,因为之前可能存在哈希冲突的情况,如果删除的是冲突1的元素,那么1后面冲突的元素就再也查找不到了,所以不能直接删除该元素。
扩展问题:
问:哈希表的桶个数,为什么是质数?
首先一定要明确一个概念,哈希表的桶个数,就是指使用除留余数法构造的哈希函数H(key)=key%p中的p值。 不是哈希表数据的长度,也不是哈希表的表长,这个概念很多文章写的模模糊糊,一定要搞清楚。
关于除留余数法请参考:数据结构 Hash表(哈希表)
链接转自:CSDN-洌冰
答:使用除留余数法构造哈希函数的哈希表在处理键值key时,就是使用键值除一个数字,得到的余数就是存储地址。如果p取合数,将会使得到的地址冲突概率更高,影响哈希表的效率;使用质数则可以减少冲突概率,使哈希表分部均匀,查找效率更高。
持续更新中…
内容总结
以上是互联网集市为您收集整理的C++八股文分享---数据结构其二---哈希表全部内容,希望文章能够帮你解决C++八股文分享---数据结构其二---哈希表所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。