java8 HashMap之tableSizeFor
在1.8的HashMap中,有一个算法,它的功能是(不考虑大于最大容量的情况) 返回大于输入参数且最近的2的整数次幂的数
|
|
网上也看了一些别人的分析,整理如下:
n |= n »> 1;也等价于 n = n | (n »>1);
我们假设 cap = 65;
|
|
再往下执行的话都是 n 的值都为1111111 即127 最后一步,就是一个嵌套的三元运算 当n < 0,就返回1,否则继续判断n是否超过最大容量,没超过就返回 n + 1 即 n= 128 对比我们的输入值 –> 大于65且最近的2的整数次幂的数 就是128
其实抛除上面这个具体的例子,整个过程可总结如下:
-
先来假设n的二进制为01xxx…xxx。接着
-
对n右移1位:001xx…xxx,再位或:011xx…xxx
-
对n右移2为:00011…xxx,再位或:01111…xxx
-
此时前面已经有四个1了,再右移4位且位或可得8个1
-
同理,有8个1,右移8位肯定会让后八位也为1。
-
综上可得,该算法让最高位的1后面的位全变为1。
-
最后再让结果n+1,即得到了2的整数次幂的值了。
这样就很清晰明了了,至于为什么最开始
-int n = cap - 1;
让cap-1再赋值给n的目的是另找到的目标值大于或等于原值。例如二进制1000,十进制数值为8。如果不对它减1而直接操作,将得到答案10000,即16。显然不是结果。减1后二进制为111,再进行操作则会得到原来的数值1000,即8。
位运算是相当高效的。