金三银四精选java面试题-为什么哈希/扰动函数能降低 hash碰撞?

发布时间:2023-11-30 09:43:29
 

为什么哈希/扰动函数能降低 hash碰撞?

扰动函数本质上是一种用于降低哈希碰撞的技术。扰动函数通常将原始哈希值进行二次哈希或其他变换,使得相同的原始哈希值在经过扰动函数处理后得到的哈希值尽可能地不同。这样,即使有不同的键值产生了相同的原始哈希值,经过扰动函数处理后仍然能够得到不同的哈希值,从而减少哈希碰撞的概率。

假如 HashMap 数组的初始大小才 16,就需要用之前需要对数组的长度取模运算,得到的余数才能用来访问数组下标。

源码中模运算就是把散列值和数组长度 - 1 做一个 "与&" 操作,位运算比取余 % 运算要快

& 全为1才为1
^ 相同为0,不同为1

i = (n - 1) & hash
hash = ((h = key.hashCode()) ^ (h >>> 16))
                       
16    0000 0000 0000 0000 0000 0000 0001 0000
15    0000 0000 0000 0000 0000 0000 0000 1111
hash  0000 0000 0000 0000 0000 0000 0000 0110
&     0000 0000 0000 0000 0000 0000 0000 0110
                                    0000-1111

32    0000 0000 0000 0000 0000 0000 0010 0000
31    0000 0000 0000 0000 0000 0000 0001 1111
hash  0000 0000 0000 0000 0000 0000 0001 0110
&     0000 0000 0000 0000 0000 0000 0001 0110

31    0000 0000 0000 0000 0000 0000 0001 1111
hash  0000 0000 0000 0000 0000 0000 0000 0110
&     0000 0000 0000 0000 0000 0000 0000 0110
									00000-11111

 
上一篇 金三银四精选java面试题-HashMap的put 实现是怎样的?
下一篇 金三银四精选java面试题-HashMap 的 get 实现?

文章素材均来源于网络,如有侵权,请联系管理员删除。

标签: Java教程Java基础Java编程技巧面试题Java面试题