为什么 HashMap 在 Java 中扩容时采用 2 的 n 次方倍？

• 标签：Java 集合、Java

🏛 业务架构师

根本原因：容量为 2 的 n 次方时，取模运算可以退化为位运算——hash & (capacity - 1) 等价于 hash % capacity，但位运算比除法快一个数量级。这个位与的本质是"取 hash 的低 log2(capacity) 位"确定桶位置。

由此带来的连锁收益：

• 扩容迁移 O(1) 判定：容量翻倍意味着"多看一位 hash"。扩容后元素的新位置只由新增的那一个高位 bit 决定——0 留原位，1 移到"原位 + 旧容量"。JDK 8 正是利用这一点，把 rehash 从"全部重算"优化成"按 bit 拆高低链"，数据量越大省得越多；
• 分布均匀：位与取的是连续低位，配合扰动函数（高 16 位异或低 16 位）把高位信息混进来，分布比普通取模更均匀。

业务视角我想提炼两点：

• 微优化的规模化效应：单次 put 省下的纳秒不起眼，但 HashMap 承载的是全 JVM 最高频的数据操作，亿次调用 × 纳秒 = 可观的机器成本。判断一个微优化值不值得做，看"调用频次 × 单次收益"的乘积，而不是单看技术上的精巧；
• 反过来也要警惕微优化沉迷：业务代码里大部分热点在 IO 与外部调用，先把架构层的钱赚了（缓存、批处理、连接复用），再来抠位运算这个层级。性能优化有优先级阶梯，从最赚钱的开始——这是我带团队做性能治理时反复强调的纪律。

2 的 n 次方是个小设计，背后"约束换效率"的思想（用结构约束换取计算捷径）在索引设计、分库分表取模里反复出现，值得内化。

🏗 系统架构师

容量取 2 的幂是为了让取模运算退化成位与，并让扩容迁移变成"按位分裂"：

• 定位优化：index = hash & (capacity - 1)。capacity 为 2 的幂时，capacity-1 的二进制是低位全 1（如 16-1=1111），按位与等价于取模但快得多，且散列充分（若不是 2 的幂，比如 15-1=1110，最低位恒 0，奇数下标永远不会被使用，散列立刻劣化）；
• 扩容迁移优化：容量翻倍只改变 hash 在多出来的一位上的取值。迁移时看 hash & oldCap：为 0 留原位 i，为 1 去 i + oldCap——不需要重算 hash，一条链表按这一位拆成两条，迁移成本从"全量重散列"降为"一遍链表分裂"，这是 JDK 8 HashMap 扩容高效的核心；
• 构造时保证：传入任意初始容量，tableSizeFor() 把它向上修正为最近的 2 的幂（如 10 → 16），把不变式内聚在构造函数里。

通用启发：这是"用数据结构不变式换取热路径效率"的典型设计。我在设计分片（分库分表取模 2^n）、一致性哈希槽位、位图索引时都沿用同一套路：先固定"桶数是 2 的幂"这个不变式，再享受位运算红利。

💻 全栈开发专家

两个收益都来自 2 的幂这个约束：

1. 取模变位运算：

index = (n - 1) & hash;   // 等价 hash % n，但位运算快且 hash 为负也不出错

2. 扩容迁移 O(1) 定位（更关键）：容量翻倍意味着只多了一个有效二进制位。迁移时每个节点只需判断 hash & oldCap 这一位：

• 0 → 新位置 = 原索引；
• 1 → 新位置 = 原索引 + oldCap。

不用重算 hash，一条链按这一位一分为二挂到新数组，这是 JDK 8 resize 高效的核心。容量不是 2 的幂的话，扩容后索引和原索引没有这种位关系，只能全部 rehash。

保证机制：构造传任意值都会被 tableSizeFor 拉到最近的 2 的幂（1000 → 1024），外部根本传不进非 2 幂的容量。

发散（加分）：这个位技巧在工程里到处都是——Redis 的 hash & (sizemask)、RedisSlot、Fenwick tree、各种分桶（userId 高位取模再 & 15）。我写分片逻辑也优先用 2 的幂分桶，扩容时只有一半数据迁移，和 ConcurrentHashMap 一致性哈希的迁移思想相通。