您当前的位置:首页 > 电脑百科 > 程序开发 > 算法

哈希表原理

时间:2021-12-07 09:58:16  来源:  作者:一棵梧桐木

在了解golang的map之前,我们需要了解哈希这个概念。

哈希表,又称散列表(Hash table),是根据键(key)而直接访问在内存储存位置的数据结构。也就是说,它通过计算出一个键值的函数,将所需查询的数据映射到表中的一个位置让人访问,这加快了查找速度。这个映射函数称为散列函数,存放记录的数组称作散列表。

1、特点

一个优秀的哈希函数应该包含以下特性:

  • 均匀性:一个好的哈希函数应该在其输出范围内尽可能均匀地映射,也就是说,应以大致相同的概率生成输出范围内的每个哈希值。
  • 高效率:哈希效率要高,即使很长的输入参数也能快速计算出哈希值。
  • 单向性:哈希过程必须是确定性的,这意味着对于给定的输入值,它必须始终生成相同的哈希值。
  • 雪崩效应:微小的输入值变化也会让输出值发生巨大的变化。
  • 不可逆:从哈希函数的输出值不可反向推导出原始的数据。

2、哈希冲突

由于哈希算法被计算的数据是无限的,而计算后的结果范围有限,因此总会存在不同的数据经过计算后得到的值相同,这就是哈希冲突。

3、解决哈希冲突的方法

解决哈希冲突的方法一般有:开放定址法、链地址法(拉链法)、再哈希法、建立公共溢出区等方法。

而我们这里主要介绍开放地址法和拉链法。

3.1、拉链法

链接地址法的思路是将哈希值相同的元素构成一个同义词的单链表,并将单链表的头指针存放在哈希表的第i个单元中,查找、插入和删除主要在同义词链表中进行。链表法适用于经常进行插入和删除的情况。

哈希表原理

 

3.2、开放地址法

从发生冲突的那个单元起,按照一定的次序,从哈希表中找到一个空闲的单元。然后把发生冲突的元素存入到该单元的一种方法。开放定址法需要的表长度要大于等于所需要存放的元素。

在开放寻址法中解决冲突的方法有:线性探测法、平方探测法、双散列函数探测法。

开放定址法的缺点在于删除元素的时候不能真的删除,否则会引起查找错误,只能做一个特殊标记。只到有下个元素插入才能真正删除该元素。

3.2.1、线性探测法

线性探查法是开放定址法中最简单的冲突处理方法,它从发生冲突的单元起,依次判断下一个单元是否为空,当达到最后一个单元时,再从表首依次判断。直到碰到空闲的单元或者探查完全部单元为止。

设Hash(key)表示关键字key的哈希值,表示哈希表的槽位数(哈希表的大小)。

线性探测法可以表示为:

  • 如果Hash(x)%M已经有数据,则尝试(Hash(x)+1)%M
  • 如果(Hash(x)+1)%M有数据,则尝试(Hash(x)+2)%M
  • 如果(Hash(x)+2)%M有数据,则尝试(Hash(x)+3)%M

同样以哈希函数H(key)=key MOD 7(除数取余法)对一组元素[50,700,76,85,92,73,101]进行映射。

哈希表原理

 

其中,empty代表槽位为空,occupied代表槽位已被占(后续映射到该槽,则需要线性向下继续探测),而lazy delete则代表将槽位里面的数据清除,并不释放存储空间。

3.2.2、平方探测法

平方探查法即是发生冲突时,用发生冲突的单元d[i], 加上 1²、 2²等。即d[i] + 1²,d[i] + 2², d[i] + 3²…直到找到空闲单元。 在实际操作中,平方探查法不能探查到全部剩余的单元。不过在实际应用中,能探查到一半单元也就可以了。若探查到一半单元仍找不到一个空闲单元,表明此散列表太满,应该重新建立。

3.2.3、双散列函数探测法

这种方法使用两个散列函数hl和h2。

其中hl和前面的h一样,以关键字为自变量,产生一个0至m-l之间的数作为散列地址;

h2也以关键字为自变量,产生一个l至m-1之间的、并和m互素的数(即m不能被该数整除)作为探查序列的地址增量(即步长),探查序列的步长值是固定值l.

对于平方探查法,探查序列的步长值是探查次数i的两倍减l;

对于双散列函数探查法,其探查序列的步长值是同一关键字的另一散列函数的值。

4、小结

哈希桶:所有哈希值组成哈希空间

装载因子:表示哈希表中元素的填满程度。
计算方式:装载因子=填入哈希表中的元素个数/哈希表的长度。
装载因子越大,填入的元素越多,空间利用率越高,发生哈希冲突的几率变大。
装载因子越小,填入的元素越少,空间利用率越低,但空间浪费多,而且会提高扩容操作的次数。

开放地址法

只用数组一种数据结构就可完成存储,继承了数组的优点,对CPU缓存友好,易于序列化操作。

但是它对内存的利用率不如链地址法,且发生冲突时代价更高。当数据量明确、装载因子小,适合采用开放寻址法。

链地址法

1、处理冲突简单,且无堆积现象

