更多优质内容
请关注公众号

算法小白的入门日记(三) Hashmap——高效查找Key-Value的无序结构-张柏沛IT博客

正文内容

算法小白的入门日记(三) Hashmap——高效查找Key-Value的无序结构

栏目:算法专题 系列:算法小白的入门日记 发布时间:2021-11-19 09:49 浏览量:290
本系列文章目录
展开/收起

· hashMap的数据结构

hashMap(散列表/哈希表)是一种提供键值映射关系数据结构,能做到高效查询key对应的value。它的底层结构是数组+链表,或者数组+树。

 

数组的每个元素都存储着一对或者多对key-valuekey可以是字符串或者其他类型,数组的下标是整型,因此需要一个可以将key转为整型的hash函数,一般的思路是通过hash函数将一个key转为一个整型A后,再用整型A对数组的长度进行取模运算得到一个数组下标B

 

当然,实际上很多高级语言或者应用都是用整型A与数组的长度掩码(即数组长度-1)进行&的位运算得到下标,因为对于计算机而言,位运算比取模要快得多。但是它们的实际效果是一样的,取模和&位运算都能得到相同的数组下标。当然了 A & (length - 1) 和 A mod length 等价的条件是 length必须是2的n次幂,而数组的长度一般都是2的n次幂。

 

hash函数应该满足2个要求:计算简单,极可能降低hash计算的复杂度;计算出来的hash值尽可能均匀分布。

 

·哈希表增删改查

 

查找

通过key寻找value的过程本质上是将key进行hash运算和位运算得到一个数组下标,根据数组下标、单个数组元素的大小和数组起始地址得到key所在下标的内存地址,并读取内存地址的内容。

已知数组查找是随机访问,复杂度为O(1),因此主要的复杂度来自哈希运算,现在计算机领域的哈希运算基本上都是O(1)的复杂度。因此综合起来,其查找复杂度可近似看做O(1)

 

插入

以链表法构建的哈希表为例,插入操作也是需要先根据key找到数组对应的位置对该数组位置下的链表链入新的value,其复杂度为O(1)

 

删除

以链表法构建的哈希表为例,删除操作也是先查找到key对应的数组元素链表指针从该链表中移除key节点。无需涉及到数组元素左移或右移,因此复杂度为O(1)

 

修改

同查找,复杂度为O(1)

 

· 解决冲突

插入时可能出现两个不同的key经过哈希运算和位运算之后得到一个相同的下标,此时发生冲突。

冲突则主流解决方法有 开放寻址法  链表法

 

开放寻址法

(又称线性探测法)即如果新添加的某个key和之前的key发生冲突(计算出来的数组下标相同),就寻找下一个空的散列地址。直到散列表足够大,空的位置总能找到。

其公式如下:

某一个key的下标 = (key哈希值 + 偏移量d) mod 数组长度

例如有一个集合{n1,..., n12},集合中的元素计算出来的哈希值为{12,67,56,16,25,37,22,29,15,47,48,34}。现在他们要放入哈希表中,哈希表内数组长度为12

.

当存储前5个数{12,67,56,16,25}时,都是没有冲突的散列地址:

轮到37的时候,(37 + 0) mod 12 = 1,所以他应该放到arr[1]的位置,但是该位置已经被25占了。因此需要把偏移量+1并重新取模:(37+1) mod 12 = 2arr[2]位置为空,因此37放到arr[2]中。如果偏移量自增后得到的下标仍被占用了,就再对偏移量自增,直到找到位置为空的下标。keyvalue的内容会被同时存到该下标中。

 

这种寻址法会随着数组中元素数量增大而效率降低,因为随着数组空闲位置数量的减少,一个key的插入可能会遇到多次冲突,寻址需要计算的次数会越来越多。

不仅是插入,连查询都要遵循上面的过程如果偏移量d自增到数组长度的次数仍未查询到对应key,就说明这个key不存在于这个哈希表中。

因此,通过寻址法构建的哈希表查询不存在的key时,就会造成O(n)的复杂度。

 

而且在数组空闲位置数量越接近0时,插入和查找的复杂度也越接近O(n)

为了避免这种情况,我们应该为数组初始化一个比较大的容量。

 

