开头我先讲个亲身经历。前两年面一个高级岗位前面聊项目聊架构都挺顺轮到基础环节面试官问了个很朴素的问题“HashMap在扩容的时候有没有可能丢数据JDK 7和JDK 8的表现有什么区别”我当时愣了一下脑子里全是“头插法”、“环链”这些关键词但真要把“为什么丢”、“怎么丢的”讲清楚发现脑子里那点东西根本不够使。那次之后我才算明白HashMap这玩意儿的“八股文”不是背出来的是得真把它钉在脑子里从存储结构到位运算从扩容到并发一条链子全串起来才算真正“理解”了。这篇算是我自己JDK源码梳理系列的第3篇。既然标题叫“八股文知多少”我就不客气了把HashMap面试里常被盘问的那些点从表层到深层一条一条捋干净。文章不会只贴源码原文我会把“为什么这样设计”、“底层到底干了什么”讲透顺带把平时写代码容易踩的坑也一并划出来。1. HashMap的存储真相数组、链表和红黑树的“三段式”1.1 先搞清楚HashMap到底把数据放哪了很多入门教程说到HashMap的底层结构都会甩一句“数组加链表”实际上到了JDK 8以后还得加上“红黑树”这一层。但光知道“数组链表红黑树”这九个字面试官再往深问一句“你想过为什么是这三个东西拼在一起吗”很多人就卡住了。我们不妨把HashMap简化成一个“存东西的柜子”。这个柜子有一个很大的编号数组数组的每个格子里要么直接放一个键值对要么挂一条链表极端情况下这条链表会转型成一棵红黑树。存的时候先根据key的hash值算出“应该去第几号格子”然后在这个格子的链表里逐个比对找到同一个key就覆盖找不到就挂到链表末尾。查的时候也一样先定位到格子再在链表上挨个找。这个设计要解决的问题核心是“查询速度”和“写入速度”的平衡。数组的查找是O(1)的只要知道下标一步就能定位到目标格子。但哈希函数算出来的下标是有限的key的hash值是无限的多个key落到同一个格子是必然事件这就是哈希冲突。链表就是用来兜底冲突的冲突了就链起来查询的时候在链上线性扫描。问题是当链表越来越长查询代价就从O(1)恶化成了O(n)所以JDK 8引入了红黑树把链表的查询从O(n)压回O(log n)。这里有个细节值得多说一句树化是有条件的不是链表稍微长一点就立刻变成树。除了链表长度达到8还要求整个数组的长度不小于64。因为如果数组本身只有16个槽位说明哈希冲突主要不是“链表太长”问题而是“桶位太少”的问题这时候扩容比树化更有效。这是JDK 8里一个非常典型的工程权衡逻辑。1.2 hash定位整条链路从hashCode到数组下标面试的时候我问过很多候选人“HashMap是怎么根据key定位到数组下标的”不少人直接答“key.hashCode() % 数组长度”。这个答案在逻辑上不算错但它掩盖了HashMap实际做的两步操作。第一步计算key的hashCode然后做一次扰动处理。为什么需要扰动因为HashMap的数组长度用的是2的整数次幂而下标计算是(n - 1) hash这意味着真正参与下标运算的其实只有hash值低位的那几个bit。如果key的hashCode设计得不好大量key的低位相同冲突就会非常厉害。扰动函数的作用就是把高位的信息往低位混合一遍让低位不再是“裸奔”的原始值。JDK 8的扰动函数长这样static final int hash(Object key) { int h; return (key null) ? 0 : (h key.hashCode()) ^ (h 16); }就是拿hashCode本身和它的高16位做异或。这个操作在专业术语里叫“扰动”你完全可以理解为“把高半区的影响辐射到低半区”。String类型的hashCode本身就设计得比较均匀但只要你自己定义了一个hashCode分布很烂的类这个扰动函数就能帮你兜住一部分损失。第二步用(n - 1) hash算出数组下标。这里n是数组长度永远是2的整数次幂。这个公式等价于hash % n但因为位运算比取模快得多而且去掉符号位的影响现实中就是这么干的。1.3 为什么容量必须是2的整数次幂这是HashMap源码里最容易被拎出来问的考点之一。两个原因一是为了位运算替代取模二是为了扩容时能高效地把元素重新分布。先说第一个。当n是2的整数次幂时(n - 1)的二进制一定是低几位全1比如n16时n-115二进制是1111。一个hash值和1111做与运算效果就是直接截取这个hash值的低4位范围正好是0~15。这个操作本质上就是hash % 16但位运算只需要一个CPU周期。再看第二个。扩容的时候数组长度从n变成2n每个元素重新计算下标如果还按hash % 新长度来算所有元素都得重新算一遍成本太高。但利用二进制特性JDK 8有一个非常巧妙的判断扩容后元素的位置要么保持不变要么是“原位置旧容量”。为什么因为新的掩码是2n - 1比原来的n - 1多了一位这一个bit恰好是hash值在“旧容量对应位”上的值。如果这个bit是0下标不变是1下标就是原来的值加上旧容量。写代码的时候如果你自己指定了初始化容量不是2的整数次幂比如new HashMap(19)HashMap不会直接拿19当数组大小而是会通过tableSizeFor方法把它“向上补齐”到最近的2的整数次幂也就是32。这个细节面试也爱问但平时看源码的人少知道的人不多。2. 扩容与树化触发时机、完整流程和那点反直觉的设计2.1 阈值、加载因子和扩容的前置条件HashMap的默认加载因子是0.75这个0.75是源码作者在时间和空间成本之间做的折中。空间上数组永远只用到四分之三剩下的四分之一是“安全缓冲”用来减少冲突概率时间上加载因子越高数组越容易在容量不足时发生碰撞链表变长查询变慢加载因子太低数组空间又太浪费。网上有人专门做过统计实验0.75左右可以让泊松分布下的链表长度超过8的概率低于千万分之一这也是后面链表树化阈值为8的一个重要理论依据。扩容的触发条件是put时发现当前元素数量大于等于size * loadFactor也就是threshold。比如初始容量16加载因子0.75threshold就是12。当你插入第13个元素时HashMap会先扩容到32再重新安排元素位置。注意一个容易混淆的点扩容判断看的是size也就是键值对总个数不是“数组里已经被占用的格子数”。这两个概念经常有人搞混。哪怕只有两个格子被占用但总元素个数到了12照样触发扩容。2.2 resize流程老数组遍历与新下标落位resize这个方法是HashMap里最吃理解的一块。整个流程按我的拆解可以分为四步新数组创建新容量是旧容量的两倍新阈值也是旧阈值的两倍。遍历旧数组的每个槽位。对槽位上的元素逐个迁移。如果槽位上只有一个节点直接用它的hash重新计算下标搬过去如果是红黑树节点走split逻辑如果是链表就把链表拆成“低位链表”和“高位链表”两条。低位链表挂到新数组的原下标高位链表挂到新数组的原下标旧容量。第3步里的“高低位链表拆分”是实现高效扩容的关键。因为这步利用了上一节说的“多出来的一位判断”不需要对每个key重新调用hash函数只需要看hash值在旧容量对应位上的值就能决定它去哪个位置。这也是JDK 8相对JDK 7的一个大优化JDK 7扩容后所有元素都要rehash再重新落位而JDK 8分成了两条链子就地搬。从面试的视角来说能讲清楚“高低位拆分”这个细节就已经能甩开一大半背八股的人了。2.3 树化的终极条件与退化机制链表的树化不仅仅是“链表长度达到8”这么简单前面提过还有个前置条件数组长度至少达到64。如果链表长度达到8但数组长度不到64HashMap会优先扩容而不是树化。原因是数组太小的时候链表长往往是“桶太少”导致的扩容让元素分散开比维护红黑树更划算。红黑树节点在什么样的情况下会退化成链表两个入口扩容时的split逻辑以及remove时的去除逻辑。扩容时如果红黑树的元素数量减少到6以下会把树拆成普通链表。remove时如果发现某个树节点被移除后树已经很小同样会退化为链表。所以你看源码里出现了一对非常经典的数值树化阈值8和反树化阈值6。中间留了2的间隔是为了避免元素在一个阈值附近反复横跳一会儿树化一会儿退化造成性能抖动。这里我多说一句经验。在很多高并发写的场景里HashMap的树化其实非常罕见。如果你的业务数据能触发大量链表树化大概率是hash分布出了问题比如自定义key的hashCode实现太烂或者数据量级到了千万级别还没扩容到位。排查的时候别先把锅甩给树化先看看自己的key设计。3. 并发场景下的HashMapJDK 7的死循环与JDK 8的数据丢失3.1 JDK 7头插法怎么把链表变成环HashMap从来就不是线程安全的容器这一点文档里写得明明白白。但面试官关心的是你知不知道它在并发下是怎么“坏”的。JDK 7的HashMap在扩容时采用的迁移方式是头插法遍历旧链表的节点每取一个节点就插到新链表的头部。头插法的好处是代码简单遍历一个节点就插入一个节点但它在多线程环境下会出大问题——链表成环。简化一下这个过程。假设旧数组的某个桶位上有一条链表A - B - C两个线程同时触发了扩容。线程1执行到一半被挂起线程2完成了完整的迁移把链表变成了C - B - A。这时候线程1恢复执行它手里的引用还指向A节点而A节点在新的链条上已经是尾节点但线程1还会继续往下遍历把B、A继续头插。两个线程来回穿插链表的next指针就可能出现循环引用形成一个环。一旦环形成后续任何get操作在这个桶位上都会陷入无限循环CPU直接飙满。这个坑在JDK 7时代是真实事故的高发源。很多做服务端的老人都经历过“CPU 100%但线程栈看不出问题”的诡异现场最后定位到HashMap扩容并发。3.2 JDK 8改尾插法为什么还是不安全JDK 8把扩容时的头插法改成了尾插法直接把“链表成环”这个致命问题解决了。但别高兴太早HashMap在并发下依然会产生其他问题最常见的就是数据丢失。数据丢失的场景有很多种最典型的是多个线程同时put时两个线程都命中同一个空桶位都执行到“把新节点放到数组槽位”这一步。线程1放完自己的节点A线程2马上覆盖了同一个槽位放上自己的节点B。A就彻底丢了没有任何异常提示。还有一个更隐蔽的场景两个线程同时put触发扩容线程1计算完新下标还没来得及搬运线程2已经完成了整个扩容过程。线程1接着用自己的旧数组引用继续搬运很可能把线程2已经迁移过的数据覆盖掉或者漏掉某些节点。所以在并发场景下HashMap的“不线程安全”不只是“可能数据不对”而是真的会静默丢数据。你写一个并发计数服务用HashMap做累加跑着跑着发现总数变少了排查半天还不知道哪个环节丢了这个体验我想很多人经历过。3.3 那并发环境该用什么替代面试里这道题的延伸几乎必然要落到ConcurrentHashMap上。但我想强调一个容易被忽略的点并不是所有并发场景都得搬出ConcurrentHashMap。在一些读写比例极不平衡、写操作很少的场景里用Collections.synchronizedMap包一层性能虽然差一点但实现简单几乎不会有并发死角。ConcurrentHashMap的优势在高并发读多写多、且需要较高吞吐的场景下才真正体现出来。ConcurrentHashMap在JDK 8的实现和JDK 7差别很大。JDK 7用的是Segment分段锁把整个Map分成16个小段每段独立加锁JDK 8放弃了Segment直接在桶位上用synchronized加锁锁粒度更细缩小到单个槽位而且读操作几乎完全无锁配合CAS和volatile做到可见性。面试的时候如果时间够建议把“JDK 7的Segment怎么定位”、“JDK 8的synchronized加锁的桶位怎么确定”、“CAS synchronized的组合怎么工作”这几条理顺。这些是HashMap八股往深度演的必由之路。4. 源码细节里的“加分项”扰动、容量设计和modCount4.1 扰动函数为什么是“右移16位再异或”很多人看过扰动函数但没细想过为什么偏偏是右移16位而不是8位。原因在于Java的int是32位的右移16位等于把高16位和低16位各据一半异或后能尽量把高位的随机性“灌”到低位。如果右移8位混合的范围不够右移24位高8位虽然也参与了但高位信息丢失得太多混合效果反而不好。16位是一个“居中”的选择兼顾了简单性和效果。还有一层原因和JDK 7有关。JDK 7做了一次更复杂的扰动h ^ (h 20) ^ (h 12); return h ^ (h 7) ^ (h 4);总共做了四次位运算。这个设计在散列效果上确实不错但四次运算在高频put场景下还是有开销。JDK 8改成一次异或性能更好而且因为有(n - 1) hash这个掩码运算的配合实际效果损失很小。我自己测试过一个大key集合按JDK 7和JDK 8两种扰动方式分别计算下标冲突率差异基本在1%以内。所以JDK 8这个改动本质上是用一点散列均匀度的让利换取性能提升属于非常典型的性能工程取舍。4.2 默认容量16与加载因子0.75的组合逻辑为什么默认容量是16而不是8或32这其实是一个“经验值”选择。太小容易频繁扩容太大浪费内存。正常业务下一个HashMap存几十个元素很常见16个初始槽位能够容纳12个键值对不被扩容对大多数场景够用了。如果你能预判数据量会超过12最好的做法是提前指定初始容量避免put过程中发生resize。这里还有一个非常实用的性能优化技巧预估初始容量可以用expectedSize / 0.75f 1这个公式反向计算。比如你确定要存1000个键值对那么初始容量最好设成1000 / 0.75 1 1334HashMap内部会补齐到2048。这样“中途扩容”这个动作就不会发生省掉了resize时全量迁移的开销。很多人只知道new HashMap(1000)不知道这个公式结果容量被补齐到2048但阈值只有1536存到第1537个元素时照样扩容。关于“传入容量就是实际容量”这件事还有一个常见的误区。new HashMap(1000)并不是真的初始就分配1000个槽位而是通过tableSizeFor补齐到最近的2的整数次幂也就是1024。你传进去的1000只是一个“期望值”HashMap会帮你做一个“适配”。这个细节虽然小但很多面试官会在这里埋坑。4.3 modCount快速失败机制的幕后裁判modCount在HashMap源码里是一个容易被忽视的字段但它是“快速失败”fail-fast机制的核心。这个字段记录的是HashMap结构性修改的次数比如put新key、remove、clear这些操作都会让modCount加1而修改已有key对应的value不会触发。迭代器在遍历时会记录初始的expectedModCount每遍历到一个节点就会检查当前modCount和expectedModCount是否一致。只要在遍历过程中发生了任何结构性修改modCount变了迭代器就会立刻抛出ConcurrentModificationException。这个机制设计得很巧妙它没有做任何加锁或并发控制只是用一个计数器保证“遍历过程中数据没被改动过”这个基本假设。一旦假设被打破宁可粗暴地抛异常也不返回脏数据。所以在多线程环境下如果你同时遍历和修改同一个HashMap即使只是在主线程里“边遍历边remove”也会触发这个异常。正确做法是在迭代器上用iterator.remove()这个东西会同步更新modCount和expectedModCount就不会抛异常。5. 从八股文到工程实践HashMap相关的真实避坑指南5.1 自定义类做key时equals和hashCode约定不能破HashMap的put和get过程本质上依赖equals和hashCode两个方法。它的查找逻辑是先算hash定位桶位然后在链表里用equals逐个比较。这里有个硬性约定两个对象equals相等hashCode必须相等反过来不成立hashCode相等不代表对象相等它们可以只是哈希碰撞。很多自定义类做key时只重写了equals没重写hashCode或者用了一个会产生大量碰撞的hashCode实现这会让HashMap的查询性能直线下降甚至出现“同一个key存进去、换个对象取不出来”的问题。我自己踩过一个非常实际的坑把订单对象作为key存HashMap这个对象包含订单号、商品列表、创建时间等一堆字段。第一次存的时候商品列表是空的后来订单商品更新了订单对象的hashCode也跟着变了。再用同一个订单号去gethash定位的桶位和最初存储时完全不一样直接返回null。排查了很久最后发现是“可变对象做key”这个经典的HashMap陷阱。解决方案很简单优先用订单ID这种不可变字段做key或者保证对象作为key期间不被修改。5.2 HashMap在真实高频场景下的性能隐患在一些中间件和框架的源码里HashMap是高频使用的数据类型但使用不当很容易成为性能瓶颈。这里说一个高并发读取场景下常见的问题如果HashMap初始化容量太小频繁触发扩容而扩容操作本身是“全量搬迁”在高并发写入时会放大写延迟。这个延迟在单线程下可能只有几百微秒但在多线程同时写入时会被放大到毫秒级甚至造成明显的毛刺。优化的手段除了前面说的预估初始容量还有一个思路是控制平均链表长度。如果业务key的hash分布不够理想可以考虑在写入前做一层hash预处理比如给key拼接一个随机盐。不过这种做法只适用于一些特殊场景常规业务不建议这么折腾。性能排查的时候如果发现HashMap的读性能异常别急着怀疑Map本身先看两件事一是链表平均长度是否过长二是是否大量key落在同一个桶位。这两个问题都指向hash分布而不是HashMap的底层算法出了问题。5.3 红黑树不是“万能加速器”别神化树化二叉树、红黑树对很多人来说是“高级数据结构”听到HashMap引入红黑树就觉得“它变厉害了”。但真实场景下红黑树的引入是有代价的。树节点TreeNode大概比普通节点Node多占用两倍内存而且红黑树的插入和删除伴随旋转操作单次操作的开销比链表插入高不少。HashMap的设计思路是在“链表长度小”时利用链表遍历的简单和低开销只有链表长度恶化到阈值8以上才切换到红黑树来压查询复杂度。这个切换是有overhead的不是“变成了红黑树就更快”。如果你在性能敏感的路径上发现HashMap里大量树化第一反应不应该是“树化保证了性能”而应该是“hash分布是不是出了问题”。平时开发中如果需要大量hash分布均匀的key尽量选String、Integer这类本身hash实现就有良好分布的类型如果key的字段组合多可以考虑在hashCode实现里引入一些较大的质数因子比如31、37、131来分散低位信息。这个不算HashMap源码的考点但算是工程上对hash散列的直接应用面试官问到“你怎么设计一个类的hashCode”时回答这套思路很加分。最后再补充一点我的实际感受自己在梳理HashMap源码时一个比较强烈的体会是很多八股考点并不是孤立的知识点它们在源码里是互相咬合的一套设计。容量为什么是2的幂、扰动函数为什么右移16位、加载因子为什么是0.75、扩容为什么分高低位这些单独看都能背但只有把整套逻辑串起来才能理解每一个细节背后的权衡。如果你是为了面试准备这部分建议别只看结论把本篇提到的那几个方法——hash、putVal、resize、split——在JDK 8源码里各读两遍。读完再自己画一遍扩容时高低位链表拆分的流程图画完你会发现HashMap这个“老伙伴”比你印象里要有意思得多。