1. 先搞懂HashMap的整体设计思路1.1 HashMap到底是个什么结构很多人一上来就背“数组加链表JDK8之后又加了红黑树”但真问一句“为什么是这三个东西凑在一起”能答清楚的人不多。我习惯把HashMap拆成两层看外面是一个数组数组每个格子里可能是一个链表也可能是一棵红黑树。数组负责用哈希值快速定位链表和红黑树负责解决哈希碰撞之后的存储问题。数组查询快但是插入删除慢链表插入删除快但是查询慢红黑树在数据量大的时候能保证查询和插入都是对数级复杂度。HashMap把这三种结构组合起来本质上是想在“绝大多数情况下都用数组直接命中偶尔碰撞了用链表顶一下碰撞太多就用树兜底”。这个设计思路一定要先理解后面看源码才不会懵。顺便说一个基础概念数组里每个格子叫bucket桶一个桶里装了多个节点就叫发生了哈希碰撞。桶的数量就是table的长度也就是table.length。HashMap里所有的存和取都围绕bucket的定位展开。1.2 为什么容量必须是2的幂次方这是HashMap里一个非常核心但又容易被忽略的细节。计算一个key应该放到哪个桶常规做法是hash % table.length取模运算能得到一个均匀的分布。但取模运算在CPU层面开销比较大HashMap选择了一个更讨巧的方案如果table长度是2的幂次方那么hash (table.length - 1)等价于hash % table.length而且位运算的速度远快于取模。所以当你调用new HashMap(17)的时候HashMap并不会真的创建一个容量为17的数组而是会向上取整到最近的2的幂次方也就是32。这个逻辑在tableSizeFor方法里通过一连串的|和操作实现。平时写代码不一定要关心但如果面试被问到“为什么扩容都是翻倍”答案的根就在这里只有一直保持2的幂次方位运算的优化才能一直成立。另一个和容量强相关的参数是负载因子默认0.75。这个值代表“当元素数量达到容量的75%时HashMap就触发扩容”。0.75是时间复杂度和空间复杂度之间的一个折中调小了桶更空碰撞更少但空间浪费严重调大了空间利用率高但碰撞概率上升链表变长查询变慢。0.75是大量测试后选出来的平衡点一般不建议改。2. 核心方法逐行拆解拒绝死记硬背2.1 put一个key到底经历了什么JDK 8之后的put流程我建议按下面这个顺序记每一步都对应源码里的一段逻辑第一步计算key的hash值。这里不是直接用hashCode()的原始值而是做了一次扰动处理。JDK 8的代码是(h key.hashCode()) ^ (h 16)相当于把高位16位和低位16位做异或让高位的特征也能参与到底位的计算中。为什么要这样因为桶的下标只有低位参与计算如果两个key的hashCode高位不同但低位相同不扰动就容易撞到同一个桶扰动之后碰撞概率会明显降低。第二步判断table是否为空。如果是第一次put会调用resize()方法初始化数组默认长度16threshold等于16 * 0.75 12。第三步用(table.length - 1) hash定位桶下标。如果这个桶是空的直接new一个Node放进去整个put就结束了。第四步如果桶不为空分三种情况判断。第一种桶首节点的key和当前put的key完全一样hash相同且equals为true直接覆盖value。第二种桶首节点是TreeNode类型说明这个桶已经树化了走红黑树的插入逻辑,在这里不得不把之前写过关于JDK和HashMap的一些理解和大家同步一下尤其是我这几年在线上问题排查时反复验证过的那些细节基本能涵盖大家面试和日常开发会碰到的多数问题。第三种普通链表从第二个节点开始往后遍历逐个用equals比较key。如果链表中找到了相同key记录那个节点循环结束后覆盖这个节点的value如果遍历到尾部还没找到在链表尾部插入新节点然后看链表长度是否达到TREEIFY_THRESHOLD - 1如果是调用treeifyBin考虑把链表转成红黑树。这里有几个非常容易忽略的边界。第一个是treeifyBin不是无脑树化它进来后会先检查table的容量如果容量小于64会优先做扩容而不是转红黑树。只有容量大于等于64且链表长度达到8才会真正树化。这个设计是因为当容量很小的时候桶少导致碰撞多此时扩容比树化更能解决问题容量够了之后如果某个桶还是频繁碰撞才说明这批key的哈希分布确实不良树化才有意义。第二个边界是put一个key时原始值如果是null怎么办。HashMap允许null作为key。put的时候会走到一个特殊分支直接存到第0个桶不参与hash计算。这也解释了为什么HashMap可以放null而Hashtable不行Hashtable压根就不允许null key和null value。2.2 get和remove背后的细节get的流程相比put简单很多但同样有值得注意的地方。还是先算hash再用(table.length - 1) hash定位桶。如果桶是空的直接返回null。如果桶首节点命中返回value。如果桶首节点是TreeNode走红黑树的查找逻辑。如果都不是遍历链表逐个比较。判断命中的条件源码里这一行是关键if (first.hash hash ((k first.key) key || (key ! null key.equals(k))))先比较hash再比较或equals。为什么要先比hash因为hash是否相等是一个非常廉价的过滤条件能直接排除掉绝大多数不匹配的key只有hash相同才有必要做昂贵的equals比较。这个顺序本身就是一种性能优化。remove流程和get大体一致区别在于找到节点之后要执行链表删除操作。这里有个细节如果被删除的节点是TreeNode走红黑树的删除逻辑删除后如果红黑树节点数量小于等于UNTREEIFY_THRESHOLD默认6会把红黑树退化成链表。树化阈值是8退化阈值是6中间留了2的缓冲空间防止在阈值临界点频繁转换。这2个数字的组合就是典型的“用空间换稳定性”的设计思路。2.3 resize扩容机制以及JDK 7头插法的致命问题扩容是HashMap里最复杂、也最值得画时间理解的部分。触发条件是size threshold也就是元素数量超过了容量乘负载因子的阈值。扩容时新容量是旧容量的两倍threshold也相应翻倍。JDK 8的扩容迁移逻辑和老版本有一个重大区别这个区别直接决定了JDK 8之后不会出现扩容死循环。老版本的迁移方式是遍历每个桶把桶里的节点按顺序重新头插到新数组的对应位置。头插法在并发场景下扩容时两个线程同时操作同一个链表很容易形成环形链表之后任何一次get到该桶都会陷入死循环。JDK 8改成尾插法并且做了一件事把原来一个桶里的链表按计算结果拆成“低位链表”和“高位链表”两条分别放到新数组的原下标和原下标 旧容量两个位置。为什么能这么拆因为扩容之后用新容量计算下标等价于在原来下标的基础上最高位多看了一个bit。如果这个bit是0下标不变如果是1下标加旧容量。所以遍历一次链表就能完成拆分不需要重新计算hash也不需要像JDK 7那样逐个头插。这块代码在源码里的resize()方法尾部是HashMap整个类里我建议重点读三遍以上的部分。顺带提一句尾插法只是解决了并发扩容死循环的问题但HashMap在并发环境下仍然是不安全的。并发put会导致数据覆盖、size统计不准等问题所以并发场景的正确选择永远是ConcurrentHashMap而不是用Collections.synchronizedMap包一层然后指望它高效。3. JDK版本演进带来的差异不只是加了一棵树3.1 JDK 7到JDK 8的变更总览把两个版本的差别列成一张表会看得更清楚对比项JDK 7JDK 8数据结构数组 链表数组 链表 红黑树链表插入方式头插法尾插法hash扰动算法4次位运算 5次异或1次位运算 1次异或扩容迁移方式重新计算hash并头插高低位拆分无需重算hash树化支持无链表长度超过8且容量超64上表里JDK 8的hash扰动算法看似简化了实际上是因为树化策略让大量碰撞场景的性能不再那么依赖扰动函数。链表在长度8之前已经把查询成本控制在一个很小的常数范围内超过8就树化所以即使hash分布不够均匀也能靠红黑树兜底。这是两个改动之间的隐性联动很多人只注意了数据结构的变化忽略了算法简化背后的逻辑。3.2 JDK 9到17HashMap里那些不起眼的变化JDK 9之后HashMap的源码层面也有不少小调整只是平时八股文很少提。比如JDK 9开始HashMap里用到的部分常量引入了jdk.internal.vm.annotation.Stable注解这个注解和JIT编译器的优化有关能让table数组在编译优化时被更稳定地处理。JDK 12引入了HashMap的keySet和entrySet视图的迭代器优化。JDK 13到17期间主要变化集中在垃圾回收器的配合上比如JDK 16在ZGC中为HashMap的迭代场景做了更好的内存屏障处理。这些内容不需要深究但有一个趋势值得注意从JDK 8到JDK 17HashMap的核心算法没有大改JVM层面的配合和优化却一直在推进。这提醒我们研究HashMap的时候不要只盯着HashMap.java一个文件还要考虑到它在整个JVM运行时环境中的表现。如果你在JDK 17上跑项目实际感受可能和JDK 8没有明显区别但这不代表JDK 17的HashMap没有变化。比如JDK 17中字符串和包装类的hashCode计算本身有优化这间接影响了HashMap的key分布质量。另外JDK 17默认启用强封装--add-opens之类的参数会影响一些依赖反射库的框架但HashMap本身不受影响。4. 线程安全专题为什么不用HashMap做并发缓存4.1 HashMap线程不安全的三个现场网上讲线程安全时都喜欢说“线程不安全建议用ConcurrentHashMap”但很少把不安全的现场还原出来。我实际操作中遇到过三类问题。第一类是数据覆盖。两个线程同时put不同的key但定位到同一个桶。线程A判断桶为空准备插入线程B也判断桶为空抢先插入。线程A随后覆盖了线程B的节点导致B的写入丢失。第二类是size统计错误。size字段被多个线程并发修改modCount快速失败机制会直接抛出ConcurrentModificationException这个异常在很多业务里表现为“莫名其妙的全量失败”排查起来非常容易绕弯路。第三类是JDK 7时代的扩容死循环JDK 8改成了尾插法从根源上消除了环形链表但如果你还在维护老系统的JDK 7代码这个问题依然是真实存在的风险。我的建议是不要写“赌自己不会遇到并发”的代码一旦用了多线程就必须有明确的并发策略。4.2 ConcurrentHashMap是怎么扛住并发的JDK 7的ConcurrentHashMap用分段锁把整个Map切成16个Segment每个Segment维护一个小HashMap锁粒度是Segment级别。JDK 8的ConcurrentHashMap直接用CAS synchronized做细粒度控制锁只落在单个桶上并发度大幅提升。具体到put操作JDK 8的流程是如果桶为空用CAS尝试直接放入如果CAS失败或桶不为空给桶首节点加synchronized锁再走链表或红黑树的插入逻辑。扩容的时候它支持多线程协同迁移每个线程负责一部分桶。同时它引入了ForwardingNode标记节点让其他线程在put或get时发现自己访问的桶已经被迁移能立刻转向新数组继续操作不需要阻塞等待整个扩容完成。日常开发中使用ConcurrentHashMap有一个非常容易踩的坑size()方法在并发环境下返回的是一个近似值。因为多线程并发写入时精确统计size需要全局锁代价太大所以ConcurrentHashMap选择了baseCount CounterCell[]的方式尽量逼近真实值。如果你的业务逻辑强依赖精确的size比如“如果map为空就执行某个操作”这种判断在并发场景下永远是危险的正确做法是用独立的原子计数或业务状态字段维护而不是依赖Map的size。5. 背八股不如真排查高频面试题速查与一线避坑5.1 高频面试题速查表下面这些题目基本覆盖了当前Java面试中关于HashMap的所有常见提问我把答案要点一并整理出来面试题关键回答要点HashMap底层数据结构数组 链表 红黑树桶内节点数超过8且容量超过64时树化为什么负载因子是0.75空间和时间复杂度的折中过高碰撞增加过低空间浪费为什么容量是2的幂次方用位运算替代取模hash (length - 1)等价于hash % lengthJDK 7和JDK 8的区别树化、尾插法、扩容高低位拆分、hash扰动简化为什么链表转红黑树阈值是8泊松分布下命中8的概率极低8是平衡点HashMap为什么不安全数据覆盖、size不准、modCount快速失败ConcurrentHashMap怎么保证安全JDK 8是CAS synchronized锁粒度到单个桶红黑树退化的条件节点数小于等于6时退化为链表key可以是null吗HashMap允许key为null时固定存到第0个桶自定义对象做key要注意什么重写equals和hashCode保持不可变回答这些题目的时候切忌只背结论。比如被问到“为什么树化阈值是8”你可以补一句“这是基于泊松分布的概率计算在负载因子0.75、随机哈希的理想情况下一个桶里出现8个节点的概率只需要大约千万分之一”。这个细节会和其他候选人拉开差距。5.2 真实项目里的HashMap排坑经验第一个经验是关于可变对象做key的。我在一个缓存场景里犯过这个错用List作为key运行一段时间后数据的hashCode变了结果key定位不到原来的value。排查的时候发现每次读出来的都是null但内存里数据明明存在。原因就是List里的内容被修改导致hashCode变了HashMap再根据原始hash找桶时根本定位不到原来的位置。这类问题一旦出现非常难排查因为代码逻辑完全没有报错只是数据“凭空消失”。所以使用HashMapkey对象必须不可变或者确保加入后绝不被修改。第二个经验是关于初始容量的预估。如果需要存1万条数据直接在构造器里指定容量可以避免多次扩容。但要注意指定容量并不能完全避免扩容因为HashMap会在size capacity * 0.75时自动扩容。如果你想存1万个元素推荐初始容量设置为10000 / 0.75 1约等于13334再向上取整到2的幂次方也就是16384。这样设置之后整个生命周期不会发生一次扩容性能是最优的。实际开发中也可以直接写Maps.newHashMapWithExpectedSize(10000)Guava帮你做了这件事。第三个经验是关于HashMap做缓存。有很多人图方便直接用HashMap当本地缓存时间久了出现OOM。排查的时候发现大量的值堆积在HashMap里无法释放。这类问题的本质是HashMap没有淘汰机制只能增长不能收缩当数据量超过JVM堆时必然OOM。而且HashMap被GC Roots引用时整个Map里的对象都无法被回收问题会被迅速放大。正确的替代方案是使用Caffeine这类带淘汰策略的缓存组件或者至少自己在业务层定制淘汰逻辑。5.3 从HashMap源码延伸到其他集合类的学习方法最后分享一个我读集合源码的方法这个方法比记住HashMap的每一个细节更有长期价值。每看一个集合类我都会问自己三个问题这个集合底层用什么结构存数据它的增删改查复杂度分别是什么它在什么情况下性能下降最严重用这套框架去读HashMap会得到三条清晰的结论底层是数组加链表加红黑树增删改查平均O(1)最坏O(log n)性能下降的原因是哈希分布不均匀和频繁扩容。然后用同样的框架去看TreeMap底层是红黑树增删改查都是O(log n)性能瓶颈在于比较器的效率。再看ConcurrentHashMap底层结构和HashMap相同但通过并发控制让单桶操作在并发场景下依然保持O(1)。整个集合框架的脉络就串起来了。读源码时也不要只看JDK 8。JDK 11之后String.hashCode()的行为、JDK 17中HashMap对迭代器的优化这些细节不会影响你回答基础的八股题但会让你在面对“你用过JDK 17吗”这类问题时有自己的真实理解而不是背了一段别人的经验。比如你可以说JDK 17下HashMap的哈希扰动算法和JDK 8一致但并发场景我更习惯用ConcurrentHashMap它从JDK 8开始改用CAS加synchronized锁粒度更细读多写少的场景还可以考虑使用ImmutableMap或ConcurrentSkipListMap。这种表达比干巴巴说“我用了JDK 17”有价值得多。我自己的习惯是遇到一个拿不准的源码细节直接在本地写一段小Demo跑一下用-Xmx限制堆内存用断点看每个局部变量的值。比如验证HashMap树化写一个自定义类让它所有实例的hashCode都返回同一个值再连续put十几个元素断点里就能看到TreeNode的生成过程。这种方式比刷一百道题都管用也建议你试试。