散列表(Hash Table)

定义

散列表是一种以平均O(1)时间插入、删除和查找的数据结构,可是类似于findMax,findMin等操作则需要以O(N)的时间才能完成

散列函数

散列函数是将关键字计算成Hash值的一个函数 散列函数的选择是非常重要的,它的复杂度影响着影响着插入、删除、查找的速度:

  1. 散列值的计算时间
    • 每次操作前需要根据关键字进行散列,寻找关键字存储位置
  2. 散列值的重合度
    • 根据散列冲突(Hash Conflict)的解决方案,从冲突的存储数据中找到真正的数据位置

解决Hash冲突

方案1:分离链接法

将关键字的Hash值相同的节点以链表的方式进行存储,以解决Hash冲突

新插入的节点都会放在第一个,因为往往新插入的节点元素最有可能被访问,所以插入效率很高。 而当需要删除/查找节点的时候,如果散列函数的计算出来的值重合度非常高,那么最坏的情况会将O(1)的常数时间变成O(N)的线性时间,因为需要把整个链表进行遍历。也可以用变种的二叉树进行存储,也只是将O(N)的时间变成了O(logN)而已。

所以散列函数的选择是非常非常重要的,尽量对关键字所计算的时间要短,并且重合度低才能保证Hash的效率

分离链接法

方案2:开放寻址法-线性探测

根据关键字散列后,找到关键字散列位置,查找散列表中离冲突单元最近的空闲单元,并且把新的键插入这个空闲单元。当插入节点满了的话,则需要进行扩容。 如下图: John Smith和Sandra Dee(都被杂凑映射到了单元873)的冲突,借由把后者放在下一个空闲单元(单元874)而解决

线性探测法

当查找节点的时候,找到Hash位置,然后一个个往下找,直到找到节点或者空节点才返回。

当删除节点的时候,单纯地清空对应的单元是不够的。这会影响到对于储存时间早于该单元、但储存位置在该单元之后的其他键,从而对查找产生影响。 相较于直接清空对应单元i,更好的做法是先清空,然后把它之后所有会造成问题的单元向前移动,来避免搜索出错。重复直到出现空单元,则删除动作安全完成。如下图:

当一对键值对被删除,可能会有必要将其他的键值对放回到它的单元中,来防止搜索时搜索到空的单元

方案3:开放寻址法-平方探测

与线性探测差不多,只是插入的间隔从1变成了冲突间隔的平方,如A与B冲突了,而C与AB都冲突了,那么C就会插入到距离A的2*2的空闲位置处。

荷载因子

散列表的载荷因子定义为:A = 填入表中的元素个数 / 散列表的长度

A越大,表明填入表中的元素越多,产生冲突的可能性就越大,A越小,标明填入表中的元素越少,产生冲突的可能性就越小

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏用户2442861的专栏

STL map, hash_map , unordered_map区别、对比

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/haluoluo211/article/d...

58450
来自专栏来自地球男人的部落格

tensorflow中取值

最近在写用tensorflow的程序时,中途遇到想取出tensorflow中的返回值是什么,可是其返回值也是一个tensor。用了两种方法,试图将tensor直...

24060
来自专栏申龙斌的程序人生

零基础学编程018:条件语句

学习了《零基础学编程017:画出我的公众号LOGO》之后,可以用几行代码,画出一个螺旋渐开线。 from turtle import * for i in r...

35860
来自专栏架构说

Effective STL(21) 永远让比较函数对相同元素返回false

问题描述: 昨天一哥们些的程序,在定义比较函数的时候是这样写的 bool cmp(const T& a, const T& b) { if (a >=...

38790
来自专栏锦小年的博客

python学习笔记6.7-简化数据结构的初始化过程

我们每编写一个类的时候都需要编写一个初始化函数,那么如果编写的类当做数据结构来用,它们的初始化结构就是一样的,例如: class Stock: def ...

22560
来自专栏Web 开发

做wordpress CMS必须用到的强力代码(转)

这个代码很强力,做一个wordpress cms的索引页面(index.php) 这个代码是必须要会使用,不然会走很多弯路。

11320
来自专栏magicsoar

Effective Modern C++翻译(5)-条款4:了解如何观察推导出的类型

条款4:了解如何观察推导出的类型 那些想要知道编译器推导出的类型的人通常分为两种,第一种是实用主义者,他们的动力通常来自于软件产生的问题(例如他们还在调试解决中...

21180
来自专栏图形学与OpenGL

WebGL画点程序v2

本文程序实现画一个点的任务,如下图。其中,点的位置坐标由Javascript传到着色器程序中,而不是直接给定(“硬编码”)在顶点着色器中。

12540
来自专栏生信技能树

R for Data Science(十二)

一直觉得编程能力好的人都会写函数,我对R语言写函数能力比较差,就学了这一章节,拆分如何写函数以及为什么写函数 例如我们看一下这个代码

14320
来自专栏小樱的经验随笔

hihoCoder #1082 : 然而沼跃鱼早就看穿了一切(字符串处理)

#1082 : 然而沼跃鱼早就看穿了一切 时间限制:1000ms 单点时限:1000ms 内存限制:256MB 描述 ? fjxmlhx每天都在被沼跃鱼刷屏,因...

29550

扫码关注云+社区

领取腾讯云代金券