ITPub博客

首页 > 应用开发 > IT综合 > 聊天室源码开发中应对哈希冲突的解决方案

聊天室源码开发中应对哈希冲突的解决方案

IT综合 作者:云豹科技程序员 时间:2021-11-23 16:23:09 0 删除 编辑

哈希冲突的解决办法:

  • 开放地址法
  • 拉链法(链地址法)
  • 再哈希法

一、开放地址法

原理是当聊天室源码发生hash冲突时,会以当前地址为基准,然后根据寻址方法(探查寻址),去寻找下一次地址。若聊天室源码依旧发生冲突,则继续寻址,直到找到一个空的位置为止。
通用的散列函数形式为:
Hi=(H(key)+di)% m (i=1,2,…,n)
其中H(key)为哈希函数,m 为表长,di称为增量序列。增量序列的取值方式不同,相应的再散列方式也不同。

寻址方法

1. 线性探查

顺序查找表的下一个单元,直到找到一个空单元或查遍全表。
即当聊天室源码的hash值为3冲突时(假设此时hash表长度为11),利用线性探查的过程为:
H1 = (3+1)%11 = 4,此时若4依旧冲突,则再hash,即
H2 = (3+2)%11 = 5 … 通过这种线性增长增量系列,直到找到空的位置为止。

2. 二次探查

这种方法的特点是,当聊天室源码出现哈希冲突时,在表的左右进行跳跃探测,比较灵活。
此时di = 1^2, -1^2, 2^2, -2^2 …
假设当hash值为3冲突时(假设此时hash表长度为11),利用二次探查的过程为:
H1 = (3+1^2)%11 = 4,此时若4依旧冲突,则再hash,即
H2 = (3+(-1)^2)%11 = 2 …
通过该方法直到找到空位置为止。

3. 伪随机探测

这种方法即是产生一些随机系列值,并给定随机数作为起点。
假设当聊天室源码的hash值为3冲突时(假设此时hash表长度为11),利用伪随机探测的过程为:
假设产生的随机系列为2,5,9 …,则
H1 = (3+2)%11 = 5
H2 = (3+5)%11 = 8
通过该方法直到找到空位置为止。

二、拉链法

拉链法应用于hashMap和hashSet中,当聊天室源码产生hash冲突时,则会以该hash冲突的位置构建一个单链表(即将所有哈希地址为i的元素构成一个称为同义词链的单链表),并将单链表的头指针存储在聊天室源码哈希表的第i个位置中。
链地址法适用于经常进行插入和删除的情况。

三、再哈希法

指聊天室源码使用哈希函数计算散列位置时,当不同散列出现同一位置时就再次使用哈希,直到不冲突。

本文转载自网络,转载仅为分享干货知识,如有侵权欢迎联系云豹科技进行删除处理
原文链接:


来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/69996194/viewspace-2843685/,如需转载,请注明出处,否则将追究法律责任。

请登录后发表评论 登录
全部评论

注册时间:2021-03-10

  • 博文量
    308
  • 访问量
    90062