当前位置:   article > 正文

C++——关联式容器(下)——哈希结构_c++ 容器 一个key有多个value hash

c++ 容器 一个key有多个value hash

哈希结构的关联式容器:

  1. unordered_map
  2. unordered_set
  3. unordered_multiset
  4. unordered_multimap

unordered系列的关联式容器之所以效率比较高,是因为其底层使用了哈希结构。

哈希概念:

顺序结构以及平衡树中,元素关键码与其存储位置之间没有对应的关系,因此在查找一个元素时,必须要经过关键码的多次比较。顺序查找时间复杂度为O(N),平衡树中为树的高度,即O(log2 N),搜索的效率取决 于搜索过程中元素的比较次数。

理想的搜索方法:可以不经过任何比较,一次直接从表中得到要搜索的元素。 如果构造一种存储结构,通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系,那么在查找时通过该函 数可以很快找到该元素。

当向该结构中:

插入元素:

根据待插入元素的关键码,以此函数计算出该元素的存储位置并按此位置进行存放

搜索元素:

对元素的关键码进行同样的计算,把求得的函数值当做元素的存储位置,在结构中按此位置取元素比较,若关键码相等,则搜索成功。

该方式即为哈希(散列)方法,哈希方法中使用的转换函数称为哈希(散列)函数,构造出来的结构称为哈希表 (Hash Table)(或者称散列表) 。

示例:


哈希:(Hash)

Hash散列,通过关于键值(key)的函数,将数据映射到内存存储中一个位置来访问。这个过程叫做Hash,这个映射函数称做散列函数,存放记录的数组称做散列表(Hash Table),又叫哈希表


Hash的查找方法:

现在有一组数据:11,12,13,14,15,16;

我们现在要找16这个数据,按照其他的数组或者是链表就需要依次遍历,遍历到最后确定是数据16,或者没有。时间复杂度O(n);

按照Hash的查询方式,散列函数为H[key] = key % 5;则集合元素对应的hash值分别为:1,2,3,4,0,1。

查找数据16只需要在Hash值为1的集合中寻找即可,这时候会发现有两个1,这就是哈希冲突,后面会讲。

如果访问没有哈希冲突的元素,例如查找数据2,可以直接访问哈希值为2的值。

因此:hash时间复杂度最差才为O(n),最优情况下只需要O(1);

数据很多的时候就不能数组或者链表查看,太慢了。


Hash散列函数的确定:

我们很清晰地看到,Hash表的查找是通过散列函数确定的,所以关键散列函数的确定。它主要有六种方法。

方法一:直接定址法

取Key或者Key的某个线性函数值为散列地址。例如:Hash(k) = k,或者Hash(k) = a*k + b,(a\b均为常数),就线性方程。

方法二:数字分析法

需要知道Key的集合,并且Key的位数比地址位数多,选择Key数字分布均匀的位。设有N个d位数,每一位可能有r种不同的符号。这r种不同的符号在各位上出现的频率不一定相同,可能在某些位上分布均匀些,每种符号出现的机会均等;在某些位上分布不均匀,只有某几种符号经常出现。可根据散列表的大小,选取其中各种符号分布均匀的若干位作为散列地址。

如下例子:Hash(Key) 取4位

列数 : 1   (2)   3   (4)   5   (6)   (7)    8    9

key1:  1    1    3    2    7    5      8     8     9     

key2:  1    2    3    3    7    6      7     8     9   

key3:  1    3    2    4    7    7      6     8     9    

key4:  5    4    3    5    3    8      5     4     5    

其中(2、4、6、7) 这4列数字无重复,分布较均匀,可以看看其他的都是重复的,对应概念中分布均匀含义,取此4列作为Hash(Key)的值。

Hash(Key1):1258

Hash(Key2):2367

Hash(Key3):3476

Hash(Key4):4585

方法三:平方取中法

