JDK源码阅读笔记--HashMap(tableSizeFor)

tableSizeFor的功能是返回大于输入参数且最近的2的整数次幂的数，比如5则返回8.
java8中的源码是

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-1是为了保证如果cap正好是2的整数次幂，则也可以保证正确的结果。
右移1位保证最高2位是11
再右移2位保证最高4位是1111
再右移4位保证最高8位是11111111
....
最后判断范围并加一正好是2的整数次幂

java12中的方法做了优化，具体哪个版本改的没有调查

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

numberOfLeadingZeros的返回值是最高位前面0的个数。负数返回0，0返回32。

@HotSpotIntrinsicCandidate
    public static int numberOfLeadingZeros(int i) {
        // HD, Count leading 0's
        if (i <= 0)
            return i == 0 ? 32 : 0;
        int n = 31;
        if (i >= 1 << 16) { n -= 16; i >>>= 16; }
        if (i >= 1 <<  8) { n -=  8; i >>>=  8; }
        if (i >= 1 <<  4) { n -=  4; i >>>=  4; }
        if (i >= 1 <<  2) { n -=  2; i >>>=  2; }
        return n - (i >>> 1);
    }

这个也做了优化，但是还是用折半计算的方法

n=31是因为最后一步移动一位，如果i=1,结果应该是31，则若使n-1>>1位31则n=31，这样减少一步比较（i>=1<<1）即跟0比较。
折半计算每次移动一半的位数，如第一次与1左移16位比较，如果大于则n减16，依此类推。

虽然用了numberOfLeadingZeros，但是位移动的次数没有变化，效率应该差不多。HotSpotIntrinsicCandidate或许可以直接调用CPU指令提高效率。