2025年hash冲突以及hash冲突的解决方法

hash冲突以及hash冲突的解决方法首先说一下 hash 冲突吧 hash 冲突在 hash 表中一般情况下是会遇到的 hash 冲突指的是你在向 hash 表中存数据时 首先要通过 key 值进行指定的 hash 算法进行计算 然后得到一个值 这个值就是你要将这个 key 对应的 value 存入的地址 但是在这个地址中已经有值存在 所以这个时候就发生了 hash 冲突 不同的 key 通过 hash 算法得到了对应的同一个值 hash 冲突解决的方法


首先说一下hash冲突吧,hash冲突在hash表中一般情况下是会遇到的;
hash冲突指的是你在向hash表中存数据时,首先要通过key值进行指定的hash算法进行计算,然后得到一个值,这个值就是你要将这个key对应的value存入的地址。但是在这个地址中已经有值存在,所以这个时候就发生了hash冲突,不同的key通过hash算法得到了对应的同一个值。

hash冲突解决的方法:

再hash法:这种方法就是有多个hash算法,当使用一个hash算法计算得到值发生hash冲突时那就使用另外一个hash算法,直到没有hash冲突。这种方法增加了计算的时间。

开放地址法
这种方法也称再散列法,其基本思想是:当关键字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
这种方法的特点是:冲突发生时,顺序查看表中下一单元,直到找出一个空单元或查遍全表。

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

伪随机探测再散列
di=伪随机数序列。
具体实现时,应建立一个伪随机数发生器,(如i=(i+p) % m),并给定一个随机数做起点。

例如,
已知哈希表长度m=11,哈希函数为:H(key)= key % 11,则H(47)=3,H(26)=4,H(60)=5,假设下一个关键字为69,则H(69)=3,与47冲突。
如果用线性探测再散列处理冲突,下一个哈希地址为H1=(3 + 1)% 11 = 4,仍然冲突,再找下一个哈希地址为H2=(3 + 2)% 11 = 5,还是冲突,继续找下一个哈希地址为H3=(3 + 3)% 11 = 6,此时不再冲突,将69填入5号单元。
如果用二次探测再散列处理冲突,下一个哈希地址为H1=(3 + 12)% 11 = 4,仍然冲突,再找下一个哈希地址为H2=(3 – 12)% 11 = 2,此时不再冲突,将69填入2号单元。
如果用伪随机探测再散列处理冲突,且伪随机数序列为:2,5,9,………,则下一个哈希地址为H1=(3 + 2)% 11 = 5,仍然冲突,再找下一个哈希地址为H2=(3 + 5)% 11 = 8,此时不再冲突,将69填入8号单元。

链地址法
就是当发生hash冲突的时候,就使用一个链表来存放这些值。也就是将hash算法得到的值相同的key对应的value放在一个链表中。
Java中的hashmap中就是使用了这个方法。

编程小号
上一篇 2025-02-06 09:06
下一篇 2025-03-11 09:01

相关推荐

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/hz/135591.html