HashMap源码解析系列(一)之HashMap#hash(Object key)方法

1.什么是哈希碰撞
2.为什么会有哈希碰撞
3.HashMap如何解决哈希碰撞
4.HashMap的hashCode为什么要右移16位
先来说说理论的东西也就是1和2的问题, 两个不同的值在取哈希值的时候相同称之为哈希碰撞
这句话就概括了1和2的问题
那HashMap如何解决哈希碰撞
我们先来看一个例子0011 1000 和 0001 1000 在对 0000 1111(等于15 假设现在HashMap的容量为16)进行按位与运算后的结果 注:(^)异或运算就是两个都为1的时候为1否则为0

//0011 1000对0000 1111做异或运算
0011 1000
0000 1111 ^
0000 1000 //运算结果
复制代码
//0011 1000对0000 1111做异或运算
0001 1000
0000 1111 ^
0000 1000 //运算结果
复制代码

两个不相同的值对数组长度-1进行按位与运算后得到的结果相同这就发生了哈希碰撞,而HashMap对hashCode进行了右移16为如:

0111 1111 1111 1111 1111 1111 1111 1111
0000 0000 0000 0000 0011 1111 1111 1111 >>> 16
复制代码

就是将原数据的高16位都变成0而低16位替换成原先数据的高16位,那为什么要这么做呢,其实就是要进行扰动计算,防止不同hashCode的高位不同但低位相同导致的hash冲突。简单点说,就是为了把高位的特征和低位的特征组合起来,降低哈希冲突的概率,也就是说,尽量做到任何一位的变化都能对最终得到的结果产生影响。
说这个之前我么就得先了解HashMap中根据key获取数组索引的另外一个算法**根据hash算出的code对数组长度进行与运算(取摸)**这代码在1.8之后在putVal方法中的第630行

if ((p = tab[i = (n - 1) & hash]) == null)
复制代码

其中 i = (n – 1) & hash
就是根据key的值来确定Node在table中的索引。
如果我们直接使用key的hashCode对数组长度-1进行取摸的话比如:以初始长度16为例,16-1=15 。二进制表示是00000000 00000000 00001111

1010 0101 1100 0100 0010 0101
0000 0000 0000 0000 0000 1111   &
-----------------------------------
0000 0000 0000 0000 0000 0101    //高位全部归零,只保留末四位
复制代码

但这时候问题就来了,这样就算我的散列值分布再松散,要是只取最后几位的话,碰撞也会很严重。更要命的是如果散列本身做得不好,分布上成等差数列的漏洞,恰好使最后几个低位呈现规律性重复,就会出现严重的哈希碰撞,其带来的结果就是在table容器中某个索引的链表特别长,而有些索引根本就没有几个甚至都没有数据的情况,这时候哈希值向右移16为的价值就体现出来了
先来了解位异或运算(^)
运算规则是:两个数转为二进制,然后从高位开始比较,如果相同则为0,不相同则为1。
位与运算符(&)
运算规则:两个数都转为二进制,然后从高位开始比较,如果两个数都为1则为1,否则为0。

1111 1111 1111 1111 1111 0000 1110 1010
0000 0000 0000 0000 1111 1111 1111 1111  >>> 16 //右移16位
-------------------------------------------------------------
1111 1111 1111 1111 0000 1111 0001 0101  ^ //位异或运算的结果
0000 0000 0000 0000 0000 0000 0000 1111 &  // //对15进行取摸(位与运算运算)
-------------------------------------------------------------
0000 0000 0000 0000 0000 0000 0000 0101 //其10进制5
复制代码

右位移16位,正好是32bit的一半,自己的高半区和低半区做异或,就是为了混合原始哈希码的高位和低位,以此来加大低位的随机性。而且混合后的低位掺杂了高位的部分特征,这样高位的信息也被变相保留下来。
那么,为什么可以使用位运算(&)来实现取模运算(%)呢?

这实现的原理如下:
X % 2^n = X & (2^n – 1)
2^n表示2的n次方,也就是说,一个数对2^n取模 == 一个数和(2^n – 1)做按位与运算 。
假设n为3,则2^3 = 8,表示成2进制就是1000。2^3 -1 = 7 ,即0111。
此时X & (2^3 – 1) 就相当于取X的2进制的最后三位数。
从2进制角度来看,X / 8相当于 X >> 3,即把X右移3位,此时得到了X / 8的商,而被移掉的部分(后三位),则是X % 8,也就是余数。
复制代码

而这也就解释了上一篇中HashMap#tableSizeFor()中的初始值长度threshold为什么要算出是2的次方数,初始值是16,之后每次扩充为原来的2倍。因为只要保证length的长度是 2^n
的话,就可以实现取模运算了,当然这只是一个用法,其实初始值长度threshold=2的次方数在之后的HashMap#resize()方法(初始化容器、扩容)也有一些奇妙的运用,我们下一篇章再分析吧

原文 

https://juejin.im/post/5efea690e51d4534714aa670

本站部分文章源于互联网,本着传播知识、有益学习和研究的目的进行的转载,为网友免费提供。如有著作权人或出版方提出异议,本站将立即删除。如果您对文章转载有任何疑问请告之我们,以便我们及时纠正。

PS:推荐一个微信公众号: askHarries 或者qq群:474807195,里面会分享一些资深架构师录制的视频录像:有Spring,MyBatis,Netty源码分析,高并发、高性能、分布式、微服务架构的原理,JVM性能优化这些成为架构师必备的知识体系。还能领取免费的学习资源,目前受益良多

转载请注明原文出处:Harries Blog™ » HashMap源码解析系列(一)之HashMap#hash(Object key)方法

赞 (0)
分享到:更多 ()

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址