Hash冲突及解决办法
创始人
2024-06-03 10:33:01
0

目录

  • 开放定址法
    • 线性探测再散列
    • 二次探测再散列
    • 伪随机探测再散列
  • 再哈希法
  • 链地址法(拉链法)
  • 建立公共溢出区

开放定址法

这种方法也称再散列法,其基本思想是:当关键字key的哈希地址p=H(key)出现冲突时,以p为基础,产生另一个哈希地址p1,如果p1仍然冲突,再以p为基础,产生另一个哈希地址p2,…,直到找出一个不冲突的哈希地址pi ,将相应元素存入其中。这种方法有一个通用的再散列函数形式:

Hi=(H(key)+di)% m i=1,2,…,n

其中H(key)为哈希函数,m 为表长,di称为增量序列。增量序列的取值方式不同,相应的再散列方式也不同。主要有以下三种:

线性探测再散列

dii=1,2,3,…,m-1, 这种方法的特点是:冲突发生时,顺序查看表中下一单元,直到找出一个空单元或查遍全表。

3,4, 5,6,69,哈希表长度m=11
H(69)=3, 则下一个哈希地址为H1=(3 + 1)% 11 = 4,仍然冲突,再找下一个哈希地址为H2=(3 + 2)% 11 = 5,仍然冲突,再找下一个哈希地址为H2=(3 + 3)% 11 = 6, 此时不再冲突,将69填入6号单元。

二次探测再散列

di=12,-12,22,-22,…,k2,-k2 ( k<=m/2 ),这种方法的特点是:冲突发生时,在表的左右进行跳跃式探测,比较灵活。.

2, 3,4, 5,6,69,哈希表长度m=11
H(69)=3, 则下一个哈希地址为H1=(3 + 1)% 11 = 4,仍然冲突,再找下一个哈希地址为H2=(3 - 1)% 11 = 2,仍然冲突,再找下一个哈希地址为H2=(3 + 4)% 11 = 7, 此时不再冲突,将69填入7号单元。

伪随机探测再散列

di=伪随机数序列。

2, 3,4, 5,6,69,哈希表长度m=11
H(69)=3, 随机数序列为:2,5,9,………,则下一个哈希地址为H1=(3 + 2)% 11 = 5,仍然冲突,再找下一个哈希地址为H2=(3 + 5)% 11 = 8,此时不再冲突,将69填入8号单元。

再哈希法

这种方法是同时构造多个不同的哈希函数:

Hi=RH1(key) i=1,2,…,k

当哈希地址Hi=RH1(key)发生冲突时,再计算Hi=RH2(key)……,直到冲突不再产生。这种方法不易产生聚集,但增加了计算时间。
在这里插入图片描述

链地址法(拉链法)

jdk1.8 中HashMap,ConcurrentHashMap都是采用这个方法,使用链表来保存发生hash冲突的key,即不同的key有一样的hash值,将这些发生冲突的 value 组成一个单向链表(只有next指针,没有pre指针)

注意:最坏的就是hash值全都映射在同一个地址上,这样哈希表就会退化成链表。jdk1.8采用红黑树解决这种情况。
在这里插入图片描述

建立公共溢出区

这种方法的基本思想是:将哈希表分为基本表和溢出表两部分,凡是和基本表发生冲突的元素,一律填入溢出表。
在查找的时候,先与哈希表的相应位置比较,如果查找成功,则返回。否则去公共溢出区按顺序一一查找。在冲突数据少时性能好,冲突数据多的时候耗时。

在这里插入图片描述

相关内容

热门资讯

喜欢穿一身黑的男生性格(喜欢穿... 今天百科达人给各位分享喜欢穿一身黑的男生性格的知识,其中也会对喜欢穿一身黑衣服的男人人好相处吗进行解...
发春是什么意思(思春和发春是什... 本篇文章极速百科给大家谈谈发春是什么意思,以及思春和发春是什么意思对应的知识点,希望对各位有所帮助,...
网络用语zl是什么意思(zl是... 今天给各位分享网络用语zl是什么意思的知识,其中也会对zl是啥意思是什么网络用语进行解释,如果能碰巧...
为什么酷狗音乐自己唱的歌不能下... 本篇文章极速百科小编给大家谈谈为什么酷狗音乐自己唱的歌不能下载到本地?,以及为什么酷狗下载的歌曲不是...
华为下载未安装的文件去哪找(华... 今天百科达人给各位分享华为下载未安装的文件去哪找的知识,其中也会对华为下载未安装的文件去哪找到进行解...
怎么往应用助手里添加应用(应用... 今天百科达人给各位分享怎么往应用助手里添加应用的知识,其中也会对应用助手怎么添加微信进行解释,如果能...
家里可以做假山养金鱼吗(假山能... 今天百科达人给各位分享家里可以做假山养金鱼吗的知识,其中也会对假山能放鱼缸里吗进行解释,如果能碰巧解...
一帆风顺二龙腾飞三阳开泰祝福语... 本篇文章极速百科给大家谈谈一帆风顺二龙腾飞三阳开泰祝福语,以及一帆风顺二龙腾飞三阳开泰祝福语结婚对应...
美团联名卡审核成功待激活(美团... 今天百科达人给各位分享美团联名卡审核成功待激活的知识,其中也会对美团联名卡审核未通过进行解释,如果能...
四分五裂是什么生肖什么动物(四... 本篇文章极速百科小编给大家谈谈四分五裂是什么生肖什么动物,以及四分五裂打一生肖是什么对应的知识点,希...