当前位置：首页 > news >正文

面试官：你说说 HashMap 的 put 过程？我直接把这篇文章甩给他，当场通过！

news 2026/5/16 13:02:53

前言

HashMap 作为 Java 集合框架中最常用的数据结构之一，几乎贯穿了我们日常开发的每个角落。同时它也是面试中的“常驻嘉宾”，从数据结构到线程安全，从 JDK 7 到 JDK 8 的变化，总能问出深度。

很多同学能背出“数组+链表+红黑树”，但当被问到扰动函数、扩容死循环或者为什么容量必须是 2 的幂时，就开始含糊。今天这篇文章，我们将从源码角度彻底拆解 HashMap 的 put 过程，把底层原理和面试考点一网打尽，建议收藏反复观看。

1. HashMap 的核心数据结构

在深入 put 操作之前，先快速过一下存储结构。

JDK 7：数组 + 单向链表（头插法）
JDK 8：数组 + 单向链表 + 红黑树（尾插法）

HashMap 内部维护了一个Node<K,V>[] table数组，每个数组元素称为“桶”（bucket）。当发生哈希冲突时，会以链表形式挂载到桶上。若链表长度≥ 8且数组长度≥ 64，链表树化为红黑树，从而将查询复杂度从 O(n) 降低到 O(log n)；当红黑树节点数≤ 6时会退化为链表。

![基本结构](https://img-blog.csdnimg.cn/...图片占位，建议自行画图。）

2. put 操作的宏观流程

一句话总结：通过 key 的哈希值定位到桶，然后放入或更新值。浓缩成源码里的putVal方法：

public V put(K key, V value) { return putVal(hash(key), key, value, false, true); }

关键步骤：

计算 key 的哈希值；
判断数组是否初始化，否则扩容/初始化；
通过哈希与数组长度取模定位桶；
如果桶为空，直接新建节点插入；
如果桶不为空，则在链表/红黑树中寻找 key，存在则更新，否则插入；
插入后判断链表是否需要树化；
最后判断是否需要扩容。

下面我逐步拆解每个细节，并附带简化的源码逻辑。

3. 哈希值计算 —— 扰动函数

HashMap 并没有直接使用key.hashCode()，而是经过了一次“扰动”：

static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }

为何扰动？
取模时通常只用到了哈希值的低位，高位特征容易被浪费。扰动函数将高 16 位与低 16 位做异或，低位的随机性增强，从而减少碰撞。
为何用异或而不是 & 或 |？
异或能让 0 和 1 各保持 50% 的概率，分布最均匀，而位与偏向 0，位或偏向 1，都会加大碰撞。

这个细节面试极爱问，记住“让高位参与运算，减少冲突”。

4. 定位桶索引 —— 为何容量必须是 2 的幂？

在putVal中，定位桶的代码是：

tab[i = (n - 1) & hash] // n 为数组长度

该语句等价于hash % n，但仅当 n 为 2 的幂时才成立。使用位运算比取模快很多，也是性能优化的关键。

容量始终为 2 的幂还有两个重要好处：

n-1二进制全为 1，哈希值的低位能完全参与索引运算；
扩容时hash & oldCap可以快速判断节点在新数组中的位置（见后文扩容部分），无需重新计算哈希。

你一定见过的面试题：“为什么扩容总是 2 倍？” 答案就是以上这些。

5. 核心 put 过程（简化源码注释）

以下是putVal的精简解读，建议对照源码阅读：

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; // 1. 数组若为空，先扩容/初始化 if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; // 2. 定位桶，若为空直接新建节点放入 if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { Node<K,V> e; K k; // 3. 桶内首个节点就是目标 key if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; // 4. 树结构下使用树的添加方法 else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); // 5. 链表遍历查找/追加 else { for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); // 树化判断：链表长度 >= 8 - 1 且数组长度 >=64 才树化 if (binCount >= TREEIFY_THRESHOLD - 1) treeifyBin(tab, hash); break; } if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } // 6. 存在映射则覆盖 value if (e != null) { V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; // 7. 判断是否需要扩容 if (++size > threshold) resize(); afterNodeInsertion(evict); return null; }

需要注意的点：

树化条件：binCount >= 7表示链表节点≥8，同时treeifyBin内部还会检查数组长度是否 < 64，若小于 64 会先扩容，而不是树化。
遍历比较：先比较哈希值，再比较引用地址==，最后才用equals，这是性能优化。
threshold= capacity * loadFactor（默认 0.75），当 size 超过该阈值就扩容。

6. 扩容机制 —— 一个 2 倍的美妙数学

扩容方法resize()核心任务：

新数组长度 = 旧数组长度 * 2
重新分配旧节点到新数组

JDK 7 采用头插法并每个节点重新计算索引，导致多线程下可能产生环形链表，引发 CPU 100% 的死循环。
JDK 8 采用尾插法，且利用了一个巧妙的规律：扩容后节点要么在原位置，要么在原位置 + 旧容量的位置。

因为 2 次幂扩容，旧索引只依赖于哈希值的低位 bit；新索引增加了一位参与运算。用旧 hash & oldCap 进行判断：

若(e.hash & oldCap) == 0，节点留在原索引；
否则，节点移动到原索引 + oldCap。

源码中将同一位置的链表分化为两条高低链（loHead, hiHead），一次性移动，避免每次重建节点的开销，同时保证了顺序不变。

面试题 “HashMap 如何扩容？” 如果能答出高低链表优化和尾插法，面试官一定会对你刮目相看。

7. JDK 7 vs JDK 8 对比，一个表格搞定

对比项	JDK 7	JDK 8
数据结构	数组 + 单向链表	数组 + 链表 + 红黑树
插入方式	头插法（导致resize死循环）	尾插法
哈希值计算	4次位运算+5次异或（更复杂）	高16位异或低16位（更简洁）
扩容定位	每个节点重新 hash 取模	利用 hash & oldCap 分流，效率高
空元素存储	允许 null 键值对（特殊处理）	同左

这些区别是面试的高频考点，特别是死循环产生原因及如何避免：要么用 ConcurrentHashMap，要么牢记多线程下不要用 HashMap。

8. 常见面试题与解答思路

HashMap 的 put 流程
按照本文第 5 步中的 7 个步骤回答，突出扰动函数、链尾插入、树化、扩容触发。
为什么从头插法改成尾插法？
头插法扩容时反转链表顺序，多线程 put 容易造成环，尾插法保持顺序不会成环。
为什么树化阈值是 8？
根据泊松分布，在负载因子 0.75 下链表达到 8 的概率极低（千万分之一），是空间与时间的权衡。同时退化为 6 防止频繁转换。
负载因子为什么是 0.75 ？
平衡了空间利用率和查找效率。过高会加大冲突，过低浪费空间。0.75 是官方反复测试的折中值。
ConcurrentHashMap 与 HashMap 的区别？
前者采用 CAS + synchronized 分段锁实现线程安全；HashMap 线程不安全，扩容时可能导致数据丢失或死循环。