1. 面试官抛出HashMap底层原理到底想听到什么如果你是Java后端方向的候选人这个问题大概不陌生。HashMap不仅是一个日常开发高频使用的容器类更是几大基础知识的交汇点哈希算法、数据结构、位运算、扩容策略和并发安全边界全都在这一个类上体现出来了。很多面试官喜欢用它当热身题因为问得快、问得深候选人水平如何三五句话里就能有个大概判断。很多人一听到“底层原理”第一反应是背源码。实际上面试官要的不是源码默写而是你能不能讲清楚三个为什么为什么HashMap要用数组加链表为什么容量正好是2的幂为什么线程不安全如果你能从现象反推到设计意图再从设计意图落到具体实现这场面试已经赢了一半。反过来如果你张口就是“默认容量16负载因子0.75”这两句基本就等于在脸上写着“我只刷过题但没理解”。这篇文章不会给你一个完美的“标准答案”而是把HashMap从网上众说纷纭的碎片信息里重新拼回一张完整地图。适合谁看刚准备跳槽的Java开发、正在学集合源码的学生以及那些用HashMap写了很多年代码、却说不清扩容时节点怎么搬家的“熟练工”。看完之后你不仅知道put和get发生了什么还能顺势答出好几个被追问的细节选JDK版本也更有底气。1.1 这题的考察边界先画一下面试官的意图。HashMap底层原理看起来很宽其实范围是收敛的底层结构、hash函数、put/get流程、扩容机制、并发问题、同族对比。你把这六块讲完基本上就是一份完整的开卷回答剩下的追问都是在这六块里继续挖。别小看这个边界划分很多人答不好不是因为不知道而是把无关的知识扯进来比如反手就开始背红黑树旋转算法结果面得更乱。1.2 一条面试回答主线我自己比较推荐的回答顺序是结构怎么说清楚哈希怎么定位冲突怎么解决扩容怎么触发并发有什么限制和别的Map差在哪。这个顺序本身就是在讲故事一个数据进来先经过哈希函数得到桶下标再放进链表或者红黑树装不下了就扩容多线程并发就出问题最后引出替代方案。故事一讲完面试官自然会追问细节比如树化阈值为什么是8、负载因子为什么是0.75这些细节正好是这篇文章后面重点展开的部分。2. HashMap的底层结构数组、链表与红黑树2.1 数组加链表的设计意图HashMap在JDK 8以后的实现中存储主体是一个NodeK,V[] table数组。每个数组位置习惯上叫桶bucket桶里放的是一个单向链表头节点。为什么需要数组因为数组支持随机访问根据下标能够在O(1)时间内定位到一个桶为什么桶里要挂链表因为哈希函数不可能做到完全无冲突多个不同key算到同一个桶时就得用链表把这些冲突元素串起来。这里有个生活化的类比一排储物柜每格柜子代表一个桶正常情况下一格柜子只放一个包。但有些人拿到的钥匙会指向同一个柜子这时柜子不够用就在柜子外面挂一根绳子把同号的多个包依次挂在绳子上。你想取A包先走到对应柜子然后顺着绳子一个个比对标签直到找到A包。链表就是这个绳子节点里的next字段就是它连接下一个元素的方式。Node节点本身很简单字段就四个hash值、key、value、next指针。其中hash并不是key.hashCode()直接返回的值而是经过一个扰动函数处理过的值这个细节后面会单独说。数组加链表解决哈希冲突的方法在数据结构里叫链地址法拉链法它比开放寻址法更适合存储动态增长的键值对因为容器扩容不用一个一个找空位整体实现起来更简单。2.2 红黑树是“补丁”而不是默认形态如果链表只有一个问题那就是冲突多的时候查询会退化成O(n)。设想一个极端场景某一堆数据全都落进同一个桶HashMap就成了纯链表get一个元素要遍历几百个节点性能惨烈。极端情况下3万个元素堆在同一个桶里get就要遍历3万次这种性能风险在线上的很多场景是不能接受的。于是JDK 8引入了一项改造当链表长度达到阈值8并且table数组长度不小于64时这个桶的链表会转换成红黑树。红黑树是平衡二叉搜索树的一种它的插入、删除、查找时间复杂度都是O(log n)。链表长度是8时最坏要比较8次树化后最坏大约比较4次当链表长度涨到10000时两种结构的差距就不是一个数量级的问题了所以这个“补丁”主要为了保护极端哈希分布。注意还有一个容易被忽略的约束table长度小于64时不会直接树化而是优先扩容。原因是节点太少时红黑树的维护成本变色、旋转、父子节点指针比链表高先扩容反而能让节点更分散从根上降低单桶长度这才是更划算的处理方式。从红黑树退化回链表也有讲究。当删除节点或者扩容后某个桶的红黑树节点数降到6及以下就会转回链表。树退化阈值选6而不选8是为了留出缓冲区间避免在临界点附近频繁反复转换。如果树化和退化都设成8一个桶的元素在7、8、9之间震荡系统就会不断做链表和树的互转白白消耗CPU。这跟空调设成26度后反复启停就会更耗电的逻辑差不多留出迟滞区间更稳定。2.3 一组必须记住的初始化参数把关键数字整理成一张表面试前可以快速默背参数值说明默认初始容量16桶数组长度最大容量1 30约等于10.7亿默认负载因子0.75扩容用的触发系数树化阈值8链表长度达到8考虑转红黑树树退化阈值6红黑树节点数降到6转回链表最小树化容量64桶数组长度小于64时优先扩容这些数字看着像魔法数字其实背后都有自己的逻辑。比如树化阈值8官方注释里提到哈希桶中的链表长度服从泊松分布在负载因子0.75和随机哈希假设下链表长度达到8的概率只有约0.00000006所以正常情况下根本不会走到红黑树红黑树纯粹是为恶意哈希或者极少数哈希碰撞准备的“保险”。面试官问到8你要是能答出泊松分布这个细节就能立住。3. put和get的完整流程一次哈希旅行的台前幕后3.1 先看hash()高位参与运算的两行代码HashMap定位桶的下标用的不是key.hashCode()本身而是对hashCode再做一次扰动static final int hash(Object key) { int h; return (key null) ? 0 : (h key.hashCode()) ^ (h 16); }这行代码的意思是把hashCode的高16位和低16位做异或让高位的差异也能扩散到低位。为什么需要这样因为计算桶下标时HashMap用的是(n - 1) hash如果table容量比较小n - 1的高位基本都是0那么结果只由hash的低位决定高位不管怎么变都可能落到同一个桶。如果key重写了hashCode但只影响高位低16位全部相同冲突率就会被放得很大。做了异或之后高低位混合桶分布会更均匀。注意JDK 7的hash扰动次数比这多执行了多次带掩码的异或而JDK 8只做一次因为随着CPU和哈希算法整体质量提高一次高位异或已经能带来很好的分散效果多了反而成为性能负担。这也是一个能跟面试官聊的演进点JDK 8为什么要简化扰动函数为了在随机性和执行速度之间找到平衡。桶下标公式是 i (n - 1) hashn表示数组长度。这个式子有两个作用第一它相当于hash对n取模因为当n是2的幂时(n - 1)的二进制就是全1掩码按位与等价于取余第二位运算比取模快得多每秒几十万次的put场景这一点点性能差距会被放大。这也是HashMap要把容量强行规整成2的幂的核心理由。3.2 put流程一步一步跟着走put方法看似复杂度不高翻开源码却有好几十行。我把关键判断收敛成以下流程第一步如果key是null哈希记为0这个null key会进入桶0后续扩容时它也会按正常规则参与重新定位不影响取值正确性。第二步对key做hash()得到扰动后的哈希值。第三步如果table还没初始化或者长度是0先调用resize()初始化桶数组初始容量默认16。第四步计算下标i (n - 1) hash取出table[i]。如果该位置是null直接用当前key-value构建新Node放入put结束。第五步如果table[i]不为null说明发生了冲突。先比较哈希值和key是否和已有节点相同如果相等说明是同一个key直接覆盖value然后返回旧value。第六步如果key不同看当前节点是不是TreeNode。是红黑树节点就走红黑树插入逻辑在树里找到合适位置放进去如果发现相同key则覆盖。第七步如果是普通链表节点就沿着next指针往后遍历。遍历过程中如果发现某个节点的key相同就替换value并返回旧值如果遍历到链表结尾都没找到就在链表尾部追加新节点尾插法。追加完成后如果链表长度达到树化阈值8调用treeifyBin方法尝试转成红黑树但treeifyBin内还会再判断一次table是否达到64不满足就扩容。第八步把modCount加1这是一个用来处理迭代器fail-fast的计数器。最后如果当前键值对数量size超过了threshold阈值触发resize()扩容。这段流程有几点值得细说。为什么JDK 8一定要用尾插法因为在扩容并发场景下头插法可能把链表顺序反转多线程并行扩容时很容易形成环形链表导致get死循环尾插法至少能保持元素之间的相对顺序虽然依然不是线程安全但那种“一个线程get卡死”的极端概率小很多。3.3 get流程差不多是put的逆过程get的流程比put简单。先对key取hash算出桶下标如果对应桶是空就直接返回null。如果桶首节点的hash和key都能匹配直接返回value。否则看首节点是不是红黑树节点是就走树查找不是就遍历链表逐个用equals判断key是否相等找到就返回值找不到就返回null。有个高频追问隐藏在equals这里hashCode相等的两个对象不一定equalsequals相等的两个对象hashCode一定相等。作为HashMap的keyequals和hashCode必须同时遵守契约。不然一个对象存进去之后第二次用“逻辑相等”的另一个对象去gethashCode不同连桶都不一样自然拿到null。自定义对象当key之前先想想这两个方法重写没有这是真实项目里特别常见的线上事故来源。4. 负载因子与扩容HashMap的性能命门4.1 为什么是0.75这个“魔法数字”负载因子等于元素个数除以桶数组长度它决定了一个HashMap装载到多“满”时触发扩容。JDK默认0.75意味着当桶的数量用了75%时就提前扩容。这时候桶里元素其实还不算多为什么要提前因为哈希表的查找时间不是均匀分布的桶个数越少哈希冲突概率越高链表和红黑树的压力越大。如果把负载因子设成1也就是数组全部塞满才扩容看着是节省了内存实际上冲突严重后查找成本飙升。如果设置到0.5吞吐率确实更稳但每个桶平均只装半个元素一半内存空间被浪费。0.75是一个经典折中它是在时间成本和空间成本之间反复权衡后得到的经验值。官方注释用泊松分布解释了为什么在0.75下单桶元素数量达到8的概率极其低这也是红黑树化只在极端情况下才出现的前提。4.2 扩容到底在做什么扩容的触发条件是size thresholdthreshold table容量 * 负载因子。默认容量16负载因子0.75所以threshold初始是12也就是put第13个键值对时会触发第一次扩容。扩容的大致过程是新数组长度变成旧数组的两倍然后遍历旧table的每一个桶把里面的节点重新放置到新数组里。这里不需要对所有Node重新计算hash值因为key的hash已经算好了变化的只是下标。由于新容量是旧容量的2倍原本在某个桶里的节点在新数组里只可能出现在两个位置一个是原来的下标不变另一个是原来的下标加上旧容量。判断依据是一条位运算if ((e.hash oldCap) 0)。这是因为oldCap是2的幂它的二进制只有一个1对应在扩容后正好变成新数组下标里新增的那一个高位。如果hash在这一位是0说明索引不变如果是1说明新的索引等于旧索引加oldCap。用位运算替代重算哈希整个扩容只需要遍历原有节点不需要重新计算下标效率高很多。还有个常识要留意扩容的代价并不止“复制一遍”这么简单。每次扩容都要重新分配一个更大的数组并且把全部节点迁移一遍所以大Map频繁扩容会造成明显的卡顿。如果事先能知道数据规模最好通过new HashMap(expectedSize / 0.75f 1)来初始化从源头减少扩容次数。这也是很多团队静态代码检查会强制要求写初始容量的原因。4.3 为什么容量强制要求是2的幂很多人背住了“HashMap初始容量是16扩容是2倍”却不知道为什么要这么做。核心原因是两个一是桶下标用位运算二是要让模运算等价于按位与从而提升寻址速度。假设容量不是2的幂比如17那么(n - 1) hash得到的结果无法覆盖0到16全部下标有些桶永远空着有些桶被多次碰撞内存分布不均匀。当调用带initialCapacity的构造方法时HashMap并不会直接用你给的数字而是调用tableSizeFor把它转成2的幂中最小的那一个。比如你传30最终初始化容量是32你传17最终是32你传100最终是128。这套“向上取整到2的幂”的逻辑就是为了保证后面每次扩容数组长度都保持2的幂寻址代码始终可以放心使用位运算。5. 并发场景下的HashMap三个经典失败现场5.1 数据覆盖两个线程同时写同一个桶很多刚接触并发的人以为HashMap的问题只有扩容死循环其实更常见也更隐蔽的是数据覆盖。两个线程同时执行put都定位到同一个空桶A线程写入一个NodeB线程后脚也写入一个Node。如果两个线程的Node没有同步前一个Node就可能被后一个覆盖或者产生一种“明明put了两次size却少一个”的现场。原因很简单put操作不是原子的读数组、判断空位、创建Node、赋值给数组这一连串步骤在CPU时间片切换下可以被拆开执行。有人会问size总该安全一点吧并不是。size包括了读size、加一、写回size三个步骤多线程下照样会丢更新。这就是为什么并发场景永远不要直接使用HashMap而是选ConcurrentHashMap或者其他线程安全容器。5.2 JDK 7扩容死循环那个让服务器卡死的传说网上流传了很多关于“HashMap扩容导致CPU 100%”的真实故障案例背后的机制主要在JDK 7。JDK 7的扩容转移链表用的是头插法遍历旧链表的每个节点每拿到一个就插入到新桶的头部。多线程并发扩容时两个线程同时处理同一条链表线程A还没来得及完成转移线程B已经把表头顺序反转了这样几个节点的next引用可能互相指回形成环形链表。之后无论是get还是再次扩容都可能在遍历链表时进入无限循环最终CPU飙升到100%服务彻底失去响应。JDK 8把插入改成尾插法虽然没有从根上解决线程安全问题数据覆盖、size异常依然存在但至少避免了这种环形链表死循环。如果面试中有人拿老版本故障来考你你完全可以顺着回答这个问题在JDK 8中已经通过尾插法和更完善的resize逻辑做了缓解但线程安全问题依然要靠并发容器解决。5.3 面试里怎么回答线程不安全一个简洁又不短的回答句式是HashMap在设计上就没有考虑并发场景。它没有锁所以put的检查与写入之间不是原子的并发写会覆盖数据size的统计也不安全会出现size与实际数量不一致更关键的扩容时多个线程同时rehash会把链表结构移动得乱七八糟旧版本甚至形成环形链表。JDK 8优化了一部分问题但依旧不能保证任何线程安全所以在并发场景必须使用ConcurrentHashMap或对HashMap做Collections.synchronizedMap包装。说完这段话面试官大概率会顺着问“ConcurrentHashMap怎么保证线程安全”正好接到下一部分。6. 同族对比一次把Map家族讲清楚6.1 HashMap与HashTable的差异清单HashTable是JDK 1.0时代的遗留类也是初代线程安全Map。它通过在方法上加synchronized锁整个表只有一把锁任何线程在操作之前都得排队并发度极低。相比之下HashMap在单线程里没有锁吞吐量更高HashTable的key和value都不允许null如果把null传进去会直接抛NullPointerException而HashMap的key和value都允许nullnull key被特殊处理。两者在扩容策略上也不一样。HashMap初始容量是16之后翻倍成长并且始终是2的幂HashTable初始容量是11扩容时变成 oldCapacity * 2 1也就是大致翻倍再加1。HashTable这种长度设计是为了降低哈希冲突但它也因此没法用位运算求下标每次要取模性能上就吃亏。HashTable在并发性能上被ConcurrentHashMap全面压制但它仍然有存在感。Java的集合工具类里有一个Collections.synchronizedMap方法它可以把任意Map包装成一个线程安全Map原理和HashTable一样都是粗粒度锁一个方法调用内部全部synchronized。这类Map适合并发量低、对性能不敏感的老系统维护不适合新项目。6.2 ConcurrentHashMap现代并发的选择面试官问到Map家族你需要知道的不只是HashTable落后还要知道ConcurrentHashMap为什么先进。JDK 7的ConcurrentHashMap把所有桶分成若干个Segment每个Segment是一把独立的锁不同的Segment可以由不同线程并发写所以叫分段锁。JDK 8把分段锁去掉了锁的粒度进一步缩小到桶单个数组元素。JDK 8的实现思路是当某个桶为空时用CAS直接放新Node当桶非空时给这个桶的头节点加synchronized锁然后执行插入或者树化操作。另外size统计使用CounterCell数组做分散计数尽量降低写锁竞争。这一套组合拳下来在容量大、并发高的场景里ConcurrentHashMap的吞吐量能比HashTable高出一大截。用一张表对比它们最直观维度HashMapHashTableConcurrentHashMap线程安全否是全表锁是桶级锁/CASKey/Value允许null是否否并发性能最高单线程最低高扩容策略2倍保持2的幂约2倍1更细粒度迁移适用场景单线程无并发老系统兼容多线程读写这里有个面试官非常喜欢的小点ConcurrentHashMap为什么不允许null key和null value官方意图是并发容器如果用null表示“查不到”就会出现歧义你get到null到底是不存在还是value本来就是null如果允许null在多线程环境下还需要再做一次containsKey确认而containsKey在并发下语义也会漂移。所以干脆从源头禁止null让空值在语义上等价于不存在。这个理由虽然业界还有争议但作为面试回答基本通用。7. 高频追问速查与实战避坑经验7.1 高频追问速答把前面零零散散的知识点收敛成几个小问题方便你当作卡片来背问链表什么时候转红黑树答同一个桶链表长度达到8并且table容量至少为64两个条件同时满足才树化否则优先扩容。问为什么退化阈值是6答7是缓冲带避免链表和树在临界点反复横跳。树节点保留了前后指针占用内存更大退化成链表后内存更省。问HashMap的key可以是null吗答可以hash()方法对null返回0所以null key在桶0但它也会在扩容时按正常规则挪位置。问两个hashCode相同的对象一定冲突吗答桶下标还要经过(n-1)hash所以只能说大概率落到同一个桶实际下标还受容量和低位掩码影响。问为什么自定义对象作为key时必须重写hashCode和equals答HashMap用hashCode定位桶用equals比较是否同一个key。只重写equals会导致逻辑相等的对象被分到不同桶get返回null。问遍历HashMap时能直接remove吗答不能。普通遍历中使用map.remove会导致modCount变化迭代器检测到就会抛ConcurrentModificationException要用iterator.remove或者先收集要删除的键再统一删除。问默认容量为什么是16答16是2的幂且作为初始容量不会太大也不会太小配合0.75负载因子默认能容纳12个键值对才扩容对大多数场景够用。7.2 项目开发里值得存档的经验第一预判容量再初始化。假如你要在启动阶段加载10万条配置new HashMap(100000)并不可靠因为当元素超过threshold时会提前扩容应该使用new HashMap(100000 / 0.75f 1)这种带余量的写法让初始容量一步到位减少扩容迁移的抖动。第二不要用HashMap做永久缓存容器。HashMap不是线程安全也未限制容量长期运行在服务器里很容易变成“内存炸弹”。做本地缓存应该考虑并发版本或者带容量限制的淘汰容器。如果你只是想实现一个LRU缓存LinkedHashMap构造参数accessOrder设为true并重写removeEldestEntry就能完成不用自己手写链表结构。第三String和Integer是最安全的key类型它们的hashCode和equals实现经过了大量场景考验分布质量好。使用自定义POJO当key时除了重写两个方法最好还确保对象不可变例如把参与hashCode计算的字段设为final否则对象某个字段变了hashCode跟着变化你再用同一个对象去get桶都找不到了。第四如果真的是读多写少的高并发缓存先调研ConcurrentHashMap的弱一致迭代器是否满足业务如果需要强一致的跨线程读取还是要加锁或者使用其他存储方案。第五看源码时不要总盯JDK 8往后的代码偶尔打开一个JDK 7的HashMap比一比你会对链表头插法和尾插法的差异理解得非常立体。历史版本里的bug和设计反复恰恰是理解“为什么这么设计”最好的老师。如果面试官最后让你说复杂度你可以收在这一句随机哈希下HashMap的put、get平均是O(1)最坏情况下所有key落同一个桶JDK 8之前退化成O(n)JDK 8之后因为红黑树的存在最坏也能到O(log n)。这句话把数据结构和最坏复杂度的理解一起带出来听起来就比单纯的“O(1)”更有层次。 
长河君 · 2026/10/13 20:58:39 · 阅读 1.2k HashMap底层原理全解析：从哈希冲突到红黑树与扩容机制
1. 面试官抛出HashMap底层原理到底想听到什么如果你是Java后端方向的候选人这个问题大概不陌生。HashMap不仅是一个日常开发高频使用的容器类更是几大基础知识的交汇点哈希算法、数据结构、位运算、扩容策略和并发安全边界全都在这一个类上体现出来了。很多面试官喜欢用它当热身题因为问得快、问得深候选人水平如何三五句话里就能有个大概判断。很多人一听到“底层原理”第一反应是背源码。实际上面试官要的不是源码默写而是你能不能讲清楚三个为什么为什么HashMap要用数组加链表为什么容量正好是2的幂为什么线程不安全如果你能从现象反推到设计意图再从设计意图落到具体实现这场面试已经赢了一半。反过来如果你张口就是“默认容量16负载因子0.75”这两句基本就等于在脸上写着“我只刷过题但没理解”。这篇文章不会给你一个完美的“标准答案”而是把HashMap从网上众说纷纭的碎片信息里重新拼回一张完整地图。适合谁看刚准备跳槽的Java开发、正在学集合源码的学生以及那些用HashMap写了很多年代码、却说不清扩容时节点怎么搬家的“熟练工”。看完之后你不仅知道put和get发生了什么还能顺势答出好几个被追问的细节选JDK版本也更有底气。1.1 这题的考察边界先画一下面试官的意图。HashMap底层原理看起来很宽其实范围是收敛的底层结构、hash函数、put/get流程、扩容机制、并发问题、同族对比。你把这六块讲完基本上就是一份完整的开卷回答剩下的追问都是在这六块里继续挖。别小看这个边界划分很多人答不好不是因为不知道而是把无关的知识扯进来比如反手就开始背红黑树旋转算法结果面得更乱。1.2 一条面试回答主线我自己比较推荐的回答顺序是结构怎么说清楚哈希怎么定位冲突怎么解决扩容怎么触发并发有什么限制和别的Map差在哪。这个顺序本身就是在讲故事一个数据进来先经过哈希函数得到桶下标再放进链表或者红黑树装不下了就扩容多线程并发就出问题最后引出替代方案。故事一讲完面试官自然会追问细节比如树化阈值为什么是8、负载因子为什么是0.75这些细节正好是这篇文章后面重点展开的部分。2. HashMap的底层结构数组、链表与红黑树2.1 数组加链表的设计意图HashMap在JDK 8以后的实现中存储主体是一个NodeK,V[] table数组。每个数组位置习惯上叫桶bucket桶里放的是一个单向链表头节点。为什么需要数组因为数组支持随机访问根据下标能够在O(1)时间内定位到一个桶为什么桶里要挂链表因为哈希函数不可能做到完全无冲突多个不同key算到同一个桶时就得用链表把这些冲突元素串起来。这里有个生活化的类比一排储物柜每格柜子代表一个桶正常情况下一格柜子只放一个包。但有些人拿到的钥匙会指向同一个柜子这时柜子不够用就在柜子外面挂一根绳子把同号的多个包依次挂在绳子上。你想取A包先走到对应柜子然后顺着绳子一个个比对标签直到找到A包。链表就是这个绳子节点里的next字段就是它连接下一个元素的方式。Node节点本身很简单字段就四个hash值、key、value、next指针。其中hash并不是key.hashCode()直接返回的值而是经过一个扰动函数处理过的值这个细节后面会单独说。数组加链表解决哈希冲突的方法在数据结构里叫链地址法拉链法它比开放寻址法更适合存储动态增长的键值对因为容器扩容不用一个一个找空位整体实现起来更简单。2.2 红黑树是“补丁”而不是默认形态如果链表只有一个问题那就是冲突多的时候查询会退化成O(n)。设想一个极端场景某一堆数据全都落进同一个桶HashMap就成了纯链表get一个元素要遍历几百个节点性能惨烈。极端情况下3万个元素堆在同一个桶里get就要遍历3万次这种性能风险在线上的很多场景是不能接受的。于是JDK 8引入了一项改造当链表长度达到阈值8并且table数组长度不小于64时这个桶的链表会转换成红黑树。红黑树是平衡二叉搜索树的一种它的插入、删除、查找时间复杂度都是O(log n)。链表长度是8时最坏要比较8次树化后最坏大约比较4次当链表长度涨到10000时两种结构的差距就不是一个数量级的问题了所以这个“补丁”主要为了保护极端哈希分布。注意还有一个容易被忽略的约束table长度小于64时不会直接树化而是优先扩容。原因是节点太少时红黑树的维护成本变色、旋转、父子节点指针比链表高先扩容反而能让节点更分散从根上降低单桶长度这才是更划算的处理方式。从红黑树退化回链表也有讲究。当删除节点或者扩容后某个桶的红黑树节点数降到6及以下就会转回链表。树退化阈值选6而不选8是为了留出缓冲区间避免在临界点附近频繁反复转换。如果树化和退化都设成8一个桶的元素在7、8、9之间震荡系统就会不断做链表和树的互转白白消耗CPU。这跟空调设成26度后反复启停就会更耗电的逻辑差不多留出迟滞区间更稳定。2.3 一组必须记住的初始化参数把关键数字整理成一张表面试前可以快速默背参数值说明默认初始容量16桶数组长度最大容量1 30约等于10.7亿默认负载因子0.75扩容用的触发系数树化阈值8链表长度达到8考虑转红黑树树退化阈值6红黑树节点数降到6转回链表最小树化容量64桶数组长度小于64时优先扩容这些数字看着像魔法数字其实背后都有自己的逻辑。比如树化阈值8官方注释里提到哈希桶中的链表长度服从泊松分布在负载因子0.75和随机哈希假设下链表长度达到8的概率只有约0.00000006所以正常情况下根本不会走到红黑树红黑树纯粹是为恶意哈希或者极少数哈希碰撞准备的“保险”。面试官问到8你要是能答出泊松分布这个细节就能立住。3. put和get的完整流程一次哈希旅行的台前幕后3.1 先看hash()高位参与运算的两行代码HashMap定位桶的下标用的不是key.hashCode()本身而是对hashCode再做一次扰动static final int hash(Object key) { int h; return (key null) ? 0 : (h key.hashCode()) ^ (h 16); }这行代码的意思是把hashCode的高16位和低16位做异或让高位的差异也能扩散到低位。为什么需要这样因为计算桶下标时HashMap用的是(n - 1) hash如果table容量比较小n - 1的高位基本都是0那么结果只由hash的低位决定高位不管怎么变都可能落到同一个桶。如果key重写了hashCode但只影响高位低16位全部相同冲突率就会被放得很大。做了异或之后高低位混合桶分布会更均匀。注意JDK 7的hash扰动次数比这多执行了多次带掩码的异或而JDK 8只做一次因为随着CPU和哈希算法整体质量提高一次高位异或已经能带来很好的分散效果多了反而成为性能负担。这也是一个能跟面试官聊的演进点JDK 8为什么要简化扰动函数为了在随机性和执行速度之间找到平衡。桶下标公式是 i (n - 1) hashn表示数组长度。这个式子有两个作用第一它相当于hash对n取模因为当n是2的幂时(n - 1)的二进制就是全1掩码按位与等价于取余第二位运算比取模快得多每秒几十万次的put场景这一点点性能差距会被放大。这也是HashMap要把容量强行规整成2的幂的核心理由。3.2 put流程一步一步跟着走put方法看似复杂度不高翻开源码却有好几十行。我把关键判断收敛成以下流程第一步如果key是null哈希记为0这个null key会进入桶0后续扩容时它也会按正常规则参与重新定位不影响取值正确性。第二步对key做hash()得到扰动后的哈希值。第三步如果table还没初始化或者长度是0先调用resize()初始化桶数组初始容量默认16。第四步计算下标i (n - 1) hash取出table[i]。如果该位置是null直接用当前key-value构建新Node放入put结束。第五步如果table[i]不为null说明发生了冲突。先比较哈希值和key是否和已有节点相同如果相等说明是同一个key直接覆盖value然后返回旧value。第六步如果key不同看当前节点是不是TreeNode。是红黑树节点就走红黑树插入逻辑在树里找到合适位置放进去如果发现相同key则覆盖。第七步如果是普通链表节点就沿着next指针往后遍历。遍历过程中如果发现某个节点的key相同就替换value并返回旧值如果遍历到链表结尾都没找到就在链表尾部追加新节点尾插法。追加完成后如果链表长度达到树化阈值8调用treeifyBin方法尝试转成红黑树但treeifyBin内还会再判断一次table是否达到64不满足就扩容。第八步把modCount加1这是一个用来处理迭代器fail-fast的计数器。最后如果当前键值对数量size超过了threshold阈值触发resize()扩容。这段流程有几点值得细说。为什么JDK 8一定要用尾插法因为在扩容并发场景下头插法可能把链表顺序反转多线程并行扩容时很容易形成环形链表导致get死循环尾插法至少能保持元素之间的相对顺序虽然依然不是线程安全但那种“一个线程get卡死”的极端概率小很多。3.3 get流程差不多是put的逆过程get的流程比put简单。先对key取hash算出桶下标如果对应桶是空就直接返回null。如果桶首节点的hash和key都能匹配直接返回value。否则看首节点是不是红黑树节点是就走树查找不是就遍历链表逐个用equals判断key是否相等找到就返回值找不到就返回null。有个高频追问隐藏在equals这里hashCode相等的两个对象不一定equalsequals相等的两个对象hashCode一定相等。作为HashMap的keyequals和hashCode必须同时遵守契约。不然一个对象存进去之后第二次用“逻辑相等”的另一个对象去gethashCode不同连桶都不一样自然拿到null。自定义对象当key之前先想想这两个方法重写没有这是真实项目里特别常见的线上事故来源。4. 负载因子与扩容HashMap的性能命门4.1 为什么是0.75这个“魔法数字”负载因子等于元素个数除以桶数组长度它决定了一个HashMap装载到多“满”时触发扩容。JDK默认0.75意味着当桶的数量用了75%时就提前扩容。这时候桶里元素其实还不算多为什么要提前因为哈希表的查找时间不是均匀分布的桶个数越少哈希冲突概率越高链表和红黑树的压力越大。如果把负载因子设成1也就是数组全部塞满才扩容看着是节省了内存实际上冲突严重后查找成本飙升。如果设置到0.5吞吐率确实更稳但每个桶平均只装半个元素一半内存空间被浪费。0.75是一个经典折中它是在时间成本和空间成本之间反复权衡后得到的经验值。官方注释用泊松分布解释了为什么在0.75下单桶元素数量达到8的概率极其低这也是红黑树化只在极端情况下才出现的前提。4.2 扩容到底在做什么扩容的触发条件是size thresholdthreshold table容量 * 负载因子。默认容量16负载因子0.75所以threshold初始是12也就是put第13个键值对时会触发第一次扩容。扩容的大致过程是新数组长度变成旧数组的两倍然后遍历旧table的每一个桶把里面的节点重新放置到新数组里。这里不需要对所有Node重新计算hash值因为key的hash已经算好了变化的只是下标。由于新容量是旧容量的2倍原本在某个桶里的节点在新数组里只可能出现在两个位置一个是原来的下标不变另一个是原来的下标加上旧容量。判断依据是一条位运算if ((e.hash oldCap) 0)。这是因为oldCap是2的幂它的二进制只有一个1对应在扩容后正好变成新数组下标里新增的那一个高位。如果hash在这一位是0说明索引不变如果是1说明新的索引等于旧索引加oldCap。用位运算替代重算哈希整个扩容只需要遍历原有节点不需要重新计算下标效率高很多。还有个常识要留意扩容的代价并不止“复制一遍”这么简单。每次扩容都要重新分配一个更大的数组并且把全部节点迁移一遍所以大Map频繁扩容会造成明显的卡顿。如果事先能知道数据规模最好通过new HashMap(expectedSize / 0.75f 1)来初始化从源头减少扩容次数。这也是很多团队静态代码检查会强制要求写初始容量的原因。4.3 为什么容量强制要求是2的幂很多人背住了“HashMap初始容量是16扩容是2倍”却不知道为什么要这么做。核心原因是两个一是桶下标用位运算二是要让模运算等价于按位与从而提升寻址速度。假设容量不是2的幂比如17那么(n - 1) hash得到的结果无法覆盖0到16全部下标有些桶永远空着有些桶被多次碰撞内存分布不均匀。当调用带initialCapacity的构造方法时HashMap并不会直接用你给的数字而是调用tableSizeFor把它转成2的幂中最小的那一个。比如你传30最终初始化容量是32你传17最终是32你传100最终是128。这套“向上取整到2的幂”的逻辑就是为了保证后面每次扩容数组长度都保持2的幂寻址代码始终可以放心使用位运算。5. 并发场景下的HashMap三个经典失败现场5.1 数据覆盖两个线程同时写同一个桶很多刚接触并发的人以为HashMap的问题只有扩容死循环其实更常见也更隐蔽的是数据覆盖。两个线程同时执行put都定位到同一个空桶A线程写入一个NodeB线程后脚也写入一个Node。如果两个线程的Node没有同步前一个Node就可能被后一个覆盖或者产生一种“明明put了两次size却少一个”的现场。原因很简单put操作不是原子的读数组、判断空位、创建Node、赋值给数组这一连串步骤在CPU时间片切换下可以被拆开执行。有人会问size总该安全一点吧并不是。size包括了读size、加一、写回size三个步骤多线程下照样会丢更新。这就是为什么并发场景永远不要直接使用HashMap而是选ConcurrentHashMap或者其他线程安全容器。5.2 JDK 7扩容死循环那个让服务器卡死的传说网上流传了很多关于“HashMap扩容导致CPU 100%”的真实故障案例背后的机制主要在JDK 7。JDK 7的扩容转移链表用的是头插法遍历旧链表的每个节点每拿到一个就插入到新桶的头部。多线程并发扩容时两个线程同时处理同一条链表线程A还没来得及完成转移线程B已经把表头顺序反转了这样几个节点的next引用可能互相指回形成环形链表。之后无论是get还是再次扩容都可能在遍历链表时进入无限循环最终CPU飙升到100%服务彻底失去响应。JDK 8把插入改成尾插法虽然没有从根上解决线程安全问题数据覆盖、size异常依然存在但至少避免了这种环形链表死循环。如果面试中有人拿老版本故障来考你你完全可以顺着回答这个问题在JDK 8中已经通过尾插法和更完善的resize逻辑做了缓解但线程安全问题依然要靠并发容器解决。5.3 面试里怎么回答线程不安全一个简洁又不短的回答句式是HashMap在设计上就没有考虑并发场景。它没有锁所以put的检查与写入之间不是原子的并发写会覆盖数据size的统计也不安全会出现size与实际数量不一致更关键的扩容时多个线程同时rehash会把链表结构移动得乱七八糟旧版本甚至形成环形链表。JDK 8优化了一部分问题但依旧不能保证任何线程安全所以在并发场景必须使用ConcurrentHashMap或对HashMap做Collections.synchronizedMap包装。说完这段话面试官大概率会顺着问“ConcurrentHashMap怎么保证线程安全”正好接到下一部分。6. 同族对比一次把Map家族讲清楚6.1 HashMap与HashTable的差异清单HashTable是JDK 1.0时代的遗留类也是初代线程安全Map。它通过在方法上加synchronized锁整个表只有一把锁任何线程在操作之前都得排队并发度极低。相比之下HashMap在单线程里没有锁吞吐量更高HashTable的key和value都不允许null如果把null传进去会直接抛NullPointerException而HashMap的key和value都允许nullnull key被特殊处理。两者在扩容策略上也不一样。HashMap初始容量是16之后翻倍成长并且始终是2的幂HashTable初始容量是11扩容时变成 oldCapacity * 2 1也就是大致翻倍再加1。HashTable这种长度设计是为了降低哈希冲突但它也因此没法用位运算求下标每次要取模性能上就吃亏。HashTable在并发性能上被ConcurrentHashMap全面压制但它仍然有存在感。Java的集合工具类里有一个Collections.synchronizedMap方法它可以把任意Map包装成一个线程安全Map原理和HashTable一样都是粗粒度锁一个方法调用内部全部synchronized。这类Map适合并发量低、对性能不敏感的老系统维护不适合新项目。6.2 ConcurrentHashMap现代并发的选择面试官问到Map家族你需要知道的不只是HashTable落后还要知道ConcurrentHashMap为什么先进。JDK 7的ConcurrentHashMap把所有桶分成若干个Segment每个Segment是一把独立的锁不同的Segment可以由不同线程并发写所以叫分段锁。JDK 8把分段锁去掉了锁的粒度进一步缩小到桶单个数组元素。JDK 8的实现思路是当某个桶为空时用CAS直接放新Node当桶非空时给这个桶的头节点加synchronized锁然后执行插入或者树化操作。另外size统计使用CounterCell数组做分散计数尽量降低写锁竞争。这一套组合拳下来在容量大、并发高的场景里ConcurrentHashMap的吞吐量能比HashTable高出一大截。用一张表对比它们最直观维度HashMapHashTableConcurrentHashMap线程安全否是全表锁是桶级锁/CASKey/Value允许null是否否并发性能最高单线程最低高扩容策略2倍保持2的幂约2倍1更细粒度迁移适用场景单线程无并发老系统兼容多线程读写这里有个面试官非常喜欢的小点ConcurrentHashMap为什么不允许null key和null value官方意图是并发容器如果用null表示“查不到”就会出现歧义你get到null到底是不存在还是value本来就是null如果允许null在多线程环境下还需要再做一次containsKey确认而containsKey在并发下语义也会漂移。所以干脆从源头禁止null让空值在语义上等价于不存在。这个理由虽然业界还有争议但作为面试回答基本通用。7. 高频追问速查与实战避坑经验7.1 高频追问速答把前面零零散散的知识点收敛成几个小问题方便你当作卡片来背问链表什么时候转红黑树答同一个桶链表长度达到8并且table容量至少为64两个条件同时满足才树化否则优先扩容。问为什么退化阈值是6答7是缓冲带避免链表和树在临界点反复横跳。树节点保留了前后指针占用内存更大退化成链表后内存更省。问HashMap的key可以是null吗答可以hash()方法对null返回0所以null key在桶0但它也会在扩容时按正常规则挪位置。问两个hashCode相同的对象一定冲突吗答桶下标还要经过(n-1)hash所以只能说大概率落到同一个桶实际下标还受容量和低位掩码影响。问为什么自定义对象作为key时必须重写hashCode和equals答HashMap用hashCode定位桶用equals比较是否同一个key。只重写equals会导致逻辑相等的对象被分到不同桶get返回null。问遍历HashMap时能直接remove吗答不能。普通遍历中使用map.remove会导致modCount变化迭代器检测到就会抛ConcurrentModificationException要用iterator.remove或者先收集要删除的键再统一删除。问默认容量为什么是16答16是2的幂且作为初始容量不会太大也不会太小配合0.75负载因子默认能容纳12个键值对才扩容对大多数场景够用。7.2 项目开发里值得存档的经验第一预判容量再初始化。假如你要在启动阶段加载10万条配置new HashMap(100000)并不可靠因为当元素超过threshold时会提前扩容应该使用new HashMap(100000 / 0.75f 1)这种带余量的写法让初始容量一步到位减少扩容迁移的抖动。第二不要用HashMap做永久缓存容器。HashMap不是线程安全也未限制容量长期运行在服务器里很容易变成“内存炸弹”。做本地缓存应该考虑并发版本或者带容量限制的淘汰容器。如果你只是想实现一个LRU缓存LinkedHashMap构造参数accessOrder设为true并重写removeEldestEntry就能完成不用自己手写链表结构。第三String和Integer是最安全的key类型它们的hashCode和equals实现经过了大量场景考验分布质量好。使用自定义POJO当key时除了重写两个方法最好还确保对象不可变例如把参与hashCode计算的字段设为final否则对象某个字段变了hashCode跟着变化你再用同一个对象去get桶都找不到了。第四如果真的是读多写少的高并发缓存先调研ConcurrentHashMap的弱一致迭代器是否满足业务如果需要强一致的跨线程读取还是要加锁或者使用其他存储方案。第五看源码时不要总盯JDK 8往后的代码偶尔打开一个JDK 7的HashMap比一比你会对链表头插法和尾插法的差异理解得非常立体。历史版本里的bug和设计反复恰恰是理解“为什么这么设计”最好的老师。如果面试官最后让你说复杂度你可以收在这一句随机哈希下HashMap的put、get平均是O(1)最坏情况下所有key落同一个桶JDK 8之前退化成O(n)JDK 8之后因为红黑树的存在最坏也能到O(log n)。这句话把数据结构和最坏复杂度的理解一起带出来听起来就比单纯的“O(1)”更有层次。