2、由于拉链法中各链表上的节点空间在需要时创建,不必像开放地址法事先申请好足够的内存,因此对内存使用率较高,适合造表前无法确定表长的情况

3、对装载因子的容忍度较高,适合存储大对象、大数据量的哈希表

4、删除结点的操作易于实现,只要简单地删去链表上相应的结点即可。



Tags:哈希表   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系(Email:2595517585@qq.com),我们将及时更正、删除,谢谢。
▌相关推荐
在了解golang的map之前,我们需要了解哈希这个概念。哈希表,又称散列表(Hash table),是根据键(key)而直接访问在内存储存位置的数据结构。也就是说,它通过计算出一个键值的函数,将...【详细内容】
2021-12-07  Tags: 哈希表  点击:(13)  评论:(0)  加入收藏
1. 封装和解构1.1 封装说明: 等号(=)右边有多个数值仅通过逗号分割,就会封装到一个元组,称为封装packing。# 示例:x = 1,y = 1,2print(type(x), x)print(type(y), y)# 输出结果...【详细内容】
2020-07-24  Tags: 哈希表  点击:(56)  评论:(0)  加入收藏
哈希表是个啥?小白: 庆哥,什么是哈希表?这个哈希好熟悉,记得好像有HashMap和HashTable之类的吧,这是一样的嘛?庆哥: 这个哈希确实经常见,足以说明它是个使用非常频繁的玩意儿,而且像你...【详细内容】
2019-12-12  Tags: 哈希表  点击:(63)  评论:(0)  加入收藏
▌简易百科推荐
前言Kafka 中有很多延时操作,比如对于耗时的网络请求(比如 Produce 是等待 ISR 副本复制成功)会被封装成 DelayOperation 进行延迟处理操作,防止阻塞 Kafka请求处理线程。Kafka...【详细内容】
2021-12-27  Java技术那些事    Tags:时间轮   点击:(1)  评论:(0)  加入收藏
博雯 发自 凹非寺量子位 报道 | 公众号 QbitAI在炼丹过程中,为了减少训练所需资源,MLer有时会将大型复杂的大模型“蒸馏”为较小的模型,同时还要保证与压缩前相当的结果。这就...【详细内容】
2021-12-24  量子位    Tags:蒸馏法   点击:(9)  评论:(0)  加入收藏
分稀疏重建和稠密重建两类:稀疏重建:使用RGB相机SLAMOrb-slam,Orb-slam2,orb-slam3:工程地址在: http://webdiis.unizar.es/~raulmur/orbslam/ DSO(Direct Sparse Odometry)因为...【详细内容】
2021-12-23  老师明明可以靠颜值    Tags:算法   点击:(7)  评论:(0)  加入收藏
1. 基本概念希尔排序又叫递减增量排序算法,它是在直接插入排序算法的基础上进行改进而来的,综合来说它的效率肯定是要高于直接插入排序算法的;希尔排序是一种不稳定的排序算法...【详细内容】
2021-12-22  青石野草    Tags:希尔排序   点击:(6)  评论:(0)  加入收藏
ROP是一种技巧,我们对execve函数进行拼凑来进行system /bin/sh。栈迁移的特征是溢出0x10个字符,在本次getshell中,还碰到了如何利用printf函数来进行canary的泄露。ROP+栈迁移...【详细内容】
2021-12-15  星云博创    Tags:栈迁移   点击:(19)  评论:(0)  加入收藏
一、什么是冒泡排序1.1、文字描述冒泡排序是一种简单的排序算法。它重复地走访要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地...【详细内容】
2021-12-15    晓掌柜丶韶华  Tags:排序算法   点击:(16)  评论:(0)  加入收藏
在了解golang的map之前,我们需要了解哈希这个概念。哈希表,又称散列表(Hash table),是根据键(key)而直接访问在内存储存位置的数据结构。也就是说,它通过计算出一个键值的函数,将...【详细内容】
2021-12-07  一棵梧桐木    Tags:哈希表   点击:(13)  评论:(0)  加入收藏
前面文章在谈论分布式唯一ID生成的时候,有提到雪花算法,这一次,我们详细点讲解,只讲它。SnowFlake算法据国家大气研究中心的查尔斯·奈特称,一般的雪花大约由10^19个水分子...【详细内容】
2021-11-17  小心程序猿QAQ    Tags:雪花算法   点击:(24)  评论:(0)  加入收藏
导读:在大数据时代,对复杂数据结构中的各数据项进行有效的排序和查找的能力非常重要,因为很多现代算法都需要用到它。在为数据恰当选择排序和查找策略时,需要根据数据的规模和类型进行判断。尽管不同策略最终得到的结果完...【详细内容】
2021-11-04  华章科技    Tags:排序算法   点击:(37)  评论:(0)  加入收藏
这是我在网上找的资源的一个总结,会先给出一个我看了觉得还行的关于算法的讲解,再配上实现的代码: Original author: Bill_Hoo Original Address: http://blog.sina.com.cn/s/bl...【详细内容】
2021-11-04  有AI野心的电工和码农    Tags: KMP算法   点击:(36)  评论:(0)  加入收藏
最新更新
栏目热门
栏目头条