HashMap中tableSizeFor()计算容量方法

当创建HashMap时，如果调用了一个或两个参数的构造方法，传入的容量参数会会被传递到 tableSizeFor(int cap)方法中。该方法返回大于等于该容量的最小2的n次方数。在JDK1.8和JDK11中有不同的实现。
对于2的n次方数，其二进制高位为1，后面为n个0，如：2^1 = 0010、2^2 = 0100、2^3 = 1000。

JDK1.8

一般地，要求大于等于一个int型数的最小2的n次方数，只需要将该int型数的二进制数从第一次出现1的高位到低位全置为1，最后结果再加1即可。如0000 1010 -> 0000 1111 -> 0001 0000. 即可求得大于10的最小2的n次方数 10 -> 15 -> 16。
tableSizeFor(int cap)正是这种做法：

 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;
    }

对于任意int型数n，例如要将0000 1xxx .... xxxx （假设 x 可同时为 0 或 1）变为 0000 1111 .... 1111。我们称第一个1会出现的位置是第一位，n右移一位，再按位或运算，即可保证前两位为1，即11xx .... xxxx，
接着n右移两位，再按位或运算，即可保证前四位为1，即1111 .... xxxx，以此类推，一共右移了31位，这就保证了在int类型整数范围内，从出现1的高位起，到最后一位，全部置为了1。
如果该数恰好是2的n次方数了。怎么办呢？这就是cap - 1的意义所在，如，16-1 = 15= 1111，右移之后再按位或运算，
得到1111，返回1111+1 = 1 0000。

缺点

当然这种算法的不足之处在于，若cap很小，如9 = 1001，执行到n |= n >>> 2 就能拿到结果，但这里要把上面依次执行完，虽然结果仍然没错，但
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
这三行代码执行的毫无意义。这种情况在JDK 11中已经得到解决，采用的是另一个算法。

JDK 11中的做法。

static final int tableSizeFor(int cap) {
    int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);
    return n < 0 ? 1 : (n >= 1073741824 ? 1073741824 : n + 1);
}

 public static int numberOfLeadingZeros(int i) {
    if (i <= 0) {
        return i == 0 ? 32 : 0;
    } else {
        int n = 31;
        if (i >= 65536) {
            n -= 16;
            i >>>= 16;
        }

        if (i >= 256) {
            n -= 8;
            i >>>= 8;
        }

        if (i >= 16) {
            n -= 4;
            i >>>= 4;
        }

        if (i >= 4) {
            n -= 2;
            i >>>= 2;
        }

        return n - (i >>> 1);
    }
}

它是先计算出cap（其实是cap-1）二进制数前面有多少个0，再将 -1 右移多少位。
达到的效果和
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
是一样的。

为什么是将-1右移呢？因为-1长这样
-1二进制：
1111 1111 1111 1111 1111 1111 1111 1111

numberOfLeadingZeros(int i)方法

int 四个字节共32位，首位是符号位， if (i <= 0) 做完边界判断后，0< i <MAX_VALUE，共31位可移动。
把cap和2^16次方作比较，
2^16 = 65536
0000 0000 0000 0001 0000 0000 0000 0000
如果>=2^16，那么，-1最多右移31 - 16 = 15位，即得到2^17-1
0000 0000 0000 0001 1111 1111 1111 1111
可是，需要右移15位吗？不一定，所以还需要比较高16位的大小。
将cap右移16位，cap的高16位就移到了低16位，再将此时的i和2^8比较
2^8 = 256
0000 0000 0000 0000 0000 0001 0000 0000
如果i>=2^8，那么，这时候-1最多右移15-8 = 7位。
以此类推，和2^4作比较，如果>= 2^{4，-1最多右移7-4=3位，和2}2作比较，如果>=2^2，-1最多右移3-2 = 1位。最后return n - (i >>> 1)
其实，等价于
if (i >= 2) {
n -= 1;
}
return n;

至此，算出需要右移的位数。
将-1右移后，后面和JDK1.8一样了。