企业官网建设流程全解析

很多读者背HashMap的面试题时都能背出“数组加链表、红黑树、负载因子0.75”这些关键点，但只要被追问“put一个key-value进去，底层代码到底是怎么一步步走的”，就开始含糊了。我当初读源码也是卡在putVal这个长方法上，它看起来分支多、变量多，但其实自上而下就是一条完整的“找位置、插节点、收尾扩容”的链路。今天这篇就把putVal()从入口到返回值的每一行都拆开讲清楚，顺便把hash()扰动、resize()扩容、以及树化阈值8和64是怎么配合的也一并串起来。无论你是准备面试，还是排查线上HashMap性能毛刺，这篇都值得对照着JDK 1.8源码读一遍。

1. 入口方法就一行：put()只是把活转交给putVal()

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

这是HashMap的put源码，就一行。很多人误以为put就是直接把元素塞进数组，实际上它只做了三件事：调用hash(key)算出二次哈希、把key和value按顺序传给putVal、再补上两个控制参数false和true，真正干活的putVal在下面。理解这行的意义在于：看源码不要只盯着put，它只是个门面方法。

1.1putVal的五个参数，分别是什么用意

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)

• hash：经过扰动后的哈希值，不是原始的hashCode()。
• key和value：要保存的键值对。
• onlyIfAbsent：为true表示“只有key不存在时才插入”，对应putIfAbsent方法；put传false，表示允许覆盖已有值。
• evict：这个参数平时没人注意，它是给LinkedHashMap用的回调参数，HashMap里只是原样传给afterNodeInsertion(evict)空方法。

put的返回值也有讲究。如果原来没有这个key，插入成功后返回null；如果原来已经有这个key，会把旧value返回。所以有人写代码时用put返回值判断“是否插入成功”并不严谨，因为旧value本身可能就是null，返回null不代表插入失败。

1.2hash()的扰动函数：为什么把hashCode的高16位混进低16位

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

key == null时哈希值为0，所以HashMap允许一个null键，它永远落在0号桶。key非空时，把hashCode()右移16位后再和原值做异或，这个操作叫扰动。为什么要多此一举？因为后面计算数组下标用的是(n - 1) & hash，如果n是16，那么只有hash的低4位参与计算。如果两个对象的hashCode()低位完全相同、高位完全不同，不扰动的话铁定碰撞。

我举个例子：假设两个对象的hashCode分别是0x00001234和0xFFFF1234，低16位都是0x1234。当HashMap容量为16时，(n - 1) = 15 = 0x000F，直接拿原哈希值做位与：

• 0x00001234 & 0x000F = 0x0004，索引4
• 0xFFFF1234 & 0x000F = 0x0004，索引4

完全碰撞。但经过h ^ (h >>> 16)扰动后再计算，第二个哈希值的高位差异被“揉进”低位，0xFFFF1234扰动后变成0xFFFFEDCB，再和15做位与得到索引11，和第一个对象4就分散开了。

这就是扰动函数的意义：让高位信息也参与低位索引的确定，降低碰撞概率。扰动计算非常轻量，一次异或一次右移，对插入性能的影响几乎可以忽略。

1.3putVal的整体骨架，先建立全局视角

putVal大体分五步：

1. 如果table数组还没初始化，先调用resize()去初始化。
2. 根据(n - 1) & hash定位到桶位，如果槽位为空，直接放一个新Node进去。
3. 如果槽位非空，分三种情况处理：首节点就是同一个key，直接记录旧节点；槽位首节点是红黑树节点，走putTreeVal；否则遍历链表，要么找到key相同的节点，要么在尾部追加新节点。
4. 如果第2、3步中找到了已经存在的key，用新value替换旧value，并返回旧value。
5. 如果是真正新增了节点，modCount加1、size加1，如果size超过threshold就触发resize()扩容。

这个框架建立之后，再往下一段一段看源码，就不会迷路。

2. 空桶直接插入：为什么先要检查resize，下标又是怎么算出来的

