在 HashMap 中，table 容量初始值为 16 。且每次插入新元素后，如果需要扩容，都是通过 << 1 运算将容量乘以 2。那么什么时候会出现容量可能不是 2 的幂次方的情况呢？

通过 putAll 方法将一个 Map 的所有元素添加到另一个 Map 中。这时 HashMap 的容量不仅很大概率不是 2 的幂次方，而且不一定能够通过一次 << 1 运算得到合适的容量。例如，原始 Map 容量为 4，添加的 Map 容量为 8，那么扩容后容量 $table.length = 4 << 1 = 8$，而需要的容量为 12，远不能满足需求。
通过 IO 流反序列化 HashMap 。基本问题和 putAll 一样，都是一次左移无法满足需求

那么 HashMap 就应该设计一个算法，计算这种一次左移无法得到的容量大小。这个问题换句话来说，就是：

给定一个 int 类型的整数 n，如何求出不小于它的最接近的 2 的整数幂 m，比如给定 10 得出 16，给定 25 得出 32？

直观地，我们会想到通过对数换底公式 $log_a(b) = \frac{log_c(b)}{log_c(a)}$ 来计算。

public static int fun(int n) {
    double m = Math.log(n) / Math.log(2);
    int m2 = (int) Math.ceil(m);
    return (int) Math.pow(2, m2);
}

尽管能够正确地解决问题，我们还是可以直观地感觉到以上方法效率很低，因为涉及到许多高层方法和浮点运算。而在源码中，HashMap 作者则通过 tableSizeFor 方法巧妙高效地解决了这个问题。

JDK 8 的处理方法

/**
 * Returns a power of two size for the given target capacity.
 */
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;
}

文章 HashMap 之 tableSizeFor 方法图解已经很好地讲解了这个函数的原理，这里我就不再赘述了。

JDK 21 的处理方法

目前对 JDK 21 的源码解析比较少，让我们直接看看 tableSizeFor 在 JDK 21 中是怎么实现的吧

/**
 * Returns a power of two size for the given target capacity.
 */
static final int tableSizeFor(int cap) {
    int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

Integer.numberOfLeadingZeros()

看来具体的实现过程发生了很大的变化，中间的许多位移运算被归纳为了 Integer.numberOfLeadingZeros ，这其实是一个 JDK 1.5 引入的方法，用于计算一个整数的二进制表示中前导 0 的个数。

/**
 * Returns the number of zero bits preceding the highest-order
 * ("leftmost") one-bit in the two's complement binary representation
 * of the specified {@code int} value.  Returns 32 if the
 * specified value has no one-bits in its two's complement representation,
 * in other words if it is equal to zero.
 *
 * <p>Note that this method is closely related to the logarithm base 2.
 * For all positive {@code int} values x:
 * <ul>
 * <li>floor(log<sub>2</sub>(x)) = {@code 31 - numberOfLeadingZeros(x)}
 * <li>ceil(log<sub>2</sub>(x)) = {@code 32 - numberOfLeadingZeros(x - 1)}
 * </ul>
 *
 * @param i the value whose number of leading zeros is to be computed
 * @return the number of zero bits preceding the highest-order
 *     ("leftmost") one-bit in the two's complement binary representation
 *     of the specified {@code int} value, or 32 if the value
 *     is equal to zero.
 * @since 1.5
 */
@IntrinsicCandidate
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);
}

在这里我简单地解释一下 numberOfLeadingZeros() 的原理。我们拿一个 int 类型的整数 i 为例子，其的二进制表示是 i = 0b 0000 0000 1011 1100 1011 1101 1010 1011 ，这个值大于 $2^{16}$，前导 0 个数为 8。

