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

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

[TOC]

1. 为什么要保证 capacity 是 2 的次幂呢？

（1）在 get 方法实现中，实际上是匹配链表中的 Node[] tab 中的数据。

(n - 1) & hash 实际上是计算出 key 在 tab 中索引位置，当 key 的 hash 没有冲突时，key 在 HashMap 存储的位置就是匹配的 node 中的第一个节点。如果 hash 有冲突，就会在 node 里面节点中查询，直至匹配到相等的 key。

（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 决定桶的索引呢？

（1）key 具体应该在哪个桶中，肯定要和 key 挂钩的，HashMap 顾名思义就是通过 hash 算法高效的把存储的数据查询出来，所以 HashMap 的所有 get 和 set 的操作都和 hash 相关。

（2）既然是通过 hash 的方式，那么不可避免的会出现 hash 冲突的场景。hash 冲突就是指 2 个 key 通过 hash 算法得出的哈希值是相等的。hash 冲突是不可避免的，所以如何尽量避免 hash 冲突，或者在 hash 冲突时如何高效定位到数据的真实存储位置就是 HashMap 中最核心的部分。

（3）首先要提的一点是 HashMap 中 capacity 可以在构造函数中指定，如果不指定默认是 2 的 (n = 4) 次方，即 16。

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

（4）HashMap 中的 hash 也做了比较特别的处理，(h = key.hashCode()) ^ (h >>> 16)。

先获得 key 的 hashCode 的值 h，然后 h 和 h 右移 16 位 做异或运算。
实质上是把一个数的低 16 位与他的高 16 位做异或运算，因为在前面 (n - 1) & hash 的计算中，hash 变量只有末 x 位会参与到运算。使高 16 位也参与到 hash 的运算能减少冲突。

例如 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);
}

3.capacity 永远都是 2 次幂，那么如果我们指定 initialCapacity 不为 2 次幂时呢，是不是就破坏了这个规则？

答案是不会的，HashMap 的 tableSizeFor 方法做了处理，能保证 n 永远都是 2 次幂。

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