先看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; if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { // 冲突处理逻辑，下一章详聊 } }

第一眼看到resize()可能觉得奇怪：我只是put一个元素，怎么还要扩容？实际上resize()在HashMap里是“一专多能”：既能扩容，也能在第一次put时完成底层数组的初始化，属于懒加载设计。

2.1 懒加载初始化：无参构造时table其实是null

用new HashMap<>()创建对象时，底层table数组默认是null，只有第一次调用put时才会通过resize()真正分配数组。这样做的好处是节省内存，尤其适合“创建了Map但没放多少数据”的场景。

方法第一行用了局部变量tab、n来接收table和它的长度，后面一系列判断都用局部变量，而不是反复读this.table。这是源码中常见的性能优化写法，减少字段访问次数。理解这一点后再看源码，就不会被一长串赋值表达式绕晕。

resize()在初始化场景下做的事很简单：根据threshold中暂存的容量值，分配一个2的幂次方大小的数组，并重新计算新的threshold。这里有一个很多人不知道的隐蔽点：如果用new HashMap<>(20)创建对象，20并不会直接成为数组长度，而是被tableSizeFor向上取整为32，然后暂时存放在threshold字段里。第一次resize()时又把32当作初始容量用，真正的扩容阈值要等这次resize()结束后才计算为32 * 0.75 = 24。所以读源码时看到“threshold里存的不是阈值，而是初始容量”，不要惊讶，这是JDK源码里一个经典的“字段复用”骚操作。

2.2(n - 1) & hash：位运算取模，比%快得多

下标计算用的是(n - 1) & hash，这一步等价于hash % n，但前提是n必须是2的幂次方。为什么？

这个结论很多人知道，但未必理解得透彻。当n = 16时，n - 1 = 15，二进制是0000 1111，低4位全1。任何数跟15做位与，结果都只保留低4位，范围正好是0到15，效果等同于对16取模。而且CPU执行位与指令比整数取模指令更快，所以HashMap用位运算代替取模。

HashMap之所以始终把容量维持为2的幂，除了计算快，还有一个深层原因是方便扩容时的高低位拆分，这部分在第四章讲resize()时会展开。如果你自己初始化时传的不是2的幂，比如17，构造函数也会通过tableSizeFor把它修正为32。

2.3 空桶落位：newNode创建了一个带hash字段的节点

if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null);

如果算出来的下标在数组里是null，说明这个桶还没放过任何元素，直接new Node放进去。这个分支没有任何equals比较，也没有链表遍历，插入时间复杂度是O(1)。

newNode(hash, key, value, null)最后一个参数是next，这里传入null表示这个节点没有后继。节点的hash字段会保存当前的哈希值，就算以后该节点被迁移到扩容后的新数组，也不需要重新调用hash()计算，直接用存好的字段就行。这也是每个Node都要保存hash的原因之一。

空桶插入看起来平淡，但它揭示了一个关键事实：只有当桶位空时，HashMap的插入才是真正的“一次到位”。绝大部分put操作的耗时差异，其实都发生在冲突之后。

3. 非空桶的两条路径：链表尾插是常态，树化是特殊保护

当(n - 1) & hash算出的桶位不为空，说明发生了哈希冲突，进入putVal的else分支。这段代码是整个方法的核心，也是最容易把人绕晕的地方。

else { Node<K,V> e; K k; if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); else { for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); 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; } } if (e != null) { V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } }

这段逻辑虽然只有二十多行，但分支条件相互嵌套，我先拆成三层来理解：先判断“桶首节点是不是我要找的key”，不是的话再看“这个桶是不是已经红黑树化”，都不是则说明“桶里是一串普通链表”，于是遍历链表。

3.1 判断“同一个key”为什么先比hash再比equals

第一层判断条件是：

if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))

这里用了两个层次的比较：先比hash是否相等，再比引用相等或equals相等。为什么不能只比equals？因为hash是一个快速过滤器，Java里两个不同对象如果hashCode不同，那它们一定不是同一个key，先比较哈希可以大概率跳过equals调用，节省性能。为什么不能只比hash？因为哈希冲突客观存在，两个不同对象的hashCode可能相同，必须用key ==或者key.equals(k)做最终确认。

