HashMap初始化容量怎么保证是2的n次方

在 Java 的 HashMap 中，哈希表的容量（即桶的数量）必须始终是 2 的幂次方。这是为了优化哈希值的映射过程（通过按位与运算 & 代替取模运算 %），从而提高性能。为了保证初始容量是 2 的幂次方，HashMap 在初始化时会对用户传入的初始容量进行调整。

以下是 HashMap 如何保证初始容量始终是 2 的幂次方的详细实现：

一、 用户传入初始容量

当用户通过构造函数指定初始容量时，HashMap 并不会直接使用这个值，而是通过一个内部方法 tableSizeFor将其调整为大于或等于该值的最小 2 的幂次方。

源码解析

public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);  // 这种思维可以学习，调用下方接口，多态的使用
}

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;
    this.threshold = tableSizeFor(initialCapacity);  // 这里拿着传入的容量参数  进行计算
}

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

如上源码，读者会疑问怎么通过向又移动1位、2位、4位、8位就保证数字会变成2的n次方减去1？

可以拿17来看，一开始减去1，转为二进制位10000，这个时候

n |= n >>> 1,可以得到n=24（11000）

n |= n >>> 2;可以得到n=30（11110）

n |= n >>> 4;可以得到n=31（11111）

…………

到这里可以看出，位运算的目的是为了填满将int类型的数的二进制位全部变为1，自然就是2的n次方减去1

注

如果读者想去研究debug源码，可以如图尝试

public static void main(String[] args) {
    HashMap map=new HashMap(17);
    map.put(12,123);
}

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;
    this.threshold = tableSizeFor(initialCapacity);
}

 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是属于懒惰加载的，初始化并不会真实分配容量，只是会记载一个数字表示容量，所以debug的时候看到初始化后之后却没有分配容量不要奇怪

二、为什么容量必须是 2 的幂次方？

1. 优化哈希值映射：
   • 哈希表的索引通过 index = (n - 1) & hash 计算，其中 n 是容量。
     • 这里是取模运算，算出的index下标始终是0-n-1这个范围
   • 如果 n 是 2 的幂次方，n - 1 的二进制形式为全 1（例如，16 - 1 = 15，二进制为 00001111）。
   • 这样，(n - 1) & hash 等价于 hash % n，但按位与运算的性能更高。
2. 减少哈希冲突：
   • 2 的幂次方容量可以更好地分散哈希值，减少冲突。
3. 扩容方便：
   • 扩容时，新容量是旧容量的 2 倍，只需左移一位即可。

三、 总结

• HashMap 通过 tableSizeFor 方法将用户传入的初始容量调整为大于或等于该值的最小 2 的幂次方。
• 容量为 2 的幂次方可以优化哈希值映射、减少冲突，并简化扩容操作。
• 这种设计是 HashMap 高性能的关键之一。

通过这种机制，HashMap 确保了初始容量始终是 2 的幂次方，从而提高了哈希表的性能和可靠性。