HashMap之tableSizeFor方法

tableSizeFor方法

HashMap内部的数组大小强制为2的幂次方，这样在根据key的hash值通过按位与非常效率的找到key在数组中的位置。

该方法返回大于输入数字的最相近2幂次方，方法原理：将输入数字的二进制表示中的0全部改为1（不包括补位的0），这样n+1之后就得到了2的幂次方

• n = cap - 1，当输入的数字即是2的幂，期望的返回值就是自身，如果不减去1会返回该数的2倍数
• 传入的肯定是一个非0的数字，那么该数字的二进制表示中肯定至少有一个1，将该1右移一位按位或，这样就至少拥有了两个1
• 然后再右移两位取或，就至少有了4个1，后面以此类推
• int是32位的整数，只需要操作到右移16即可
• 在操作完之后取得一个除补位以外全是1的数字，如果不是负数或者超过了最大容量，+1即可

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