HashMap 底层实现：数组容量为什么必须是 2 的幂-云帆数科

先给结论因为要用 (n-1)代替取模。n 是 2 的幂时n-1的二进制全是 1位与的结果刚好等价于取模而且比取模快。但更值钱的理由在扩容那一步多数人不知道。一个很常见的初始化很多团队写代码时都会这么干已知要放 1000 个元素于是new HashMap(1000)心想一次分配到位省一次扩容。实际上它还是会扩一次。原因在后面第 4 节看完就明白为什么阿里巴巴的开发手册建议写成new HashMap(expectedSize / 0.75 1)。扩容不是小事。一次 resize 要重新分配一个两倍大的数组再把所有元素搬过去数据量大的时候这是一次明显的停顿。缓存类的 Map 如果初始化容量没算对启动阶段可能连续扩三四次。先把问的是哪一层搞清楚HashMap 底层实现其实是把四个问题打包在一起问数据结构长什么样hash 值怎么算的拿到 hash 之后怎么定位到数组下标容量不够时怎么扩容。多数人只会答第一层。第三层和第四层才藏着 2 的幂这个答案。逐层拆开数据结构数组加链表链表太长变红黑树JDK 1.8 的 HashMap 是数组table、链表、红黑树的组合。每个数组位置叫一个桶哈希冲突的元素挂在同一个桶上形成链表。链表长了查询会退化成 O(n)所以 1.8 加了树化链表长度超过 8并且数组长度达到 64链表转成红黑树查询变成 O(log n)。注意是两个条件同时满足。数组还没到 64 的时候优先做的是扩容而不是树化因为扩容能直接把冲突分散开代价通常比建树低。反过来树上的元素减少到 6 时会退化成链表。为什么不是 8中间留了 1 的缓冲避免某个桶的元素数在 8 附近反复横跳导致来回转换。hash 值一次高位异或// JDK 1.8 java.util.HashMap static final int hash(Object key) { int h; return (key null) ? 0 : (h key.hashCode()) ^ (h 16); }把 hashCode 的高 16 位和低 16 位做异或结果还是 32 位。这一步叫扰动。它的目的不是让 hash 更随机。真正的原因是数组长度比较小的时候定位下标只用到低位高 16 位完全不参与。如果两个 key 的低位一样、高位不同它们会撞到同一个桶。异或之后高位的信息被混进了低位冲突概率就降下来了。HashMap 只在这一处做了扰动没有用多重哈希那种更重的算法。这是个取舍多花一次异或的代价换大部分场景下的冲突改善够了。定位下标用位与取代取模// JDK 1.8putVal 里的定位 // n table.length int index (n - 1) hash;取模的正经写法是hash % n。位运算比取模快但两者等价有个前提n必须是 2 的幂。n 是 16n-1是 15二进制1111。任何数跟1111做与运算结果就是它最低 4 位的值范围 0 到 15正好是取模的结果。n 是 10n-1是 9二进制1001。做与运算之后第 2 位和第 3 位永远是 0也就是说下标 2、3、4、5、6、7 里有好几个永远空着。一半的桶浪费了冲突率直接翻倍。这就是必须是 2 的幂最直接的技术理由。扩容这才是 2 的幂真正的价值这部分是被答得最薄的一层。容量从 16 扩到 32(n-1) hash里的掩码从1111变成11111多参与了一位。于是每个元素的新下标只有两种可能原下标不变或者原下标加上旧容量16。判断条件极简单看 hash 在那新增的一位上是 0 还是 1// JDK 1.8 resize 里的拆分逻辑简化后 if ((e.hash oldCap) 0) { // 新下标原下标留在 lo 链 } else { // 新下标原下标 oldCap进 hi 链 }一次位与就能决定去向不用重新算 hash不用重新取模。好处还不止省了一次运算。因为同一条链上的元素只可能分到两个桶里JDK 1.8 直接把原来那条链拆成 lo 和 hi 两条各自挂到新位置链上元素的相对顺序还能保持原样。这顺手解决了 1.7 头插法导致的扩容死循环问题。如果容量不是 2 的幂这套拆分逻辑完全不成立每个元素都得老老实实重算一遍模。扩容是 HashMap 最贵的操作成本翻一倍是很难接受的。顺带说初始化那件事。构造时传入的初始容量会被tableSizeFor往上取整到最近的 2 的幂// JDK 1.8把任意正整数变成它的最小 2 的幂 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 MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n 1; }传入 1000得到 1024。但扩容阈值是1024 * 0.75 768放到第 769 个元素时就触发扩容了。所以想放 1000 个元素又不扩容初始值得写成1000 / 0.75 1约等于 1335。面试官在等的那句答完 (n-1)比取模快及格了。但这句话任何背过八股的人都会说没有区分度。真正让人抬眼的是这一句取模快只是顺带的收益2 的幂真正解决的是扩容成本。正因为容量翻倍时掩码只多一位每个元素的新下标只有两种可能判断只需要一次位与JDK 1.8 才能把一条链拆成两条直接搬走不用逐个 rehash。顺带说一句负载因子取 0.75 也是有依据的。源码注释里给了个数在理想的随机 hash 下桶里的元素数服从泊松分布负载因子 0.75 时链表长度达到 8 的概率大约是千万分之六小到可以忽略。所以 8 这个树化阈值不是拍脑袋定的。第二段尤其加分因为大多数人只会背默认 0.75说不出它是怎么来的。五个常见误区误区一以为 new HashMap(1000) 就不会扩容会扩。容量被上调到 1024但阈值是 1024 乘 0.75等于 768。要按预期元素数除以 0.75 再加 1 来给初始值。误区二以为链表长度超过 8 就树化还要数组长度达到 64。没到 64 时优先扩容因为那时候冲突多半是容量不够造成的。误区三以为元素少于 8 就从红黑树退回来退化阈值是 6。中间留的缓冲是为了避免在临界点反复转换。**误区四把扰动函数说成让哈希更均匀**它解决的是低位信息不足的问题。数组小的时候只有低几位参与运算高 16 位被混下来才有意义。**误区五以为 1.8 的 HashMap 线程不安全只是数据覆盖**死循环确实被尾插法解决了但并发 put 依然会丢数据并发扩容也有风险。要线程安全还是得用 ConcurrentHashMap。至于用 Hashtable我一般不选全表一把锁并发下退化得很厉害。这条看你们的具体场景我给不了死结论。速查表参数取值为什么默认初始容量162 的幂 (n-1)可用负载因子0.75泊松分布下链长达 8 概率约千万分之六扩容倍数2 倍掩码只多一位拆分成本最低树化阈值链表 8 且数组 ≥ 64优先扩容扩容解决不了再建树退化阈值6留缓冲避免临界反复转换扰动h ^ (h 16)让高 16 位参与低位运算关于本文HashMap 这条线还有几道没写为什么线程不安全、1.7 头插法死循环的完整过程、ConcurrentHashMap 从分段锁到 CAS 加 synchronized 的演进。J014 会讲 ConcurrentHashMap那篇和这篇连着看会顺很多。我会接着更新。感兴趣的话可以留个关注方便下次找。另外完整的十二个模块Java / C / Go / JVM / MySQL / Redis / MQ / 分布式 / 事务 / 网络 / 系统设计 / 项目深挖我整理成了一份手册每题都标了考察点和加分答法。【草丛后端架构】持续分享后端架构与底层原理。

