1. 从一次线上故障说起为什么HashMap的容量必须是2的幂很多人对HashMap的认识停留在数组加链表这个层面面试的时候背一背初始容量16、负载因子0.75、扩容翻倍就过去了。但真正在项目里踩过坑的人会知道光背结论根本不够用。几年前我参与过一个订单导入模块的重构上游给了十万条数据我们用HashMap做去重和聚合本地测试跑得好好的压测到线上数据量翻了三倍之后接口响应时间从两百毫秒蹿到了三秒多。当时排查了半天最后定位到的问题居然跟HashMap的容量设置有关——构造的时候随手传了个初始容量结果触发了多次扩容每一次扩容都要把已有元素重新算一遍位置。这件事让我意识到把扩容机制吃透比记住几个数字有用得多。先聊聊HashMap到底是个什么东西。它是Java集合框架里的一个键值对容器官方定位是允许null键和null值、不保证顺序、非线程安全。它把键映射到值你给它一个key它能在接近常量的时间复杂度里把value还给你。这个接近常量背后的实现就是它值得反复研究的地方。适合读这篇文章的人包括正在准备Java面试题的同学也包括已经工作、但对底层细节还模模糊糊的开发者。因为面试官越来越喜欢追着HashMap的实现原理和扩容机制问而且问法越来越刁钻比如为什么容量非得是2的幂扩容的时候元素位置怎么算并发下会发生什么。要理解容量的设计先得明白HashMap内部的存储结构。它底层是一个数组我们叫它table数组的每个格子叫一个桶bucket。往里面放数据的时候先根据key算出hash值再通过某种映射把hash值落到某个桶的下标上。这里有个关键点数组的长度是有限的而hash值的取值范围是int的全部范围两者要做映射最简单高效的办法就是取模。取模运算hash % n能保证结果落在[0, n-1]区间内逻辑上是没问题的。可问题在于取模是个相对昂贵的操作。对于HashMap这种每次读写都要用到的运算一点点开销都会被放大。于是设计者用了一个技巧当容量n是2的幂时hash % n等价于hash (n - 1)。位运算比取模快得多这就是为什么容量必须是2的幂。你可以自己验算一下n等于16的时候n-1是15二进制是0000 1111一个hash值和它做与运算结果只保留低四位范围正好是0到15跟对16取模完全一致n等于8的时候n-1是7二进制0000 0111结果落在0到7。换成非2的幂比如n等于15n-1是14二进制0000 1110最低位永远是0那么所有hash值算出来的下标都是偶数第0、2、4……这些位置永远空着一半的桶被浪费碰撞概率还翻倍。我见过有人在初始化的时候写new HashMap(15)以为能省点空间结果容量会被向上取整到16因为内部调用了tableSizeFor方法把容量规整到最接近的2的幂。这个方法的实现也很有意思它通过一连串的无符号右移和或运算把最高位后面的所有位都填成1最后加1得到2的幂。这不是重点但了解它能让你在面试里多一个可以展开的点。容量nn-1的二进制可用下标范围是否所有桶可用160000 11110~15是150000 11100,2,4,...,14否奇数位全空320001 11110~31是310001 11100~30中的偶数否提示自己构造HashMap时如果明确知道要存多少元素最好给一个预估的初始容量避免反复扩容。但要注意传进去的值会被向上取整到2的幂而且真正的扩容阈值是容量乘以负载因子所以如果你预估要存1000条直接传1000实际可能还是会扩容一两次比较稳妥的算法是预期元素数 / 0.75 1后再向上取整。理解了容量必须是2的幂这件事后面很多结论就顺理成章了。索引计算快、扩容时元素的新位置有规律可循都是建立在这个前提上的。很多人背扩容结论却背不牢根本原因就是没把2的幂和位运算这层关系串起来。2. 拆开put方法一次键值对写入到底走了哪些路光知道结构还不够得看数据是怎么进去的。把put方法的执行路径走一遍你就明白HashMap在读写时的完整逻辑链路了。我先给出一个简化版的流程描述然后再逐个拆解关键环节。当你调用map.put(k, v)时内部大致经历这么几步先判断数组有没有初始化没有就先初始化然后计算key的hash值用hash值和数组长度算出下标看这个桶是不是空的空就直接放进去不空就遍历这个桶如果找到相同的key就覆盖值找不到就在链表尾部追加或者往红黑树里插插入之后检查元素总数有没有超过阈值超了就扩容。第一步是hash值的计算这里藏着HashMap的第一个设计亮点。你可能会想直接用key.hashCode()不行吗为什么要多此一举再加工一下。JDK里的实现是这样static final int hash(Object key) { int h; return (key null) ? 0 : (h key.hashCode()) ^ (h 16); }注意这里key为null的时候直接返回0所以HashMap允许一个null键它会被固定放在下标0的位置。那非null的情况它取到了key的hashCode然后把这个值无符号右移16位再和原值做异或。为什么要多这一步回到上一节的结论索引计算用的是(n - 1) hash当容量比较小的时候比如n等于16n-1是15只有低四位参与运算。也就是说hash值的高28位全被丢掉了只有低4位真正决定元素落在哪个桶。如果一堆key的hashCode恰好低位相同高位不同它们就会全部挤到一个桶里。JDK的设计者用高16位异或到低16位这个操作让高位的信息也能参与到下标计算中相当于把高低位信息混合了一下降低了碰撞概率。这个操作常被叫做扰动函数面试里经常单独拎出来问。第二步是定位桶。有了hash值用(n - 1) hash算出下标这一步就是上一节讲的位运算不再展开。第三步是插入这里要区分几种情况。桶是空的直接new Node放进去这是最快的情况。桶不空就要沿着链表或者红黑树找。如果树节点走红黑树的查找和插入逻辑时间复杂度是O(log n)。如果是链表就从头遍历每到一个节点先比hashhash相同再用或equals比key。这里有个特别容易忽略的细节比较key的时候是先比hash还是先比equals答案是有先后顺序的先比hash值hash不同直接跳过hash相同才调用equals。因为hash不相等的时候两者必不相等能省下调用equals的开销。if (e.hash hash ((k e.key) key || (key ! null key.equals(k))))这行代码是判断找到了同一个key的核心你可以看到hash的判断在前面利用了短路特性。这也是为什么重写equals的时候必须重写hashCode如果两个对象equals相等但hashCode不同它们在HashMap里会被当成两个不同的key存进去去重逻辑就失效了。这个坑我在实际项目里见过一次一个实体类只重写了equals没重写hashCode导致明明相等的对象在Set里存了两份排查了很久。第四步是插入后的检查。插入新节点之后如果是在链表里追加的会判断链表长度是否达到了树化阈值默认8同时整个map的size加一如果size超过了阈值容量乘负载因子就触发扩容。注意这里判断的是size也就是所有键值对的总数而不是某个桶的长度。这两个阈值容易混淆往下看会更清楚。关于链表的插入方式这里有个版本差异值得一说。JDK 1.7用的是头插法新节点插到链表头部JDK 1.8改成了尾插法新节点追加到链表尾部。为什么改头插法在并发扩容的情况下可能导致链表成环进而让后续操作陷入死循环这就是著名的HashMap并发死循环问题。尾插法虽然在并发场景下依然不安全但至少不会形成环能避免最糟糕的那种情况。正常单线程场景下尾插法也更符合直觉先插入的元素在链表里靠前遍历顺序更稳定。注意这里说的先比hash再比equals以及1.7头插1.8尾插都是面试里出现频率很高但很多人答不全的点。答的时候最好能延伸到为什么这么设计而不是只丢一个结论。走完这一遍你会发现put方法的每一步都是为了一个目标在任何情况下都能高效地找到或者插入一个键值对。hash扰动是为了减少碰撞先比hash是为了减少equals调用红黑树是为了防止极端情况下的性能退化。理解了这些设计动机再回头看代码就不会觉得枯燥了。3. 扩容不是简单复制rehash背后的性能账本扩容这块是很多人心里的一根刺。不只是因为它涉及性能更因为面试官喜欢在这里深挖从阈值计算一直问到元素搬家的细节。我先讲清楚扩容什么时候发生再讲元素怎么搬最后算一算扩容的成本账。扩容的触发条件是size threshold。threshold等于容量乘以负载因子默认情况下容量16负载因子0.75阈值就是12。也就是说当你往一个默认的HashMap里放入第13个元素时扩容就会发生容量翻倍到32阈值变成24。这里有个小细节扩容判断发生在插入之后所以严格来说是放进第13个元素、size变成13之后才触发扩容而不是放不进去才扩。那为什么负载因子是0.75不是0.5也不是1这个0.75有点折中的意思。负载因子太小比如0.5意味着桶有一半是空的就要扩容空间利用率低而且扩容频繁每次扩容都要搬运数据整体性能反而下降。负载因子太大比如1.0意味着桶几乎全满才扩容空间利用率上去了但碰撞概率大增链表变长查找效率下降。0.75是一个在时间和空间之间取得平衡的经验值官方的注释里也提到在理想情况下桶中元素数量服从参数为0.5的泊松分布当元素数量达到8时的概率大约只有千万分之六也就是说链表长度达到8的概率极低这既支撑了0.75的合理性也支撑了后面树化阈值取8的选择。扩容时元素怎么搬是1.7和1.8差别最大的地方。1.7的做法比较直接遍历老数组的每个桶对桶里的每个节点重新计算indexFor也就是用新容量重新算一遍下标然后放进新数组对应的位置。由于1.7用头插法重算之后链表的顺序会反过来。1.8做了一个非常重要的优化它发现容量翻倍之后原来的元素要么留在原位要么移动到原位加上旧容量的位置不需要重新算hash。判断依据是一个简单的位运算if ((e.hash oldCap) 0) { // 留在低位链位置不变 } else { // 进入高位链新位置 旧位置 oldCap }我用一个例子说明为什么。假设旧容量是16某个key的hash值是17二进制是0001 0001。旧下标是17 15也就是0001 0001 0000 1111结果等于1。容量翻倍到32新下标是17 31也就是0001 0001 0001 1111结果等于17正好是 1 16。再看一个hash值是1的key二进制0000 0001旧下标是1新下标0000 0001 0001 1111还是1位置不变。这两个key的区别在哪区别就在第5位从0开始数——容量16对应的最高位是第4位扩容后新容量32多出来一位是第5位。hash的第5位是0还是1决定了元素留在原位还是加上oldCap。而hash oldCap恰好就是取这一位所以这个判断是精确的。场景旧容量旧下标新容量新下标变化hash低5位00001161321不变hash低5位100011613217加16hash低5位00010162322不变hash低5位100101623218加16这个优化带来的好处是不需要重新计算hashhash值早就存好了只需要判断一个比特位然后决定放到低位链还是高位链。1.8的代码里会把原来的链表拆成两条低位链保持相对顺序放在新数组的原位置高位链放在新位置避免了1.7那种每个节点都重算、还把顺序打乱的问题。再算一笔性能账。每次扩容都要遍历所有元素做一次搬家这个操作的时间复杂度是O(n)。如果容量从16一直扩到很大比如存一千万条数据从16开始翻倍要经历很多次扩容每一次都要遍历当时的全部元素。累加起来的工作量大致是扩容次数乘以平均元素数量级是相当大的。这就是我在开头提到的那个线上故障的根源没有预估容量让HashMap自己反复扩容白白浪费了大量时间。一个实操建议是如果能在初始化时估算出大概的元素数量就按元素数 / 0.75 1算出一个初始容量传进去这样能一次性分配到位避免中间的所有扩容。不过也要提醒一句初始容量给得太大也不是好事。假如你预估要存一百万个元素直接传了100万HashMap内部会向上取整到一个2的幂可能是1048576这个数组一上来就占用了相应的内存如果实际上大部分时间只用了很少一部分就是浪费。所以更稳妥的思路是宁可在临界点附近多留一点余量也不要动辄翻个十倍。经验值是对于中大型的map初始化容量给到预估值的1.3到1.5倍就够用了。扩容还有个容易被忽略的点扩容不仅仅是数组变大、元素搬家链表和红黑树也会被拆分。如果某个桶原本是红黑树扩容时同样按低位高位拆分拆完之后如果某条链上的节点数小于等于6还会退化成链表。这个化树和退化的阈值下一节详细说。4. 链表转红黑树那个8和6的阈值到底怎么来的前几节一直在说链表和红黑树的转换这节专门讲清楚这件事。先明确HashMap里红黑树存在的意义链表在极端情况下会变得很长查找一个元素要从头遍历到尾时间复杂度是O(n)性能急剧退化。红黑树是一种自平衡二叉搜索树查找、插入、删除都是O(log n)在链表很长的时候优势非常明显。HashMap的设计者并没有一上来就用红黑树因为树结构的维护成本比链表高节点也要占用更多内存只有在确实需要的时候才转。树化的触发条件是某个桶的链表长度达到8同时数组容量不小于64。这里有两个门槛缺一不可。看代码第一个判断在putVal里链表长度达到TREEIFY_THRESHOLD8时调用treeifyBin。第二个判断在treeifyBin里如果当前数组容量小于MIN_TREEIFY_CAPACITY64不转树而是先扩容。为什么容量不够的时候优先扩容而不是转树因为容量小的时候桶本来就少元素容易扎堆这时候扩容能通过增加桶的数量来分散元素成本比把链表转成树再维护要低。只有当容量已经够大至少64链表还长到8那说明是真的碰撞严重这时候才值得上红黑树。if (binCount TREEIFY_THRESHOLD - 1) // TREEIFY_THRESHOLD 8 treeifyBin(tab, hash); // treeifyBin 内部 if (tab null || (n tab.length) MIN_TREEIFY_CAPACITY) resize();为什么阈值是8再回到那个泊松分布。在hash设计得足够好的前提下桶里元素的个数服从参数为0.5的泊松分布。有好事者算过一个桶里有8个元素的概率大约是0.00000006也就是不到一亿分之六。也就是说正常情况下链表长到8几乎不可能如果真长到了那说明要么hash分布出了问题要么数据本身就特殊转成树是一种防御性设计防止最坏情况下性能崩盘。为什么退化阈值是6比8小2中间留了一个缓冲区避免在7、8之间反复横跳。如果树退化的阈值也定8那么一个桶在8个元素附近增加删减就会不停地化树退化白白消耗性能。取6能保证只有元素显著减少时才退化。阈值值含义TREEIFY_THRESHOLD8链表长度达到该值尝试树化UNTREEIFY_THRESHOLD6树节点数降到该值退化回链表MIN_TREEIFY_CAPACITY64树化的最低容量要求不够先扩容DEFAULT_INITIAL_CAPACITY16默认初始容量DEFAULT_LOAD_FACTOR0.75默认负载因子MAXIMUM_CAPACITY2的30次方最大容量树化和退化的代码实现细节也值得了解。树化的时候先把链表节点Node转换成树节点TreeNode然后调用红黑树的插入方法把每个节点插进去最后把桶的引用指向树根。TreeNode本身继承自LinkedHashMap.Entry再往上继承Node所以红黑树的节点依然保留了链表节点的next指针这也是为什么在扩容拆分时树节点可以像链表一样被遍历、被拆分。退化发生在两个地方一是删除元素时如果树的节点数太少就退化二是扩容拆分时如果拆出来的某条链节点数小于等于6也退化。退化的时候会把TreeNode转回Node并恢复成单链表。这样设计的好处是数据结构能随元素数量动态调整元素少的时候用链表省内存、操作简单元素多的时候用树保证查询效率。我在实际项目里几乎没见过真的触发树化的情况绝大多数时候链表长度都在0到2之间。有一次遇到过一个业务里大量用了同一个字符串作为key的一部分前缀hashCode分布比较接近链表长度偶尔能到4、5但也远没到8。所以可以这么理解树化机制更多是一种兜底平时用不到但它保证了即使在最坏情况下HashMap的查找性能也不会退化到线性。面试的时候如果能把用不到但必须有这层意思讲出来会比单纯背阈值加分。有个相关的面试题很常见如果两个key的hashCode相同HashMap怎么处理答案就是它们会落到同一个桶形成链表需要靠equals区分。如果大量key的hashCode都相同链表会很长触发树化后由于所有节点的hash都相同红黑树的查找依然会退化成线性比较因为树是通过hash值来排序的hash相同时比较key。这种情况下红黑树的优势就不明显了。所以终极结论是hashCode分布越均匀HashMap的性能越好这也是为什么重写hashCode要用高质量的算法比如用31作为乘数、把各个字段都参与进去。5. 面试高频问题逐一拆解从hash扰动到并发陷阱前面几节把原理铺开了这节集中回答一些高频的面试题。我尽量按问题—答案要点—背后的why这个结构来写方便你对照自己的掌握程度。这些都是我在面试别人和准备自己面试时总结出来的有些问题看起来基础但能答深答全的人其实不多。第一个问题HashMap的默认初始容量是多少为什么是16默认初始容量是16。为什么是16而不是8或者32官方没有明确说但可以理解为16是一个经验值既能减少扩容次数又不会一上来就占用太多空间。更重要的是16是2的幂符合前面讲的索引计算要求。如果初始容量设为8稍微存几个元素就要扩容设为32很多小map又浪费。所以16是一个比较均衡的选择。第二个问题为什么HashMap的容量必须是2的幂两个原因。一是位运算替代取模hash (n-1)比hash % n快。二是扩容时元素的新位置只有原位和原位加oldCap两种可能判断只需要看hash oldCap那一位不需要重新计算hash大幅提升扩容效率。如果容量不是2的幂这两点都不成立扩容就得老老实实重新算下标。第三个问题HashMap线程安全吗多线程下会有什么问题不安全。多线程put可能导致数据覆盖因为put不是原子操作多个线程可能同时判断某个桶为空然后都往里面写后写的覆盖先写的。1.7里还有一个著名的问题多线程同时扩容时头插法可能导致链表成环之后执行get会陷入死循环CPU飙升。1.8改成了尾插成环问题基本没了但数据覆盖、size计算不准这些问题依然存在。要用线程安全的map可以用ConcurrentHashMap它用了分段锁1.7或者CAS加synchronized1.8来保证并发安全性能比直接用Collections.synchronizedMap包装要好很多。第四个问题负载因子为什么是0.75能不能改0.75是时间和空间的折中前面详细说过。它是可以改的构造函数允许传入。但一般不建议乱改除非有非常明确的场景。比如你把负载因子设成1.0空间利用率高了但碰撞概率增加设成0.5查询快但扩容频繁、内存占用高。0.75是被大量实践验证过的平衡点。第五个问题HashMap的get方法大概是怎么走的先判断数组是否为空、key算出的下标处是否有节点没有直接返回null有的话先比hash再比key命中就返回如果是链表就顺着找是红黑树就按树的方式找。整体逻辑和put的查找部分一致先比hash再比equals。第六个问题HashMap允许null键吗null键存在哪允许唯一的null键它的hash值被特殊处理为0所以会放在下标0的桶里。null值也可以有多个。这一点和Hashtable不同Hashtable不允许null键和null值。第七个问题HashMap的遍历顺序是固定的吗不固定而且不保证顺序。更要注意的是扩容之后顺序可能完全变化因为元素要么留在原位要么移动到新位置。所以任何依赖HashMap遍历顺序的业务逻辑都是不可靠的我见过有同事用HashMap存配置然后导出结果发现每次导出顺序不一样就是踩了这个坑。提示涉及顺序敏感的场景要么用LinkedHashMap维护插入顺序或访问顺序要么用TreeMap按key排序。别指望HashMap。把这些问题串起来看你会发现它们都围绕几个核心概念2的幂、负载因子、hash扰动、链表与树的转换、扩容的rehash优化、非线程安全。只要把这些点吃透绝大多数变体问题都能现场推出来。面试官真正想考察的不是你背了多少而是你能否从这些设计里看出取舍的思路。6. 实战中的选择与取舍什么场景该用什么场景该换原理讲完了最后聊聊怎么在实际项目里用好这个类。先说一个我反复强调的原则预估容量、避免扩容。前面讲过扩容的成本不小最好的办法就是一开始就给出一个合适的初始容量。我的习惯是如果一次操作的map元素数能估计出来就按元素数 / 0.75 1再往上取整到2的幂。比如要聚合一万条记录初始容量给10000 / 0.75 1 ≈ 13334向上取整到16384。这个数字不是拍脑袋来的是把负载因子的损耗也算进去了。这样整个聚合过程中一次扩容都不会发生性能最稳定。再说数据结构的选择。HashMap适合根据一个键快速找到值的场景比如缓存、去重、映射表。但如果场景变了它会力不从心。要保证插入顺序用LinkedHashMap它内部额外维护了一条双向链表串起所有entry遍历的时候按插入顺序或访问顺序构造时传true开启。要对key排序用TreeMap底层是红黑树能提供有序遍历和范围查询比如找大于等于X且小于Y的所有键HashMap就做不到。要并发用ConcurrentHashMap。要一个只存不重的集合用HashSet它内部其实就是组合了一个HashMapvalue 统一放一个占位对象。需求场景推荐容器原因按下标/键快速查找HashMapO(1) 平均查找保留插入顺序LinkedHashMap额外维护双向链表按键排序、范围查询TreeMap红黑树有序多线程读写ConcurrentHashMap并发安全性能好缓存淘汰LRULinkedHashMap开访问顺序后可重写removeEldestEntry去重集合HashSet基于HashMap实现关于LinkedHashMap实现LRU缓存这里多说一句因为它很实用。你只需继承LinkedHashMap构造时super(capacity, 0.75f, true)第三个参数true表示按访问顺序排列然后重写removeEldestEntry方法当size() capacity时返回true它就会自动淘汰最久未访问的元素。这个方法在写本地缓存、会话管理这类功能时特别方便比自己维护一套淘汰逻辑简单得多。回到HashMap本身还有几个实战细节值得记住。第一作为key的对象equals和hashCode一定要正确重写而且参与计算的字段应该是不可变的否则对象放进去之后hash值变了就再也找不回来了。第二如果用可变对象做key要格外小心改字段等于改hash会出现存进去找不出来的情况。第三如果key的类型没有重写hashCode用的是Object默认的实现那每个实例的hash都不一样即使内容相同也会被认为是不同的key去重就失效了。第四遍历的时候删除元素必须用Iterator的remove或者removeIf直接调map.remove会抛ConcurrentModificationException。// 错误的删除方式 for (Map.EntryString, Integer entry : map.entrySet()) { if (entry.getValue() 0) { map.remove(entry.getKey()); // 会抛 ConcurrentModificationException } } // 正确的方式一使用迭代器 IteratorMap.EntryString, Integer it map.entrySet().iterator(); while (it.hasNext()) { Map.EntryString, Integer entry it.next(); if (entry.getValue() 0) { it.remove(); } } // 正确的方式二removeIf map.entrySet().removeIf(entry - entry.getValue() 0);注意ConcurrentModificationException的本质是modCount和expectedModCount不一致。迭代器在创建时记录了modCount每次next都会检查发现被外部修改了就抛异常。用迭代器的remove方法会同步更新expectedModCount所以不会抛。我自己在这块踩过的坑是有一次在遍历map的时候调用了另一个方法那个方法内部又改了这个map结果抛异常。排查的时候发现是这个隐蔽的副作用导致的花了点时间。后来我的习惯是遍历过程中尽量只做只读操作需要修改的话先收集要改的键遍历完再统一处理。如果从性能和内存的角度再抠一点细节还有几点可以聊。HashMap的节点对象Node除了存key和value还要存hash和next指针所以它比单纯的键值对要占更多内存。在内存敏感的场景里如果key是整数可以考虑用一些压缩结构但大多数业务场景不用这么抠。另外HashMap不是线程安全的但很多人会误用比如在并发环境下用map做计数器用map.put(k, map.getOrDefault(k, 0) 1)这种写法在多线程下会丢计数因为get和put之间不是原子的。正确做法是用ConcurrentHashMap的merge或compute方法。最后说说我个人的体会。HashMap这个类看似简单但它的每个设计都不是拍脑袋定的容量是2的幂是为了快负载因子0.75是为了平衡树化阈值8是统计推断rehash的位运算优化是性能考量。把这些串起来你会发现它其实是一份在时间、空间、复杂度之间反复权衡的经典答卷。面试的时候能把这些why讲清楚比背一堆结论要打动面试官得多。至于那些层出不穷的面试题本质上都是围着这几个核心转把地基打牢无论题目怎么变你都能从原理往上推出来。真要说有什么捷径那就是自己动手写一个简化版的HashMap把put、get、resize都实现一遍写过之后你会对扩容时拆成高低位链这种细节有完全不一样的理解。