专栏首页做不甩锅的后端解决哈希冲突的常用方法分析

解决哈希冲突的常用方法分析

文章目录

1.基本概念

哈希算法:根据设定的哈希函数H(key)和处理冲突方法将一组关键字映象到一个有限的地址区间上的算法。也称为散列算法、杂凑算法。 哈希表:数据经过哈希算法之后得到的集合。这样关键字和数据在集合中的位置存在一定的关系,可以根据这种关系快速查询。 非哈希表:与哈希表相对应,集合中的 数据和其存放位置没任何关联关系的集合。

由此可见,哈希算法是一种特殊的算法,能将任意数据散列后映射到有限的空间上,通常计算机软件中用作快速查找或加密使用。

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

2.解决哈希冲突的方法

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

2.1 开放定址法

从发生冲突的那个单元起,按照一定的次序,从哈希表中找到一个空闲的单元。然后把发生冲突的元素存入到该单元的一种方法。开放定址法需要的表长度要大于等于所需要存放的元素。 在开放定址法中解决冲突的方法有:线行探查法、平方探查法、双散列函数探查法。 开放定址法的缺点在于删除元素的时候不能真的删除,否则会引起查找错误,只能做一个特殊标记。只到有下个元素插入才能真正删除该元素。

2.1.1 线行探查法

线行探查法是开放定址法中最简单的冲突处理方法,它从发生冲突的单元起,依次判断下一个单元是否为空,当达到最后一个单元时,再从表首依次判断。直到碰到空闲的单元或者探查完全部单元为止。 可以参考csdn上flash对该方法的演示: http://student.zjzk.cn/course_ware/data_structure/web/flash/cz/kfdzh.swf

2.1.2 平方探查法

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

2.1.3 双散列函数探查法

这种方法使用两个散列函数hl和h2。其中hl和前面的h一样,以关键字为自变量,产生一个0至m—l之间的数作为散列地址;h2也以关键字为自变量,产生一个l至m—1之间的、并和m互素的数(即m不能被该数整除)作为探查序列的地址增量(即步长),探查序列的步长值是固定值l;对于平方探查法,探查序列的步长值是探查次数i的两倍减l;对于双散列函数探查法,其探查序列的步长值是同一关键字的另一散列函数的值。

2.2 链地址法(拉链法)

链接地址法的思路是将哈希值相同的元素构成一个同义词的单链表,并将单链表的头指针存放在哈希表的第i个单元中,查找、插入和删除主要在同义词链表中进行。链表法适用于经常进行插入和删除的情况。 如下一组数字,(32、40、36、53、16、46、71、27、42、24、49、64)哈希表长度为13,哈希函数为H(key)=key%13,则链表法结果如下:

0       
1  -> 40 -> 27 -> 53 
2
3  -> 16 -> 42
4
5
6  -> 32 -> 71
7  -> 46
8
9
10 -> 36 -> 49
11 -> 24
12 -> 64

注:在java中,链接地址法也是HashMap解决哈希冲突的方法之一,jdk1.7完全采用单链表来存储同义词,jdk1.8则采用了一种混合模式,对于链表长度大于8的,会转换为红黑树存储。

2.3 再哈希法

就是同时构造多个不同的哈希函数: Hi = RHi(key) i= 1,2,3 … k; 当H1 = RH1(key) 发生冲突时,再用H2 = RH2(key) 进行计算,直到冲突不再产生,这种方法不易产生聚集,但是增加了计算时间。

2.4 建立公共溢出区

将哈希表分为公共表和溢出表,当溢出发生时,将所有溢出数据统一放到溢出区。

本文参与 腾讯云自媒体分享计划 ,欢迎热爱写作的你一起参与!
本文分享自作者个人站点/博客:https://blog.csdn.net/dhaibo1986复制
如有侵权,请联系 cloudcommunity@tencent.com 删除。
登录 后参与评论
0 条评论

