什么是Hash碰撞 |
您所在的位置：网站首页 › hashmap的碰撞是怎么产生的 › 什么是Hash碰撞 |
|
Hash是一种校验方法， 其中应用最广为人知的就是 HashMap。 当然Hash算法并不完美，有可能两个不同的原始值在经过哈希运算后得到同样的结果，这样就是哈希碰撞。 哈希碰撞有几种解决办法 · 开放定址法 · 链地址链地址法 链地址法其实就是HashMap中用的策略。 原理是在HashMap中同样哈希值的位置以一串链表存储起来数据， 把多个原始值不同而哈希结果相同的数据以链表存储起来。 Java编程基础——哈希碰撞是什么，怎么解决 开放定址法 当发生地址冲突时，按照某种方法继续探测哈希表中的其他存储单元，直到找到空位置为止。 用方程来表达的话是这样子， 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 13Java编程基础——哈希碰撞是什么，怎么解决 本文仅代表作者个人观点，不代表巨推链平台发声，对文章观点有疑义请先联系作者本人进行修改，若内容非法请联系平台管理员，邮箱[email protected]。更多区块链资讯，请到百万区块链发烧友聚集平台巨推链www.jutuilian.com学习区块链技术请到巨推学院www.jutuiedu.com |
今日新闻 |
推荐新闻 |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |