HashMap位运算你可知一二

我们平时在写代码过程中用的位运算操作比较少,因为我们更关注于可读性而不是性能,如果为了性能而使用较多的位运算,我想我们的同事会疯掉。但在框架里位运算却非常常见,因为框架的性能是我们关注的点。下面就来一起回顾一下常见的位运算操作:

<< : 左移运算符,num << 1,相当于num乘以2  低位补0
>> : 表示右移,如果该数为正,则高位补 0,若为负数,则高位补 1。
>>> : 表示无符号右移,也叫逻辑右移,即若该数为正,则高位补 0,而若该数为负数,则右移后高位同样补 0。
 % : 模运算 取余
^ :   位异或 第一个操作数的的第n位于第二个操作数的第n位相反,那么结果的第n为也为1,否则为0
 & : 与运算 第一个操作数的的第n位于第二个操作数的第n位如果都是1,那么结果的第n为也为1,否则为0
 | :  或运算 第一个操作数的的第n位于第二个操作数的第n位 只要有一个是1,那么结果的第n为也为1,否则为0
 ~ : 非运算 操作数的第n位为1,那么结果的第n位为0,反之,也就是取反运算(一元操作符:只操作一个数)
复制代码

HashMap的hash函数算法

static final int hash(Object key) {
   int h;
   return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

复制代码

此时我们心中会有两个疑惑:

  • 为什么要无符号右移 16 位后做异或运算
  • key 本身的 hashCode 直接拿来用不行吗

来看这样一个例子:

HashMap位运算你可知一二

将 h 无符号右移 16 为相当于将高区 16 位移动到了低区的 16 位,再与原 hashcode 做异或运算,可以看作是 将高低位二进制特征混合起来

从上图中可以看出,高位的 16 位与原 hashcode 相比没有发生变化,低位的 16 位发生了变化。

上面的 (h = key.hashCode ()) ^ (h >>> 16) 进行运算后,可以把高区与低区的二进制特征混合到低区,那么为什么要这么做呢?

我们要知道,上面计算出来的hashcode值接下来要参与到hashmap中数组槽位的计算,其计算公式是:(n – 1) & hash,现在假设数组槽位大小是16,那么槽位计算过程如下:

HashMap位运算你可知一二

观察可以看出,如果我们不做刚才移位异或运算,那么在计算槽位时将丢失高区特征。也许你可能会说,即使丢失了高区特征,不同 hashcode 也可以计算出不同的槽位来,但是细想当两个哈希码很接近时,那么这高区的一点点差异就可能导致一次哈希碰撞,所以这也是将性能做到极致的一种体现。

为什么要采用异或运算

异或运算能更好的保留各部分的特征,如果采用 & 运算计算出来的值会向 1 靠拢,采用 | 运算计算出来的值会向 0 靠拢。

为什么槽位数必须使用 2^n

这里假设槽位数不是 16,而是 17,那么槽位计算公式就变成:(17 – 1) & hash。

HashMap位运算你可知一二

可以看出计算结果将会大大趋同,hashcode 参加 & 运算后被更多位的 0 屏蔽,计算结果只剩下两种,分别是0 和 16,这对于 hashmap 来说是一种灾难。

总结

HashMap当中运用了很多精巧的位运算操作,这对于提高性能有很大帮助,更多的,很多的优化点,最终目的还是为了让哈希后的结果更均匀的分部,减少哈希碰撞,提升 hashmap 的运行效率。

参考文章

[1] https://zhuanlan.zhihu.com/p/149583558
[2] https://juejin.im/entry/5e1a960d5188254c257c38e5
[3] https://www.jianshu.com/p/eb9ab4211163
复制代码

原文 

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

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

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

转载请注明原文出处:Harries Blog™ » HashMap位运算你可知一二

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

评论 0

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