HashMap扩容的时候为什么是2的n次幂？

HashMap扩容时选择2的n次幂作为新的容量，主要基于以下几个关键原因：

一、位运算的高效性

当HashMap的容量是2的n次幂时，可以通过位运算（与操作）来高效地计算元素的索引位置。具体地，计算索引的公式可以从hash % capacity简化为hash & (capacity - 1)。这种简化基于以下数学原理：

• 假设容量为2的n次幂，即capacity = 2^n，那么capacity - 1的二进制表示将是一串连续的1（例如，当n=3时，capacity = 8，capacity - 1 = 7，其二进制表示为0111）。
• 当一个哈希值与capacity - 1进行与操作时，实际上只保留了哈希值的低n位。这是因为与操作会逐位比较两个操作数，只有当两个操作数的对应位都为1时，结果的对应位才为1。由于capacity - 1的低n位都是1，因此与操作会保留哈希值的低n位。

与操作比取模操作更快，因为它只涉及简单的二进制位操作，而不需要进行复杂的算术计算。

二、元素分布的均匀性

使用2的n次幂作为容量有助于确保元素在HashMap中的均匀分布。这是因为：

• 哈希函数通常会将键映射到一个相对较大的整数范围内。当这个范围被映射到HashMap的容量（即数组长度）上时，如果容量是2的n次幂，那么哈希值的低n位将直接决定元素在数组中的位置。
• 由于哈希值的低n位是随机分布的（假设哈希函数是良好的），因此元素在HashMap中的位置也将是随机分布的。这有助于减少哈希冲突，并提高HashMap的整体性能。

三、扩容的便捷性

HashMap的扩容机制是以2倍的形式进行扩容。当容量是2的n次幂时，扩容后的新容量也是2的n+1次幂。这种设计简化了扩容过程，并减少了重新计算所有key的hash值再重新分布的开销。具体地：

• 在扩容过程中，已存在的键值对在新的表中的位置可能是原索引或原索引+原容量（取决于扩容后哈希值高位的变化）。这种设计有助于保持元素在扩容前后的相对位置关系。
• 由于扩容后的容量是原来的两倍，因此可以通过简单的位操作来确定元素在新表中的位置。这减少了重新计算hash值的需要，并提高了扩容的效率。

综上所述，HashMap扩容时选择2的n次幂作为新的容量是基于位运算的高效性、元素分布的均匀性和扩容的便捷性等多方面的考虑。这种设计有助于优化HashMap的性能并提高数据存储效率。