首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >哈希碰撞是什么,怎么解决

哈希碰撞是什么,怎么解决

作者头像
PhoenixZheng
发布2018-08-07 16:18:49
2.2K0
发布2018-08-07 16:18:49
举报

Hash是一种校验方法, 其中应用最广为人知的就是 HashMap。 当然Hash算法并不完美,有可能两个不同的原始值在经过哈希运算后得到同样的结果, 这样就是哈希碰撞。

哈希碰撞有几种解决办法 · 开放定址法 · 链地址

链地址法

链地址法其实就是HashMap中用的策略。 原理是在HashMap中同样哈希值的位置以一串链表存储起来数据, 把多个原始值不同而哈希结果相同的数据以链表存储起来。

开放定址法

当发生地址冲突时,按照某种方法继续探测哈希表中的其他存储单元,直到找到空位置为止。 用方程来表达的话是这样子,

H i ( key ) = ( H ( key )+ d i ) mod m ( i = 1,2,…… , k ( k ≤ m – 1))

m 是哈希表的长度。 举一个实际的例子, 一个哈希函数是 H ( key ) = key mod 7 , 哈希表长度为 7, 关键字序列( 32 , 13 , 49 , 55 , 22 , 38 , 21 ) 如果以线性探测再散列来生成哈希表的话, 过程是这样的

32 % 7 = 4 ; 13 % 7 = 6 ; 49 % 7 = 0 ; 55 % 7 = 6 发生冲突,下一个存储地址( 6 + 1 )% 7 = 0 ,仍然发生冲突,再下一个存储地址:( 6 + 2 )% 7 = 1 未发生冲突,可以存入。 22 % 7 = 1 发生冲突,下一个存储地址是:( 1 + 1 )% 7 = 2 未发生冲突; 38 % 7 = 3 ; 21 % 7 = 0 发生冲突,按照上面方法继续探测直至空间 5 ,不发生冲突

所得到的哈希表对应存储位置:

下标: 0 1 2 3 4 5 6 49 55 22 38 32 21 13

本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2018-05-22,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 Android每日一讲 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 链地址法
  • 开放定址法
相关产品与服务
对象存储
对象存储(Cloud Object Storage,COS)是由腾讯云推出的无目录层次结构、无数据格式限制,可容纳海量数据且支持 HTTP/HTTPS 协议访问的分布式存储服务。腾讯云 COS 的存储桶空间无容量上限,无需分区管理,适用于 CDN 数据分发、数据万象处理或大数据计算与分析的数据湖等多种场景。
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档