写点什么

一篇文章带你彻底了解哈希表

作者:武师叔
  • 2022 年 6 月 02 日
  • 本文字数:2830 字

    阅读完需:约 9 分钟

一篇文章带你彻底了解哈希表

哈希表

文章内有一些词语(网络热梗等)和插图,他是方便大家理解,并对算法产生(浓厚的)兴趣!

不要根据一些注释,过分曲意理解作者哦!!!!

文章内容来源本作者对该领域内容的归纳总结

文章画图软件(www.processon.com

一、认识哈希表

1.1 哈希表出现缘由

要查一个数在数组中的位置,那可是太费劲了,只能从头开始一个个的比较,直到找到相等的才算完事。

这个方法,说实话也太笨了,简直不是我这种懒人应该做的事。

就不能有种方法直接看到这个数,就直接在数组中查到位置嘛?!


点击并拖拽以移动

编辑

诶,你别说,还真有。

因为总有比我更懒的,我只是懒是只能躺着,人家大佬的懒是直接动手解决,果然那句”懒是第一生产力“!

1.2 哈希表概述

这个就是我今天要给家人们带来的哈希表


点击并拖拽以移动

编辑


哈希表,别名儿叫散列表,洋名儿叫 Hash Table。


我在上面说,希望有种方法,直接看到数,就知道它在数组中的位置,其实里就用到了哈希思想。


哈希思想就是说不用一些无用的比较,直接可以通过关键字 key 就能找到它的存储位置。


这里举一个栗子(可不是堂嫂栗子哦),可能更清楚点:

智能班有 40 个学生,每个学生的学号由入学年份 + 年级 + 班级 + 编号组成,例如 2020.20.01.32 是 2020 年入学的 20 级 01 班的 32 号同学。(学号怕你看混,给你个"."分割,贴心不~)


现在有个需求(烦人的 PM):我们需要快速找到某个同学的个人信息。

那这个时候我们就要建立一张表,按理来说我要是想要知道某个同学的个人信息,其实就知道学号就好了,但是在这不行,学号的值实在太大了,我们不能把学号当作下标。

学号不可以,那什么可以呢?我们定睛一看,咦,编号可以呀,编号是从 1 ~ 40。(我真是一个小聪明啊)


点击并拖拽以移动

编辑


那咋取到编号?不就是学号对 2020.20.01.00 取余就 KO 了嘛。(你不会没理解把,不就是相当于(上面栗子 32 这位大帅哥),32/00=32 嘛)

此时,如果我们想查学号为 2020.20.01.32 的学生个人信息,只要访问下标为 32 的数据即可。

其实这就可以在时间复杂度为 O(1) 内解决找到。(不要问我什么是时间复杂的,什么是空间复杂度,生产队的 LV 马上更,不要打拉)

秒男实锤了。(这摸快,O(1),比三秒都快哦)


点击并拖拽以移动

编辑


用公式表示就是:存储位置 = f(关键字)

这里的 f 又叫做哈希函数,每个 key 被对应到 0 ~ N-1 的范围内,并且放在合适的位置。

在上面的例子中 f(key) = key % 2021210100。


点击并拖拽以移动

编辑


存储时,通过同一个哈希函数的计算 key 的哈希地址,并按照此哈希地址存储该 key。

最后形成的表就是哈希表,它主要是面向查找的存储结构,简化了比较的过程,提高了效率。


点击并拖拽以移动

编辑


1.3 哈希示例

上面看明白的话,那再举个大栗子加深点印象。

有个 n = 10 的数组,哈希函数 f(key) = key % 10,将 4,10,11,19,29,39 散列到数组中。

哈希函数确定后,剩下的就是计算关键字对应的存储位置。

4 % 10 = 4,所以将 4 放入下标为 4 的位置。


点击并拖拽以移动

编辑

 10 % 10 = 0,所以将 10 放入下标为 0 的位置。


点击并拖拽以移动

编辑

11 % 10 = 1,所以将 11 放入下标为 1 的位置。


点击并拖拽以移动

编辑


19 % 10 = 9,所以将 19 放入下标为 9 的位置。


点击并拖拽以移动

编辑

29 % 10 = 9,所以将 29 放入下标为 9 的位置。

但是现在问题来了,下标为 9 的这个坑已经被 19 占了,这 29 计算出来的下标冲突了。(作为工具人的我,呜呜,就让我为你来平定冲突和亲去,昭君我来了)


点击并拖拽以移动

编辑


这种情况有个学名,叫:哈希(散列)冲突

1.4 处理哈希冲突

对于两个不相等的关键字 key1 和 key2,若 f(key1) = f(key2),这就是哈希冲突。

key1 占了坑,那 key2 只能想别的办法,啥办法呢?

一般处理哈希冲突有以下几种办法:

  • 开放定址法

  • 再哈希(散列)函数法

  • 链地址法

  • 。。。(别想了,就等你来创造一个,作为算法“行业冥灯”,击垮他们!)

1.4.1 开放定址法

开放定址法就是:一旦发生冲突,就选择另外一个可用的位置。

开放定址法有 2 个最常用的策略:

  • 线性探测法

  • 二次探测法

线性探测法

线性探测法,顾名思义,直来直去的探测。

且看它的公式:

f(key) = (f(key) + di) % m (di = 1, 2, 3, ... , m-1)。

我还是用“哈希示例”中的栗子(栗子都快熟了):

n = 10 的数组,哈希函数 f(key) = key % 10,将 4,10,11,19,29,39 散列到数组中。


点击并拖拽以移动

编辑


到了 29 的时候,29 % 10 = 9。

但此时下标 9 已经有了元素 19,所以此时探测下一个位置 (9 + 1) % 10 = 0。

下标为 0 的位置上已经有了元素 10,所以继续探测下一个位置 (9 + 2) % 10 = 1。

下标为 1 的位置上也有了元素 11,所以还得继续探测下一个位置 (9 + 3) % 10 = 2。

下标为 2 的位置上总算是空的,因此 29 找到了家(我家的猫不会跳舞,但是会爬树):


点击并拖拽以移动

编辑

不知道你发现了没,对于 29 这个来说,本来只是和 19 冲突,整着整着和 10,11 也冲突了。

这样就使得每次要处理好几次冲突,而且这样会出现大量数字聚集在一个区域的情况,大大降低了插入和查找的效率。

后来不知道哪个大佬在线性的基础上做了改进,捣鼓出二次探测法。


点击并拖拽以移动

编辑

二次探测法

二次探测法就是把之前的 di 整成了平方,公式如下:

f(key) = (f(key) + di) % m (di = 1², -1², 2², -2², ..., q², -q², q ≤ m/2)

比如对于 29 来说,下标为 9 的位置上呆了 19,所以此时探测下一个位置 (9 + 1²) % 10 = 0。

下标为 0 的位置上占了元素 10,那下一次就探测上一个位置 (9 - 1²) % 10 = 8。

下标为 8 的位置上空着,直接占住:


点击并拖拽以移动

编辑


点击并拖拽以移动

编辑

1.4.2 再哈希(散列)函数法

再哈希的话,就是不只是一个哈希函数,而是使用一组哈希函数 f1(key)、f2(key)、f3(key)....。

当使用第一个哈希函数计算到的存储位置被占了,那就用第二个哈希函数计算,反正总会有一个散列函数能把冲突解决掉。

依次类推,直到找到空的位置,然后占住。

当然这种方法不会出现大量数字聚集在一个区域的情况,但这种情况明显增加了计算的时间。

1.4.3 链地址法

是谁说出现冲突后只能找别的坑位的,几个人蹲一个坑它不香嘛。(还记得伦敦的谜语吗)


点击并拖拽以移动

编辑


可能真的有巨佬觉得香,然后就整出了链地址法。


链地址法呢是将得出同一个结果的 key 放在一个单链表中,哈希表存储每条单链表的头指针。


还是用老栗子:n = 10 的数组,哈希函数 f(key) = key % 10,将 4,10,11,19,29,39 散列。


最后得到如下图:


点击并拖拽以移动

编辑


你看,链地址法就不会出现此坑被占,就得去找别的坑的情况。


大家一起蹲,这样就绝不会出现找不到地址的情况,而是直接插到对应的单链表中即可,所以插入的时间复杂度为 O(1)


当然有得必有失,这样的情况必然造成了查找上的性能损耗,这里的查找的时间复杂度为 O(k),其中 k = n / 单链表条数


点击并拖拽以移动

编辑


1.5 结语和附录

好啦,到这里哈希表就讲完辣,是不是看起来还挺简单的。


哈希表作为非常高高高高高效的查找数据结构,丢掉了关键字之间反复无意义的比较,直接一步到位查找结果,非常顶(咳咳)。


这么看来它处理冲突啥的这点屁事就显得不是那么烦人了,毕竟有得有失才对嘛。


点击并拖拽以移动

编辑


文献来源:

编程文青李狗蛋——ACM 选手带你玩转哈希表!

LeetCode 242 题目中的解法和讨论区

下一篇:牛刀小试——LeetCode 242 (Python 和 Java)

要想获得更多内容就关注我吧~

发布于: 刚刚阅读数: 4
用户头像

武师叔

关注

每天丰富自己,去过自己想要的生活! 2022.04.28 加入

一个喜欢最新技术,研发的人工智能专业的大二学生,用自己的代码做一些有意义的事情! 目前大二结束有去大厂研发岗实习的计划,每天丰富自己的技术,去过自己想要的实习生活。

评论

发布
暂无评论
一篇文章带你彻底了解哈希表_6月月更_武师叔_InfoQ写作社区