相关文章

  • 哈希冲突常用解决方法

    哈希算法:根据设定的哈希函数H(key)和处理冲突方法将一组关键字映象到一个有限的地址区间上的算法。也称为散列算法、杂凑算法。

    Dabelv
  • 解决哈希冲突的常用方法有哪些?

    基本思想是:当关键字key的哈希地址p=H(key)出现冲突时,以p为基础,产生另一个哈 希地址p1,如果p1仍然冲突,再以p为基础,产生另一个哈希地址p2,...

    葆宁
  • 解决哈希冲突的方法「建议收藏」

    在实际的应用中,选取合适的哈希函数可减少冲突,但冲突是不可避免的。所以我就想给大家说几种解决哈希冲突的方法啦~

    全栈程序员站长
  • 哈希冲突的产生原因及解决方法

    ‍一、哈希冲突的产生原因 哈希是通过对数据进行再压缩,提高效率的一种解决方法。但由于通过哈希函数产生的哈希值是有限的,而数据可能比较多,导致经过哈希函数处理后仍...

    码农编程进阶笔记
  • jar包冲突常用的解决方法

    转载自https://www.cnblogs.com/xiayangy/p/4038347.html

    allsmallpig
  • MASS幸运哈希游戏系统开发丨冲突解决方法(代码分析)

    设关键字序列为 47 , 7 , 29 , 11 , 16 , 92 , 22 , 8 , 3 , 50 , 37 , 89 , 94 , 21 47, 7, ...

    KFZ433
  • 哈希表基本概念介绍及哈希冲突的处理方法(附源码)

      哈希表(散列表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这...

    嵌入式与Linux那些事
  • 解决hash冲突的几种方法_hashmap hash冲突

    hash函数 首先来说hash函数,java中对象都已一个hashCode() 方法,那为什么还需要hash函数呢?hashCode是在jdk中是有符号...

    全栈程序员站长
  • 你还应该知道的哈希冲突解决策略

    哈希是一种通过对数据进行压缩, 从而提高效率的一种解决方法,但由于哈希函数有限,数据增大等缘故,哈希冲突成为数据有效压缩的一个难题。本文主要介绍哈希冲突、解决方...

    2020labs小助手
  • Android嵌套滑动冲突的解决方法

    android在嵌套滑动的时候会产生滑动冲突。之前我也碰到,但是以前的笔记本丢失了,所以只能重新再写一章。

    砸漏
  • Algorithms_算法专项_Hash算法的原理&哈希冲突的解决办法

    数组下标: 初始化一个能够容纳最大数据的int数组,数组中的值默认为0 ,然后把出现的这n个数的下标置为1,判断某个数是否存在—>直接判断这个数在数组中对应的下...

    小小工匠
  • PhpStorm快速解决Git合并(Merge)冲突的方法

    PhpStorm 是我非常喜欢的一款 IDE 编辑器,一般在遇到冲突时,我都是直接干代码。

    德顺
  • AndroidStudio Gradle 解决包冲突的方法——开发记录

    方案二、去掉部分冲突 例如去除 com.github.niorgai:StatusBarCompat:2.1.3 引用的 com.android.suppor...

    紫兮木溪
  • 散列表(二):冲突处理的方法之链地址法的实现(哈希查找)

    首先需要澄清的一点是,这里讲的是hash table/hash map ,即数据项所存储的表要用数组来实现。 一、链地址法 这种基本思想:将所有哈希地址为i 的...

    s1mba
  • 解决transition动画与display冲突的几种方法

    如demo(如果没有显示,请查看源地址http://jsfiddle.net/ihardcoder/HNduT/2/)所示,基本的效果是在点击“Translat...

    寒月十八
  • git的常用命令及工作中冲突问题解决方法

    信息填写好了以后,在个人输入的路径(注意一定要写全路径)下就可以看到刚才命令生成的2个文件了

    _kyle
  • django 渲染模板与 vue 的 {{ }} 冲突解决方法

    如果不可避免的在同一个页面里既有 django 渲染又有 vue 渲染的部分,可有 2 种方式解决

    kirin

扫码关注腾讯云开发者

领取腾讯云代金券