首先，如果 i 等于 0 ，那么 i 的二进制表示中没有 1 ，直接返回 32；如果 i 小于等于 0 ，那么 i 的二进制表示中最高位是 1 ，直接返回 0；否则，继续执行下面的步骤。
初始化变量 n = 31
如果 i 大于等于 $2^{16}$ ，那么 n 减去 16 ，i 右移 16 位。我们的例子符合这个条件。
1
2
n - 16 = 31 - 16 = 15
i >>> 16 = 0b 0000 0000 0000 0000 0000 0000 1011 1100
如果 i 大于等于 $2^8$ ，那么 n 减去 8 ，i 右移 8 位。由于现在 i = 0b 1011 1100 < 0b 0001 0000 0000 ，不符合条件。
如果 i 大于等于 $2^4$ ，那么 n 减去 4 ，i 右移 4 位。而 i = 0b 1011 1100 > 0b 0001 0000 ，符合条件。
1
2
n - 4 = 15 - 4 = 11
i >>> 4 = 0b 0000 0000 0000 0000 0000 0000 0000 1011
如果 i 大于等于 $2^2$ ，那么 n 减去 2 ，i 右移 2 位。而 i = 0b 0000 1011 > 0b 0000 0010 ，符合条件。
1
2
n - 2 = 11 - 2 = 9
i >>> 2 = 0b 0000 0000 0000 0000 0000 0000 0000 0010
最后，返回 n - (i >>> 1) ，即 9 - 1 = 8 。 8 即为 i 的二进制表示中前导 0 的个数。

看过这段计算后，你应该已经看出，numberOfLeadingZeros 的计算过程其实就是通过 二分位移 来快速地在确定的几次位移运算之内，计算出一个整数的二进制表示中前导 0 的个数。其二分计算的思想实际上和 JDK 8 中类似，但在 JDK 21 中只是复用了这个 Integer 类的静态方法，免于重复造轮子，也省去了学习成本。

tableSizeFor()

这时你肯定要说，不对啊，只是得到了前导 0 的个数，怎么就能得到最接近的 2 的整数幂了呢？接下来我们回到 tableSizeFor 方法看看代码。

我们详细讲讲 int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1) 这一行代码。

对于输入的任意容量 cap ，我们首先减去 1 ，得到 cap - 1 。稍后解释这样做的原因。
计算 cap - 1 的前导 0 的个数，我们假设前导 0 的个数是 k 。
将 -1 无符号右移，得到一个前 k 位为 0，其余位为 1 的数。

这一步是怎么得到的呢？
首先我们需要知道，-1 的二进制表示是 0b 1111 1111 1111 1111 1111 1111 1111 1111 。
且 >>> 在 Java 中是 无符号 右移。
因此右移 k 位后，前 k 位都是 0 ，其余位都是 1 。
假设 k = 8 ，那么右移后的结果是 0b 0000 0000 1111 1111 1111 1111 1111 1111 。

在计算完 n 之后，我们看到 return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1 直接返回了 n + 1 。

实际上这就能解释为什么我们在计算前导 0 的个数时，要先减去 1 了。我们首先要明确的是，tableSizeFor 方法的目的是得到一个不小于 cap 的最接近的 2 的整数幂，而一个 2 的整数幂必然在其二进制的某一位为 1 ，其他位为 0。

2 = 0b 0000 0000 0000 0000 0000 0000 0000 0010
4 = 0b 0000 0000 0000 0000 0000 0000 0000 0100
8 = 0b 0000 0000 0000 0000 0000 0000 0000 1000
16 = 0b 0000 0000 0000 0000 0000 0000 0001 0000
...

在 Java 中，获取一个特定位以下全 1 的数，计算是较为便捷的（通过上文所示方法）。那么，我们先通过 cap - 1 得到一个特定位以下全 1 的数 n，最后再将这个 1 加回来，就能直接得到我们想要的一个值为 2 的整数幂的数了。

// 假设 cap = 10
cap = 0b 0000 0000 0000 0000 0000 0000 0000 1010
cap - 1 = 0b 0000 0000 0000 0000 0000 0000 0000 1001

n = -1 >>> Integer.numberOfLeadingZeros(cap - 1)
  = -1 >>> 28
  = 0b 1111 1111 1111 1111 1111 1111 1111 1111 >>> 28
  = 0b 0000 0000 0000 0000 0000 0000 0000 1111

n + 1 = 0b 0000 0000 0000 0000 0000 0000 0001 0000
      = 16
// 16 是不小于 10 的最接近的 2 的整数幂，因此 HashMap 的 table 接下来应当扩容的到 16

本文参考文章：

HashMap 之 tableSizeFor 方法图解