HashMap源码中的位运算符&详解

网友投稿 687 2023-05-09

HashMap源码中的位运算符&详解

HashMap源码中的位运算符&详解

引言

最近在读HashMap源码的时候,发现在很多运算符替代常规运算符的现象。比如说用hash & (table.length-1) 来替代取模运算hash&(table.length);用if((e.hash & oldCap) == 0)判断扩容后元素的位置等等。

1.取模运算符%底层原理

​总所周知,位运算&直接对二进制进行运算;而对于取模运算符%:a % b 相当于 a - a / b * b,底层实际上是除法器,究其根源也是由底层的减法和加法共同完成。所以其运行效率要远远小于位运算符&。

2.位运算符&如何实现取模功能

​我们先来看两个例子

5 & 7                9 & 7

0101----5&http://nbsp;           1001----9

&                         &

0111----7             0111----7

=                          =

0101----5             0001----1

​确实,hash & (table.length-1) 来实现了运算hash&(table.length)从二进制的角度来说,5%8实际上是将二进制5(0101)向右移动3位,而与7(0111)进行与运算实际上就是将位数向右移动三位。不过要注意的是,只有当length的长度为2^n时,结论才成立。

3.位运算符&在if((e.hash & oldCap) == 0)判断扩容后元素的位置

​这是出自于JDK1.8中扩容函数resize()的一行代码,用于判断在扩容后原数组中的元素是否需要移动。举个例子:

0001 1010----26                0000 1010----10                

&      &iVyfvwLRnbsp;                       &

0001 0000----16                0001 0000----16

=                              =

0001 0000----非0               0000 0000-----0

利用hash值和oldCap进行与运算,很明显当结果大于0代表hash值大于oldCap时,下标位置变为旧数组的下标j + oldCap;若结果等于0代表小于oldCap,则下标位置不变。相比于JDK1.7重新计算每个元素的哈希值,通过高位运算(e.hash & oldCap)无疑效率更高。

版权声明:本文内容由网络用户投稿,版权归原作者所有,本站不拥有其著作权,亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容,请联系我们jiasou666@gmail.com 处理,核实后本网站将在24小时内删除侵权内容。

上一篇:MyBatis 添加元数据自定义元素标签的实现代码
下一篇:Maven打包jar包没有主属性问题解决方案
相关文章

 发表评论

暂时没有评论,来抢沙发吧~