1. 项目概述HashMap 源码到底该读哪些地方前两天一位同事踩了个很典型的坑他在一个模拟项目X里用 HashMap 做缓存提前给了一个偏大的初始容量结果内存占用一直很高。他问我HashMap 源码里不是明明写了扩容规则吗怎么我配得越大越浪费我说你只看到了容量没看到加载因子和桶数组的关系。这就是我为什么一直推荐大家认真读 HashMap 源码的原因——它不只是一张“字典”它背后是一整套哈希表工程实现节点结构、哈希扰动、扩容策略、树化条件每个细节都在影响你的线上表现。HashMap 源码详解这个主题看起来知识点很散但其实主线非常清楚一句话HashMap 是基于数组实现的哈希表用链表和红黑树解决哈希冲突用加载因子控制扩容节奏用位运算换执行速度。理解这套主线之后你再去看 put、get、resize看到的就不再是一堆代码而是同一个设计逻辑在不同入口上的体现。这篇内容适合谁适合准备面试的开发者更适合已经在项目里被 HashMap 卡过性能、遇过并发问题的同学。文章不会照着一行行去念源码而是从工程取舍的角度去拆读抽出来的都是你自己写代码时能用得上的东西。我会把核心结构、方法链路、并发问题和调优手段串成一条线读完你至少能回答清楚这么几个问题HashMap 为什么快为什么慢为什么线程不安全以及遇到性能瓶颈时第一步该看哪。2. 核心结构设计拆解2.1 桶数组、链表节点、红黑树节点是怎么配合的HashMap 的底层容器是一个 Node 数组习惯上叫 table。数组的每个位置叫桶一个桶里可能挂一条链表也可能挂一棵红黑树。Node 节点保存四个信息hash 值、key、value 和 next 指针。这里的关键是桶的下标并不是 key 直接决定而是 key 的 hash 经过处理后与数组长度做位运算得到。当多个 key 落进同一个桶就形成冲突。冲突最直接的解决办法是拉链法也就是把冲突的 key 串成链表。链表的问题是查询是 O(n) 的如果同一个桶挂了上万条数据get 性能会直线下降。所以实现里加入了一个树化机制当链表长度超过一定阈值并且桶数组长度也达到门槛时链表会转换成红黑树把查询复杂度从 O(n) 降成 O(log n)。结构解决的问题代价数组桶用下标快速定位需要控制容量和扩容链表处理哈希冲突冲突多时查询慢红黑树链表过长时加速查询维护树结构开销大、节点内存更大这个设计的巧妙之处在于绝大多数场景下链表很短没必要动用树化只有极端哈希冲突出现树化才出手兜底。也就是说HashMap 牺牲了极小部分场景下的树维护成本换来了整体的平均 O(1) 性能。2.2 哈希扰动与下标计算为什么 hash 要先右移再异或在经典实现里put 和 get 的第一步都是拿到 key 的 hashCode然后对这个值做一次扰动把高 16 位与低 16 位异或。代码类似这样的伪代码int h key.hashCode(); int hash h ^ (h 16);为什么要多做这一步因为桶下标是 hash 与数组长度减一相与得到的而数组长度是 2 的幂。比如初始容量 16下标就是 hash 15实际上只用了 hash 的低 4 位。如果 key 的 hashCode 设计得不好高 16 位变化剧烈、低 16 位却总是一样那么这些 key 全都会挤到少数几个桶里形成严重冲突。右移 16 位再异或等于把高位信息“搅拌”到低位里让参与下标计算的低 16 位尽可能多地携带 key 的特征。你可以把它理解成做菜之前先腌一下让味道均匀渗透到每个部位。这个扰动函数是源码里非常经典的一小段虽然只有一行但它用最小成本换来了哈希分布的显著改善。下标计算本身也值得留意用的是(n - 1) hash而不是hash % n。原因很简单位运算比取模快而且当 n 是 2 的幂时(n - 1) hash的结果和hash % n完全等价。这就是为什么 HashMap 会强制数组长度必须是 2 的幂不是为了好看是为了能用位运算替代除法。你在自己设计哈希表时也一样如果能保证长度是 2 的幂就用位运算算下标速度提升在数据量大时非常明显。2.3 容量、加载因子、阈值为什么是 0.75HashMap 默认的初始容量是 16加载因子是 0.75。这两个参数决定了扩容阈值阈值等于容量乘以加载因子。容量 16 时阈值是 12也就是说元素个数超过 12 个下一次 put 就会触发扩容。加载因子为什么是 0.75而不是 0.5 或 1.0这是空间和时间的折中。加载因子过大例如 1意味着桶快被填满才扩容内存利用率高了但哈希冲突概率明显增加链表变长查询变慢加载因子过小例如 0.5冲突变少了查询更快但一半的桶空着内存浪费严重。0.75 是在大量实验和概率模型下冲突率与空间利用率都比较均衡的取值。从源码视角看扩容不是一次性搬完的每次 resize 会重新分配桶数组并重算所有已有节点的位置。如果频繁扩容重哈希成本很高如果扩容太晚查询性能又会下降。所以阈值定在 0.75实际上是在“少扩容”和“少冲突”之间找平衡点。你完全可以改加载因子比如追求更快的查询时设成 0.5追求更低内存时设成 0.8 左右。但大多数业务场景下 0.75 是稳的没有必要乱动。3. 核心方法源码级解读与实操要点3.1 put 方法全链路从找桶到树化都发生了什么put 是 HashMap 最核心的入口。为了好理解我把它拆成几条清晰的路线。第一步计算 key 的扰动 hash。第二步如果 table 为空先执行 resize 初始化。第三步用hash (capacity - 1)计算桶下标拿到桶里的第一个节点。如果桶是空的直接 new 一个 Node 放进去整个 put 结束。如果桶里已经有数据就进入冲突处理逻辑先看第一个节点如果 hash 和 key 都相等说明是同一个 key直接覆盖 value如果第一个节点是红黑树节点就调用红黑树插入方法否则遍历链表逐个比对 key找到了就覆盖没找到就在链表尾部追加新节点。追加完之后检查链表长度如果达到树化阈值就尝试将链表转红黑树。最后modCount加一记录结构修改次数同时判断size是否超过阈值超过就扩容。这里有个容易忽略但很关键的点put返回的是旧值。如果你写代码时用了map.put(key, newValue)却没意识到旧值可能为 null也没有判空很容易在业务逻辑里埋下“看起来没反应”的 bug。我在一个订单状态更新的场景里就遇到过误把 null 返回值当成了异常结果排查了很久才发现是旧值本来就是 null。还有一个细节树化条件不是只链表长度达到阈值就行还需要桶数组长度达到 64。如果容量还很小即便链表已经很长也会先尝试扩容把链表尽量拆散而不是立刻树化。源码里这个条件是双重判断目的就是尽量避免在容量不足时搞一棵不必要的红黑树因为树节点占的内存是普通节点的两倍多。3.2 get 方法全链路为什么查找性能能稳定在 O(1)get 的流程比 put 简单但同样藏了不少细节。第一步也是计算扰动 hash然后算桶下标取出桶里的第一个元素。如果第一个元素就是我们要找的 key直接返回 value如果不是再判断第一个节点是不是红黑树节点是树就走树的查找逻辑不是树就遍历链表。这里有一个常见的误解很多人以为 get 每次都会把整个链表都走一遍所以 HashMap 的查询是数组里 O(1)、链表里 O(n) 的混合复杂度。实际上平均下来链表长度非常短大部分桶里只有一个节点因此整体表现为 O(1)。而一旦某个桶的链表长度涨到 8 以上说明这个 key 的 hash 分布已经很不健康了源码会尝试用树化来兜底。get 方法里还有一个很微妙的点比较 key 时先用hash快速筛选再用equals精确比较。如果两个 key 的 hash 不同那肯定不是同一个 key如果 hash 相同还需要 equals 相等才算匹配。所以源码对 key 的第一条要求是hashCode 和 equals 必须按合约实现。否则你可能 put 进去了get 回来却得到 null而且很难排查——这在后面“常见问题”部分我会专门展开。3.3 resize 扩容链路两倍扩容背后的位运算艺术扩容是整个 HashMap 里最耗时、也最容易出问题的操作。触发条件有两个一是 put 之后 size 超过阈值二是 table 还是空数组时需要初始化。扩容第一步计算新容量和新阈值。在老容量大于 0 时直接把容量和阈值左移一位也就是乘 2老容量等于 0 但阈值大于 0 时用阈值作为新容量如果都为 0就用默认值 16 和 12。扩容真正麻烦的是迁移旧数据。新数组建好后要遍历旧数组的每个桶把桶里的链表或红黑树按新下标拆开重新放置。这里有一个非常漂亮的优化因为容量是 2 的幂所以旧下标和新下标之间只差一个旧容量完全可以用“只看 hash 新增的那一位是 0 还是 1”来决定节点留原地还是搬到新位置。简单写一下这段逻辑if ((e.hash oldCap) 0) { // 留在原下标 lo } else { // 移到 原下标 oldCap }为什么可以这样因为扩容前下标是hash (oldCap - 1)扩容后下标是hash (2 * oldCap - 1)。在二进制上新下标相当于在原下标的高位多了一位这一位正是hash oldCap。为 0新下标不变为 1新下标等于原下标加 oldCap。这个判断不需要重新遍历整条链表去算每个节点的取模值只需要一次位运算这也是 HashMap 源码能保持高效的一个重要原因。从实际使用的角度看扩容迁移过程中会创建新数组会重新挂节点瞬时内存和 CPU 开销都会明显上涨。所以如果你能预估数据量提前指定好初始容量让整个生命周期里尽量少扩容这是最直观的调优点。4. 并发场景下的问题与规避4.1 HashMap 的线程不安全具体表现在哪很多人背结论说 HashMap 线程不安全但不知道不安全在哪里。我用一个模拟场景就够说明问题两个线程同时执行 put且两个 key 计算出的桶下标相同。线程 A 判断当前桶是空的准备往里放节点线程 B 也判断当前桶是空的也准备放节点。结果就是后写的一方可能把前写的一方覆盖掉最终 size 里面显示有两条实际桶里只剩一条数据直接丢。并发下更严重的问题是扩容过程中的“互相踩踏”。两个线程同时触发 resize各自创建新数组然后把旧节点往新数组迁移过程中很可能会把同一个 key 的引用在两个新数组之间来回搬导致数据丢失甚至链表结构错乱。某些老版本实现里还出现过并发扩容导致链表成环的问题表现为某个 key 永远 get 不到或者 CPU 被打满这是非常典型的源码级事故。我建议大家在写代码时养成一个习惯只要 HashMap 会被多个线程同时写就不要再碰原生 HashMap。不要相信偶尔几次本地测试没出问题就觉得没事并发缺陷是概率性的线上流量一大就会现形。替代方案很明确要么用自带并发控制的哈希容器要么在外部加锁把所有 put/get/resize 串行化。4.2 并发压测一跑size 就出卖了它为了让你对“不安全”有个量化感知我拆一个常见的压测小实验定义一个 HashMap初始容量 16加载因子 0.75。用一个循环让 8 个线程各写 10000 个不重复的 key理论上最终 size 应该是 80000。实际跑下来size 经常只有七万出头而且每次结果都不一样。如果哈希冲突再多一点丢的数据会更夸张。这个现象背后的原因就是我在 4.1 里说的覆盖和扩容竞态。单线程下 HashMap 的 put 是原子的吗不是但不会出问题多线程下两个线程同时修改同一个桶的链表头或者同时触发 resize就可能把别人的写入吞掉。所以在需要高并发读写的项目里别把 HashMap 当默认容器。如果是读多写少可以考虑给读操作加读写锁如果是写也很多直接换线程安全的哈希结构更省心。源码之所以单独拎出线程安全问题就是想提醒大家HashMap 的性能优势有一个前提就是单线程环境。把这个前提忘了性能优势很快就会变成事故现场。5. 从源码到调优几个高频追问5.1 初始容量到底怎么算才不浪费很多文章会说“已知数据量时指定初始容量”但没告诉你具体怎么指定。源码里有个方法会把传入的容量调整成大于等于它的最小 2 的幂所以你不能直接填数据量。比如预计要放 1000 个元素如果你初始化成 1000真实容量会被翻成 1024阈值是 1024 乘以 0.75约等于 768还没放满就已经扩容了等于白指定。正确做法是反推。要放 N 个元素且不扩容容量 C 需要满足C * 0.75 N所以 C 至少是N / 0.75再向上取到 2 的幂。以 1000 为例1000 / 0.75 1333.3向上取 2 的幂是 2048这样阈值是 1536能稳稳放下 1000 个元素还不浪费太多内存。预计元素数直接设容量的阈值反推容量后的阈值是否触发扩容10001024阈值7682048阈值1536会10002048阈值15362048阈值1536不会这个计算看起来简单但实际项目里很多人要么不设要么拍脑袋设一个很大的数。不设会遇到扩容拍脑袋设太大则会导致桶数组占用大量内存。最稳的做法是预估数据量按公式算出一个容量再结合内存预算微调。如果你拿不准宁可设得稍大一点也别让它频繁扩容。5.2 为什么重写 equals 必须重写 hashCode源码里 get 的第一步永远是拿 hashCode 定位到桶第二步才用 equals 比较 key。如果你只重写了 equals不重写 hashCode那么两个业务上相等的对象很可能 hashCode 不一样就会定位到不同的桶导致你按 key A 存进去用 key Bequals 相等去查结果得到 null。我见过一个订单类的真实案例订单号相同就认为同一个订单但类里只重写了 equals没有重写 hashCode。结果用同一个订单号在不同时点构造两个对象第一次 put 成功第二次 get 返回 null业务判断成了“订单不存在”。排查过程很曲折最后通过把 hashCode 改成都基于订单号计算问题立刻消失。从源码实现看HashMap 对 key 的要求不只是“能用”还需要满足哈希契约equals 相等的两个对象hashCode 必须相等hashCode 相等的两个对象equals 不一定相等。前者是正确性要求后者是效率差异。所以写自定义类当 key 的时候equals 和 hashCode 一定要一起重写并且保证参与 hashCode 计算的字段与参与 equals 判断的字段一致。只要字段变化会导致 equals 判等就要让 hashCode 也跟随变化。6. 常见问题与排查技巧实录6.1 常见问题速查表现象可能的源码原因排查方向插入后查询不到自定义 key 的 equals/hashCode 不一致检查两个方法是否一起重写接口偶尔变慢哈希碰撞严重链表过长甚至频繁树化看是否是连续低位相同的 key内存占用过高初始容量过大或者加载因子设得过小按预估数据量反推容量多线程 put 后 size 不增加并发覆盖或扩容竞态换线程安全容器或加锁频繁扩容导致耗时长初始容量设定不足按公式预估并设置容量老版本并发出现死循环并发扩容期间链表结构错乱禁止并发使用原生 HashMap这张表我建议你收藏到项目笔记里。排查 HashMap 问题第一件事不是看日志而是先确认你的使用场景符不符合源码设计的前提单线程、可预估容量、key 的哈希分布良好。只要有一条不满足都可能是线上问题的源头。6.2 一个典型性能排查过程把哈希分布拉到桌面上看我曾经在一个后台接口优化里做过一次 HashMap 层面的验证。接口会从缓存里读取大量配置项数据量大约几十万线上偶尔出现耗时抖动。第一反应不是看 HashMap 源码而是先写了个小工具把所有 key 的 hashCode 和它们落进的桶号统计出来。结果发现大量 key 的桶号只集中在少数几个桶里其中一个桶的链表长度超过了 100。原因也很朴实业务侧生成的 key 是一串连续编号本身哈希分布没问题但有人在拼接 key 的时候做了某种会让低位趋同的加工。定位到这一步后我给这些 key 增加了一个不计入业务含义的盐值来重新计算 hash也就是在进入 HashMap 前先做一次自定义的扰动。改完之后同量数据集下最大链表长度从 100 多降到了个位数接口耗时抖动也消失了。这个例子想说明的是源码里的扰动函数只是通用兜底它不能保证每个自定义 key 都均匀分布。真实项目里你自己用代码拼接出的 key 很可能就踩中低位聚集的坑。排查 HashMap 性能不要只盯着 CPU 和内存更直接的办法是把桶的负载分布打印出来用数据判断冲突是否异常。6.3 读源码的几个实操心得读完 HashMap 源码之后我最想分享的心得是读源码别按顺序从头读到尾那样特别容易陷进细节里出不来。我自己的读法是分三轮。第一轮看主结构把 table、Node、TreeNode、阈值这些成员变量画成一张草图第二轮跟着 put 走一遍完整链路画出好几种分支路径比如桶空、链表中、树化、扩容第三轮再看 get 和 resize重点关注那些看起来“多余”的判断这些判断往往才是防 bug 的关键。另外不要只看一遍就完事。HashMap 的源码在不同实现版本里细节会有差异比如并发问题、树化条件、节点插入位置都有变化。如果你在面试中被问到最好能说出你本地环境对应实现的行为而不是照搬网上的统一答案。自己写个测试用例故意构造极端哈希观察源码怎么处理比背十篇源码解析都管用。还有一个很小但很实用的技巧看源码时把hash (capacity - 1)和hash oldCap这两行单独抄出来手动算两个数对比一下。你只要亲手算过一次就会彻底记住为什么 HashMap 要求容量是 2 的幂为什么扩容之后节点要么留在原地要么跳到原位置加旧容量。这个理解一旦建立后续再看任何哈希表实现都会轻松非常多。