C/C++教程

C++八股文分享---数据结构其二---哈希表

本文主要是介绍C++八股文分享---数据结构其二---哈希表,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

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++八股文分享---数据结构其二---哈希表的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!