HashMap 源码专场:从 put 到扩容,面试官想挖的 8 个坑

前两天有个读者面试，面到一半回来跟我说，被一道题问住了。

面试官让他讲讲 HashMap 的 put 流程。

他张口就来："数组加链表，超过 8 个转红黑树，扩容翻倍。"

说完挺得意。结果面试官追了一句："那为什么是 8 个，不是 7 个？"

他懵了。

这其实就是 HashMap 面试的真相：背结论谁都会，面试官要挖的是结论背后的原因。

今天这篇，把 HashMap 从 put 到扩容完整拆一遍，顺带把这 8 个坑全填上。看完，你也能反问回去。

一、先看底层结构：数组 + 链表 + 红黑树

HashMap 底层，一句话讲清：一个数组，数组里每个格子叫"桶"，桶里挂链表，链表太长就换成红黑树。

为什么是个数组？因为数组有个独门绝技，按下标取值，O(1)。

你把 key 算出一个下标，直接怼进数组那个位置，下次取的时候还按这个下标找，一次定位。这就是 HashMap 快的根子。

问题来了：key 千奇百怪，怎么变成一个数组下标？这就是 hash 干的事，也是第一个坑。

二、put 全流程，一步步拆

先把 put 完整走一遍，心里有个地图。

第一步，算 hash。

static final int hash(Object key) {

int h;

return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);

}

这一步不是直接用 hashCode，而是把 hashCode 的高 16 位和低 16 位做了一次异或。这个动作叫"扰动"，坑就藏在这。

第二步，算下标。

int index = (n - 1) & hash; // n 是数组长度

用位运算 (n-1) & hash 定位到具体桶。这里藏着第二个和第三个坑。

第三步，怼进桶。桶里空着，直接放。桶里有人，就得往下看：是同一个 key 就覆盖，是链表就遍历，是红黑树就按树的方式插。

第四步，判断扩容。元素个数超过容量 × 0.75，数组翻倍，所有元素重新搬家。第四个坑，就是这个 0.75。

流程就这四步，看着不难。难的是每一步背后，面试官都能挖出一个坑。

下面把这 8 个坑，一个一个填平。

三、8 个坑，逐个挖

坑1：hash 为什么要高 16 位异或低 16 位？

你想一个场景。数组长度默认 16，取下标靠的是 (n-1) & hash，也就是只用了 hash 的低 4 位（16 的二进制 1111）。

高 28 位呢？全被丢了。

问题就来了：如果你的 key 的 hashCode，高位在变、低位都差不多，那这些 key 会疯狂撞到同一个桶里，链表拖得老长。

所以源码把高 16 位和低 16 位异或一下，让高位的特征也"混"进低位。这样定位时，高位的差异也能参与进来，碰撞自然就少了。

一句话：让高位也出力，别闲着。

坑2：为什么用 (n-1) & hash，不用 % 取模？

先说结论：这俩在 n 是 2 的幂时，结果一模一样。

但 & 是位运算，% 是除法。位运算快得多，CPU 一条指令就完事，除法要慢一个量级。

HashMap 追求的就是这个快。

坑3：容量为什么非得是 2 的幂？

这是坑2的续集。

(n-1) & hash 要等于 hash % n，前提是 n 是 2 的幂。

因为只有 n 是 2 的幂，n-1 的二进制才全是 1。比如 16 减 1 是 15，二进制 1111。跟 1111 做 & 运算，就相当于把 hash 均匀地"分"到 0 到 15 每个格子。

如果 n 不是 2 的幂，比如 14，那 n-1 是 13，二进制 1101，中间有个 0。这个 0 会让某些下标永远落不到，数组空着一半，另一半挤爆。

所以源码里，不管你 new 的时候传多大容量，它都会帮你往上取整到最近的 2 的幂。

坑4：扩容因子为什么是 0.75？

这个 0.75，是空间和时间的平衡点。

调小一点，比如 0.5，数组还有一半空位就扩容，碰撞少，但浪费内存。

调大一点，比如 1.0，数组塞满才扩容，省内存，但桶里链表拖得长，查得慢。

0.75 是大量实验后取的一个折中值。面试你就这么说：太低浪费空间，太高碰撞增多，0.75 是权衡的结果。

坑5：树化阈值为什么是 8？

链表不是随便就能转红黑树的，得先排队排到 8 个。