先计算构成关键码的标识符的内码的平方,然后按照散列表的大小取中间的若干位作为散列地址。(取Key平方值的中间几位作为Hash地址)。因为在设置散列函数时不一定知道所有关键字,选取哪几位不确定。一个数的平方的中间几位和数本身的每一位都有关,这样可以使随机分布的Key,得到的散列地址也是随机分布的 。

例如:Hash(Key) 取4位

Key值Key值的平方Hash(Key)
123123151592731295927
4564562083520799365207

方法四:折叠法

把关键码自左到右分为位数相等的几部分,每一部分的位数应与散列表地址位数相同,只有最后一部分的位数可以短一些。把这些部分的数据叠加起来,就可以得到具有关键码的记录的散列地址。(将关键字分割成位数相同的几部分(最后一部分的位数可以不同),然后取这几部分的叠加和(舍去进位)作为哈希地址。 当Key的位数较多的时候数字分布均匀适合采用这种方案

两种方法:分为移位法和折叠法。

例子:若Key为下列数串,地址位数为7,两种方法的Hash(key)分别如下:

Key:1638343 | 1538625 | 8448743| 23656

表中的结果 = 1638343 + 1538625 + 8448743 + 23656(几段的加法)

 移位折叠法: 折叠折叠法: 
第一段1638343是本来数字1638343是本来数字
第二段1538625是本来数字5268351把数字逆置了
第三段8448743是本来数字3478448把数字逆置了
第四段23656是本来数字65632把数字逆置了
结果:11649367 10450774 
Hash(Key)1649367取七位450774取七位

方法五:随机数法

具体实现:建立一个伪随机数发生器,Hash(Key) = random(Key)。以此伪随机数作为哈希地址。

方法六:除留余数法

取关键字被某个除数 p 求余,得到的作为散列地址。

即 H(Key) = Key % p;

6种构造哈希函数的方法,选择时要尽量减少产生冲突,根据Key值的位数,分布情况,范围大小做出更优的选择


哈希冲突:

不管选用何种散列函数,不可避免的都会产生不同Key值对应同一个Hash地址的情况,这种情况叫做哈希冲突。

哈希冲突的处理方法:

方法一:开放定址法

当冲突发生时,探测其他位置是否有空地址 (按一定的增量逐个的寻找空的地址),将数据存入。

根据探测时使用的增量的取法,分为:线性探测、平方探测、伪随机探测等。

  • 线性探测(Linear Probing)——一次探测

d i = a * i + b; a\b为常数。

相当于逐个探测地址列表,直到找到一个空置的,将数据放入。

  • 平方探测(Quadratic Probing)——二次探测

d i = a * i^2 (i <= m/2) m是Key集合的总数。a是常数。

探测间隔 i^2 个单元的位置是否为空,如果为空,将地址存放进去。

  • 伪随机探测

d i = random(Key);

探测间隔为一个伪随机数。

上图片来源(图中所示博客链接): https://blog.csdn.net/xxpresent/article/details/55806298

方法二:链表法

将散列到同一个位置的所有元素依次存储在单链表中,或者也有存储在栈中。具体实现根据实际情况决定这些元素的数据存储结构。

图示:

在拉链法中,装填因子 α 可以大于 1,但一般均取 α ≤ 1。

装载因子:

散列表的载荷因子定义为:

α = 填入表中的元素个数 / 散列表的长度.

α 是散列表装满程度的标志因子。由于表长是定值,α 与“填入表中的元素个数”成正比,所以,α 越大,表明填入表中的元素越多,产生冲突的可能性就越大;反之,α 越小,标明填入表中的元素越少,产生冲突的可能性就越小。实际上,散列表的平均查找长度是载荷因子α 的函数,只是不同处理冲突的方法有不同的函数。

对于开放定址法,荷载因子是特别重要因素,应严格限制在0.7-0.8以下。超过0.8,查表时的CPU缓存不命中(cache missing)按照指数曲线上升。因此,一些采用开放定址法的hash库,如Java的系统库限制了荷载因子为0.75,超过此值将resize散列表。

 

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/秋刀鱼在做梦/article/detail/808294
推荐阅读
相关标签
  

闽ICP备14008679号