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中就是使用了这个方法。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/184350.html原文链接:https://javaforall.cn
相关文章
- Mac常见疑难问题汇总以及解决方法详解
- Mac鼠标光标消失怎么办?苹果电脑鼠标指针不显示的解决方法
- 宝塔运行Django Admin项目错误解决方法
- 开发时遇到监听的事件处理机制和SoundPool播放音效解决方法以及外部类的使用【Android】
- SQL Server阻止保存修改表结构的解决方法
- Hibernate通过SQL查询常量时只返回第一个字符解决方法详解编程语言
- Linux下域名解析实现方法(linux域名解析)
- 解决MySQL数据显示乱码的方法(mysql数据显示乱码)
- 解决方法大全:Linux 服务启动失败如何解决?(linux服务启动失败)
- 了解Oracle ASM文件的存储和管理方法(oracleasm文件)
- 解决MySQL无法编辑的问题有效方法一览(mysql 不能编辑)
- MySQL无法正常关闭解决方法(mysql不能正常关闭)
- MySQL数据无法提交解决方法(mysql不能提交数据)
- 查看Oracle中所有表的方法(oracle中查所有表)
- mysql连接过多和死掉以及拒绝服务的解决方法
- asp.net程序在调式和发布之间图片路径问题的解决方法
- jquery下动态显示jqGrid以及jqGrid的属性设置容易出现问题的解决方法
- VC6.0打开文件以及向工程中添加文件时程序崩溃自动退出解决方法
- .net框架(framework)版本不匹配的解决方法
- JS跳转页面延迟2种方法
- c语言中用字符串数组显示菜单的解决方法
- php读取csv文件后,uft8bom导致在页面上显示出现问题的解决方法
- debian安装后sudo命令不能用的解决方法
- Json序列化和反序列化方法解析
- MSSQL自动重建出现碎片的索引的方法分享
- iis6和iis7限制上传文件(请求头)大小以及不支持FSO解决方法
- MYSQL设置触发器权限问题的解决方法
- JavaScript中实现异步编程模式的4种方法