“写出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对应的二进制是10000，16减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.75=12时，数组就会翻倍成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，退化判断是6，6和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都是String，hashCode实现本身很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是“默认选项”，不是“万能选项”。
如果你需要元素顺序稳定有序，别用HashMap，LinkedHashMap可以保持插入顺序，TreeMap可以按键排序。如果你需要高并发写入，别指望HashMap，ConcurrentHashMap的原子化接口更适合。如果key是区间型的，比如“按时间范围查找”，HashMap的哈希定位帮不上忙，老老实实上跳表或倒排索引。我自己在维护项目时，见过一份业务代码为了“性能”强行用HashMap存大对象，但读取量并不大，反而因为反复扩容占用了大量内存，最后换成更朴素的数组列表，GC压力立刻降下来。
还有一条关于调优的经验想多说一句：很多人一旦遇到性能问题，第一反应是调负载因子或者搞自定义初始容量，但HashMap的性能瓶颈往往不是寻址本身，而是数据量、冲突分布和内存占用三件事叠在一起决定的。比如你放进去100万个元素，初始容量设为131072，负载因子0.75，那么当数据量接近98304时就会扩容到262144。看起来会经历多次扩容，但每次扩容都是倍速增长，整体搬迁次数并不多。真正该做的，是一开始就把容量估计准确，避免小步快跑的反复扩容。
HashMap里最值得学的，其实不是记住那几个阈值，而是它“用概率模型指导工程判断”的思路：什么样的冲突可以接受，什么程度的冲突需要结构升级，都在做之前就算好了。我自己每写一个自定义的哈希结构，都会先问两句话：我的哈希函数能不能把信息散布到整个地址空间？我的表长变化能不能用位运算完成？这两个问题想清楚，比背十套源码注释都管用。
最后分享一个小细节：HashMap允许null作为key，而且null的哈希值是0，这在我一开始接触时也很困惑。后来想想，如果你自己实现一个Map，要处理“null key到底放到哪个桶”的问题，最简单的办法就是固定放第0个桶。HashMap就好在这：所有细节都看着随意，但背后全有交代。设计这个东西的人，确实值得那句“天才”。
