HashMap 的长度为什么必须是 2 的 n 次方

首先咱们看下 HashMap 中的源码当中那里奠定了长度是 2 的 n 次方，并且是凑近cap 这个值 最近的 2 的 n 次方

static final int tableSizeFor(int cap) {
    // 首先 cap- 1 使得 n 的最初一位和 cap 最初一位相对不一样
    int n = cap - 1;
    // 向右无符号的挪动了 1 位，并应用或运算使 n 的所有有 1 的位上全副是 1
    n |= n >>> 1;
    // 向右无符号挪动 2 位，应用或运算将低位填充为 1
    n |= n >>> 2;
    // 同理可得
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    // 曾经向右挪动多个位，最终 00011111 = 31 那么 +1 既成为了 2 的 n 次方
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

由上方代码能够看出，上方的办法是 将cap无符号的向右挪动，再启动期间，应用 | 运算保障低位全副是 1。

看起来有点简单，那咱们举个例子：

1. 首先咱们传入 cap 初始值为 17
2. 通过 int n = cap -1 也就是 17- 1 后n = 16
3. 将 n 进行如下的 位挪动和逻辑运算，最初失去n = 31
4. 返回是依据三目运算符，得值返回值是n + 1 = 32，正好是 2 的 5 次方

通过上方的容量计算，咱们曾经确定在 HashMap 中 capacity 肯定是 2 的 n 次方，那么为什么咱们必须要

• & 运算速度快，至多比 % 取模运算快

• 能保障索引值必定在 capacity 中，不会超出数组长度，(n - 1) & hash，当为 2 的 n 次方时，会满足一个公式：(n - 1) & hash = hash % n

两种运算效率差异到底有多少，这里能够间接做个测试：

public static void main(String[] args) {
    int times = Integer.MAX_VALUE;
    /* 此处计算 2^31- 1 次 9999 整数对 1024 的取模，应用的数学计算
     * 屡次执行放大工夫
     */
    long currentTimeMillis = System.currentTimeMillis();
    int a = 0;
    for (long i = 0; i < times; i++) {a = 9999 % 1024;}
    long currentTimeMillis2 = System.currentTimeMillis();
    /* 此处计算 2^31- 1 次 9999 整数对 1024 的取模，应用的位运算
     * 因为要求 hash&(n-1) 中 n 必须为 2 的 n 次方，这里取 1024
     */
    int b = 0;
    for (long i = 0; i < times; i++) {b = 9999 & (1024 - 1);
    }

    long currentTimeMillis3 = System.currentTimeMillis();
    System.out.println(a + "," + b);// 最初的后果应该是一样的
    System.out.println("数学计算耗时:" + (currentTimeMillis2 - currentTimeMillis));// 1839ms
    System.out.println("位运算耗时:" + (currentTimeMillis3 - currentTimeMillis2));// 852ms
}

那么当咱们在 HashMap 初始化时，如果指定非 2 的 n 次方整数为初始化容量initialCapacity，那么会不会以致 HashMap 中的数组变更

public HashMap(int initialCapacity, float loadFactor) {if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity:" +
                                           initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor:" +
                                           loadFactor);
    this.loadFactor = loadFactor;
    // 此处能够看到下一次扩容的值曾经通过转换，是 2 的 n 次方，并且只有在 put 时才会有 Entry 数组的创立
    this.threshold = tableSizeFor(initialCapacity);
}

由下面的源码咱们能够看到，HashMap 的容量通过了 tableSizeFor 办法解决，能保障容量永远都是 2 次幂。