企业数字化 ERP 产品动态

相关推荐

消防维保之——（防排烟系统）（一）

一、排烟系统组成板式排烟口、远程执行机构，排烟防火阀、柔性接头、排烟风机、风机控制柜、排烟管道、挡烟垂壁、电动排烟窗。二、防烟系统组成常闭式加压送风口、送风管道、防火阀、柔性接头、送风风机、风机控制柜。三、打开排烟口联动启动排烟风机确认火灾报警… · 2026/11/4 12:15:06

K8s 集群备份落到自建对象存储：Velero 接 RustFS 配置指南

etcd 快照救的是 API server 里的数据，PV 里的数据不在其中；业务对象加 PV 数据的应用级备份，K8s 生态里的标准工具是 Velero：把集群资源对象和 PV 数据备份进对象存储桶，恢复时再从桶里拉回来。它通过 AWS 插件兼容任… · 2026/11/4 12:15:06

11 · 并发容器全家桶

一句话定位：除了 ConcurrentHashMap，JUC 还提供了一整套线程安全容器，各有适用场景。1. 为什么不用 Collections.synchronizedXxx List<String> list Collections.synchronizedList(new ArrayList<>());本质是给每个方法加 sync… · 2026/11/4 12:15:06

深度学习生成模型：RBM原理与PyTorch实现详解

1. 项目概述：深度学习经典教材精读系列这个编号为"deeplearningbook_027-2"的项目，是我在系统研读《Deep Learning》教材过程中整理的系列笔记之一。作为AI领域的经典著作，该书由Ian Goodfellow等权威学者撰写，全面覆盖… · 2026/11/4 12:58:40

优化Claude命令行交互的6个高效工具链

1. 为什么需要优化Claude命令行体验作为AI开发者，我们每天都要与Claude这类大模型进行大量命令行交互。但原生环境下的操作体验往往存在几个痛点：响应延迟明显、结果格式化混乱、历史记录管理困难、多会话切换繁琐。这些问题直接影响了开发调试效率&… · 2026/11/4 12:58:40

MySQL版本信息获取方法与兼容性判断指南

1. 为什么需要获取MySQL版本信息在日常数据库管理和开发工作中，准确获取MySQL版本信息是一项基础但至关重要的技能。作为关系型数据库管理系统，MySQL的不同版本在功能支持、语法细节和性能表现上存在显著差异。了解当前使用的MySQL版本，可以帮… · 2026/11/4 12:58:40

Excel筛选重复项怎么做？四种方法选型与避坑指南

1. 先把"重复"这件事的定义搞清楚Excel如何筛选重复项，这个问题几乎是每个和数据打交道的人都会撞上的一道坎。不管你是做人事花名册、电商订单核对、门店库存盘点，还是帮导师整理问卷回收结果，只要数据来源超过两个，重… · 2026/11/4 12:58:40

Sora MCP协议集成实战：从原理到商业应用

1. Sora MCP 集成项目概述Sora MCP（Media Control Protocol）是一种专为多媒体设备设计的控制协议，主要用于音视频设备的集中管理和控制。在实际项目中，我们经常需要将Sora MCP集成到现有的智能家居系统或媒体控制中心中。这个集成… · 2026/11/4 12:58:40

AI学术写作工具的核心功能与伦理实践

1. 学术写作工具的变革浪潮去年帮导师审阅研究生论文时，一个现象让我震惊：超过60%的投稿在文献综述部分出现了惊人的相似结构。直到某天实验室的师弟悄悄给我展示了他使用的AI写作辅助工具，才解开了这个谜团。当前学术圈正在经历一场静默的技… · 2026/11/4 12:57:40

双极步进电机控制实战：DRV8818PWPR与PIC18F86K22驱动调试

/* MD / 富文本中的 .toc（含博客园搬家等嵌套结构）；.toc-box 在侧栏，不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p（:empty 仍占 20px），一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/4 3:16:49