1. 先从一次线上告警说起这场“血案”还要从一张工单讲起。几个月前我们一个订单服务在晚高峰时段突然爆出一堆线程阻塞告警堆栈信息全指向同一个方法——往HashMap里put数据。排查到最后问题根源并不是内存泄漏也不是并发写导致的死循环毕竟JDK 8早就修复了这个问题而是我那位同事在一个被多线程并发访问的缓存场景里直接用了一个朴素的HashMap。其实那一瞬间我特别能理解他很多人从学Java第一天起就在用HashMap增删改查丝滑得不行以为这就是一个“线程不安全但随便用”的容器。但实际上理解HashMap的底层实现原理不光是为了面试时能倒背如流那几道八股题更是为了避免在真实的业务场景里踩坑。这篇文章我会围绕hashmap的核心设计思路把一个完整的数据结构从存储设计、哈希寻址、扩容机制到红黑树退化全部拆开讲清楚。不管你是在准备面试还是单纯想把这玩意儿用明白看完应该都能建立起一套完整的认知框架至少下次再遇到并发问题你会下意识地问一句这里合适吗2. 整体设计思路为什么 HashMap 长这样2.1 数组是骨架链表和红黑树是血肉先看最基本的问题我们要存键值对需要支持快速的查找、插入和删除。如果你只选一种数据结构数组能做到 O(1) 查找但插入删除要搬移元素链表插入删除方便但查找是 O(n)。HashMap的精髓在于组合——它用数组作为底层主存储这是它能实现 O(1) 查找的根本保证但是哈希冲突导致的碰撞数据用链表挂接后来链表太长了又升级成红黑树这是它应对最坏情况的兜底策略。用一个生活化的类比来理解数组就像一栋公寓楼每个房间有门牌号数组下标。你按门牌号直接进房间这就是 O(1)。但总有几个住户会算出同一个房间号哈希碰撞那这个房间就变成一个走廊大家排队站好链表。走廊人太多了进出效率太低于是物业把走廊改造成一棵索引树红黑树找人的速度快一些。所以HashMap的底层结构实际上是一个NodeK,V[] table数组数组里每个元素要么是null要么是一个节点这个节点可能只代表单个键值对也可能是链表的头节点还可能是一棵红黑树的根节点。JDK 8 之后所有节点都实现了统一的结构链表节点和树节点在类型上做了继承关联。2.2 哈希函数整个数据结构的灵魂讲HashMap绕不开哈希函数因为数组下标怎么来完全取决于它。源码里有这样一段static final int hash(Object key) { int h; return (key null) ? 0 : (h key.hashCode()) ^ (h 16); }这个函数做完的事情就是把key.hashCode()算出来的32位哈希值和自己的高16位做一次异或业内称为“扰动函数”。为什么要扰动因为后面算数组下标时用的公式是这样的index (n - 1) hash // n 是数组长度n是数组长度一般是 2 的整数次幂。比如默认长度 16那么n-1的二进制就是0000 1111也就是说计算下标时实际上只使用了哈希值的低 4 位。低 4 位能决定什么它只能代表 0~15 这 16 个下标。如果多个 key 的哈希值恰好在低 4 位上相同哪怕它们高 28 位千差万别也会全部落到同一个数组位置产生大量碰撞。扰动函数的作用就是让高位信息“混入”低位让最终参与下标计算的几个二进制位尽可能分散。我用一个例子说明假设一个 key 的原始哈希值是1010 1100 0110 1001 1110 0011 0101 0110无符号右移16位得到0000 0000 0000 0000 1010 1100 0110 1001两者异或之后原来低16位里的某些位就被高16位的特征改变了。这样一来哪怕两个对象的hashCode()在高位有区别但低位相同经过扰动后低位也可能变得不同从而分散到不同的数组槽位。很多人会忽略这个细节直接拿hashCode()去与(n-1)做与运算。这在 key 分布不够均匀时后果很明显尤其是当n比较小、参与运算的位数极少时你会发现某个槽位挤了一条长链旁边一片空位。所以这个细节不只是面试考点它直接决定了哈希冲突的概率。2.3 为什么数组长度必须是 2 的整数次幂除了让(n-1) hash等价于取模运算之外2 的整数次幂还有一个隐藏的好处扩容时旧元素迁移非常高效。我先把这个结论放在这后面讲扩容机制时会展开说。实际操作时即使你传入的初始容量不是 2 的幂构造方法也会帮你调整成大于该值且最接近的 2 的幂。如果你初始化时传了new HashMap(15)实际上底层容量是 16传 17底层就是 32。源码里通过一系列无符号右移和或运算实现简洁且生猛。3. 核心机制拆解put 和 get 到底经历了什么3.1 put 一个 key 的完整流程很多人背过“先算哈希再找下标冲突就挂链表”但源码里判断分支比想象的细很多。我把putVal的主要流程整理成下面这个过程如果table还未初始化或者长度为 0先触发一次resize()扩容。通过(n-1) hash算出下标若该位置上为null直接放入新节点。如果该位置已经有节点分三种情况处理如果该节点的hash和key都与插入的键值对完全一致则直接覆盖旧值。如果该节点是红黑树节点TreeNode则走红黑树的插入逻辑。否则说明它是一个普通链表节点遍历链表找相同 key找到就覆盖找不到就追加到链表尾部。追加完毕后判断长度是否达到红黑树化阈值 8达到则转换结构。容器中的键值对数量超过threshold容量乘以负载因子则调用resize()扩容。这里有一个细节默认加载因子是0.75f阈值 容量 * 加载因子。为什么是 0.75 而不是 0.5 或 1.0我在网上看过很多解释最合理的一种说法是负载因子是时间复杂度和空间复杂度之间的折中。负载因子太小就像一栋楼只住了一半人就轰隆隆加盖楼层空间浪费严重负载因子太大桶位拥挤链表变长查找性能下降。0.75 是 JDK 作者在大量实测中权衡出来的经验值。基于常见实践我自己试验过把负载因子调到 1内存确实省了但查找性能明显劣化尤其是 key 分布不太均匀时某个槽位链表能有几十个节点。所以除非你内存极度敏感否则不建议修改默认值。3.2 get 一个 key 的完整过程get的过程基本是put的逆向简化版先算出 key 的扰动哈希然后通过(n-1) hash定位到数组下标。如果该位置为null直接返回null。如果该位置第一个节点的哈希值和 key 都匹配直接命中。如果第一个节点是TreeNode走红黑树的查询逻辑。否则遍历链表逐个比较hash和key。这里很多人会忽略一点HashMap允许key为null。当key null时哈希值强制为 0所以null永远被放在table[0]这个桶位。get时同样遵循这个逻辑所以哪怕你用null作为 key也能正确查到值。这个设计看起来简单但实现时要小心因为hashCode()不能对null调用所以源码里专门用三目运算符做了分支。3.3 红黑树化当链表超过 8 个节点时JDK 8 引入红黑树是本方案最主要的优化点之一。当链表的长度达到阈值 8也就是第九个节点要插入时链表会转换为红黑树。为什么选 8源码注释里给了一个统计学的解释在随机哈希码的情况下链表中的节点数量呈泊松分布负载因子 0.75 时单个桶位中出现 8 个节点的概率约为千万分之六。这个概率已经小到可以认为“正常业务几乎不可能触发”。但“几乎不可能”不等于“不可能”一旦发生了——比如 key 的哈希分布被恶意设计或者哈希函数实现得极其糟糕——红黑树能把查找从 O(n) 降到 O(log n)至少不至于让接口彻底卡死。这里有一个容易误解的地方不是链表一变成红黑树就万事大吉。树化之前JDK 还会额外判断当前数组容量是否小于 64如果数组太小而链表已经很长它会优先选择扩容而不是树化。原因很简单数组容量小的时候哈希低位重复的概率本来就高此时扩容能更直接地缓解冲突而建树本身有成本在小数组场景下“性价比”不高。只有当容量大于等于 64 且链表长度超过 8才会真正树化。红黑树节点占用的内存大约是普通链表节点的两倍所以这个判断实际上也在控制内存成本。3.4 扩容机制为什么扩容时元素要么原位不动要么移动旧容量这一步是整个HashMap实现里我认为最精妙的地方也是很多资料语焉不详的地方。先说结论当元素数量超过阈值时HashMap会将数组容量扩大为原来的两倍同时重新分配所有已有元素的位置。普通思路是每个元素都重新计算 hash 和下标但 JDK 8 的源码用了更聪明的办法。假设旧数组容量是 16对应的掩码n-1是0000 1111。扩容后容量是 32掩码变成0001 1111。从二进制的角度看容量翻倍其实只是掩码在高位多了一个 1。这时候再看元素的哈希值它的第 5 位从低位往高位数如果是 0那么它和旧掩码、新掩码做与运算的结果完全一样也就是说这个元素留在原下标即可如果第 5 位是 1那么和新的掩码做与运算结果就会比原来的下标多出一个 16。所以扩容时每个元素只有两个去处原地不动或者“原下标 旧容量”。源码里甚至不需要单独存这个元素的新下标只要判断(e.hash oldCap) 0就能决定方向。这个判断非常快而且天然地把节点分成了两个链表低位链留在原位高位链一次性接到新数组的对应位置上去。整个过程不需要重新计算每个 key 的扰动哈希也不需要借助额外的数据结构。实际扩容时HashMap会创建两倍长度的新数组再把旧数组元素迁移过去。迁移完以后table指向新数组threshold也会同步更新为新容量乘以负载因子。这里有个细节可能出乎你的意料扩容不是每个元素都做一次而是每次桶位处理时把整条链表拆成高低两截然后一次性挂到新数组上。复杂度控制在 O(n)而且不会因为链表的某个节点被拆走而影响其他桶位的遍历。4. 为什么说 JDK 7 和 JDK 8 的 HashMap 是两个物种4.1 头插法 vs 尾插法知道HashMap历史的人应该都听说过 JDK 7 在多线程扩容时可能形成环形链表导致下一次查询陷入无限循环。这个问题的根源在于头插法扩容迁移链表时JDK 7 会把旧链表上的节点按原顺序反向插入到新数组里也就是后遍历到的节点反而成了新链表的头节点。在单线程下这个过程没问题顶多是把链表的顺序翻转一下但多线程并发扩容时两个线程可能同时遍历同一链表、同时执行“把节点插到新表头”导致最后一个节点的next指针指向一个已经被搬走的节点形成环。JDK 8 把插入方式改成了尾插法新节点始终追加到链表末尾。这样做有一个好处——链表在迁移过程中保持原有的相对顺序就算并发也大概率不会形成环。但我不建议你把“尾插法”当成多线程安全的理由因为并发环境下put依然会出现数据覆盖、丢数据等问题。JDK 8 只是解决了一个极端问题并没有把HashMap变成线程安全的容器。4.2 为什么源码里用光了位运算JDK 8 的实现里大量使用位运算替代取模、比较、赋值操作。比如判断树化条件、计算扩容迁移方向、初始化容量时把任意数字抬到最近的 2 的幂全部是位移和逻辑运算。这不是为了炫技而是因为在高频路径上每减少一次算术运算都能换来可观的吞吐提升。HashMap每秒可能要处理几十万次put对于这类基础数据结构微小的性能差距都会被规模放大。5. 并发场景用还是不用这是个问题5.1 HashMap 并发写入的三个典型故障我先列举一下并发使用HashMap可能会出现的具体故障这些我都见过有人踩过数据覆盖两个线程同时往同一个桶位插入键值对后插入的可能会覆盖前一个线程写入但尚未可见的数据。这在缓存场景里表现得很隐蔽某些 key 时不时变成旧值。扩容期间的丢失并发扩容时一个线程正在重新分配节点另一个线程在旧数组里读或写可能读到null或写进一个已经废弃的旧数组最终数据丢失。死循环问题JDK 7这个前面说过环形链表形成后get操作会陷入死循环CPU 直接飙满。JDK 8 下概率大幅降低但依然不建议尝试。针对并发场景解决方案分档位如果只是读多写少且不要求强一致可以用Collections.synchronizedMap(new HashMap())如果是高并发读写直接上ConcurrentHashMap。ConcurrentHashMap内部采用分段锁机制JDK 7 的概念和 CAS 局部加锁JDK 8 的实现它对并发性能的优化思路和在单个桶位上的冲突处理方式都明显优于给整个HashMap加一把大锁。5.2 ConcurrentHashMap 的底层思路简述JDK 8 的ConcurrentHashMap虽然也是数组 链表 红黑树的结构但它把“锁”的颗粒度降到了单个桶位首节点。来找扩容时它还会用ForwardingNode标记正在迁移的桶位让其他线程识别并协助迁移把扩容的成本分摊到多个线程上。这种思路和HashMap的单线程扩容完全不同从设计上规避了并发扩容数据错乱问题。如果你的业务确实需要HashMap那种 O(1) 访问再加上线程安全ConcurrentHashMap基本是唯一合理的默认选择。6. 常见问题与排查技巧实录6.1 频繁扩容如何提前规避默认容量是 16意味着你往里面插入第 13 个键值对时就会触发一次扩容16 * 0.75 12。扩容不是零成本——需要新建数组、重算位置、迁移节点。如果预估数据量是 1000直接写new HashMap(1000)只会创建 1024 的容量阈值是 768装到第 769 个时又一次扩容。想避免这次扩容初始容量应该设为expectedSize / 0.75f 1也就是 1334 左右自动扩到 2048阈值变成 1536足够装下 1000 条数据。这个公式我建议直接背下来只要是固定数据规模的场景都能用上。6.2 key 的 equals 与 hashCode 必须同步重写这是我见过最多人犯错的地方只重写了equals()不重写hashCode()或者两者重写的规则不一致。HashMap在寻找 key 时先用hash定位桶位再用equals判断是否存在相同 key。如果equals认为两个对象相等但hashCode返回不同的值这两个对象会被定位到不同桶位导致get永远查不到put进去的数据。反过来如果hashCode相同但equals不相等只会发生哈希碰撞不影响正确性但影响性能。所以在业务对象作为 key 时这两个方法的规则必须保持“相等对象必须有相同哈希值”的基本原则。6.3 链表树化的阈值不是死的虽然代码里写的是TREEIFY_THRESHOLD 8但前面说过树化前还有一个前提数组容量必须大于等于 64。如果数组容量不够就算链表超过 8 个节点也只会触发扩容。所以当你看到某个哈希桶的链表越来越长时不要只想着“是不是 key 设计有问题”也要检查数组容量是否已经足够大。我调试过一个数据倾斜的案例最后发现不是因为 key 分布差而是初始容量太小导致不断扩容扩容后又立刻填满链表始终没有机会树化。6.4 用 HashMap 做 LRU 缓存要注意什么最后一个实操小技巧。有人喜欢用LinkedHashMap的访问顺序模式来做简单的 LRU 缓存这是可行的但要清楚底层依然是HashMap的实现逻辑只是额外多了一条贯穿所有节点的双向链表。如果你在重写removeEldestEntry时返回 true 的阈值设得太小会导致缓存频繁淘汰命中率下降如果设得太大内存占用又不可控。根据我的经验这个阈值需要结合业务的实际访问分布来调不能想当然。另外LinkedHashMap同样不适合多线程直接使用加锁时最好把整个结构包进同步块里而不是只锁单次操作。7. 最后说点实在话我在排查线上问题的时候发现很多故障追根溯源都不是HashMap本身写得有问题而是用的人没有想清楚它的适用边界。HashMap是一个优秀的数据结构它在 JDK 8 之后的设计已经相当精细——扰动函数、尾插法、红黑树化、高低位拆分扩容每一步都有性能和安全性上的考量。但它依然只是一个单线程友好的容器绝不意味着你可以拿它去扛所有场景。我个人在实际项目里养成了一个习惯每写一个new HashMap()前先问自己三件事——这个容器的生命周期多长会被多个线程共享吗写入的 key 分布是否可控只要有一个问题让你犹豫优先换成更合适的容器。如果你还在用HashMap做本地缓存建议改成Caffeine这类成熟方案它们内部对容量控制、淘汰策略和并发处理都已经处理得相当到位远比你在项目里手写一套强得多。数据结构本身没有绝对的好坏关键还是匹配场景。希望这篇文章能帮你在面试之外真正把HashMap用得心里有底。