上面这种寻址方式是一次探测法。考虑一种情况,当数组如下图的时候:

如果某个keyhash3434 mod 12 = 10。找到arr[10]这个位置,但已经被占用。反而是他前一个位置arr[9]空闲, 那么就要需要再进行11次寻址计算才能找到arr[9]这个空闲位置:(34 + 11) mod 12 = 9,此时偏移量d需要自增到11才能找到正确的空闲位置。

 

优化方法是对偏移量考虑其相反数来计算,即偏移量d = 0, 1, -1, 2, -2...,这样偏移量改变到第2次是就能正确找到34的下标了。

我们称这种方法为二次探测法。

 

除此之外,我们可以通过生成不重复值的随机函数来获取一个随机偏移量,这种方式叫随机探测法。

上面这几种探测法都属于开放寻址法,只要数组有空闲位置就总能解决冲突。

 

 

链表法

 

链表法是让数组的每个元素存储一个单向链表(存链表的头指针),存储的key-value会作为一个节点对象存到数组元素中。如果某个key-value存入位置k发生冲突时,该key-value会作为尾部节点追加到arr[k]所存储的链表中(可能是追加到头部或尾部,追加到头部复杂度为O(1),加到尾部复杂度为O(n))。

 

链表法是目前最主流的解决哈希表冲突的方法,在不同的高级语言或应用中,数组元素保存的数据结构不同,有些使用单向链表,有些为了提高插入效率和查找效率使用红黑树,有些则使用双向链表。

 

 

再散列函数法

在插入和查找时使用多个散列函数而非一个散列函数。

插入时:使用第一个散列函数发生冲突则使用第二个散列函数,再冲突就用第三个散列函数,直到不冲突。但如果所有散列函数用完仍未找到空闲位置则冲突无法解决,因此需要结合其他解决冲突的方式一起使用。

 

查找时使用第一个散列函数寻找key的下标如果找到的key不是目标key则用第二散列函数寻找key的下标,直到找到的key与目标key匹配取出对应的value。如果执行完所有散列函数都没找到说明key不存在。

 

公共溢出区法

准备两个表:基本表和溢出表,基本表是一个hash表,溢出表则是一个普通的链表或者数组用来存储所有冲突的key

插入时:通过计算hash值并取模找到数组下标,如果没冲突则key-value存入基本表的对应下标中。如果有冲突,则key-value存入溢出表中(存入溢出表的尾部)。

查找时:通过计算hash值并取模找到数组下标,在基本表的该下标找到key与目标key比对,如果两个key不符则再到溢出表找。此时需要遍历溢出表,用目标key与溢出表的key逐一比对直到找到一致的key

 

在冲突很少的情况下,公共溢出表的查询性能也还是很高的。

 

 

·扩容

当哈希表的数组已经放满key-value之后,需要对哈希表进行扩容,否则哈希表插入和查询等操作效率降低并且无法解决冲突。

 

Java中的哈希表为例,它的哈希表是以链表法构建的,决定一个哈希表是否扩容取决于HashMap的负载因子(Lf表示,默认的Lf0.75)

 

负载因子 = HashMap中数组长度 / HashMap中链表节点数量

负载因子衡量的是每个数组下标平均存储k-v节点个数,也是每个数组下标的拥挤程度。如果有很多key因为解决冲突而放到同一数组下标的链表中,那么这个HashMap的负载因子就容易高。此时查询效率都会降低(因为链表的查询效率是O(n)),插入效率可能降低(要看插入到链表尾部还是头部)。

 

 

扩容的过程:

  1. 底层会创建一个新的哈希表数组,该数组长度是原数组的2倍。
  2. 对原有hashMap的所有节点rehash,即对所有key重新进行hash计算并放入到新数组的对应位置。数组长度变大后,求模得到每个key的数组下标会和之前不同。



更多内容请关注微信公众号
zbpblog微信公众号

如果您需要转载,可以点击下方按钮可以进行复制粘贴;本站博客文章为原创,请转载时注明以下信息

张柏沛IT技术博客 > 算法小白的入门日记(三) Hashmap——高效查找Key-Value的无序结构

热门推荐
推荐新闻