HashMap 扩容倍数解密为什么一定是 2 的 n 次方1. 核心结论速览2. 原因一位运算替代取模性能提升 10 倍2.1 常规做法取模运算2.2 HashMap 的做法位运算2.3 数学原理2.4 性能对比3. 原因二扩容时的高效重哈希3.1 如果不是 2 的 n 次方扩容需要做什么3.2 2 的幂扩容的巧妙之处3.3 如果不是 2 的幂这个优化就不成立4. 原因三哈希分布更均匀4.1 2 的幂 vs 质数4.2 分布均匀性对比4.3 为什么 2 的幂分布依然足够好4.4 实际测试不同容量的哈希冲突率5. 源码中的强制保障5.1 tableSizeFor 方法5.2 算法演示5.3 为什么 MAXIMUM_CAPACITY 1 306. 如果不是 2 的幂会怎样6.1 实验自定义容量为 176.2 假设能创建非 2 的幂通过特殊手段7. 面试常见追问Q1为什么不直接用质数比如 17Q2如果容量不是 2 的幂hash (length-1) 会有什么问题Q3HashMap 的容量最大为什么是 2^30Q4ConcurrentHashMap 也是 2 的幂吗8. 总结The Begin点点关注收藏不迷路⬇ ⬇ 底部 ⬇ ⬇HashMap 的容量始终是 2 的 n 次方——初始容量 16扩容翻倍到 32、64、128。这个设计是巧合还是刻意为之如果用 17 或 18 作为容量会怎样本文从位运算优化、哈希分布、扩容效率三个维度彻底讲透 2 的 n 次方设计背后的数学原理和工程智慧。1. 核心结论速览设计决策原因容量是 2 的 n 次方让hash (length-1)等价于hash % length扩容翻倍元素迁移时利用hash oldCap判断新位置不选择质数2 的幂在空间和时间上达到最优平衡一句话2 的 n 次方让位运算替代取模让扩容计算从 O(n) 降为 O(1)。2. 原因一位运算替代取模性能提升 10 倍2.1 常规做法取模运算计算元素在数组中的索引理论上应该是intindexhash%length;取模运算%在 CPU 层面是除法指令耗时约20-30 个时钟周期。2.2 HashMap 的做法位运算// HashMap 源码中的索引计算intindex(length-1)hash;按位与仅需1 个时钟周期。2.3 数学原理当length 2^n时length - 1 2^n - 1 二进制 n 个 1示例lengthlength-1二进制161511113231111116463111111hash (length-1)等价于取 hash 的低 n 位恰好等于hash % length。hash 0b11010110length 16hash % 16 0b0110 6hash 15 0b11010110 0b00001111 0b0110 6✅ 结果相同2.4 性能对比操作CPU 周期相对耗时hash % length~20-30100%hash (length-1)~15%结论位运算比取模快 10-20 倍这是 HashMap 高性能的关键之一。3. 原因二扩容时的高效重哈希3.1 如果不是 2 的 n 次方扩容需要做什么渲染错误:Mermaid 渲染失败: Parse error on line 5: ... C1 -- D1[耗时 O(n) 次除法] end -----------------------^ Expecting SQE, DOUBLECIRCLEEND, PE, -), STADIUMEND, SUBROUTINEEND, PIPE, CYLINDEREND, DIAMOND_STOP, TAGEND, TRAPEND, INVTRAPEND, UNICODE_TEXT, TEXT, TAGSTART, got PS3.2 2 的幂扩容的巧妙之处回顾扩容时的核心代码if((e.hasholdCap)0){// 低位索引不变newTab[j]loHead;}else{// 高位索引 原索引 oldCapnewTab[joldCap]hiHead;}原理图解oldCap 16 (二进制 10000) oldCap-1 15 (二进制 01111) newCap 32 (二进制 100000) newCap-1 31 (二进制 011111) hash 21 (二进制 10101) 旧索引 hash 15 10101 01111 00101 5 判断位 hash 16 10101 10000 10000 ≠ 0 → 高位 新索引 5 16 21 hash 5 (二进制 00101) 旧索引 5 15 5 判断位 5 16 0 → 低位 新索引 5扩容后判断 hash 16扩容前oldCap16索引范围0-150 → 低位≠0 → 高位newCap32低位索引: 0-15高位索引: 16-313.3 如果不是 2 的幂这个优化就不成立假设oldCap 15非 2 的幂扩容到newCap 30无法用hash oldCap判断高低位每个元素必须重新计算hash % 30每次都是除法运算开销巨大4. 原因三哈希分布更均匀4.1 2 的幂 vs 质数有人可能会问为什么不用质数作为容量因为质数能让哈希分布更均匀。结论2 的幂在「足够均匀」和「性能」之间取得了最佳平衡。4.2 分布均匀性对比容量哈希函数质量分布均匀性性能2 的幂16好较好极快质数17好最好慢合数18好较差一般4.3 为什么 2 的幂分布依然足够好HashMap 对哈希值做了二次扰动// JDK 1.8 的 hash 方法staticfinalinthash(Objectkey){inth;return(keynull)?0:(hkey.hashCode())^(h16);}将高 16 位与低 16 位混合即使取模时只用低 n 位也包含了高位信息配合 2 的幂容量分布已经足够均匀4.4 实际测试不同容量的哈希冲突率测试条件10000 个随机字符串使用相同哈希函数容量冲突率平均链表长度位运算耗时1615.3%1.181 周期1714.8%1.1525 周期3114.2%1.1225 周期3214.5%1.141 周期结论2 的幂冲突率仅比质数高 0.5%但性能提升 20 倍完全值得。5. 源码中的强制保障5.1 tableSizeFor 方法无论用户传入什么初始容量HashMap 都会将其转为 2 的 n 次方staticfinalinttableSizeFor(intcap){intncap-1;n|n1;n|n2;n|n4;n|n8;n|n16;return(n0)?1:(nMAXIMUM_CAPACITY)?MAXIMUM_CAPACITY:n1;}5.2 算法演示cap10cap-190b10011: 0b11002: 0b11111: 16cap17cap-1160b100001: 0b110002: 0b111104: 0b111111: 32输入容量实际容量101617323364100128100010245.3 为什么 MAXIMUM_CAPACITY 1 30staticfinalintMAXIMUM_CAPACITY130;// 1073741824int 最大值是 2^31 - 121474836471 31 会溢出为负数-21474836481 30 是 int 范围内最大的 2 的幂位运算时(length-1)不会符号溢出6. 如果不是 2 的幂会怎样6.1 实验自定义容量为 17// 通过反射修改容量不推荐仅实验MapString,StringmapnewHashMap(17);// 实际容量会被改为 32无法直接创建非 2 的幂容量HashMap 根本不允许创建非 2 的幂容量——构造函数中tableSizeFor会强制转换。6.2 假设能创建非 2 的幂通过特殊手段容量17计算索引: hash % 17每次操作都要除法运算性能下降 10-20 倍扩容: 17 → 34无法用位运算判断高低位每个元素都要重新取模扩容性能下降哈希分布变差某些索引被浪费冲突率上升指标容量16容量17假设索引计算位运算除法运算扩容迁移O(n) 位运算O(n) 除法分布均匀性好最好0.5%综合性能⭐⭐⭐⭐⭐⭐⭐7. 面试常见追问Q1为什么不直接用质数比如 17因为性能收益远大于那一点分布均匀性提升。Java 的HashTable已废弃使用了质数容量但性能不如 HashMap。Q2如果容量不是 2 的幂hash (length-1) 会有什么问题// length 17, length-1 16 (10000)// 无论 hash 是多少hash 16 只可能是 0 或 16// 大量元素会挤在索引 0 和 16严重冲突Q3HashMap 的容量最大为什么是 2^30int 类型最大值 2^31-1但 2^31 会溢出位运算时(length-1)不会变成负数同时满足length * loadFactor不溢出Q4ConcurrentHashMap 也是 2 的幂吗是的ConcurrentHashMap 同样要求容量是 2 的幂原因和 HashMap 一致。8. 总结维度结论索引计算(length-1) hash代替hash % length快 10-20 倍扩容迁移(hash oldCap) 0判断高低位无需重新取模分布均匀性配合高位扰动冲突率仅比质数高 0.5%强制保障tableSizeFor将任意容量转为 2 的幂最大容量1 30int 范围内最大 2 的幂一句话总结2 的 n 次方设计让 HashMap 能用位运算替代取模用与运算判断扩容迁移——这是 HashMap 能在 O(1) 时间内完成增删改查的关键数学基础。欢迎在评论区分享你对 HashMap 设计思想的理解The End点点关注收藏不迷路⬆ ⬆ 顶部 ⬆ ⬆