ConcurrentHashMap源码解读-算法部分

tableSizeFor

private static final int tableSizeFor(int c) {
       int n = c - 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;
   }

该算法相当奇妙，目的是输入一个数字c，然后返回离它最近的且值大于它的2的n次幂，例如输入7，返回8，输入123，返回128。

首先定义一个变量n为c-1，至于为什么为c-1，之后会说到。

我们输入c=13来带入计算一下

1. n = c-1    //此时n =  12，二进制为1100
2. n |= n >>> 1; n >>> 1，也就是n右移一位，得到0110，然后再与1100或运算，得到1110，此时n=1110；
3. n |= n >>> 2; 这里n右移两位，得到0011，然后或运算得到1111；到这里n已经全为1了，不管怎么或运算，都会是1111。因此下面的几个结果都是1111
4. n |= n >>> 4;
5. n |= n >>> 8;
6  n |= n >>> 16;
7. 这里进行计算，如果n大于MAXIMUM_CAPACITY，返回MAXIMUM_CAPACITY，否则返回n+1，n目前的值是1111，是奇数，而我们要得到的是2的n次方，因此需要加一计算，得到想要的结果

这里我们可以回头看上面的第一步，n = c-1，如果不执行c-1的话，我们加入c为16，那么二进制就是10000，经过一番操作之后，会得到最后的n为11111，然后加一就会变成100000，也就是32，而理论结果应该是16。

对于一个传进来的非0数字，从第一个1开始，右移一位，然后或运算，相当于第一位和第二位都变成了1，然后右移两位，变成了第一二三四位都变成了1，依次类推，一直右移1+2+4+8+16位，也就是最大右移了31位，最终再加一，就是2的32位