为什么是 8？这里有个漂亮的数学解释。

源码注释里给过泊松分布的计算：在扩容因子 0.75 的前提下，一个桶里链表长度到 8 的概率，大约是 0.00000006。

亿分之六。翻译成人话：如果你的 hash 函数正常，一个桶挂 8 个元素的概率，小到几乎不可能发生。

反过来说，一旦真发生了，说明要么 hash 函数有问题，要么有人故意构造了恶意 key 来攻击（哈希碰撞攻击）。这时候转红黑树，就是兜底，防止链表退化成 O(n) 被拖垮。

坑6：为什么还有个 64 的门槛？

链表到 8 了，也不是立马转树，还有个前提：数组长度得大于等于 64。

这个 64 叫 MIN_TREEIFY_CAPACITY，最小树化容量。

逻辑是这样的：如果数组还很小，比如就 16 个格子，链表挂 8 个，说明是数组太小、元素太挤了。这时候转树没用，直接把数组扩容，元素一分散，链表自然就短了。

只有数组够大了（64），还出现长链表，才说明是真碰撞，才值得转树。

所以遇到链表到 8，先别急着转树，看数组大小，小就扩容，大才树化。

坑7：退化阈值为什么是 6，不是 8？

树化是 8，退化却是 6，中间留了个 2 的缓冲带。

这是为了防止"抖动"。你想，如果树化是 8、退化也是 8，那一个桶在 7 和 8 之间反复横跳，就会不停地"转树—退链—转树—退链"，白白浪费性能。

留个缓冲带，7 的时候不转也不退，稳稳的，不会来回折腾。

坑8：1.7 的头插死循环，是怎么回事？

这是 HashMap 历史上最著名的一个 bug，也是"线程不安全"的铁证。

JDK 1.7 扩容时，链表用的是头插法——新元素插到链表头部。

多线程同时扩容，两个线程都可能拿到同一个旧链表。一个线程刚把头节点的 next 改了，另一个线程又反过来改，链表就会被串成一个环。

环是什么概念？就是你 get 的时候，顺着 next 一直找，永远找不到头，CPU 直接飙到 100%，服务器卡死。

JDK 1.8 怎么治的？两个动作。

第一，改成尾插法，新元素插到链表尾部，不反转顺序，从根上掐断了环的形成。

第二，扩容时用高低位拆分，把一条链表按 hash 分成"留在原位"和"挪到高位"两条，各自保持原顺序。

但注意，1.8 只是把死循环这个 bug 修了，HashMap 本身依然线程不安全。并发场景下，该用 ConcurrentHashMap 还是得用。

四、两个高频追问，提前备好

追问1：HashMap 到底为什么线程不安全？

记住两个场景。

1.7 是死循环：头插法扩容，多线程下形成环，get 直接卡死。

1.8 是数据覆盖：两个线程同时 put 同一个位置，后写的那条把前一条盖掉，丢数据。还有 size++ 也不是原子的，计数会不准。

所以结论就一句：HashMap 设计之初就没考虑并发，并发请用 ConcurrentHashMap。

追问2：get 为什么是 O(1)？

严格说，是"平均 O(1)"。

理想情况：hash 算出下标，数组直接定位，一次拿到，O(1)。

退化情况：碰撞严重，桶里链表拖长，那 get 就退化到 O(n)。所以才有了红黑树，把最坏情况压到 O(log n)。

所以准确的说法是：哈希均匀时接近 O(1)，最坏 O(log n)。

最后，一张清单收走

这篇的干货，浓缩成几条带走：

一、HashMap = 数组 + 链表 + 红黑树，数组保证 O(1) 定位。

二、hash 高 16 位异或低 16 位，是让高位参与定位、减少碰撞。

三、容量 2 的幂，是为了 (n-1) & hash 能均匀散列，还能用位运算提速。

四、树化阈值 8（概率兜底）+ 最小树化容量 64（先扩容再树化）+ 退化阈值 6（留缓冲防抖动）。

五、1.7 头插会成环死循环，1.8 尾插加高低位拆分修掉了环，但并发还是得用 ConcurrentHashMap。

别光收藏。今天打开你电脑里的 HashMap 源码，对着 put 方法把这 8 个坑的位置挨个找出来。看过一遍源码，比背十遍八股都管用。

关注我，Java 面试干货，一期一个考点，持续更新 🔥