“写出hashMap的人真TM是个天才”——这句话我念叨过很多次在和技术同事讨论容器的时候念叨在面试复盘的时候也念叨。HashMap大概是Java日常开发里最“普通”的一个类普通到很多人天天在用却答不出它为什么这么快也说不清它内部那张“数组链表红黑树”的设计图到底妙在哪里。这篇文章不劝你背面试八股我只想顺着一个程序员看到HashMap源码时会“卧槽”的瞬间把那几个核心设计点拆开讲明白。适合刚工作不久、被HashMap搞得一头雾水的同学也适合天天写业务、突然想补一补基础的老手翻一翻。1. 整体设计思路从“查字典”到“按页翻书”1.1 把查找拆成两件事定位和冲突处理在没有HashMap之前想在一个集合里找一个元素办法无非两条路要么顺序遍历要么用平衡树二分。前者复杂度O(n)数据一多就卡后者稳定在O(log n)看起来不错但要维护树的平衡插入删除的代价并不便宜。HashMap的思路其实不复杂先用一个数组作为“索引目录”再通过哈希函数把key换算成一个数组下标之后直接到那个下标位置去找。这个操作很像查字典时先翻到页、再定位字而不是从第一页开始逐字扫。但任何哈希函数都不能保证不同的key永远算出不同的下标这种“撞位置”的情况叫哈希冲突。数组每个格子里存的不再只是单个元素而是一条链表冲突了就往链表后面挂。这样一来理想情况下一次哈希就直接命中平均时间复杂度O(1)就算有冲突也只在桶内做小范围线性扫描只要这个桶里的元素很少性能依旧很可观。所以整个设计的核心就拆成了两件事一是让哈希值散布得足够均匀减少冲突二是当真冲突了用一套成本可控的结构去兜底并且当兜底结构也撑不住时还有自动升级和扩容的方案。三个手段要协同工作这个度才是真正见功力。1.2 为什么数组容量是16而且必须是2的幂很多讲HashMap的文章都会提到默认容量16但很少问一句为什么偏偏是16不是10不是32也不是100原因在寻址运算上。HashMap计算元素落点的关键动作不是传统的“取模”而是位运算。当一个数组长度是2的幂时hash % length可以用hash (length - 1)来替代而且结果完全一致。16对应的二进制是1000016减1是01111。任何数和01111做与运算只保留最低4位结果范围恰好是0到15和取模效果一样但位运算比拼除法快得多。这个结论还不是最妙的。最妙的地方在于扩容时容量翻倍从16变32相当于在二进制上多了一位。旧掩码是01111新掩码是11111。同一个哈希值在新数组里的下标要么不变要么在旧下标基础上加16判断依据仅仅是哈希值的某个bit是0还是1。这一下省掉了对所有元素重新计算哈希的功夫。后面扩容那一节会专门展开这里先记住一个关键结论长度保持2的幂是让HashMap整体性能最优的基石之一。日常使用中经常有人犯的错是创建map时用new HashMap(15)。这个15不是2的幂构造函数会自动把它调整成大于等于传入值的最小的2的幂也就是16。写代码的人如果不知道这一步会很困惑“为什么我传了15打印size却看到16”。另外自定义初始容量的时候也要按“预计元素数量÷负载因子之后再取2的幂”来估而不是拍脑袋。1.3 负载因子为什么是0.75负载因子是HashMap里出现频率极高的一个参数。它表示当元素个数达到容量的75%时触发扩容。默认容量16意味着元素个数达到16×0.7512时数组就会翻倍成32。按这个逻辑继续当元素到24时扩容到64到48时扩容到128一路2倍翻下去。这个数字不是随便拍的。如果把负载因子调大比如调到1.0那么空间利用率高了但碰撞概率也会升高查找成本变大如果调小到0.5碰撞少了但数组经常有一半位置空着内存浪费严重。0.75是时间和空间成本的一个折中点。还有一个容易被忽略的点负载因子还影响扩容次数。如果元素总量恒定是1000容量从16起步负载因子0.75对应着一共要扩容6次左右如果负载因子是0.5中途扩容的次数就更多每次扩容不仅要申请新数组还要把旧数据全部搬到新位置这是一笔不小的开销。所以不要一看到“内存空间浪费”就把负载因子往大了调扩容搬运的高成本往往比那点内存更肉疼。2. 扰动函数与位寻址hash里全是细节2.1 key的hashCode不是直接用先说一个很多人忽略的细节key.hashCode()返回的是一个32位int但数组长度如果只有16掩码只取最低4位也就是说高28位的信息全部被丢弃了。这就带来一个问题如果两个不同key的hashCode在高位上差异很大低位却恰好相同它们会算到同一个桶里。更极端的情况下一个设计糟糕的hashCode会让大量key的低位频繁重复导致哈希退化成链表。为了尽可能避免这种“低效寻址”HashMap在拿到hashCode()之后并不会直接用而是先做一次扰动把高16位和低16位做异或代码很简单就一行static final int hash(Object key) { int h; return (key null) ? 0 : (h key.hashCode()) ^ (h 16); }这步操作的意思是让高16位的信息也参与进低16位的计算。因为任何哈希函数最终都要和length - 1做与运算低位16位才是真正决定索引的部分。通过h 16把高位挪到低位再异或回去就相当于把高位的随机性和低位做了混合让低位的分布不再只依赖原始哈希值的低位。这个操作在古典时期尤其重要因为很多早期实现的hashCode并不均匀比如基于算术运算的哈希经常低位重复。即便到了现代也仍然有效当一个集合没有重写过hash分布或者采用了顺序ID、时间戳一类的数据扰动函数依然能把不同区间的差别带进低位的落点。2.2 用hash (len - 1)取代取模HashMap拿到扰动后的hash值后计算下标用的就是这个位运算tab[(n - 1) hash] (n - 1)和% n在n为2的幂时完全等价但性能更好。这里要特别提醒新手不要试图在自己代码里随意用hash (arrayLen - 1)替代取模前提是arrayLen必须是2的幂。如果不是这个公式结果会错得离谱得到的下标范围甚至可能超出数组边界。为了把这条链彻底弄明白举个例子。假设一个key的原始hashCode()是0xACED491B换成二进制先高16位异或低16位得到扰动后的h然后和15做与运算。由于15的二进制低4位全是1所以最终只看h最低4位。如果最低4位是1010那么下标就是10。整个过程CPU只需要几条指令不需要做除法这也是HashMap在绝大多数场景下能保持“吝嗇”性能的重要原因。当你自己实现一个类似HashMap的结构时也应该沿用这个思路表长保持为2的幂下标计算用位与长度满负载后就翻倍。很多新手喜欢用一个任意的素数作为取模基数认为这样分布更均匀但代价是每次寻址都要做真正的除法运算这在数据量大的时候损耗很明显。HashMap的取舍是默认的hash质量已经足够好再用位运算把最后的寻址成本压到最低。2.3 重写hashCode最常见的两个坑第一直接把类里面某一个字段的值当成hashCode返回。比如一个订单类只按订单号算hashCode看起来没问题但订单号往往是连续递增的比如120301、120302它们的二进制低位变化其实很小如果数组又不够大极易出现连续冲突最终退化成链表。第二让hashCode每次返回固定值。有同学图省事把hashCode()直接return 1所有key都会落到同一个桶HashMap瞬间变成一条超长链表树化之前每个操作都是O(n)。这在测试数据量小的时候根本感知不出来稍微压一下量就立马卡死。有名的经验规则是自定义key时hashCode的“信息熵”要尽量散布到高位和低位只需遵守equals方法判等为true时hashCode必须相等但反过来并不需要对所有不等的对象都分配不同的哈希值。一个常见的实用写法是把几个主要字段的哈希值组合起来再通过移位异或混合而不是只取其中一个字段。下表是几个常见坑位的直观对比场景现象根因只用一个整型字段当hashCode且字段值连续大量key集中到相邻桶低bit变化太少高位信息丢失hashCode恒为常数全部元素挤在一个桶映射完全没有区分度用可变对象当key改完再查询查不到旧值哈希值变了定位到新桶用自定义key但没重写equals明明值相同却查不到equals判不等导致无法命中3. 树化阈值8和64这些数字背后是概率计算3.1 为什么桶内链表长度到8就转红黑树当链表过长查找复杂度退化到O(n)。HashMap采取的措施是链表转红黑树当某个桶内元素数量超过8且整个数组容量大于等于64时链表会转成一棵红黑树。红黑树的查找复杂度是O(log n)能在冲突严重时兜住性能。如果链表转树的阈值是8退化判断是66和8之间差了一个元素这个不对称很讲究不是笔误而是为了避免“抖振”。设想一下如果阈值是7某桶在当前时刻有7个元素转树过了一会儿删掉一个变6又转回链表再插入一个又变7再转树那么在临界区反复横跳会带来频繁的结构切换白白浪费CPU和内存。让树化发生在8退化发生在6中间留下一个缓冲带是一种典型的滞回设计。学过嵌入式或自动控制的同学对这类防抖应该很有共鸣。那为什么偏偏是8不是6不是9这里牵扯到一个概率模型。在哈希函数设计得足够均匀的理想假设下每个桶内的元素数量服从泊松分布。假设负载因子0.75那么桶内出现k个元素的概率可以用泊松公式估算。在某个主流JDK版本的源码注释里可以看到这组数据链表长度8的出现概率约为千万分之六长度9及以上的概率更低到几乎可以忽略。所以8这个阈值实际上是“几乎不可能发生”和“真发生了说明hash出了大问题”之间的一道分界线。只要哈希函数本身没写崩桶内链表长度到8的概率微乎其微树化这个机制大多数情况下是“备而不用”。但一旦某个key的hashCode写得极差比如所有key哈希值全相同树化机制就能保证即使全挤到同一个桶也不会完全退化到线性扫描。3.2 64这个数组容量门槛又是什么树化条件不止“链表长度8”还要求“数组容量64”。两个条件同时满足才转树。为什么要加这个门槛这个设计非常典型地体现了“先扩容、后树化”的策略当整个数组容量还很小比如只有16时即使出现一个桶里塞了8个元素大概率也不是哈希函数太差而是数据量相对容量而言确实太大了。此时正确的做法是先把容量翻倍让元素分散到更多桶里去而不是立刻对单个桶做树化。如果反过来一出现长链表就直接转树那么在数据量增长的前期树化操作会非常频繁而每次扩容又会让元素重新分布可能树化完没过多久又要拆回链表白折腾。让64作为门槛的意思就是先把宏观容量铺开再对个别深入问题的桶做手术。实际开发里把这两个数字记在脑子里会有用当你用HashMap存储了一个大量元素的集合并观察到某个桶内始终是红黑树形态就该怀疑是不是hashCode的分布出了问题而不是先怀疑树化本身。同理当你在代码里看到一个循环频繁往里塞数据而且初始容量设得太小扩容和树化往往会在同一段时期集中爆发表现为明显的CPU尖峰。4. resize扩容二倍扩容和链表拆分的位运算魔法4.1 扩容时如何免于全部重算哈希HashMap在元素数量超过容量×负载因子时会创建一个长度为原来两倍的新数组。真正让人拍案叫绝的是元素迁移的过程。旧容量为16时数组掩码是1111也就是低4位新容量为32时掩码变成11111低5位。原来低4位相同的两个元素到了新数组里下标是否还能保持一致取决于它们的第5位二进制从低往高第5位是否同为0或同为1。如果第5位是0新下标和旧下标完全一样如果第5位是1新下标就在旧下标基础上加上16。这个16恰好就是oldCap。这个地方神奇之处在于不用再对每个旧元素重新调用哈希函数只要检查(e.hash oldCap)是0还是非0就行。因为oldCap在二进制里是一个单独的1比如16的二进制是10000和哈希值做与运算得到非0就说明哈希值的这一位是1。是1就移动到“原索引oldCap”的位置是0就留在原地。一个位运算搞定了所有元素的去向。源码里的逻辑大致长这样if ((e.hash oldCap) 0) { // 留在原索引 newTab[j] e; } else { // 原索引 oldCap newTab[j oldCap] e; }这让扩容过程不需要对每个节点重新计算哈希也不需要重新散列只是把每条链表根据某一个bit拆成两条再接到新数组的两个位置上。时间复杂度直接从“每个元素重新算一遍”降到了“每个元素做一次与运算”。4.2 JDK7头插法与JDK8尾插法的差别老开发者应该听说过一个著名的坑JDK7及之前的版本在并发扩容时可能形成环形链表导致下一次get卡成死循环。原因在于旧版扩容采用的是“头插法”迁移链表时把新节点不断插到链头这样链表顺序会反转。一旦两条线程同时扩容、同时移动同一条链表互相覆盖引用链表就可能成环。JDK8改用“尾插法”迁移后新链表的顺序和旧链表保持一致成环概率大幅降低但这不是说JDK8就线程安全了。一个常见的误解是“JDK8的HashMap可以并发用了”。实际不是。多线程同时put仍可能丢数据可能出现ConcurrentModificationException只不过死循环这个问题没有那么容易触发了。正确做法并发场景用ConcurrentHashMap不要在HashMap外面套一层Collections.synchronizedMap就当保险它只能锁住单个方法边界复合操作仍然有可能出问题。4.3 扩容带来的现场感什么时候触发、怎么观察一个运行中的Java应用HashMap从16开始反复扩容到128甚至256这个过程中会有多次数组复制和信息搬运。虽然单次扩容很快但如果初始容量设置得极不合理扩容会频繁发生。线上排查时有一个比较经典的观察路径如果某个接口的QPS很高同时每次请求都会新创建一个HashMap并不断put数据那么扩容开销会真实影响到接口耗时尤其是当创建次数以百万计的时候。提前估算容量的办法很简单初始容量 预估元素数量 ÷ 负载因子 1。比如预估要存1000个元素那初始容量最好设置成1000 / 0.75 1 ≈ 1334再取近似的2的幂也就是2048。没必要精确到字节但至少别让HashMap从16一步步扩到1024中间白白多搬好几次数据。5. 高频问题排查与常见误区实录5.1 查一个“明明存在”却取不到的key这类问题高居HashMap踩坑榜第一名。场景通常是用某个自定义对象作key放入map后后续又去查询一个字段值完全相同的对象结果返回null。原因一般是没有重写equals()和hashCode()或者两者重写不一致。HashMap定位元素分两步先按hashCode()找到桶再在桶内用equals()逐一比对。如果hashCode()相同但equals()不同会在同一个桶内找不到该对象如果hashCode()不同连桶都进错。你要保证两点参与equals()比较的字段必须参与hashCode()计算反过来判断“不能等值”的两个对象其哈希值也不必非要不同。很多人只在类里加了一个equals()就以为万事大吉漏了hashCode()这类bug隐蔽性极强。5.2 可变对象当key的坑有不少人喜欢把一个自定义对象当key这个对象里有一个字段后面还被修改了。一旦字段修改导致hashCode()变化这个key在map里的桶位置也跟着变了。再想get按新hash找过去那里当然没有旧hash对应的旧桶里倒是还有这个entry但你永远不可能再按正常的key逻辑找到它。更隐蔽的问题是hashCode可能被缓存。HashMap在某个JDK版本里会对key做一次哈希计算并把结果存到节点里如果key内部的哈希值随字段改变而缓存没有同步更新那索引位置可能还是老的但equals()在新字段值下可能对另一个对象返回true。这一类问题的排查往往只能加班。实用的建议是作为key的对象要尽量做成不可变的。平时能用String、Integer、Long这类标准包装类型就不要自己设计一个可变对象来当key。所谓的不可变不是说对象创建之后不能有任何字段变动而是说参与哈希判断的那几个关键字段不能变。改其他无关字段是可以的但前提是你确认不参与hashCode()和equals()。5.3 hashCode均匀但依然性能差还有一种奇怪的现象代码里所有key都是StringhashCode实现本身很OK但接口性能还是慢。这时候大概率不是HashMap的问题而是数据分布恰好在容量很小的阶段集中撞进了同一个桶。举个例子一个HashMap初始容量16往里放50个字符串这50个字符串的哈希值低4位恰好分布不均匀冲突自然多但这不怪哈希函数怪初始容量太小。解决方式很简单预估数据量给足初始容量并且尽量让容量是2的幂。也可以在存放数据后发现resize变得非常频繁就把初始容量调大。很多团队规范里会强调“集合创建时必须指定容量”原因也就在这里为了减少无谓的扩容和重排。5.4 对HashMap做并发读写导致的未来式故障HashMap不是线程安全的这个大家都知道但真实生产环境里很多人还是会因为“这个Map只在一个局部方法内用”而掉以轻心。如果这个局部方法被多个线程同时执行而方法内新建了一个HashMap并只做put不会出问题但如果你把一个Map作为共享字段或静态字段在多线程下读、写那么数据不一致、丢数据、迭代异常都可能在某个流量尖峰的时候集中爆发。排查方向出现了ConcurrentModificationException看堆栈定位到迭代处再看这个Map是否有共享生命周期。不要在迭代过程中直接put或remove如果一定要删用迭代器的remove()。更干脆一点的做法是并发场景直接用ConcurrentHashMap。不要出于“我设置了初始容量所以很安全”的想法线程安全和容量没有任何关系。6. 个人实战心得别把“天才”理解成“完美”拆完这些设计之后我最大的感受是写出HashMap的人并不只是在写一个能用的容器而是在一个极其受限的模型里做了大量精妙的工程权衡。但天才的立意不代表它适合所有场景。实战中有一句话我一直挂在嘴边HashMap是“默认选项”不是“万能选项”。如果你需要元素顺序稳定有序别用HashMapLinkedHashMap可以保持插入顺序TreeMap可以按键排序。如果你需要高并发写入别指望HashMapConcurrentHashMap的原子化接口更适合。如果key是区间型的比如“按时间范围查找”HashMap的哈希定位帮不上忙老老实实上跳表或倒排索引。我自己在维护项目时见过一份业务代码为了“性能”强行用HashMap存大对象但读取量并不大反而因为反复扩容占用了大量内存最后换成更朴素的数组列表GC压力立刻降下来。还有一条关于调优的经验想多说一句很多人一旦遇到性能问题第一反应是调负载因子或者搞自定义初始容量但HashMap的性能瓶颈往往不是寻址本身而是数据量、冲突分布和内存占用三件事叠在一起决定的。比如你放进去100万个元素初始容量设为131072负载因子0.75那么当数据量接近98304时就会扩容到262144。看起来会经历多次扩容但每次扩容都是倍速增长整体搬迁次数并不多。真正该做的是一开始就把容量估计准确避免小步快跑的反复扩容。HashMap里最值得学的其实不是记住那几个阈值而是它“用概率模型指导工程判断”的思路什么样的冲突可以接受什么程度的冲突需要结构升级都在做之前就算好了。我自己每写一个自定义的哈希结构都会先问两句话我的哈希函数能不能把信息散布到整个地址空间我的表长变化能不能用位运算完成这两个问题想清楚比背十套源码注释都管用。最后分享一个小细节HashMap允许null作为key而且null的哈希值是0这在我一开始接触时也很困惑。后来想想如果你自己实现一个Map要处理“null key到底放到哪个桶”的问题最简单的办法就是固定放第0个桶。HashMap就好在这所有细节都看着随意但背后全有交代。设计这个东西的人确实值得那句“天才”。