HashMap 底层原理解析：容量设计为何总是 2 的 n 次方

原文来自于：zha-ge.cn/java/23

HashMap 底层原理解析：容量设计为何总是 2 的 n 次方

引子：一个让人疑惑的设计

前几天调试一个性能问题时，我突然注意到一个有趣的现象：无论我给 HashMap 设置多大的初始容量，打印出来的实际容量总是 16、32、64 这样的数字。比如我设置容量为 10，实际却变成了 16；设置为 20，变成了 32。

这让我产生了一个疑问：为什么 HashMap 的容量设计必须是 2 的 n 次方？这背后隐藏着什么样的设计智慧？

探索：从哈希碰撞说起

要理解这个设计，我们得先从 HashMap 的工作原理说起。想象一下，HashMap 就像一个巨大的停车场，每个车位都有编号。当一辆车（键值对）要停车时，停车场管理员（哈希函数）会根据车牌号（key 的 hashCode）计算出应该停在哪个车位。

最直观的做法是用取模运算：车位号 = hashCode % 容量。这样确实能把所有车都分配到合适的车位，但问题来了——取模运算在计算机世界里是个"昂贵"的操作，特别是在高并发场景下。

转折：位运算的巧妙替代

这时候，HashMap 的设计者想到了一个绝妙的优化：如果容量是 2 的 n 次方，那么取模运算可以用位运算替代！

具体来说：当容量是 2^n 时，hashCode % capacity 等价于 hashCode & (capacity - 1)。

让我们看看这个神奇的转换：

// 传统取模方式（慢）
int index = hashCode % 16;

// 位运算方式（快）
int index = hashCode & (16 - 1);  // 16-1 = 15 = 1111（二进制）

// HashMap 内部实现的核心片段
static int hash(Object key) {
    int h = key.hashCode();
    return (h ^ (h >>> 16)) & (table.length - 1);
}

踩坑瞬间：为什么是减 1？

刚开始理解这个原理时，我一直不明白为什么要减 1。后来才恍然大悟：

• 容量 16 的二进制是 10000
• 容量 16-1=15 的二进制是 01111

当我们用 hashCode & 01111 时，实际上就是取 hashCode 的低 4 位，这样得到的结果范围正好是 0~15，完美对应 16 个槽位！

解决：容量自动调整的奥秘

现在我们来看看 HashMap 是如何确保容量始终是 2 的 n 次方的：

// HashMap 初始化时的容量计算
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 + 1;
}

这个算法的巧妙之处在于：无论你输入什么数字，它都会返回大于等于该数字的最小的 2 的 n 次方。比如：

经验启示：性能优化的艺术

通过这次探索，我深深感受到了 HashMap 设计的精妙：

1. 性能优化

• 位运算比取模运算快 10 倍以上
• 在高频操作的 get/put 方法中，这种优化效果显著

2. 哈希分布均匀性

• 2 的 n 次方减 1 得到的掩码能最大程度保证哈希值的均匀分布
• 减少哈希碰撞，提升查找效率

3. 扩容策略的优雅

// 扩容时只需要简单的位移操作
newCapacity = oldCapacity << 1;  // 相当于乘以 2

总结：小细节大智慧

HashMap 容量设计为 2 的 n 次方这个看似简单的规则，背后蕴含着深刻的计算机科学智慧。它不仅体现了对性能的极致追求，更展现了用数学原理解决工程问题的优雅思路。

下次当你在面试中被问到这个问题时，不要只回答"为了性能优化"，而要从位运算、哈希分布、扩容策略等多个维度去阐述。这样的回答，才能真正体现你对底层原理的深度理解。

毕竟，优秀的程序员不仅要会用工具，更要理解工具背后的设计哲学。