HashMap 容量为什么总是为 2 的次幂？

HashMap是根据key的hash值决策key放入到哪个桶（bucket）中，通过 tab=[(n - 1) & hash] 公式计算得出，其中tab是一个哈希表。

2）因为 n 永远是2的次幂，所以 n-1 通过 二进制表示，永远都是尾端以连续1的形式表示（00001111，00000011）

当(n - 1) 和 hash 做与运算时，会保留hash中 后 x 位的 1

例如 00001111 & 10000011 = 00000011

这样做有2个好处

• &运算速度快，至少比%取模运算块
• 能保证 索引值 肯定在 capacity 中，不会超出数组长度
• (n - 1) & hash，当n为2次幂时，会满足一个公式：(n - 1) & hash = hash % n

2.为什么要通过 (n - 1) & hash 决定桶的索引呢？

public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

例如1000000的二进制是 

00000000 00001111 01000010 01000000 

右移16位：                     

00000000 00000000 00000000 00001111

异或                                

00000000 00001111 01000010 01001111

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

/**
 * Returns a power of two size for the given target capacity.
 */
static final int tableSizeFor(int cap) {
    //cap-1后，n的二进制最右一位肯定和cap的最右一位不同，即一个为0，一个为1，例如cap=17（00010001），n=cap-1=16（00010000）
    int n = cap - 1;
    //n = (00010000 | 00001000) = 00011000
    n |= n >>> 1;
    //n = (00011000 | 00000110) = 00011110
    n |= n >>> 2;
    //n = (00011110 | 00000001) = 00011111
    n |= n >>> 4;
    //n = (00011111 | 00000000) = 00011111
    n |= n >>> 8;
    //n = (00011111 | 00000000) = 00011111
    n |= n >>> 16;
    //n = 00011111 = 31
    //n = 31 + 1 = 32, 即最终的cap = 32 = 2 的 (n=5)次方
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

作者：Helloworld先生

https;?/blog.csdn.net/u010841296/article/details/82832166