文档章节

什么是哈希表?

武培轩
 武培轩
发布于 02/17 01:03
字数 2000
阅读 67
收藏 0

我们在这篇文章将要学习最有用的数据结构之一—哈希表,哈希表的英文叫 Hash Table,也可以称为散列表或者 Hash 表

哈希表用的是数组支持按照下标随机访问数据的特性,所以哈希表其实就是数组的一种扩展,由数组演化而来。可以说,如果没有数组,就没有散列表。

哈希表存储的是由键(key)和值(value)组成的数据。 例如,我们将每个人的性别作为数据进行存储,键为人名,值为对应的性别,其中 M 表示性别为男,F 表示性别为女。

为什么需要哈希表?

为了和哈希表进行对比,我们先将这些数据存储在数组中。

此处准备了6个箱子(即长度为6的数组)来存储数据,假设我们需要查询 Ally 的性别,由于不知道 Ally 的数据存储在哪个箱子里,所以只能从头开始查询,这个操作便叫作线性查找。一般来说,我们可以把键当成数据的标识符,把值当成数据的内容。

从 0 号箱子开始查找,发现 0 号箱子中存储的键是 Joe 而不是 Ally,因此接着查找 1 号箱子。

哦豁,1 号箱子中的也不是 Ally,没办法,只能接着往下找。

有点小糟糕,2 号、3 号箱子中的也都不是 Ally。

功夫不负有心人,当我们查找到 4 号箱子的时候,发现其中数据的键为 Ally,把键对应的值取出,我们就知道 Ally 的性别为女(F)。

通过上面的查找过程,我们发现数据量越多,线性查找耗费的时间就越长。由此可知:由于数据的查询较为耗时,所以此处并不适合使用数组来存储数据。

但使用哈希表便可以解决这个问题,首先准备好数组,这次我们用 5 个箱子的数组来存储数据。

尝试把 Joe 存进去,使用哈希函数(Hash)计算 Joe 的键,也就是字符串 Joe 的哈希值,比如得到的结果为4928。

将得到的哈希值除以数组的长度 5,求得其余数,这样的求余运算叫作mod运算,此处mod运算的结果为3。

因此,我们将 Joe 的数据存进数组的 3 号箱子中,重复前面的操作,将其他数据也存进数组中。

Sue 键的哈希值为 7291, mod 5 的结果为 1,将 Sue 的数据存进 1 号箱中。

Dan 键的哈希值为 1539, mod 5 的结果为 4,将 Dan 的数据存进 4 号箱中。

Nell 键的哈希值为 6276, mod 5 的结果为 1,本应将其存进数组的 1 号箱中,但此时 1 号箱中已经存储了 Sue 的数据,这种存储位置重复了的情况便叫作冲突

遇到这种情况,可使用链表在已有数据的后面继续存储新的数据(链表法)。

Ally 键的哈希值为 9143, mod 5 的结果为 3,本应将其存储在数组的 3 号箱中,但 3 号箱中已经有了 Joe 的数据,所以使用链表,在其后面存储 Ally 的数据。

Bob 键的哈希值为 5278, mod 5 的结果为 3,本应将其存储在数组的 3 号箱中,但 3 号箱中已经有了 Joe 和 Ally 的数据,所以使用链表,在 Ally 的后面继续存储 Bob 的数据。

像这样存储完所有数据,哈希表也就制作完成了。

接下来讲解数据的查询方法,假设我们要查询 Dan 的性别。

为了知道 Dan 存储在哪个箱子里,首先需要算出 Dan 键的哈希值,然后对其进行 mod 运算,最后得到的结果为 4,于是我们知道了它存储在 4 号箱中。

查看 4 号箱可知,其中的数据的键与 Dan 一致,于是取出对应的值,由此我们便知道了 Dan 的性别为男(M)。

那么,想要查询 Ally 的性别时该怎么做呢?为了找到它的存储位置,先要算出 Ally 键的哈希值,再对其进行 mod 运算,最终得到的结果为 3。

然而 3 号箱中数据的键是 Joe 而不是 Ally,此时便需要对 Joe 所在的链表进行线性查找。

于是我们找到了键为 Ally 的数据,取出其对应的值,便知道了 Ally 的性别为女(F)。

哈希冲突

在哈希表中,我们可以利用哈希函数快速访问到数组中的目标数据。如果发生哈希冲突,就使用链表进行存储,这样一来,不管数据量为多少,我们都能够灵活应对。

如果数组的空间太小,使用哈希表的时候就容易发生冲突,线性查找的使用频率也会更高;反过来,如果数组的空间太大,就会出现很多空箱子,造成内存的浪费。因此,给数组设定合适的空间非常重要。

在存储数据的过程中,如果发生冲突,可以利用链表在已有数据的后面插入新数据来解决冲突,这种方法被称为链表法,也被称为链地址法

其中在 Java 集合类的 HashMap 中解决冲突的方法就是采用的链表法,建议阅读 HashMap 源码。