这段代码还有一个细节容易忽略：key != null判断放在equals调用前。如果key本身是null，就只靠引用相等来判断；否则才调用key.equals(k)，避免空指针异常。当然，HashMap的nullkey只会落在0号桶，这里前置判断主要是为了代码的健壮性。

3.2 桶首不是目标key，可能桶里是红黑树

第一层判断不满足后，紧接着看p instanceof TreeNode。p是桶位上的首节点，如果它是TreeNode类型，说明这个桶已经被树化，不能再当普通链表遍历，于是调用((TreeNode)p).putTreeVal(this, tab, hash, key, value)。

putTreeVal是红黑树内部的插入逻辑，它会按照红黑树的比较规则在树中查找key，找到就返回旧节点，没找到就插入新节点并做平衡旋转。作为普通使用者，不需要背红黑树的旋转细节，但一定要记住：一旦桶变成红黑树，put查找复杂度从链表的O(n)降为O(log n)，这是树化对抗极端哈希冲突的核心意义。

3.3 链表遍历：尾插法、binCount计数和treeifyBin

更常见的情况是桶里是一条尚未树化的链表，进入for循环。这个循环里有两个出口：一是遍历到链表尾部p.next == null，说明链表里没有相同key，执行尾插；二是在遍历中间某个节点时发现e.hash == hash且key相等，说明找到了已存在的key，直接break，后续走替换value的流程。

循环里的binCount从0开始计数，每往后走一个节点加1。当尾插发生时，如果binCount >= TREEIFY_THRESHOLD - 1，即binCount >= 7，就调用treeifyBin(tab, hash)。这里的7不是直接和链表长度比较，因为binCount记录的是“当前节点的前驱个数”。假设一个新节点插入前，链表已经有7个节点，此时binCount从0累加到6，判断6 >= 7不成立；当链表已经有8个节点时，binCount会累加到7，判断7 >= 7成立，触发树化尝试。所以binCount >= 7对应的是“链表节点数达到8”。

循环里还有个容易看错的地方：每轮先看p.next，命中尾部就插入新节点并break；中间判断的是e（也就是p.next）是不是目标key，只有e不是目标key时才执行p = e，把游标后移。这种写法使得每次比较的节点恰好是“下一个节点”，配合binCount的计数方式，逻辑上是自洽的。

3.4 treeifyBin的第二个门槛：容量必须大于等于64

