tableSizeFor()方法源码解析
稍微查看过HashMap源码的同学们应该都知道，该方法接收一个int类型的参数，通过一系列的位运算，返回一个大于等于该参数的最小的2的n次方。如传入9，返回16；传入16，返回16。源码如下图所示，其中>>>表示无符号右移， |=表示或运算并赋值，即 a|=b 表示 a=a|b。
/**
* Returns a power of two size for the given target capacity.
*/
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
我们以传入参数cap=257为例，257的二进制表达为100000001。
int n = cap - 1，此时n=256，即100000000n |= n >>> 1，将n与n无符号右移1位的结果进行或运算，并将结果赋值给n。此时n=110000000
n |= n >>> 2，将n与n无符号右移2位的结果进行或运算，并将结果赋值给n。此时n=111100000
n |= n >>> 4，将n与n无符号右移4位的结果进行或运算，并将结果赋值给n。此时n=111111110
n |= n >>> 8，将n与n无符号右移8位的结果进行或运算，并将结果赋值给n。此时n=111111111
n |= n >>> 16，将n与n无符号右移16位的结果进行或运算，并将结果赋值给n。此时n=111111111
(n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1因为此时
n=111111111，即511，补全高位后n=00000000 00000000 00000001 11111111，最高位为0，说明为非负数。所以最终计算结果为
n+1= 511 + 1 = 512。即2的9次方。
在这几个右移和或运算的过程中，我们发现它的目的就是将最高有效位以及后面的位都置为1，再配合最后一步的n+1使得结果变为2的n次方。
先减1再位运算的意义
大家知道为什么在这个方法的首行要进行减1操作吗int n = cap - 1？
我们先把这行代码去掉，那么该方法就如下所示：
static final int tableSizeFor(int n) {
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
如果我们传入参数n=4，即n = 4 = 100，按照上面的方法进行一系列运算后，得到的n = 111 = 7，在最后一行会再进行一次n + 1操作，得到的结果就变成了8，因此得出结论，如果不进行减1操作，那么返回的结果将是大于该参数的最小的2的n次方，这与本方法的预期结果不一致。
所以int n = cap - 1的目的就是为了避免传入的参数恰好为2的n次方而导致结果不符合预期。
