总结:因为HashMap中查找位置采用的取模运算,而使用位运算进行取模效率更高,所以为什么HashMap的初始长度位16(2^4),每次扩容为原先的2倍(2^(n+1))。

为什么可以使用位运算(&)来实现取模运算(%)呢?这实现的原理如下:

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,也就是余数。

举个例子(不得不佩服前辈们的逻辑思维能力):

6 % 8 = 6 ,6 & 7 = 6

10 % 8 = 2 ,10 & 7 = 2

Rick  12浏览  0评论  2020-09-16

如果觉得我的文章对你有用,请随意赞赏
扫一扫支付
上一篇