第一次被 HashMap 拖到凌晨三点是在一个看似毫无波澜的版本上线之后。监控面板上某个订单查询接口的 P99 从 40 毫秒慢慢爬到了两秒随后几台机器的 CPU 直接被打到 100%线程栈抓下来一堆线程卡在HashMap.get上转圈。那是 JDK7 时代一个多线程共享的缓存容器在并发扩容时被插成了环形链表get 操作顺着环永远走不到头。从那次事故之后我才真正愿意坐下来把 HashMap 的每一行源码读完把hashCode、equals、负载因子、扩容阈值这些看起来只是面试八股的东西当成线上稳定性的必修课。这篇内容就是那次“补课”的产物。我会把 HashMap 的底层实现原理、扩容机制从头到尾拆一遍把源码里那些藏在注释和位运算背后的设计意图挖出来再把我这些年面试别人和被面试时反复遇到的高频问题整理成一份可以直接对照的答题清单。同时我也会分享几个真实踩过的坑容量初始化写成多少才合适、可变对象当 key 会出什么幺蛾子、为什么扩容时元素要么原地不动要么整体后移一个 oldCap以及 JDK7 和 JDK8 在链表插入顺序上的差别到底意味着什么。不管你是刚学完集合框架想弄明白“为什么容量非得是 2 的幂”的新手还是写了几年业务代码、想搞清楚线上偶发卡顿到底是不是哈希冲突引起的进阶选手这篇内容都能给你一份能直接拿去用的参考。我把原理、源码、参数计算、面试答法和避坑经验放在一起讲尽量做到看完能自己讲出来也能自己动手写一个最小可用的版本。1. 从一个真实的线上问题说起为什么值得死磕 HashMap1.1 那次 CPU 打满的凌晨到底发生了什么那次事故的根因并不复杂一个静态的HashMap被当成了本地缓存多个业务线程同时往里放数据正好撞上扩容。JDK7 的transfer方法在迁移链表时用的是头插法也就是新桶里的节点顺序和原链表完全颠倒。并发场景下两个线程同时做迁移指针相互引用最终形成了A.next B且B.next A的环形结构。之后所有落到这个桶上的查询都会陷入死循环CPU 自然被打满而且这种问题不会抛异常、不会打日志只表现为线程卡死排查成本极高。这件事给我最大的教训是HashMap 的设计目标是单线程下的高性能散列表它从来没有承诺过并发安全。JDK8 把插入方式改成了尾插法解决了环形链表这个致命问题但并发下的数据覆盖、size 计数不准、扩容丢失节点这些毛病依然存在。如果你真的需要并发场景下的键值容器那ConcurrentHashMap才是正解用分段锁或者 CAS 加 synchronized 保证桶级别的并发安全比你自己在外面套一把大锁要高效得多。理解这个边界之后再回头看 HashMap 的源码你会发现它的每一个设计细节都在为“单线程下尽可能快”这个目标服务位运算替代取模、容量强制 2 的幂、扰动函数压缩高位信息、链表到红黑树的转换阈值。这些不是炫技而是在真实数据分布下反复权衡的结果值得逐个拆开看。1.2 HashMap 到底解决了什么问题从数据结构的角度讲HashMap 要解决的是查找效率问题。数组的随机访问是 O(1)但按值查找是 O(n)链表的插入删除是 O(1)但查找是 O(n)。哈希表把两者的优点拼起来用哈希函数把 key 映射成一个整数再用这个整数定位到数组下标理想情况下一次就能命中查找、插入、删除的平均复杂度都逼近 O(1)。它提供的能力很朴素以键值对的形式存储数据通过 key 快速拿到 value允许一个 null key 和多个 null value不保证遍历顺序稳定。但正是这种朴素让它在工程里无处不在配置缓存、对象去重、分组统计、图结构建模、去重计数、词频统计、接口返回结果的本地索引几乎所有需要“按某个标识快速找东西”的场景第一反应都是 HashMap。代价也很明确哈希冲突无法完全避免。两个不同的 key 算出同一个下标就必须有一个位置能挂多个元素这就是链地址法。冲突一旦变多链表变长查找就退化到 O(n)。所以 HashMap 真正的技术含量不在“怎么用数组存”而在“怎么把冲突控制在可接受范围内”以及“冲突严重时怎么兜底”。扩容机制和红黑树转换本质上都是这个问题的答案。1.3 这篇内容适合谁以及我建议的阅读顺序如果你是完全的新手建议从第 2 章开始顺着读先把“数组加链表加红黑树”这个骨架建立起来再看第 3 章的 put/get 流程最后回到第 4 章的扩容。扩容是整个 HashMap 里最绕的部分前置知识不够直接啃会很痛苦。如果你是准备面试的可以直接跳到第 5 章的题目清单和答题框架再回头补第 4 章因为扩容几乎是每一轮技术面必问的深水区。如果你是在线上出过问题的老兵第 6 章的踩坑记录可能对你最有用容量预设怎么写、loadFactor 什么时候该调、可变 key 有多坑、什么时候干脆换掉 HashMap。这些内容在教科书里基本看不到都是一次次故障和性能压测换来的。提示本文涉及的源码基于 JDK8 的 HashMap 实现个别细节在 JDK7 中不同我会在对应位置标注出来。不同厂商的 JDK 发行版在实现上可能有微调但整体设计思路一致。2. 拆开 HashMap 的骨架数组、链表、红黑树是怎么配合的2.1 数组是骨架链表是补丁红黑树是保险把 HashMap 想象成一栋楼的信箱区最外层是数组NodeK,V[] table也就是信箱墙本身。每个数组位置叫一个“桶”bucket桶里放的是一个链表或者一棵红黑树。你拿着 key 算出一个下标就知道该去哪个桶里翻找桶里可能有零个、一个或者多个元素。数组的长度决定了桶的数量也决定了冲突的概率。桶越多冲突越少但内存占用越大桶越少内存省了冲突变多链表变长查找变慢。这就是为什么需要扩容也是为什么需要一个负载因子来权衡。链表是解决冲突的第一层手段也就是所谓的“拉链法”或者链地址法冲突的元素挂在同一个桶下面形成一个单向链表。当链表长度达到阈值 8 且数组容量达到 64 时链表会转换成红黑树把最坏情况下的查找复杂度从 O(n) 优化到 O(log n)。注意链表转红黑树的条件是两个缺一不可。链表长度达到 8 只是其一如果当前数组容量小于 64HashMap 会选择先扩容而不是树化因为小容量下冲突多本来就是容量太小导致的扩容比树化更划算。红黑树是一种自平衡二叉搜索树插入删除时通过变色和旋转维持大致平衡最坏查找路径长度被限制在 2 倍最短路径以内。用在这里的好处是即使哈希函数被恶意构造、大量 key 落到同一个桶查找性能也不会崩到线性。代价是每个树节点比普通链表节点多维护 parent、left、right、prev、red 五个字段内存开销明显更大所以只有链表足够长时才值得转换。2.2 容量为什么非得是 2 的幂这是 HashMap 里最经典的设计之一答案有两层。第一层是索引计算HashMap 用(n - 1) hash来算数组下标这里的 n 是容量。当 n 是 2 的幂时n - 1的二进制是低位全 1比如 16 - 1 15 0b1111此时运算的结果恰好等价于hash % n但位运算比取模快得多。计算机里除法和取模是相对昂贵的操作能用位运算替代就能省下可观的 CPU 周期。第二层是扩容时的元素迁移。容量翻倍后元素的新下标只可能是两个值原来的下标或者原下标加上旧容量。原因在于新容量是旧容量的两倍newCap - 1比oldCap - 1在二进制上多了一个高位 1这个位正好来自 hash 中对应位置的 bit。判断方法极其简单(e.hash oldCap) 0就留在原位否则移动到原下标 oldCap。不需要重新计算 hash也不需要重新取模这在扩容时是巨大的性能节省。反过来说如果容量不是 2 的幂n - 1的二进制里就会出现 0 位与运算后某些下标永远取不到数组空间被浪费同时冲突分布也会变差。所以哪怕你通过构造方法传入一个不是 2 的幂的初始容量HashMap 也会用tableSizeFor把它向上取整到最接近的 2 的幂。比如传 17实际容量会是 32传 100实际容量会是 128。2.3 hash() 里的那次右移 16 位到底在干嘛JDK8 的哈希扰动函数只有一行static final int hash(Object key) { int h; return (key null) ? 0 : (h key.hashCode()) ^ (h 16); }核心是h ^ (h 16)也就是把 hashCode 的高 16 位无符号右移到低位然后和原值做异或。这么做的原因是数组下标计算只用到 hash 的低位因为n - 1通常是低位全 1而很多对象的hashCode实现里低位的信息量并不充分高位反而更有区分度。如果直接拿原始 hashCode 去取低位高位的信息就白白浪费了冲突概率会上升。把高 16 位移到低位再异或相当于让高位也参与下标计算用一个几乎零成本的操作提升了散列均匀度。这里用异或而不是与、或是因为异或能同时保留两种比特的信息两个 bit 不同时为 1相同时为 0混合效果最好。JDK7 的扰动要复杂得多做了一次右移 20、一次右移 12、一次右移 7 和一次右移 4再叠加多次异或还引入了hashSeed来防止哈希碰撞攻击但收益并不明显JDK8 就简化成了这一行。提示key null时返回 0所以 null key 永远落在下标 0 的位置。这也是 HashMap 允许一个 null key 的实现方式而 Hashtable 直接抛空指针。2.4 Node 与 TreeNode 的字段设计各有讲究普通节点NodeK,V只有四个字段final int hash、final K key、V value、NodeK,V next。hash 用 final 修饰是因为它在节点创建时就固定了后续不再变化这样在扩容和查找时可以直接复用不用重新计算。key 声明为 final 是为了保证哈希一致性如果 key 能被替换就可能出现同一个节点算不出原来下标的尴尬情况。value 不加 final因为可以覆盖。红黑树节点TreeNodeK,V继承自LinkedHashMap.Entry而后者又继承自Node所以它天然带着 next 指针。额外的字段有parent、left、right、prev和boolean red。其中prev这个前驱指针不是红黑树本身需要的它主要用于树化过程中的链表结构维护以及红黑树退化成链表时能快速重建链表。树化后节点之间的next关系依然被保留所以在红黑树状态下遍历仍然可以按链表方式走这也是为什么遍历 HashMap 时不会因为树化而出现奇怪的行为。3. put 和 get 的完整执行链路拆解3.1 putVal 逐步拆解每一行都有理由先看 JDK8 中putVal的主体逻辑我把它按执行顺序梳理一遍。第一步是判断table null || (n table.length) 0如果是就调用resize()完成初始化这是懒加载设计构造方法只记录阈值真正的数组分配推迟到第一次插入。这样做的好处是如果创建了对象却一直没放数据就不会白白占用数组内存。第二步是计算下标i (n - 1) hash取出桶头节点 p。如果p null直接新建一个节点放进桶里这是最理想的情况一次插入就完成。如果桶头不为空就比较桶头节点p.hash hash (p.key key || (key ! null key.equals(p.key)))成立说明是同一个 key记下引用 e 准备覆盖 value。第三步是冲突处理。如果桶头是 TreeNode 类型调用putTreeVal走红黑树的插入逻辑。否则就沿着链表往后走用binCount计数每走一步加一如果走到链表尾部还没找到相同 key就新建节点挂到尾部同时判断binCount TREEIFY_THRESHOLD - 1也就是链表长度达到 8触发treeifyBin。第四步是收尾。如果 e 不为空说明命中了已有 key把新值写入并返回旧值modCount和size都不变。如果是新增节点modCount、size再判断size threshold超过阈值就扩容。整个流程是“先找找到了就换没找到就加加完再看要不要扩容”逻辑非常清晰。3.2 桶内比较为什么先比 hash 再比 equals注意p.hash hash (...)这个顺序先比较 hash 值再比较 key。这不是随意写的而是一种典型的短路优化。hash 是 int比较是一次 CPU 指令级别的基本操作成本极低而equals可能涉及字段逐个比较甚至包含字符串逐字符扫描成本高得多。绝大多数情况下同一个桶里的节点 hash 值都不同所以先用 hash 过滤能挡掉绝大部分无意义的 equals 调用。这也解释了为什么重写 equals 必须重写 hashCode。如果两个对象 equals 相等但 hashCode 不同它们会被分配到不同的桶HashMap 永远找不到彼此集合里会出现“明明相等却存了两份”的诡异现象。反过来hashCode 相同而 equals 不同的两个 key 是允许的它们会落到同一个桶形成冲突这是正常的散列现象。注意p.key key这个引用相等判断也不能省。对于同一个对象引用直接用就能判定相等省掉一次 equals 调用。这是很多 JDK 集合类里通用的微优化手段在 key 大量复用同一实例的场景下收益明显。3.3 getNode 的查找路径比你想的更直白get方法最终调用getNode(hash(key), key)逻辑几乎是 put 的查找部分。先判断表非空、桶头非空然后三步走桶头的 hash 和 key 都匹配就直接返回如果桶头是 TreeNode走getTreeNode否则沿着链表遍历逐个比对 hash 和 equals命中就返回 value走到 null 就返回 null。这里有个很多人忽略的细节get返回 null 有两种可能一是 key 不存在二是 key 存在但 value 恰好是 null。要区分这两种情况必须用containsKey。这也是为什么containsKey不是多余的 API它在业务代码里判断“这个 key 到底有没有配过”时非常关键。如果你写if (map.get(k) ! null)来做存在性判断遇到 value 为 null 的键值对就会误判。查找效率上理想情况是一次定位、一次比较O(1)。最坏情况是桶里挂着长链表O(n)树化之后最坏是 O(log n)。所以提升查找性能的核心就是降低冲突率而降低冲突率的手段无非两个提高哈希函数质量以及让容量足够大。3.4 remove 与 modCountfail-fast 是怎么实现的删除逻辑同样先定位桶然后分链表和红黑树两条路径处理。链表删除需要维护前驱节点找到目标后把前驱的 next 指向目标的 next红黑树删除调用removeTreeNode内部会判断树节点数量是否退化到 6 以下如果满足就转回链表。删除成功后modCount、--size。modCount这个字段记录的是结构性修改次数凡是有节点增删都会加一。迭代器在创建时会把当前的modCount保存为expectedModCount每次调用next()都检查两者是否一致不一致就抛ConcurrentModificationException。这就是 fail-fast 机制它不保证一定能检测到并发修改但能在大多数情况下尽早暴露问题避免出现难以复现的数据错乱。提示想边遍历边删除不要直接用map.remove要用Iterator.remove()它会同步更新expectedModCount不会触发异常。JDK8 之后也可以用removeIf底层同样走的是迭代器安全删除。4. 扩容机制resize() 里藏着的全部细节4.1 负载因子 0.75 到底是怎么定下来的负载因子loadFactor默认 0.75含义是“当元素个数超过容量的 75% 时就扩容”。这个数字不是拍脑袋定的它来自空间和时间的一次权衡。源码注释里提到在理想随机哈希下桶中节点数量近似服从泊松分布当负载因子为 0.75 时一个桶中出现 8 个节点的概率大约是千万分之六级别低到几乎不可能。所以链表长度达到 8 才树化是一个在统计上兜底的阈值而不是经常触发的常规路径。如果把负载因子调高比如 0.9空间利用率上去了但冲突概率明显增加链表变长查询变慢调低到 0.5冲突少了查询快了但数组要频繁扩容、内存占用翻倍。0.75 是在大量实测下表现最均衡的取值。当然它不是铁律如果你的场景读多写少、对延迟极其敏感可以适当调低如果内存极度紧张、对查询延迟不敏感可以适当调高但要清楚代价。4.2 resize() 的源码级流程拆解resize()分两大块先算新容量和新阈值再把旧表数据迁移过去。算容量时分三种情况。第一种是oldCap 0说明表已经存在如果旧容量已经达到最大容量1 30就把阈值设为Integer.MAX_VALUE并且不扩容直接返回旧表否则新容量等于旧容量左移一位也就是翻倍新阈值也翻倍。第二种是oldCap 0但oldThr 0说明是构造时指定了初始容量此时新容量直接等于旧阈值这是初始化路径。第三种是两者都为 0说明用的是无参构造走默认值容量 16阈值 12。最后如果新阈值没算出来就用newCap * loadFactor补算同时把阈值限制在Integer.MAX_VALUE以内。迁移阶段是新表逐个桶处理。如果桶里只有一个节点直接newTab[e.hash (newCap - 1)] e重新定位不需要遍历。如果是红黑树调用split方法按高低位拆成两棵子树或两条链表。如果是普通链表就走高低位拆分逻辑这部分是 JDK8 扩容优化的核心。4.3 高低位拆分JDK8 最值钱的一次优化JDK8 在迁移链表时不再逐个重新计算下标而是把原链表拆成两条一条留在原来的下标 j一条移动到 j oldCap。判断依据就是那一行(e.hash oldCap) 0。为什么这么判断因为容量翻倍后参与下标计算的有效位数多了一位这多出来的一位正好是 oldCap 的二进制 1 所在的位置。如果 hash 在这一位上是 0那么新下标和旧下标完全一样如果是 1新下标就等于旧下标加上 oldCap。这样一来扩容迁移只需要一次遍历、两次指针拼接时间复杂度 O(n)而且不需要任何取模运算。更妙的是它天然保持了链表的相对顺序拆分后每个节点的 next 关系不变不会出现 JDK7 那种顺序颠倒的问题。代码结构也很有对称美loHead/loTail维护低位链hiHead/hiTail维护高位链遍历结束后把低位链挂到newTab[j]、高位链挂到newTab[j oldCap]。4.4 JDK7 的头插法留下了什么历史包袱JDK7 迁移链表时用的是头插每取一个节点就插到新桶的头部结果就是链表顺序完全反转。单线程下这没问题但并发场景下隐患极大。假设线程 A 和线程 B 同时对同一个桶做迁移两个线程各自持有部分节点的引用头插过程中相互交错修改 next 指针就可能形成环。一旦成环后续任何落到这个桶上的 get 都会在环里无限循环表现为 CPU 打满但线程不报错。JDK8 改成尾插法之后环形链表问题基本消失因为尾插不会打乱原有顺序并发交错修改最多导致部分节点丢失或者 size 不准不会再出现死循环。但请注意这不等于 JDK8 的 HashMap 就线程安全了。并发 put 依然可能覆盖数据、丢失节点多线程环境下必须换 ConcurrentHashMap这一点没有任何商量余地。对比项JDK7 HashMapJDK8 HashMap数据结构数组 链表数组 链表 红黑树插入方式头插法尾插法哈希扰动4 次移位 多次异或1 次右移 16 位 异或扩容迁移逐个 rehash 计算下标高低位拆分一次遍历并发扩容风险可能形成环形链表CPU 打满可能丢数据不会死循环树化无链表长度 ≥ 8 且容量 ≥ 644.5 怎么把扩容次数压下来扩容是 HashMap 里最贵的操作一次扩容要分配新数组、遍历所有节点、重新建立引用关系。如果容量预估不准一个不断增长的 Map 可能反复扩容五六次每次都要搬一遍数据。解决办法很简单在创建时就把预期元素数量告诉它。但这里有个容易踩的坑构造方法传进去的initialCapacity并不等于最终容量。HashMap 会用tableSizeFor把它向上取整到 2 的幂而且阈值是按capacity * loadFactor算的。所以如果你预计要放 1000 个元素写new HashMap(1000)是不够的因为阈值只有 750放到 751 个就会触发扩容。正确写法是new HashMap(1000 / 0.75 1)也就是约 1334向上取整到 2 的幂后实际容量是 2048阈值 1536足够容纳 1000 个元素且不扩容。// 预期存放 expectedSize 个元素且不想触发扩容 int expectedSize 1000; int initialCapacity (int) (expectedSize / 0.75f) 1; MapString, Object map new HashMap(initialCapacity); // 如果用的是 Guava可以直接调用现成的方法 MapString, Object map2 Maps.newHashMapWithExpectedSize(expectedSize);注意tableSizeFor的实现是先减一再做五次无符号右移或运算最后加一目的是把任意整数向上补齐到 2 的幂。减一是为了处理本身已经是 2 的幂的情况比如传 16如果不减一会被补成 32。5. 面试高频问题清单与答题框架5.1 基础原理题速查表下面这张表是我这些年整理出的高频问题从“底层结构”到“哈希函数”基本覆盖了第一轮面试会问到的内容。答题时不要只背结论最好能说出“为什么”。问题核心答法加分补充HashMap 的底层结构JDK8 是数组 链表 红黑树JDK7 只有数组 链表没有树化默认容量和负载因子16 和 0.75容量必须是 2 的幂构造时会被 tableSizeFor 补齐为什么容量是 2 的幂索引可用位运算代替取模扩容时元素位置可预测非 2 的幂会导致部分下标永远取不到hash 函数为什么右移 16 位让高位参与运算提升散列均匀度只做一次扰动JDK7 做了多次怎么解决哈希冲突链地址法冲突元素挂成链表链表长度到 8 且容量到 64 时转红黑树树化阈值为什么是 8泊松分布下概率极低属于兜底退化阈值是 6中间留 7 做缓冲put 的流程定位桶、比较、覆盖或新增、判断扩容先判 table 是否为空懒加载初始化为什么重写 equals 必须重写 hashCode否则相等对象可能落到不同桶查找失效反之 hashCode 相同 equals 不同是合法的5.2 扩容与并发相关的高频追问扩容是面试官最爱深挖的地方因为能同时考察源码熟悉度和并发意识。第一个常见追问是“扩容后元素的新下标怎么算”。标准答案是要么保持原下标要么变成原下标加旧容量判断依据是(e.hash oldCap) 0。如果你能顺手说出为什么这个判断成立也就是容量翻倍后有效位数多一位基本就能拿到这一分。第二个追问是“JDK7 和 JDK8 扩容的区别”。要答到三点插入方式从头插改尾插迁移方式从逐个 rehash 改成高低位拆分风险从可能的环形链表死循环变成可能的数据丢失。第三个追问往往落在线程安全上HashMap 线程不安全并发 put 可能覆盖数据、size 计数不准JDK7 还可能死循环所以并发场景要用 ConcurrentHashMap。提示如果面试官继续问 ConcurrentHashMap 怎么保证安全可以答 JDK7 用分段锁、JDK8 用 CAS synchronized 锁单个桶头节点再配合 volatile 保证可见性扩容时支持多线程协助迁移。这个问题展开能聊很久但至少要知道版本差异。5.3 手写一个能跑的最小 HashMap面试里有时会让你手写一个简易版重点不是功能完整而是看你能不能把核心思想表达清楚。下面这个版本保留了数组加链表、容量 2 的幂、扰动函数、扩容高低位拆分的完整骨架去掉红黑树和并发处理方便在纸上或者编辑器里快速实现。public class SimpleHashMapK, V { static class NodeK, V { final int hash; final K key; V value; NodeK, V next; Node(int hash, K key, V value, NodeK, V next) { this.hash hash; this.key key; this.value value; this.next next; } } private static final int DEFAULT_CAPACITY 16; private static final float LOAD_FACTOR 0.75f; private NodeK, V[] table; private int size; private int threshold DEFAULT_CAPACITY; private static int hash(Object key) { int h; return key null ? 0 : (h key.hashCode()) ^ (h 16); } public V put(K key, V value) { if (table null) { resize(); } int h hash(key); int i (table.length - 1) h; NodeK, V p table[i]; if (p null) { table[i] new Node(h, key, value, null); } else { NodeK, V e p; while (true) { if (e.hash h (e.key key || (key ! null key.equals(e.key)))) { V old e.value; e.value value; return old; } if (e.next null) { e.next new Node(h, key, value, null); break; } e e.next; } } size; if (size threshold) { resize(); } return null; } public V get(K key) { if (table null) { return null; } int h hash(key); NodeK, V e table[(table.length - 1) h]; while (e ! null) { if (e.hash h (e.key key || (key ! null key.equals(e.key)))) { return e.value; } e e.next; } return null; } SuppressWarnings(unchecked) private void resize() { int oldCap table null ? 0 : table.length; int newCap oldCap 0 ? DEFAULT_CAPACITY : oldCap 1; NodeK, V[] newTab (NodeK, V[]) new Node[newCap]; if (table ! null) { for (int j 0; j oldCap; j) { NodeK, V e table[j]; if (e null) { continue; } table[j] null; if (e.next null) { newTab[e.hash (newCap - 1)] e; } else { NodeK, V loHead null, loTail null, hiHead null, hiTail null; while (e ! null) { if ((e.hash oldCap) 0) { if (loTail null) { loHead e; } else { loTail.next e; } loTail e; } else { if (hiTail null) { hiHead e; } else { hiTail.next e; } hiTail e; } e e.next; } if (loTail ! null) { loTail.next null; newTab[j] loHead; } if (hiTail ! null) { hiTail.next null; newTab[j oldCap] hiHead; } } } } table newTab; threshold (int) (newCap * LOAD_FACTOR); } }写完之后面试官大概率会问你为什么不用红黑树、为什么不在外面加锁、如果并发调用会出什么问题。这些正好是展示你理解边界的机会比单纯把代码写完更有价值。5.4 回答时的加分点与减分点加分点有几个方向。一是能主动说出设计的权衡比如为什么负载因子是 0.75 而不是 0.5 或 0.9为什么树化阈值是 8 而不是 4。二是能把版本差异讲清楚体现你不是只背了一个版本。三是能联系实际比如提到容量预设的公式、提到可变 key 的坑、提到并发场景该换容器。减分点同样明显。只背“数组加链表加红黑树”却说不出红黑树什么时候用、为什么用会显得很浮。把“HashMap 线程不安全”说成“加个 synchronized 就好了”说明对并发成本没概念。把hashCode和equals的关系说反或者坚持认为 hashCode 相同就一定相等这是基础硬伤。还有一种常见问题是被问到扩容时只说“容量翻倍”却答不出元素迁移的具体规则这往往是没真正读过源码的表现。6. 实战踩坑与性能调优记录6.1 踩坑速查表下面这些坑我在实际项目里要么自己踩过要么在代码评审和故障复盘里见过整理成表格方便对照。现象可能原因处理方式接口偶发卡死、CPU 打满并发使用 HashMapJDK7 可能成环换 ConcurrentHashMap抓线程栈确认map.get 返回 null 误判为不存在value 本身允许为 null改用 containsKey 或者用 Optional 包装数据明明放进去了却取不到key 是可变对象字段变化导致 hashCode 变了key 用不可变对象或放进去后不再修改内存占用远超预期初始容量设置过大或长期只增不删按预期元素数设置定期清理或用弱引用容器大量元素时性能断崖式下跌哈希函数质量差冲突集中检查 key 的 hashCode 实现必要时自定义包装类扩容频繁发生拖慢写入初始容量未预设逐个增长用 expectedSize / 0.75 1 预设容量6.2 容量初始化到底该写多少很多人的习惯是new HashMap()无参构造觉得反正会自己扩容。小数据量下没问题但一旦这个 Map 会长期存放上千甚至上万条数据无参构造就意味着从 16 开始一路扩容到 2048 甚至更大中间十几次数组分配和数据迁移都是纯开销。在高频写入路径上这些开销会直接体现在接口的 P99 上。正确的做法是根据业务数据量预估容量。这里要注意两点一是预期元素数量除以 0.75 再向上取整二是 HashMap 会再把容量补齐到 2 的幂所以实际分配可能比你算的还大一点。如果不确定数据量上限可以给一个偏保守的估计宁可稍微浪费一点内存也别让它频繁扩容。如果实在不知道该填多少可以参考历史监控里这个容器的元素数量峰值取峰值除以 0.75 再加一。6.3 可变对象当 key 的坑有多深把可变对象当作 key 是 HashMap 使用中最隐蔽的错误之一。假设你定义了一个 User 对象只重写了 equals 和 hashCode基于 id 字段计算哈希值然后把它作为 key 放进 Map。后来业务逻辑修改了这个 User 的 id这时候它的 hashCode 变了但它在数组里的位置还是按旧的哈希值算的。之后你再用这个对象去 get计算出的新下标指向另一个桶自然找不到而原来那个桶里躺着的节点又永远不会被访问到形成实质上的内存泄漏。解决方案有三个层次。首选是用不可变对象作为 key比如 String、Integer、枚举或者你自己定义的 final 字段类。如果一定要用可变对象那就保证放进去之后不再修改任何参与 hashCode 计算的字段。实在控制不住可以给 key 加一层不可变包装或者干脆把 key 换成 id 这种稳定值。吃过一次亏之后我现在的习惯是只要看到 Map 的 key 是自定义对象第一反应就是去检查它的 hashCode 是不是基于可变字段算的。注意如果两个不同的可变对象在放入时 hashCode 相同之后其中一个字段变化导致 hashCode 改变也会出现类似的查找失效问题。这种 bug 不会抛异常只会在某个时间点开始表现成“数据丢了”排查起来非常耗时。6.4 什么时候该果断换掉 HashMapHashMap 不是万能容器以下几种情况我会毫不犹豫地换掉它。第一是多线程读写直接上 ConcurrentHashMap这是底线。第二是需要按插入顺序或者访问顺序遍历用 LinkedHashMap它在 HashMap 的基础上多维护了一条双向链表可以指定accessOrder实现 LRU。第三是 key 需要排序用 TreeMap底层红黑树保证有序也支持范围查询。第四是元素数量极少比如三五个且查找频繁这时候一个数组遍历可能都比哈希计算加下标定位快因为常数因子更小。还有一种情况容易被忽略如果这个 Map 的 key 是枚举类型用 EnumMap 会比 HashMap 快很多因为枚举的 ordinal 天然是连续整数可以直接当数组下标用完全不需要哈希计算。这类针对性优化在自己的工具类里用起来很舒服只是要注意可读性别为了微小的性能提升把代码写得没人看得懂。在写完这一大圈之后我个人实际操作下来的体会是HashMap 真正难的不是记住“数组加链表加红黑树”这句话而是搞清楚每个数字背后的权衡以及这些权衡在什么场景下会失效。0.75、8、6、64、16 这几个数字单看都是结论串起来看才是设计思路。当你下次在代码里写下new HashMap()的时候能顺手想一想这个容器大概会装多少条数据、会不会被多个线程碰到、key 是不是稳定的那这篇内容的目的就达到了。 HashMap底层原理、扩容机制与并发避坑全解析
第一次被 HashMap 拖到凌晨三点是在一个看似毫无波澜的版本上线之后。监控面板上某个订单查询接口的 P99 从 40 毫秒慢慢爬到了两秒随后几台机器的 CPU 直接被打到 100%线程栈抓下来一堆线程卡在HashMap.get上转圈。那是 JDK7 时代一个多线程共享的缓存容器在并发扩容时被插成了环形链表get 操作顺着环永远走不到头。从那次事故之后我才真正愿意坐下来把 HashMap 的每一行源码读完把hashCode、equals、负载因子、扩容阈值这些看起来只是面试八股的东西当成线上稳定性的必修课。这篇内容就是那次“补课”的产物。我会把 HashMap 的底层实现原理、扩容机制从头到尾拆一遍把源码里那些藏在注释和位运算背后的设计意图挖出来再把我这些年面试别人和被面试时反复遇到的高频问题整理成一份可以直接对照的答题清单。同时我也会分享几个真实踩过的坑容量初始化写成多少才合适、可变对象当 key 会出什么幺蛾子、为什么扩容时元素要么原地不动要么整体后移一个 oldCap以及 JDK7 和 JDK8 在链表插入顺序上的差别到底意味着什么。不管你是刚学完集合框架想弄明白“为什么容量非得是 2 的幂”的新手还是写了几年业务代码、想搞清楚线上偶发卡顿到底是不是哈希冲突引起的进阶选手这篇内容都能给你一份能直接拿去用的参考。我把原理、源码、参数计算、面试答法和避坑经验放在一起讲尽量做到看完能自己讲出来也能自己动手写一个最小可用的版本。1. 从一个真实的线上问题说起为什么值得死磕 HashMap1.1 那次 CPU 打满的凌晨到底发生了什么那次事故的根因并不复杂一个静态的HashMap被当成了本地缓存多个业务线程同时往里放数据正好撞上扩容。JDK7 的transfer方法在迁移链表时用的是头插法也就是新桶里的节点顺序和原链表完全颠倒。并发场景下两个线程同时做迁移指针相互引用最终形成了A.next B且B.next A的环形结构。之后所有落到这个桶上的查询都会陷入死循环CPU 自然被打满而且这种问题不会抛异常、不会打日志只表现为线程卡死排查成本极高。这件事给我最大的教训是HashMap 的设计目标是单线程下的高性能散列表它从来没有承诺过并发安全。JDK8 把插入方式改成了尾插法解决了环形链表这个致命问题但并发下的数据覆盖、size 计数不准、扩容丢失节点这些毛病依然存在。如果你真的需要并发场景下的键值容器那ConcurrentHashMap才是正解用分段锁或者 CAS 加 synchronized 保证桶级别的并发安全比你自己在外面套一把大锁要高效得多。理解这个边界之后再回头看 HashMap 的源码你会发现它的每一个设计细节都在为“单线程下尽可能快”这个目标服务位运算替代取模、容量强制 2 的幂、扰动函数压缩高位信息、链表到红黑树的转换阈值。这些不是炫技而是在真实数据分布下反复权衡的结果值得逐个拆开看。1.2 HashMap 到底解决了什么问题从数据结构的角度讲HashMap 要解决的是查找效率问题。数组的随机访问是 O(1)但按值查找是 O(n)链表的插入删除是 O(1)但查找是 O(n)。哈希表把两者的优点拼起来用哈希函数把 key 映射成一个整数再用这个整数定位到数组下标理想情况下一次就能命中查找、插入、删除的平均复杂度都逼近 O(1)。它提供的能力很朴素以键值对的形式存储数据通过 key 快速拿到 value允许一个 null key 和多个 null value不保证遍历顺序稳定。但正是这种朴素让它在工程里无处不在配置缓存、对象去重、分组统计、图结构建模、去重计数、词频统计、接口返回结果的本地索引几乎所有需要“按某个标识快速找东西”的场景第一反应都是 HashMap。代价也很明确哈希冲突无法完全避免。两个不同的 key 算出同一个下标就必须有一个位置能挂多个元素这就是链地址法。冲突一旦变多链表变长查找就退化到 O(n)。所以 HashMap 真正的技术含量不在“怎么用数组存”而在“怎么把冲突控制在可接受范围内”以及“冲突严重时怎么兜底”。扩容机制和红黑树转换本质上都是这个问题的答案。1.3 这篇内容适合谁以及我建议的阅读顺序如果你是完全的新手建议从第 2 章开始顺着读先把“数组加链表加红黑树”这个骨架建立起来再看第 3 章的 put/get 流程最后回到第 4 章的扩容。扩容是整个 HashMap 里最绕的部分前置知识不够直接啃会很痛苦。如果你是准备面试的可以直接跳到第 5 章的题目清单和答题框架再回头补第 4 章因为扩容几乎是每一轮技术面必问的深水区。如果你是在线上出过问题的老兵第 6 章的踩坑记录可能对你最有用容量预设怎么写、loadFactor 什么时候该调、可变 key 有多坑、什么时候干脆换掉 HashMap。这些内容在教科书里基本看不到都是一次次故障和性能压测换来的。提示本文涉及的源码基于 JDK8 的 HashMap 实现个别细节在 JDK7 中不同我会在对应位置标注出来。不同厂商的 JDK 发行版在实现上可能有微调但整体设计思路一致。2. 拆开 HashMap 的骨架数组、链表、红黑树是怎么配合的2.1 数组是骨架链表是补丁红黑树是保险把 HashMap 想象成一栋楼的信箱区最外层是数组NodeK,V[] table也就是信箱墙本身。每个数组位置叫一个“桶”bucket桶里放的是一个链表或者一棵红黑树。你拿着 key 算出一个下标就知道该去哪个桶里翻找桶里可能有零个、一个或者多个元素。数组的长度决定了桶的数量也决定了冲突的概率。桶越多冲突越少但内存占用越大桶越少内存省了冲突变多链表变长查找变慢。这就是为什么需要扩容也是为什么需要一个负载因子来权衡。链表是解决冲突的第一层手段也就是所谓的“拉链法”或者链地址法冲突的元素挂在同一个桶下面形成一个单向链表。当链表长度达到阈值 8 且数组容量达到 64 时链表会转换成红黑树把最坏情况下的查找复杂度从 O(n) 优化到 O(log n)。注意链表转红黑树的条件是两个缺一不可。链表长度达到 8 只是其一如果当前数组容量小于 64HashMap 会选择先扩容而不是树化因为小容量下冲突多本来就是容量太小导致的扩容比树化更划算。红黑树是一种自平衡二叉搜索树插入删除时通过变色和旋转维持大致平衡最坏查找路径长度被限制在 2 倍最短路径以内。用在这里的好处是即使哈希函数被恶意构造、大量 key 落到同一个桶查找性能也不会崩到线性。代价是每个树节点比普通链表节点多维护 parent、left、right、prev、red 五个字段内存开销明显更大所以只有链表足够长时才值得转换。2.2 容量为什么非得是 2 的幂这是 HashMap 里最经典的设计之一答案有两层。第一层是索引计算HashMap 用(n - 1) hash来算数组下标这里的 n 是容量。当 n 是 2 的幂时n - 1的二进制是低位全 1比如 16 - 1 15 0b1111此时运算的结果恰好等价于hash % n但位运算比取模快得多。计算机里除法和取模是相对昂贵的操作能用位运算替代就能省下可观的 CPU 周期。第二层是扩容时的元素迁移。容量翻倍后元素的新下标只可能是两个值原来的下标或者原下标加上旧容量。原因在于新容量是旧容量的两倍newCap - 1比oldCap - 1在二进制上多了一个高位 1这个位正好来自 hash 中对应位置的 bit。判断方法极其简单(e.hash oldCap) 0就留在原位否则移动到原下标 oldCap。不需要重新计算 hash也不需要重新取模这在扩容时是巨大的性能节省。反过来说如果容量不是 2 的幂n - 1的二进制里就会出现 0 位与运算后某些下标永远取不到数组空间被浪费同时冲突分布也会变差。所以哪怕你通过构造方法传入一个不是 2 的幂的初始容量HashMap 也会用tableSizeFor把它向上取整到最接近的 2 的幂。比如传 17实际容量会是 32传 100实际容量会是 128。2.3 hash() 里的那次右移 16 位到底在干嘛JDK8 的哈希扰动函数只有一行static final int hash(Object key) { int h; return (key null) ? 0 : (h key.hashCode()) ^ (h 16); }核心是h ^ (h 16)也就是把 hashCode 的高 16 位无符号右移到低位然后和原值做异或。这么做的原因是数组下标计算只用到 hash 的低位因为n - 1通常是低位全 1而很多对象的hashCode实现里低位的信息量并不充分高位反而更有区分度。如果直接拿原始 hashCode 去取低位高位的信息就白白浪费了冲突概率会上升。把高 16 位移到低位再异或相当于让高位也参与下标计算用一个几乎零成本的操作提升了散列均匀度。这里用异或而不是与、或是因为异或能同时保留两种比特的信息两个 bit 不同时为 1相同时为 0混合效果最好。JDK7 的扰动要复杂得多做了一次右移 20、一次右移 12、一次右移 7 和一次右移 4再叠加多次异或还引入了hashSeed来防止哈希碰撞攻击但收益并不明显JDK8 就简化成了这一行。提示key null时返回 0所以 null key 永远落在下标 0 的位置。这也是 HashMap 允许一个 null key 的实现方式而 Hashtable 直接抛空指针。2.4 Node 与 TreeNode 的字段设计各有讲究普通节点NodeK,V只有四个字段final int hash、final K key、V value、NodeK,V next。hash 用 final 修饰是因为它在节点创建时就固定了后续不再变化这样在扩容和查找时可以直接复用不用重新计算。key 声明为 final 是为了保证哈希一致性如果 key 能被替换就可能出现同一个节点算不出原来下标的尴尬情况。value 不加 final因为可以覆盖。红黑树节点TreeNodeK,V继承自LinkedHashMap.Entry而后者又继承自Node所以它天然带着 next 指针。额外的字段有parent、left、right、prev和boolean red。其中prev这个前驱指针不是红黑树本身需要的它主要用于树化过程中的链表结构维护以及红黑树退化成链表时能快速重建链表。树化后节点之间的next关系依然被保留所以在红黑树状态下遍历仍然可以按链表方式走这也是为什么遍历 HashMap 时不会因为树化而出现奇怪的行为。3. put 和 get 的完整执行链路拆解3.1 putVal 逐步拆解每一行都有理由先看 JDK8 中putVal的主体逻辑我把它按执行顺序梳理一遍。第一步是判断table null || (n table.length) 0如果是就调用resize()完成初始化这是懒加载设计构造方法只记录阈值真正的数组分配推迟到第一次插入。这样做的好处是如果创建了对象却一直没放数据就不会白白占用数组内存。第二步是计算下标i (n - 1) hash取出桶头节点 p。如果p null直接新建一个节点放进桶里这是最理想的情况一次插入就完成。如果桶头不为空就比较桶头节点p.hash hash (p.key key || (key ! null key.equals(p.key)))成立说明是同一个 key记下引用 e 准备覆盖 value。第三步是冲突处理。如果桶头是 TreeNode 类型调用putTreeVal走红黑树的插入逻辑。否则就沿着链表往后走用binCount计数每走一步加一如果走到链表尾部还没找到相同 key就新建节点挂到尾部同时判断binCount TREEIFY_THRESHOLD - 1也就是链表长度达到 8触发treeifyBin。第四步是收尾。如果 e 不为空说明命中了已有 key把新值写入并返回旧值modCount和size都不变。如果是新增节点modCount、size再判断size threshold超过阈值就扩容。整个流程是“先找找到了就换没找到就加加完再看要不要扩容”逻辑非常清晰。3.2 桶内比较为什么先比 hash 再比 equals注意p.hash hash (...)这个顺序先比较 hash 值再比较 key。这不是随意写的而是一种典型的短路优化。hash 是 int比较是一次 CPU 指令级别的基本操作成本极低而equals可能涉及字段逐个比较甚至包含字符串逐字符扫描成本高得多。绝大多数情况下同一个桶里的节点 hash 值都不同所以先用 hash 过滤能挡掉绝大部分无意义的 equals 调用。这也解释了为什么重写 equals 必须重写 hashCode。如果两个对象 equals 相等但 hashCode 不同它们会被分配到不同的桶HashMap 永远找不到彼此集合里会出现“明明相等却存了两份”的诡异现象。反过来hashCode 相同而 equals 不同的两个 key 是允许的它们会落到同一个桶形成冲突这是正常的散列现象。注意p.key key这个引用相等判断也不能省。对于同一个对象引用直接用就能判定相等省掉一次 equals 调用。这是很多 JDK 集合类里通用的微优化手段在 key 大量复用同一实例的场景下收益明显。3.3 getNode 的查找路径比你想的更直白get方法最终调用getNode(hash(key), key)逻辑几乎是 put 的查找部分。先判断表非空、桶头非空然后三步走桶头的 hash 和 key 都匹配就直接返回如果桶头是 TreeNode走getTreeNode否则沿着链表遍历逐个比对 hash 和 equals命中就返回 value走到 null 就返回 null。这里有个很多人忽略的细节get返回 null 有两种可能一是 key 不存在二是 key 存在但 value 恰好是 null。要区分这两种情况必须用containsKey。这也是为什么containsKey不是多余的 API它在业务代码里判断“这个 key 到底有没有配过”时非常关键。如果你写if (map.get(k) ! null)来做存在性判断遇到 value 为 null 的键值对就会误判。查找效率上理想情况是一次定位、一次比较O(1)。最坏情况是桶里挂着长链表O(n)树化之后最坏是 O(log n)。所以提升查找性能的核心就是降低冲突率而降低冲突率的手段无非两个提高哈希函数质量以及让容量足够大。3.4 remove 与 modCountfail-fast 是怎么实现的删除逻辑同样先定位桶然后分链表和红黑树两条路径处理。链表删除需要维护前驱节点找到目标后把前驱的 next 指向目标的 next红黑树删除调用removeTreeNode内部会判断树节点数量是否退化到 6 以下如果满足就转回链表。删除成功后modCount、--size。modCount这个字段记录的是结构性修改次数凡是有节点增删都会加一。迭代器在创建时会把当前的modCount保存为expectedModCount每次调用next()都检查两者是否一致不一致就抛ConcurrentModificationException。这就是 fail-fast 机制它不保证一定能检测到并发修改但能在大多数情况下尽早暴露问题避免出现难以复现的数据错乱。提示想边遍历边删除不要直接用map.remove要用Iterator.remove()它会同步更新expectedModCount不会触发异常。JDK8 之后也可以用removeIf底层同样走的是迭代器安全删除。4. 扩容机制resize() 里藏着的全部细节4.1 负载因子 0.75 到底是怎么定下来的负载因子loadFactor默认 0.75含义是“当元素个数超过容量的 75% 时就扩容”。这个数字不是拍脑袋定的它来自空间和时间的一次权衡。源码注释里提到在理想随机哈希下桶中节点数量近似服从泊松分布当负载因子为 0.75 时一个桶中出现 8 个节点的概率大约是千万分之六级别低到几乎不可能。所以链表长度达到 8 才树化是一个在统计上兜底的阈值而不是经常触发的常规路径。如果把负载因子调高比如 0.9空间利用率上去了但冲突概率明显增加链表变长查询变慢调低到 0.5冲突少了查询快了但数组要频繁扩容、内存占用翻倍。0.75 是在大量实测下表现最均衡的取值。当然它不是铁律如果你的场景读多写少、对延迟极其敏感可以适当调低如果内存极度紧张、对查询延迟不敏感可以适当调高但要清楚代价。4.2 resize() 的源码级流程拆解resize()分两大块先算新容量和新阈值再把旧表数据迁移过去。算容量时分三种情况。第一种是oldCap 0说明表已经存在如果旧容量已经达到最大容量1 30就把阈值设为Integer.MAX_VALUE并且不扩容直接返回旧表否则新容量等于旧容量左移一位也就是翻倍新阈值也翻倍。第二种是oldCap 0但oldThr 0说明是构造时指定了初始容量此时新容量直接等于旧阈值这是初始化路径。第三种是两者都为 0说明用的是无参构造走默认值容量 16阈值 12。最后如果新阈值没算出来就用newCap * loadFactor补算同时把阈值限制在Integer.MAX_VALUE以内。迁移阶段是新表逐个桶处理。如果桶里只有一个节点直接newTab[e.hash (newCap - 1)] e重新定位不需要遍历。如果是红黑树调用split方法按高低位拆成两棵子树或两条链表。如果是普通链表就走高低位拆分逻辑这部分是 JDK8 扩容优化的核心。4.3 高低位拆分JDK8 最值钱的一次优化JDK8 在迁移链表时不再逐个重新计算下标而是把原链表拆成两条一条留在原来的下标 j一条移动到 j oldCap。判断依据就是那一行(e.hash oldCap) 0。为什么这么判断因为容量翻倍后参与下标计算的有效位数多了一位这多出来的一位正好是 oldCap 的二进制 1 所在的位置。如果 hash 在这一位上是 0那么新下标和旧下标完全一样如果是 1新下标就等于旧下标加上 oldCap。这样一来扩容迁移只需要一次遍历、两次指针拼接时间复杂度 O(n)而且不需要任何取模运算。更妙的是它天然保持了链表的相对顺序拆分后每个节点的 next 关系不变不会出现 JDK7 那种顺序颠倒的问题。代码结构也很有对称美loHead/loTail维护低位链hiHead/hiTail维护高位链遍历结束后把低位链挂到newTab[j]、高位链挂到newTab[j oldCap]。4.4 JDK7 的头插法留下了什么历史包袱JDK7 迁移链表时用的是头插每取一个节点就插到新桶的头部结果就是链表顺序完全反转。单线程下这没问题但并发场景下隐患极大。假设线程 A 和线程 B 同时对同一个桶做迁移两个线程各自持有部分节点的引用头插过程中相互交错修改 next 指针就可能形成环。一旦成环后续任何落到这个桶上的 get 都会在环里无限循环表现为 CPU 打满但线程不报错。JDK8 改成尾插法之后环形链表问题基本消失因为尾插不会打乱原有顺序并发交错修改最多导致部分节点丢失或者 size 不准不会再出现死循环。但请注意这不等于 JDK8 的 HashMap 就线程安全了。并发 put 依然可能覆盖数据、丢失节点多线程环境下必须换 ConcurrentHashMap这一点没有任何商量余地。对比项JDK7 HashMapJDK8 HashMap数据结构数组 链表数组 链表 红黑树插入方式头插法尾插法哈希扰动4 次移位 多次异或1 次右移 16 位 异或扩容迁移逐个 rehash 计算下标高低位拆分一次遍历并发扩容风险可能形成环形链表CPU 打满可能丢数据不会死循环树化无链表长度 ≥ 8 且容量 ≥ 644.5 怎么把扩容次数压下来扩容是 HashMap 里最贵的操作一次扩容要分配新数组、遍历所有节点、重新建立引用关系。如果容量预估不准一个不断增长的 Map 可能反复扩容五六次每次都要搬一遍数据。解决办法很简单在创建时就把预期元素数量告诉它。但这里有个容易踩的坑构造方法传进去的initialCapacity并不等于最终容量。HashMap 会用tableSizeFor把它向上取整到 2 的幂而且阈值是按capacity * loadFactor算的。所以如果你预计要放 1000 个元素写new HashMap(1000)是不够的因为阈值只有 750放到 751 个就会触发扩容。正确写法是new HashMap(1000 / 0.75 1)也就是约 1334向上取整到 2 的幂后实际容量是 2048阈值 1536足够容纳 1000 个元素且不扩容。// 预期存放 expectedSize 个元素且不想触发扩容 int expectedSize 1000; int initialCapacity (int) (expectedSize / 0.75f) 1; MapString, Object map new HashMap(initialCapacity); // 如果用的是 Guava可以直接调用现成的方法 MapString, Object map2 Maps.newHashMapWithExpectedSize(expectedSize);注意tableSizeFor的实现是先减一再做五次无符号右移或运算最后加一目的是把任意整数向上补齐到 2 的幂。减一是为了处理本身已经是 2 的幂的情况比如传 16如果不减一会被补成 32。5. 面试高频问题清单与答题框架5.1 基础原理题速查表下面这张表是我这些年整理出的高频问题从“底层结构”到“哈希函数”基本覆盖了第一轮面试会问到的内容。答题时不要只背结论最好能说出“为什么”。问题核心答法加分补充HashMap 的底层结构JDK8 是数组 链表 红黑树JDK7 只有数组 链表没有树化默认容量和负载因子16 和 0.75容量必须是 2 的幂构造时会被 tableSizeFor 补齐为什么容量是 2 的幂索引可用位运算代替取模扩容时元素位置可预测非 2 的幂会导致部分下标永远取不到hash 函数为什么右移 16 位让高位参与运算提升散列均匀度只做一次扰动JDK7 做了多次怎么解决哈希冲突链地址法冲突元素挂成链表链表长度到 8 且容量到 64 时转红黑树树化阈值为什么是 8泊松分布下概率极低属于兜底退化阈值是 6中间留 7 做缓冲put 的流程定位桶、比较、覆盖或新增、判断扩容先判 table 是否为空懒加载初始化为什么重写 equals 必须重写 hashCode否则相等对象可能落到不同桶查找失效反之 hashCode 相同 equals 不同是合法的5.2 扩容与并发相关的高频追问扩容是面试官最爱深挖的地方因为能同时考察源码熟悉度和并发意识。第一个常见追问是“扩容后元素的新下标怎么算”。标准答案是要么保持原下标要么变成原下标加旧容量判断依据是(e.hash oldCap) 0。如果你能顺手说出为什么这个判断成立也就是容量翻倍后有效位数多一位基本就能拿到这一分。第二个追问是“JDK7 和 JDK8 扩容的区别”。要答到三点插入方式从头插改尾插迁移方式从逐个 rehash 改成高低位拆分风险从可能的环形链表死循环变成可能的数据丢失。第三个追问往往落在线程安全上HashMap 线程不安全并发 put 可能覆盖数据、size 计数不准JDK7 还可能死循环所以并发场景要用 ConcurrentHashMap。提示如果面试官继续问 ConcurrentHashMap 怎么保证安全可以答 JDK7 用分段锁、JDK8 用 CAS synchronized 锁单个桶头节点再配合 volatile 保证可见性扩容时支持多线程协助迁移。这个问题展开能聊很久但至少要知道版本差异。5.3 手写一个能跑的最小 HashMap面试里有时会让你手写一个简易版重点不是功能完整而是看你能不能把核心思想表达清楚。下面这个版本保留了数组加链表、容量 2 的幂、扰动函数、扩容高低位拆分的完整骨架去掉红黑树和并发处理方便在纸上或者编辑器里快速实现。public class SimpleHashMapK, V { static class NodeK, V { final int hash; final K key; V value; NodeK, V next; Node(int hash, K key, V value, NodeK, V next) { this.hash hash; this.key key; this.value value; this.next next; } } private static final int DEFAULT_CAPACITY 16; private static final float LOAD_FACTOR 0.75f; private NodeK, V[] table; private int size; private int threshold DEFAULT_CAPACITY; private static int hash(Object key) { int h; return key null ? 0 : (h key.hashCode()) ^ (h 16); } public V put(K key, V value) { if (table null) { resize(); } int h hash(key); int i (table.length - 1) h; NodeK, V p table[i]; if (p null) { table[i] new Node(h, key, value, null); } else { NodeK, V e p; while (true) { if (e.hash h (e.key key || (key ! null key.equals(e.key)))) { V old e.value; e.value value; return old; } if (e.next null) { e.next new Node(h, key, value, null); break; } e e.next; } } size; if (size threshold) { resize(); } return null; } public V get(K key) { if (table null) { return null; } int h hash(key); NodeK, V e table[(table.length - 1) h]; while (e ! null) { if (e.hash h (e.key key || (key ! null key.equals(e.key)))) { return e.value; } e e.next; } return null; } SuppressWarnings(unchecked) private void resize() { int oldCap table null ? 0 : table.length; int newCap oldCap 0 ? DEFAULT_CAPACITY : oldCap 1; NodeK, V[] newTab (NodeK, V[]) new Node[newCap]; if (table ! null) { for (int j 0; j oldCap; j) { NodeK, V e table[j]; if (e null) { continue; } table[j] null; if (e.next null) { newTab[e.hash (newCap - 1)] e; } else { NodeK, V loHead null, loTail null, hiHead null, hiTail null; while (e ! null) { if ((e.hash oldCap) 0) { if (loTail null) { loHead e; } else { loTail.next e; } loTail e; } else { if (hiTail null) { hiHead e; } else { hiTail.next e; } hiTail e; } e e.next; } if (loTail ! null) { loTail.next null; newTab[j] loHead; } if (hiTail ! null) { hiTail.next null; newTab[j oldCap] hiHead; } } } } table newTab; threshold (int) (newCap * LOAD_FACTOR); } }写完之后面试官大概率会问你为什么不用红黑树、为什么不在外面加锁、如果并发调用会出什么问题。这些正好是展示你理解边界的机会比单纯把代码写完更有价值。5.4 回答时的加分点与减分点加分点有几个方向。一是能主动说出设计的权衡比如为什么负载因子是 0.75 而不是 0.5 或 0.9为什么树化阈值是 8 而不是 4。二是能把版本差异讲清楚体现你不是只背了一个版本。三是能联系实际比如提到容量预设的公式、提到可变 key 的坑、提到并发场景该换容器。减分点同样明显。只背“数组加链表加红黑树”却说不出红黑树什么时候用、为什么用会显得很浮。把“HashMap 线程不安全”说成“加个 synchronized 就好了”说明对并发成本没概念。把hashCode和equals的关系说反或者坚持认为 hashCode 相同就一定相等这是基础硬伤。还有一种常见问题是被问到扩容时只说“容量翻倍”却答不出元素迁移的具体规则这往往是没真正读过源码的表现。6. 实战踩坑与性能调优记录6.1 踩坑速查表下面这些坑我在实际项目里要么自己踩过要么在代码评审和故障复盘里见过整理成表格方便对照。现象可能原因处理方式接口偶发卡死、CPU 打满并发使用 HashMapJDK7 可能成环换 ConcurrentHashMap抓线程栈确认map.get 返回 null 误判为不存在value 本身允许为 null改用 containsKey 或者用 Optional 包装数据明明放进去了却取不到key 是可变对象字段变化导致 hashCode 变了key 用不可变对象或放进去后不再修改内存占用远超预期初始容量设置过大或长期只增不删按预期元素数设置定期清理或用弱引用容器大量元素时性能断崖式下跌哈希函数质量差冲突集中检查 key 的 hashCode 实现必要时自定义包装类扩容频繁发生拖慢写入初始容量未预设逐个增长用 expectedSize / 0.75 1 预设容量6.2 容量初始化到底该写多少很多人的习惯是new HashMap()无参构造觉得反正会自己扩容。小数据量下没问题但一旦这个 Map 会长期存放上千甚至上万条数据无参构造就意味着从 16 开始一路扩容到 2048 甚至更大中间十几次数组分配和数据迁移都是纯开销。在高频写入路径上这些开销会直接体现在接口的 P99 上。正确的做法是根据业务数据量预估容量。这里要注意两点一是预期元素数量除以 0.75 再向上取整二是 HashMap 会再把容量补齐到 2 的幂所以实际分配可能比你算的还大一点。如果不确定数据量上限可以给一个偏保守的估计宁可稍微浪费一点内存也别让它频繁扩容。如果实在不知道该填多少可以参考历史监控里这个容器的元素数量峰值取峰值除以 0.75 再加一。6.3 可变对象当 key 的坑有多深把可变对象当作 key 是 HashMap 使用中最隐蔽的错误之一。假设你定义了一个 User 对象只重写了 equals 和 hashCode基于 id 字段计算哈希值然后把它作为 key 放进 Map。后来业务逻辑修改了这个 User 的 id这时候它的 hashCode 变了但它在数组里的位置还是按旧的哈希值算的。之后你再用这个对象去 get计算出的新下标指向另一个桶自然找不到而原来那个桶里躺着的节点又永远不会被访问到形成实质上的内存泄漏。解决方案有三个层次。首选是用不可变对象作为 key比如 String、Integer、枚举或者你自己定义的 final 字段类。如果一定要用可变对象那就保证放进去之后不再修改任何参与 hashCode 计算的字段。实在控制不住可以给 key 加一层不可变包装或者干脆把 key 换成 id 这种稳定值。吃过一次亏之后我现在的习惯是只要看到 Map 的 key 是自定义对象第一反应就是去检查它的 hashCode 是不是基于可变字段算的。注意如果两个不同的可变对象在放入时 hashCode 相同之后其中一个字段变化导致 hashCode 改变也会出现类似的查找失效问题。这种 bug 不会抛异常只会在某个时间点开始表现成“数据丢了”排查起来非常耗时。6.4 什么时候该果断换掉 HashMapHashMap 不是万能容器以下几种情况我会毫不犹豫地换掉它。第一是多线程读写直接上 ConcurrentHashMap这是底线。第二是需要按插入顺序或者访问顺序遍历用 LinkedHashMap它在 HashMap 的基础上多维护了一条双向链表可以指定accessOrder实现 LRU。第三是 key 需要排序用 TreeMap底层红黑树保证有序也支持范围查询。第四是元素数量极少比如三五个且查找频繁这时候一个数组遍历可能都比哈希计算加下标定位快因为常数因子更小。还有一种情况容易被忽略如果这个 Map 的 key 是枚举类型用 EnumMap 会比 HashMap 快很多因为枚举的 ordinal 天然是连续整数可以直接当数组下标用完全不需要哈希计算。这类针对性优化在自己的工具类里用起来很舒服只是要注意可读性别为了微小的性能提升把代码写得没人看得懂。在写完这一大圈之后我个人实际操作下来的体会是HashMap 真正难的不是记住“数组加链表加红黑树”这句话而是搞清楚每个数字背后的权衡以及这些权衡在什么场景下会失效。0.75、8、6、64、16 这几个数字单看都是结论串起来看才是设计思路。当你下次在代码里写下new HashMap()的时候能顺手想一想这个容器大概会装多少条数据、会不会被多个线程碰到、key 是不是稳定的那这篇内容的目的就达到了。