HashMap 源码读透它Java 集合面试与实战就稳了一半。这篇文章我基于源码层面详细拆解其核心数据结构、关键方法逻辑、扩容与树化机制并结合实际踩坑经验帮你把这块硬骨头啃下来。1. 整体设计为什么 HashMap 能兼顾查找与插入很多人一开始接触 HashMap只记住它是“数组加链表”但没深想为什么是这种组合。数组的查找效率是 O(1)但插入和删除需要搬移元素链表的插入删除是 O(1)但查找需要遍历。HashMap 的数组加链表结构本质上是拿哈希函数把 key 映射到数组下标冲突的 key 用链表挂起来这样大部分情况下查找只需一次定位加少量比较极端情况下才需要遍历链表。从全局看HashMap 的核心成员变量就几个NodeK,V[] table、size、threshold、loadFactor。table 是真正存数据的桶数组size 是已存储的键值对数量loadFactor 是负载因子threshold 是扩容阈值等于 capacity 乘以 loadFactor。这些变量在源码里都有明确注释读源码时建议先把这几个字段的语义搞清后面看 put、resize 就会顺畅很多。站在源码角度HashMap 在 Java 8 之后做了几个重要演进。第一是链表长度超过阈值默认 8且数组长度达到 64 时链表转红黑树把最坏情况从 O(n) 降到 O(log n)。第二是扩容时不再重新计算每个 key 的 hash而是通过(e.hash oldCap) 0判断元素是留在原位置还是移动到“原位置加 oldCap”的新位置这个优化对扩容性能提升非常明显。第三是引入了TreeNode内部类树化后的节点同时保留 next 字段方便在拆分红黑树时重新组织成链表。拿实际场景来说假设你往 HashMap 里存了 1 万条用户记录key 是用户 ID。如果哈希函数设计得合理数据会均匀散落在各个桶里每次 get 平均只要比较一两次。如果哈希函数很差所有 key 都映射到同一个桶那查找就会退化成遍历链表性能会急剧下降。HashMap 内部通过扰动函数和高低位异或来降低这种风险这也是源码里hash()方法存在的意义。2. 核心方法源码拆解put、get 与 hash 扰动背后的逻辑2.1 hash 方法为什么要把高 16 位异或到低 16 位先看hash()方法的源码static final int hash(Object key) { int h; return (key null) ? 0 : (h key.hashCode()) ^ (h 16); }这个方法做的事很简单拿到 key 的 hashCode然后把高 16 位和低 16 位做异或。为什么这么做因为计算数组下标时用的是(n - 1) hashn 是数组长度通常是 2 的幂。当 n 比较小的时候比如默认 16n - 1的二进制是 0000...00001111只有低 4 位参与运算高位信息全部丢失。这会导致哈希冲突概率增大尤其是当 key 的 hashCode 高位差异大、低位差异小时。把高 16 位异或到低 16 位相当于把高位信息混合到低位里让(n - 1) hash的结果更分散。这本质上是一个“搅动”过程虽然会增加一次异或运算的开销但能显著降低冲突属于典型的用时间换空间和性能的做法。实际开发中如果你自定义对象作为 key重写 hashCode 时也要注意高位的分布。比如用 String 作为 keyString 的 hashCode 算法本身已经比较分散但如果你用某些业务 ID 直接做 key而这些 ID 的二进制低几位很相似例如连续递增的数字高位异或就能帮你把差异扩散到低位。2.2 put 方法从定位到插入的完整链路put(K key, V value)的源码逻辑可以拆成几个阶段。第一阶段计算 hash然后调用putVal(hash(key), key, value, false, true)。第二阶段在putVal里先检查 table 是否为 null 或长度为 0如果是就调用resize()初始化数组。第三阶段根据(n - 1) hash定位到具体桶如果桶为空直接新建 Node 放进去。如果桶不为空说明发生碰撞此时会判断桶里的第一个节点是否和当前 key 相同p.hash hash ((k p.key) key || (key ! null key.equals(k)))相同就直接覆盖 value。如果第一个节点是 TreeNode 类型说明这个桶已经树化走红黑树的插入逻辑。否则遍历链表找是否有相同 key如果找到了就覆盖并返回旧值如果遍历到链表尾部都没找到就尾插法插入新节点。这里有个容易忽略的细节尾插法是在 Java 8 引入的Java 7 用的是头插法。头插法在多线程扩容时可能出现环形链表导致 get 操作死循环。Java 8 改成尾插法后虽然多线程并发 put 仍然可能丢数据但至少不会出现环形链表这种极端故障了。链表插入后还要检查当前桶的链表长度是否达到TREEIFY_THRESHOLD8如果达到并且数组长度大于等于 64就调用treeifyBin把链表转成红黑树。如果数组长度还没到 64即使链表很长也只会执行resize()扩容而不是直接树化。原因是数组太小的时候扩容比树化更划算能把长链表重新分散开。最后如果size threshold就执行扩容。这里 size 增加的是 HashMap 中键值对的总数不是某个桶的节点数所以扩容条件是全局的。每次 put 完如果插入的是新 keysize 会加一然后和 threshold 比较超过就扩容。2.3 get 方法查找路径上的三个分支get(Object key)调用getNode(hash(key), key)同样先判断 table 不为空且长度大于 0再定位到桶。桶为空直接返回 null。桶不为空时三个分支分别处理第一桶首节点就是目标节点直接返回。这也是为什么把最近插入或最先插入的节点放在链表头部的设计考量Java 8 是尾插法所以越早插入的节点越靠前。第二首节点是 TreeNode走红黑树的getTreeNode查找。第三普通链表就循环遍历比对 hash 和 key。红黑树查找的逻辑相对复杂但核心是根据 key 的 hashCode 或 Comparable 接口来判断左右子树方向如果节点是 TreeNode 且有next字段也可能退化为链表式遍历。对普通应用来说不需要深入红黑树的旋转细节但理解“树化之后查找复杂度是 O(log n)”这个结论就够了。关于 key 为 null 的情况HashMap 允许一个 null key。hash(null)返回 0所以 null key 会落在数组下标 0 的位置。这也是 HashMap 和 Hashtable 的一个区别Hashtable 不允许 null key 和 null value。2.4 resize 扩容初始化与翻倍的细节处理resize()方法承担两个职责初始化数组和扩容。初始化数组中如果 oldCap 大于 0说明是扩容新容量变成旧容量的两倍threshold 也变成两倍。如果 oldCap 等于 0 且 oldThr 大于 0说明创建 HashMap 时指定了初始容量threshold 就是那个大于等于 initialCapacity 的 2 的幂。如果两者都为 0就用默认值即容量 16threshold 12。扩容时还有一个关键点为什么新容量一定是两倍因为 HashMap 要求容量必须是 2 的幂这样(n - 1) hash才能均匀分布且扩容后元素位置变化时只需看 hash 的二进制特定位。如果容量不是 2 的幂哈希分布会不均匀冲突概率会增大。元素迁移是扩容的核心难点。Java 8 的做法是遍历每个桶对桶里的每个节点判断(e.hash oldCap)是否为 0。为 0 表示该节点在新数组中的位置和旧数组一样不为 0 则表示位置是“旧位置 oldCap”。这个判断很巧妙因为扩容后 n 变成旧 n 的两倍n - 1的有效位多了一位多出来的那一位恰好是 oldCap 对应的二进制位。hash 在该位是 0 就留在原地是 1 就移动。如果桶里是红黑树扩容时会调用split方法把红黑树拆成两条链表一条留在原位置一条移动到新位置。如果拆分后的链表长度小于等于 6还会把树退化成链表因为此时链表效率已经优于红黑树了。这个退化阈值是UNTREEIFY_THRESHOLD默认 6先树化再退化中间留了个缓冲避免频繁震荡。3. 关键设计细节树化阈值、负载因子与容量计算的权衡3.1 为什么树化阈值是 8 而不是 10 或 6源码注释里提到根据泊松分布当负载因子为 0.75 时桶中链表长度达到 8 的概率约为千万分之六。也就是说在哈希函数正常的情况下链表长度到 8 已经是非常极端的情况了。此时树化是为了抵御极端哈希冲突或恶意攻击而不是常态优化。选 8 作为阈值还有一层考虑是时间复杂度和空间开销的平衡。红黑树节点TreeNode比普通Node多了一些指针和颜色标记内存开销更大。如果阈值设得太低比如 6可能在 hash 正常时也偶尔触发树化白白增加内存消耗。而设成 8正常场景几乎不会触发只有真正冲突严重时才付出这个代价。树化和退化的阈值设计也很有意思。树化阈值是 8退化阈值是 6两者之间差了 2。如果只有一个阈值比如都用 8那么在链表长度在 8 左右波动时会反复触发树化和退化性能开销很大。两个阈值形成滞回避免这种抖动。实际使用中如果你的业务 key 自身 hashCode 实现很差导致大量冲突HashMap 会频繁树化和扩容性能依然会大幅下降。这时候应该优先优化 key 对象的 hashCode 算法而不是调整 HashMap 的阈值参数。源码里这两个阈值都是 package-private 的 static final不能通过外部配置修改想调整只能改源码或者换别的方式减少冲突。3.2 负载因子 0.75空间和性能的经典折中负载因子是容器中元素个数与容量的比值默认 0.75。含义是当键值对数量达到容量的 75% 时就触发扩容。如果调低负载因子比如 0.5数组会更早扩容桶会更稀疏冲突更少但内存浪费更多。如果调高负载因子比如 1.0数组利用更充分但冲突变多查找和插入性能下降。0.75 这个值是从多个维度权衡出来的。它在时间和空间成本上取得了较好的平衡也是工程界广泛验证的经验值。源码注释里明确说0.75 是空间和时间成本的折中。如果你能预知键值对数量可以在创建 HashMap 时通过容量构造器指定初始容量提前分配好空间减少扩容次数。计算初始容量时有一个经典公式expectedSize / 0.75 1。比如你确定要存 1000 个元素那么初始容量应该设为1000 / 0.75 1 1334然后 HashMap 内部会通过 tableSizeFor 方法计算出大于等于这个数的 2 次幂即 2048。这样能避免在插入到 750 个元素时就触发扩容减少一次全量迁移。3.3 tableSizeFor 方法找出不小于 cap 的 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; }这个方法的原理是把 cap 减一后通过一系列无符号右移和按位或操作把最高位之后的低位全部置为 1最后加一得到 2 的幂。为什么先减一因为如果 cap 本身就是 2 的幂比如 16不减一的话结果会是 32不符合“大于等于 cap 的最小 2 的幂”的要求。减一之后16 变成 15位移后是 15加一得到 16刚好正确。这个方法不依赖循环或乘法纯位运算效率非常高。它保证了扩容阈值的对齐也保证了(n - 1) hash的均匀性。这也是为什么通过构造器指定非 2 次幂容量时HashMap 内部实际容量会被调整为 2 的幂。举个例子如果你指定初始容量是 10tableSizeFor(10) 的结果是 16。如果你指定 100结果是 128。了解这个逻辑对预估内存占用有帮助你会发现 HashMap 实际容量往往会比你期望的初始容量大不少这在大数据量场景下需要纳入内存预算。4. 实操经验源码之外的避坑指南4.1 指定初始容量避免频繁扩容很多人创建 HashMap 时直接new HashMap()不指定容量然后在循环里插入几万个元素。这会触发多次扩容每次扩容都要重新 hash 并迁移所有元素性能损耗很大。如果插入数据前能预估数量一定要用new HashMap(expectedSize)。这里有个细节前面提到用expectedSize / 0.75 1计算初始容量但有研究表明即使是这个公式在某些 JDK 版本下可能还是不够精确建议再乘一个安全系数。比如 Guava 库的Maps.newHashMapWithExpectedSize就是基于类似公式并加上额外冗余来实现的。如果不用 Guava自己按 1.5 倍预估也可以宁多勿少多出一点空间比你多几次扩容要划算。扩容的代价不只是遍历迁移元素还会触发树化和退化逻辑。比如一个长链表可能在扩容后被拆成两个链表红黑树也可能被拆成两条链表。整个过程涉及大量指针操作和内存分配在响应时间敏感的场景里一次扩容可能会导致显著的延迟尖刺。4.2 并发场景下不要直接用 HashMapHashMap 不是线程安全的。多线程同时 put 时可能发生数据覆盖。比如两个线程同时往同一个空桶里插入节点各自都创建了 Node后插入的会覆盖先插入的丢失数据。虽然 Java 8 修复了链表成环问题但数据丢失和并发修改导致的异常依然存在。如果并发度不高可以用Collections.synchronizedMap(new HashMap())包装但它的锁粒度是整个 Map并发性能一般。如果读多写少用ConcurrentHashMap更合适它把整个 Map 分成多个 Segment 或使用 CAS 加局部锁并发性能好很多。如果你的场景是单线程读、单线程写但读多可以考虑CopyOnWriteMap不过这类场景在实际项目里出现得比较少。一个常见的问题是为什么 HashMap 在高并发下会出现死循环这是 Java 7 头插法扩容导致的Java 8 改成尾插法后已经修复。但如果你的应用还在跑 Java 7这个问题仍然存在如果已经升级到 Java 8 以上不用太担心死循环但数据丢失问题还是要靠并发容器解决。4.3 重写 equals 和 hashCode 的坑HashMap 的位置由 key 的 hashCode 决定比较是否相同会先用判断再用equals判断。所以如果你把自定义对象当 key不重写 hashCode那么不同对象的 hashCode 大概率不同即使它们的业务字段完全一样也会被当作不同的 key导致你 get 的时候取不到值。最佳实践是重写 equals 时必须同时重写 hashCode且相等对象的 hashCode 必须一致。equals 中用到的字段都应该参与 hashCode 的计算。如果你用了不可变类作为 key比如 String 或 Integer就不需要担心这个问题。排列一个反例有一个 Person 类字段是 id 和 name你只重写了 equals 没重写 hashCode。你往 HashMap 里 put 了一个 id1、name张三 的 Person然后又 new 了一个相同字段的 Person 去 get能得到值吗不能因为 hashCode 不同定位到了不同的桶。这属于非常经典的面试题但也是实际代码里真实存在的隐患。4.4 遍历时删除元素必须用迭代器HashMap 提供了entrySet()、keySet()、values()等遍历方式。如果你在遍历过程中直接调用map.remove(key)会抛出ConcurrentModificationException因为 modCount 已经变了。正确做法是用Iterator遍历并调用iterator.remove()方法删除。Iterator.remove()内部会维护 expectedModCount删除后会同步更新不会触发并发修改检测。另一个替代方案是先用遍历收集要删除的 key遍历结束后再统一 remove。这在一次要删除大量元素时性能更好因为不会在遍历过程中频繁修改结构。如果你是在 for-each 循环里用map.remove一旦触发异常你的程序可能直接崩溃特别是在定时任务里扫描过期数据时这类 bug 经常半夜出现在告警里。用迭代器写法虽然代码多了几行但安全性和可读性都会更好。4.5 HashMap 允许 null 的特性与坑HashMap 允许一个 null key 和任意多个 null value。Hashtable 和 ConcurrentHashMap 都不允许 null keyConcurrentHashMap 也不允许 null value。在跨容器迁移代码时这一点要特别注意。假如你把代码从 HashMap 迁移到 ConcurrentHashMap原来存储在 null key 下的数据会直接抛NullPointerException你可能要费很大劲才能定位到问题在哪。反过来如果把 ConcurrentHashMap 的 null value 放到 HashMap 里语义上没问题但可能掩盖了业务逻辑的一些边界情况。还有一个相关坑如果你用 Optional 或自定义空对象来消除 null value会多一层包装增加不必要的内存开销和代码复杂度。对于 HashMap 来说null value 是合法的用它来表达“不需要值”通常没问题。5. 高频问题排查实录从源码层面定位疑难杂症5.1 为什么 put 之后 get 不到值这个问题有很多种原因但最常见的两种是key 对象的 hashCode 不稳定或者 key 对象被修改了。如果你用一个可变对象当 key放入 HashMap 后修改了它的某个字段它的 hashCode 会变HashMap 定位下标时用新 hashCode 算出的位置和原来的位置不同自然 get 不到。源码里getNode的查找过程是先算 hash 找桶再比对桶里的链表。如果你 key 变了hash 变了桶对不上根本不会走后面的 equals 逻辑。这也是为什么源码注释和各类文档都建议用不可变类作为 HashMap 的 key。排查流程一般是先看 key 的 hashCode 在 put 和 get 时是否一致再看 equals 和 hashCode 是否满足契约最后检查是否存在多线程并发修改。很多时候这类问题不是 HashMap 本身的 bug而是使用方式踩了坑。5.2 为什么容量明明是 100实际用了这么大空间这是因为 HashMap 内部容量是 2 的幂你指定的 100 会被 tableSizeFor 调整为 128而 threshold 是 96。如果你创建时用了new HashMap(100)put 到第 97 个元素时就会触发扩容变成 256。所以真正能 “不满不扩” 的初始容量是预期元素数 / 0.75 1而不是直接传元素个数。另外capacity乘以负载因子算出的 threshold 只是一个阈值而不是一个硬性上限。即使 size 超过 threshold 也还能继续 put只是扩容会被触发。扩容后 threshold 变为新容量乘以负载因子整个容器会继续正常工作。如果对内存占用敏感可以在 put 完所有数据后用HashMap提供的构造器重新复制一份或者调用clear()后重新 put但这在工程上很少用。更推荐的是在创建时就预留好容量减少这种内存浪费。5.3 为什么数组长度必须是 2 的幂这个问题的核心在于(n - 1) hash这个下标计算方式。只有 n 是 2 的幂时n - 1的二进制才是低位全 1高位全 0。这样和 hash 做按位与时结果只取决于 hash 的低位部分而且能覆盖 0 到 n-1 的所有可能值不会出现某些下标永远空着的情况。如果 n 不是 2 的幂比如 n15n - 1是 14二进制是 1110最低位是 0那么所有 hash 算出来的下标最低位永远是 0奇数下标永远不会被使用浪费近一半空间。所以 HashMap 要求容量是 2 的幂是为了保证哈希值的比特位能被充分利用。在扩容时元素位置的变化也依赖于这个特性扩容后 n 加倍n - 1多了一位 1只需要看 hash 的对应位是 0 还是 1就能决定元素留在原地还是移动到高位区间。如果容量不是 2 的幂扩容时每个元素都要重新计算下标性能会差很多。5.4 HashMap 在 JDK 7 与 JDK 8 之间的核心差异很多人面试时被问到这个其实核心差异就几条。数据结构上JDK 7 只有数组加链表JDK 8 加入了红黑树链表过长时树化。插入方式上JDK 7 是头插法JDK 8 是尾插法。哈希计算上JDK 7 的 hash 方法扰动次数更多JDK 8 简化成一次异或但效果依然可靠。扩容迁移上JDK 7 需要重新计算每个元素的 hash 和下标JDK 8 通过高位判断优化。JDK 7 的头插法在多线程扩容时可能造成链表环导致死循环JDK 8 的尾插法避免了这个问题。但 JDK 8 的多线程 put 依然存在数据丢失风险所以并发场景还是不能用 HashMap。JDK 8 引入红黑树后HashMap 的内存占用有所增加因为 TreeNode 节点是普通 Node 的两到三倍大小。如果你确定不会出现极端哈希冲突可以在某些场景下使用自定义类或调整 hash 策略避免触发树化。当然绝大多数业务场景不需要做这种微操默认配置已经足够好。6. 一个亲手验证过的实战案例从源码角度优化一个慢接口我之前优化过一个内部系统的数据汇总接口接口每次要读取大约 2 万条记录然后按业务 ID 聚合。最初实现直接new HashMap()在循环里 put接口平均耗时从 300ms 一路涨到 2 秒多。用火焰图一分析发现大量时间消耗在 HashMap 扩容和 rehash 上。优化方式很简单先统计业务 ID 的种类数大约 1.2 万然后new HashMap(16000)16000 是 12000 / 0.75 1 之后再取整的近似值这样避免了多次扩容接口耗时降到了 80ms 左右。这个案例里其实没有涉及任何特殊技巧纯粹是尊重了 HashMap 扩容机制。还有一次遇到连续 key 导致的哈希冲突当时的 key 是产品 ID看起来像纯数字但低 8 位高度相似。HashMap 的扰动函数把高位异或到低位之后冲突概率已经降低但那批数据的 hashCode 本身分布不均匀还是有一两个桶挂了几十上百个节点。后来把 key 改成 String 类型String 的 hashCode 算法天然分散冲突就缓解了。这类案例说明一个道理HashMap 的设计已经做了很多优化但最终的数据分布质量还是取决于 key 的 hashCode 质量。如果业务上能预期到某些 key 形态会触发冲突最好在设计阶段就规避而不是等性能问题暴露后再去排查。7. 面试高频追问清单从源码中提炼必考点面试官通常不会只问你 HashMap 的 put 过程他们会一层层深入。最基本的是HashMap 在 JDK 8 中的数据结构是什么put 的流程是什么。进阶一点的是为什么链表转红黑树的阈值是 8为什么负载因子是 0.75。再难一点的是扩容时元素怎么迁移JDK 7 和 JDK 8 差异在哪。还有一个特别经典的追问HashMap 的容量为什么是 2 的幂。这个问题可以从下标计算、扩容迁移、tableSizeFor 三个角度回答。你如果能写出(n - 1) hash的二进制过程面试官通常就会满意。另一个高频追问是HashMap 在并发环境下会有什么问题。你要能说清数据覆盖、modCount 检测失败、JDK 7 的循环链表死循环这几个点。同时要能对比 ConcurrentHashMap 的做法从锁粒度、CAS 运用、扩容机制等方面说出区别。如果面试官再往深了问就可能涉及红黑树的插入、删除、左旋右旋。对这一层我的建议是理解红黑树的核心性质根黑、叶黑、红节点的子节点必须黑、任意路径黑节点数相同但不需要完整复现旋转调整的每个细节。你可以坦诚地说红黑树的旋转逻辑看源码能看懂但脱离源码手写确实困难面试官基本能接受。在我个人的经验里很多人对 HashMap 源码停留在“背结论”的阶段比如数据结构和阈值但对背后为什么如此设计缺乏理解。源码阅读这件事结论重要推导过程更重要。如果你能把hash扰动、tableSizeFor、resize这几个方法的位运算逻辑完全吃透遇到类似的数据结构设计问题时你会有更强的迁移能力。最后分享一个小技巧读 HashMap 源码时不要在一开始就死磕红黑树。先把 Node 链表版本的执行路径走通把 put、get、resize 的流程画一遍再去看 TreeNode 相关逻辑。红黑树只是链表在极端情况下的替代品核心的设计思想依然围绕数组加链表展开。理清了主干再深入分支会顺畅得多。