final void treeifyBin(Node<K,V>[] tab, int hash) { int n, index; Node<K,V> e; if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) resize(); else if ((e = tab[index = (n - 1) & hash]) != null) { // 把单向链表转成双向链表，再调用hd.treeify(tab)转红黑树 } }

MIN_TREEIFY_CAPACITY常量值是64。也就是说，即使链表长度已经达到8，如果当前整个HashMap的容量还小于64，treeifyBin并不会真正转红黑树，而是调用resize()去扩容。

这个设计非常讲究。容量小的时候，哈希冲突大概率是“桶不够用”导致的，此时应该让数组变大、把元素分散开，而不是急着把链表转成红黑树；红黑树节点TreeNode大约是普通Node的两倍大小，过早树化既浪费内存，又可能因为扩容后树被拆散而白费功夫。只有容量已经大于等于64，说明桶空间足够，但某个桶仍然积累了大量节点，这才有理由怀疑存在严重的哈希分布问题或恶意哈希攻击，此时树化才是合理选择。

关于TREEIFY_THRESHOLD为什么是8，源码注释里给了参考：在负载因子0.75的随机哈希场景下，同一个桶内链表长度达到8的概率极低（按泊松分布估算约千万分之六），可以认为属于异常情况。这个概率分布平时不需要背，但面试被问到时要能说出“8这个阈值既考虑了红黑树的空间成本，也考虑了冲突概率的统计结果”。

3.5 头插法到尾插法：JDK 8在并发层面的一次妥协

老读者应该听说过JDK 7里HashMap并发扩容形成死循环的问题，根子就在于JDK 7采用头插法：每次在链表头部插入新节点，扩容迁移时链表顺序被反转，并发情况下容易造成循环引用。JDK 8改成尾插法，新节点永远追加在链表尾部，扩容迁移时也就不会产生逆序链，从根上消除了形成环的一个诱因。

注意“一个诱因”这个措辞。尾插法只是降低了风险，HashMap在任何版本下都不是线程安全的。并发写入依然可能丢数据，比如两个线程同时走到++size，各自加1但最终只写回一次，size就少了。所以并发场景请老老实实使用ConcurrentHashMap，不要拿HashMap将就。

4. 收尾阶段的三个动作：modCount维护、size自增和resize扩容

如果前面的流程是“新增了一个节点”，也就是没有走e != null替换分支，putVal最后会执行：

++modCount; if (++size > threshold) resize(); afterNodeInsertion(evict); return null;

这三行信息量很大，很多人只记住了resize，把modCount和afterNodeInsertion遗漏了。

4.1 modCount：保护迭代器的快速失败机制

modCount翻译过来是“修改次数计数器”。每次发生结构性修改时它都会加1，这里的“结构性修改”指新增或删除节点。注意：如果put时key已经存在，只是替换了value，那走的是前面e != null分支，modCount并不会增加。

这个计数器和迭代器密切相关。如果用iterator遍历HashMap，同时另一个线程往里put了元素，迭代器在下一次next()时发现modCount已经变了，会立刻抛出ConcurrentModificationException。这就是快速失败机制，目的是让程序尽早暴露并发修改问题，而不是在未知时刻崩溃。

顺带说一句，modCount只统计结构性修改，所以“覆盖旧value”不会触发快速失败。这个细节在面试中经常被拎出来考，别记混了。

4.2 size超过threshold：为什么是“大于”而不是“大于等于”

threshold的计算公式是capacity * loadFactor，默认负载因子0.75。16容量的表，阈值是12。当size涨到13，也就是++size > 12成立时，触发resize()；而size正好等于12时不会扩容。用“大于”而不是“大于等于”意味着HashMap允许容量暂时用到阈值那一刻，超过一个才扩容，少一次临界扩容。

resize()做的事情可以概括为三步：把数组长度翻倍、把阈值翻倍、把旧数组每个桶里的元素迁移到新数组。翻倍操作在源码里就是一句newCap = oldCap << 1，因为容量始终是2的幂，左移一位就是乘2。

4.3 扩容迁移的高低位拆分：一条链分成两条链

迁移元素时最精彩的逻辑在这里：

if ((e.hash & oldCap) == 0) { // 放入低位链 loHead / loTail } else { // 放入高位链 hiHead / hiTail }

为什么一个hash & oldCap就能判断节点该留在原索引还是移动到“原索引 + oldCap”？

关键在于索引计算的变化。旧容量是oldCap，旧索引是(oldCap - 1) & hash。新容量是2 * oldCap，新索引是(2 * oldCap - 1) & hash。容量翻倍后，参与位与运算的位数多了1位，刚才没参与计算的那一位，恰好就是oldCap对应的那个二进制位。如果这一位是0，新索引和旧索引完全相同；如果这一位是1，新索引等于旧索引加上oldCap。

举个具体例子。假设oldCap = 16，某个节点hash的二进制是... 0001 0101。oldCap - 1 = 15 = 0000 1111，hash & 15 = 0101 = 5，旧索引是5。扩容后newCap = 32，newCap - 1 = 31 = 0001 1111，hash & 31 = 0001 0101 = 21，新索引变为了5 + 16。因为hash在16这一位（也就是oldCap位）上是1。再看另一个节点hash = ... 0000 0101，oldCap位是0，新索引依然是5。

通过e.hash & oldCap判断高低位，迁移时不需要重新计算索引，只需把一条原链表按这个位拆成lo和hi两条链，再分别挂到新数组的j和j + oldCap两个位置。这个设计充分利用了容量是2的幂的特性，迁移效率极高。JDK 8也把迁移从JDK 7的“每个节点重算index、头插法插入”优化成了“链表原序拆分、两个尾指针直接挂载”。

4.4 afterNodeInsertion：给LinkedHashMap留的钩子

void afterNodeInsertion(boolean evict) { }

这个空方法在HashMap里什么都不做，但它是专门留给子类LinkedHashMap的扩展点。LinkedHashMap重写它之后，可以在每次插入完成后检查是否需要删除最老的节点，从而实现LRU缓存。这是JDK里很典型的模板方法模式应用：主流程固定，扩展点留空，子类按需覆盖。理解了这一层，你会发现putVal的三个尾巴动作其实各有各的职责：modCount管迭代安全，size管扩容，afterNodeInsertion管扩展。

5. 把putVal读穿之后：几个高频追问和几个实战调试技巧

源码读到这个程度，再回头看那些常被追问的HashMap问题，答案就不再是死记硬背，而是一套自洽的设计逻辑。

5.1 高频追问串讲

为什么容量必须是2的幂？数组下标计算要用(n - 1) & hash，只有n是2的幂，n - 1的二进制才是低位全1，位与才能等价于取模。同时这个特性支撑了resize时用hash & oldCap做高低位拆分，让扩容迁移不必重算每个节点的下标。

null key存在哪里？hash(null)固定返回0，所以null key永远被分配到0号桶。第二次put null key时，会走替换value的分支，旧value被返回。这也是HashMap只允许一个null key的原因。

负载因子为什么默认0.75？这是时间和空间的折中。负载因子越大，比如1.0，数组利用率高但冲突更多，查询变慢；负载因子越小，比如0.5，冲突更少但浪费空间。0.75在大多数场景下表现均衡。此外，源码注释里有泊松分布推算，0.75的负载因子下链表长度达到8的概率低到可以忽略。

链表长度到8就一定会树化吗？不一定。treeifyBin还有两个前置条件：table非空且长度大于等于64。如果链表长度已经是8但数组容量还不到64，会先走resize()扩容而不是树化。

put返回null代表什么？只代表旧value是null，或者之前根本没有这个key，不能直接当成“插入失败”理解。

5.2 自己动手验证：三种能快速加深理解的调试方式

读源码最怕“眼睛会了，手没跟上”。我建议你把JDK源码里的putVal和resize复制到一个独立Demo工程里，自己加日志或断点观察。

第一种，在putVal入口打断点，观察连续put若干元素时table.length、size、threshold的变化。你会发现前12次插入都不扩容，第13次插入后size变为13，超过threshold=12，触发第一次扩容，数组长度从16变32，阈值变为24。

第二种，写一个hashCode()固定返回某个常数的类，连续put多个对象到同一个桶里。比如让hashCode恒为1，那么所有元素都落在1号桶，你会看到链表慢慢变长；当链表长度到8时，如果此时容量只有16或32，会先扩容到64；等到容量达到64后再继续让该桶积累到8，才会真正看到红黑树生成。

第三种，在resize()迁移循环处打断点，观察同一个桶内的节点被拆分成lo链和hi链的过程，再对比迁移前后的(n-1)&hash计算结果。亲眼看到“原位不动”和“原索引+oldCap”这两种走向，比背十遍源码都管用。

5.3 容易背错的细节清单

最后列几个我自己读源码时栽过跟头、也常被同行朋友问到的点：

• 用new HashMap<>(17)创建对象，底层容量不是17，而是向上取整到32，而且这个32在初始化前被存在threshold字段里，第一次put初始化后阈值才变成32 * 0.75 = 24。
• putVal里替换旧value时，oldValue直接用e.value读出来，返回给调用者，同时新value写入。这个过程不会改动modCount。
• 链表尾插后触发treeifyBin的条件写的是binCount >= TREEIFY_THRESHOLD - 1，因为binCount从0开始，实际对应链表长度8。
• resize()不仅扩容，还承担初始化任务，所以putVal第一行判断table == null时就会调用它。
• 红黑树节点TreeNode是普通Node的子类，所以桶首节点是TreeNode时，p instanceof TreeNode为true，可以直接走树插入。

我自己的体会是，HashMap的源码设计紧凑到了“少一行不行、多一行浪费”的程度。读懂putVal，你就打通了哈希设计、冲突处理、扩容策略和扩展点设计这四块知识的任督二脉。建议读的时候不要光看，把每个分支的触发条件用笔写下来，再对照自己的Demo观察一遍，这个过程比刷十道面试题都值。