除了链地址法以外,还有几种解决冲突的方法。其中,应用较为广泛的是开放地址法,或称为开放寻址法。这种方法是指当冲突发生时,立刻计算出一个候补地址(数组上的位置)并将数据存进去。如果仍然有冲突,便继续计算下一个候补地址,直到有空地址为止,可以通过多次使用哈希函数线性探测法等方法计算候补地址。

在 Java 中,ThreadLocal 所使用的就是开放地址法

哈希函数设计的好坏决定了哈希冲突的概率,也就决定哈希表的性能。

总结

这篇文章主要讲了一些比较基础的哈希表知识,包括哈希表的由来、哈希冲突的解决方法。

哈希表也叫散列表,来源于数组,它借助哈希函数对数组这种数据结构进行扩展,利用的是数组支持按照下标随机访问元素的特性,是存储 Key-Value 映射的集合。

哈希表两个核心问题是哈希函数设计和哈希冲突解决。对于某一个 Key,哈希表可以在接近 O(1) 的时间内进行读写操作。哈希表通过哈希函数实现 Key 和数组下标的转换,通过开放寻址法和链表法来解决哈希冲突。哈希函数设计的好坏决定了哈希冲突的概率,也就决定哈希表的性能。

有兴趣的可以在 JDK 中阅读 HashMap 的源码,在 JDK 8 和之前的版本的实现还有许多不多,比如在 JDK 8 中,引入红黑树,当链表长度太长(默认超过 8)时,链表就转换为红黑树,就可以利用红黑树快速增删改查的特点,提高 HashMap 的性能。

参考

《我的第一本算法书》

https://github.com/wupeixuan/JDKSourceCode1.8

© 著作权归作者所有

武培轩
粉丝 12
博文 64
码字总数 118325
作品 0
海淀
私信 提问
加载中

评论(0)

查找算法(7)--Hash search--哈希查找

1.哈希查找   (1)什么是哈希表(Hash)    我们使用一个下标范围比较大的数组来存储元素。可以设计一个函数(哈希函数, 也叫做散列函数),使得每个元素的关键字都与一个函数值(即数组下...

```...简单点
2019/09/28
0
0
Python核心编程 第七章课后习题

核心笔记:什么是哈希表?它们与字典的关系是什么? 序列类型用有序的数字键做索引将数据以数组的形式存储。一般,索引值与所存储的数据毫无 关系。还可以用另一种方式来存储数据:基于某种相关值...

toddler
2015/01/17
249
0
什么叫哈希表(转载)

google搜索到的头条:散列表(也叫哈希表),是根据关键码值直接进行访问的数据结构,也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数...

云栖希望。
2017/12/04
0
0
redis-hash类型的hset、hmset,有什么区别?

  hset      描述:将哈希表key中的域field的值设为value。如果key不存在,一个新的哈希表被创建并进行HSET操作。如果域field已经存在于哈希表中,旧值将被覆盖。   参数:keyfieldv...

运维菜
2018/02/01
0
0
机器学习时代的哈希算法,将如何更高效地索引数据

  选自blog.bradfieldcs   作者:Tyler Elliot Bettilyon   机器之心编译      哈希算法一直是索引中最为经典的方法,它们能高效地储存与检索数据。但在去年 12 月,Jeff Dean 与 ...

机器之心
2018/05/06
0
0

没有更多内容

加载失败,请刷新页面

加载更多

科技战疫之企业篇:年度最火直播 "云监工"下造医院

“5G信号现在起什么作用?”、“蹭什么热点,现在大部分人都没有5G手机吧?”1月24日,当三大运营商刚刚宣布为武汉火神山和雷神山医院建设5G时,大多数网友都予以质疑。而不到一周后,两个医...

osc_n9lb74k9
10分钟前
14
0
nginx http模块11个阶段驱动模式详解

在nginx调用ngx_http_process_request_headers()方法读取完所有的header数据之后,就调用ngx_http_process_request()方法开始了请求的处理过程,这也就是nginx http模块开始处理请求的11个阶...

爱宝贝丶
10分钟前
18
0
电视广告关不掉?江苏拟规定广告开机可4秒内消失

智能电视开机必须要看一段广告,针对这一饱受消费者诟病的问题。3月10号上午,江苏省消保委发布了《智能电视开机广告技术规范(征求意见稿)》,对开机广告一键关闭功能的设置,提出了明确的标...

osc_c0usoa3v
11分钟前
12
0
B站向武汉等七城隔离观察群众捐赠首批10万个大会员

2月10日午间消息,为丰富抗击疫情地区隔离群众的精神文化生活,哔哩哔哩(以下简称“B站”)联合人民网向抗击新冠肺炎的部分地区,公益捐赠10万个为期一个月的B站大会员。“大会员”是B站推出...

osc_n75mz9au
13分钟前
9
0
基于压力测试工具构建虚拟用户脚本的并发模型

在对于WEB系统进行性能测试时,第一时间想到的是测试出WEB系统能够承受的最大并发虚拟用户(VU)用户数,因为系统的最大VU并发数可以直接反应系统的承载能力。但是人们往往忽略了VU的并发模型...

osc_p0v6j6lt
14分钟前
14
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部