本博客日IP超过2000，PV 3000 左右，急需赞助商。
极客时间所有课程通过我的二维码购买后返现24元微信红包，请加博主新的微信号：xttblog2，之前的微信号好友位已满，备注：返现
受密码保护的文章请关注“业余草”公众号，回复关键字“0”获得密码
所有面试题(java、前端、数据库、springboot等)一网打尽，请关注文末小程序
腾讯云】1核2G5M轻量应用服务器50元首年，高性价比，助您轻松上云
关于 Java 集合的面试题网上也有很多，很多都是基于源码的解毒。但有时候面试官会出其不意，问一些设计方面的问题。
比如，我们今天标题要讨论的，Java 中常见的 HashMap 等 Map 类集合，在扩容时，为什么是 2 倍，而不是 1.5 倍，3 倍，10 倍等。这么设计有什么意义吗？
当 map 中包含的 Entry 的数量大于等于 threshold = loadFactor * capacity 的时候，且新建的 Entry 刚好落在一个非空的桶上，此刻触发扩容机制，将其容量扩大为 2 倍。
这个 2 是有一些特殊的意义的。我们先从一些源码中看出这些设计的巧妙之处。
/**
* The default initial capacity - MUST be a power of two.
*/
static final int DEFAULT_INITIAL_CAPACITY = 16;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);
// Find a power of 2 >= initialCapacity 找到一个大于等于初始容量的且是2的幂的数作为实际容量
int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1;
this.loadFactor = loadFactor;
threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
table = new Entry[capacity];
useAltHashing = sun.misc.VM.isBooted() &&
(capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
init();
}通过以上我们知道 HashMap 的容量必须是 2 的幂，那么为什么要这么设计呢？答案当然是为了性能。在 HashMap 通过键的哈希值进行定位桶位置的时候，调用了一个 indexFor(hash, table.length); 方法。
/**
* Returns index for hash code h.
*/
static int indexFor(int h, int length) {
return h & (length-1);
}可以看到这里是将哈希值 h 与桶数组的 length-1（实际上也是 map 的容量-1）进行了一个与操作得出了对应的桶的位置，h & (length-1)。
但是为什么不采用 h % length 这种计算方式呢？
那是因为 Java 中的 %、/ 操作比 & 慢 10 倍左右，因此采用 & 运算会提高性能。
通过限制 length 是一个 2 的幂数，h & (length-1) 和 h % length 结果是一致的。这就是为什么要限制容量必须是一个 2 的幂的原因。
举个简单的例子说明这两个操作的结果一致性：
假设有个 hashcode 是 311，对应的二进制是(1 0011 0111)。
length 为 16，对应的二进制位 (1 0000)。
- %操作：311 = 16*19 + 7；所以结果为7，二进制位(0111)；
- &操作：(1 0011 0111) & (0111) = 0111 = 7, 二进制位(0111)
1 0011 0111 = (1 0011 0000) + (0111) = (12^4 + 1 2^5 + 02^6 + 02^7 + 12^8 ) + 7 = 2^4(1 + 2 + 0 + 0 + 16) + 7 = 16 * 19 + 7; 和 % 操作一致。
如果 length 是一个 2 的幂的数，那么 length-1 就会变成一个 mask, 它会将 hashcode 低位取出来，hashcode 的低位实际就是余数，和取余操作相比，与操作会将性能提升很多。
参考资料
最后，欢迎关注我的个人微信公众号：业余草（yyucao）！可加作者微信号：xttblog2。备注：“1”，添加博主微信拉你进微信群。备注错误不会同意好友申请。再次感谢您的关注！后续有精彩内容会第一时间发给您！原创文章投稿请发送至532009913@qq.com邮箱。商务合作也可添加作者微信进行联系！
本文原文出处：业余草： » Java Map 扩容时，为什么推荐是2的幂