Vue3.4中diff算法核心梳理

基于 Vue 3.4+（runtime-core）

一、组件更新链路

响应式数据变化 ↓ 触发 effect（scheduler） ↓ 组件 render 函数重新执行 ↓ 生成新的 VNode Tree ↓ patch(oldVNode, newVNode) ↓ 精确更新真实 DOM

虚拟 DOM 的职责：描述 UI 结构​diff 的职责：最小化 DOM 更新

二、Vue3 的虚拟 DOM 本质

Vue3 中的 VNode 是一个​高度优化的 JS 对象​：

interface VNode { type: string | Component props: Record<string, any> | null children: string | VNode[] | null key: any el: HTMLElement | null // 对应真实 DOM shapeFlag: number // 节点类型位运算标识 patchFlag: number // 告诉 diff：哪里可能变 dynamicProps: string[] | null // 动态 ptops 列表 }

三、diff 的目标

单个 DOM 之间的对比，一般只需要对比节点类型、属性、文本内容等，而最最重要的其实是他们子节点的对比过程，因此下面主要讲解子节点的对比。

diff 的输入：

oldChildren: VNode[] newChildren: VNode[]

diff 的目标只有三个：

1. 复用能复用的 DOM
2. 最少的 DOM 操作
3. 保证最终 DOM 顺序正确

diff 不关心“组件更新”，只关心“同一父节点下 children 的变化”

patchKeyedChildren( c1: VNode[], // oldChildren c2: VNode[], // newChildren container: Element )

前提条件：

• children 是数组
• 并且 ​有 key​（无 key 是另一套退化逻辑）

四、Vue3 diff 的完整阶段

Vue3 的 diff ​严格分 5 个阶段​，而且​顺序不能乱​：

1️⃣ 从头同步 2️⃣ 从尾同步 3️⃣ 新节点多 → 挂载 4️⃣ 旧节点多 → 卸载 5️⃣ 中间乱序 diff（重点）

一阶段：从头同步

let i = 0 while ( i <= e1 && i <= e2 && isSameVNodeType(c1[i], c2[i]) ) { patch(c1[i], c2[i]) i++ }

old: A B C D new: A B E D ↑

• A === A→ patch
• B === B→ patch
• C !== E→ 停

为什么要做这一步？

其实我们现实业务中“头部稳定”是最常见情况：

• 列表 append
• 局部更新

这是一个O(n) 的优化。

二阶段：从尾同步

while ( i <= e1 && i <= e2 && isSameVNodeType(c1[e1], c2[e2]) ) { patch(c1[e1], c2[e2]) e1-- e2-- }

old: A B C D new: A E C D ↑

• D === D
• C === C
• 停

尾部稳定在 prepend / insert 场景很常见

三阶段：只剩新节点

if (i > e1 && i <= e2)

说明：

• oldChildren 已处理完
• newChildren 还有剩余

old: A B new: A B C D ↑ ↑

while (i <= e2) { patch(null, c2[i], container, anchor) i++ }

纯新增，直接 mount，零 diff 成本

四阶段：只剩旧节点

if (i > e2 && i <= e1)

old: A B C new: A B ↑

while (i <= e1) { unmount(c1[i]) i++ }

到这里为止，90% 的列表更新已经解决了。

只有剩下“中间乱序”的情况，才进入真正的复杂 diff。

五阶段：中间乱序 diff

这里你要好好听了！！！有一步走神后面就听不懂了！！！

此时新旧元素 index 数组：

old: [i ... e1] new: [i ... e2]

例如：

old: A B C D E new: B A E C D

头和头比较，不同，停止；然后尾和尾比较，不同，停止；所以这个整体进入中间乱序 diff 的比较过程。

第 1 步：建立 newChildren 的 key → index 映射

const keyToNewIndexMap = new Map() for (let j = i; j <= e2; j++) { keyToNewIndexMap.set(c2[j].key, j) }

​目的：​O(1) 数组直接查找新节点位置，避免 O(n²)

newChildren: index: 0 1 2 3 4 node: B A E C D

构建 Map（node -> index）：

{ B → 0, A → 1, E → 2, C → 3, D → 4 }

第 2 步：遍历旧节点，尝试复用

const newIndexToOldIndexMap = new Array(toBePatched).fill(0)

遍历 oldChildren：

for (let j = i; j <= e1; j++) { const oldVNode = c1[j] const newIndex = keyToNewIndexMap.get(oldVNode.key) if (newIndex === undefined) { unmount(oldVNode) } else { newIndexToOldIndexMap[newIndex - i] = j + 1 patch(oldVNode, c2[newIndex]) } }

关键设计点，为什么存j + 1？

0 → 表示“新节点”，所以如果存在复用节点至少为1，否则有歧义 >0 → 表示旧节点索引 + 1

遍历：

old : A B C D E index: 0 1 2 3 4

构建新节点数组索引到旧节点数组索引的映射表：

newIndexToOldIndexMap = []

• 数组长度 = newChildren 中“乱序区间”的长度
• 下标 = newIndex（新节点的位置）
• 值 = oldIndex + 1

第 3 步：判断是否需要移动（moved 标记）

if (newIndex < maxNewIndexSoFar) { moved = true } else { maxNewIndexSoFar = newIndex }

如果 newIndex 出现逆序，说明顺序乱了。这是什么意思呢？看下面示例演示：

依次遍历旧节点：

遍历 old[0] = A

• 在 new 中 index = 1
• 记录：0 + 1 = 1（oldIndex+1）

newIndexToOldIndexMap:​[_, 1, _, _, _]

记录索引为 1， 对应这 newIndex（新节点的索引位置）

遍历 old[1] = B

• newIndex = 0
• 记录：1 + 1 = 2

[2, 1, _, _, _]

👉 **这里已经出现逆序（2>1）**→moved = true

遍历 old[2] = C

• newIndex = 3
• 记录：2 + 1 = 3

[2, 1, _, 3, _]

遍历 old[3] = D

• newIndex = 4
• 记录：3 + 1 = 4

[2, 1, _, 3, 4]

遍历 old[4] = E

• newIndex = 2
• 记录：4 + 1 = 5

[2, 1, 5, 3, 4]

最终结果：newIndexToOldIndexMap = [2, 1, 5, 3, 4]

含义：

如果你🫵看到这里可以完全看懂，那么恭喜你，第一个难点已经攻破。

第 4 步：计算最长递增子序列（LIS）

只有在：

if (moved) { const increasingNewIndexSequence = getSequence(newIndexToOldIndexMap) }

newIndexToOldIndexMap: [2, 1, 5, 3, 4] LIS = [1, 3, 4] // 对应的是 A -> C -> D

LIS 对应的节点：

• 相对顺序已经正确
• 不需要移动 DOM（A -> C -> D）

第 5 步：倒序遍历，执行 DOM 操作

for (let j = toBePatched - 1; j >= 0; j--) { const newIndex = j + i const newVNode = c2[newIndex] const anchor = nextIndex < c2.length ? c2[nextIndex].el : null if (newIndexToOldIndexMap[j] === 0) { patch(null, newVNode, container, anchor) } else if (moved) { if (!isInLIS(j)) { move(newVNode, container, anchor) } } }

为什么要 ​倒序​？保证 anchor 永远是稳定的 DOM。

倒序处理 newChildren：

D → C → E → A → B

1️⃣ 处理 D（在 LIS）

👉 不动

DOM 还是：

A B C D E

2️⃣ 处理 C（在 LIS）

👉 不动

3️⃣ 处理 E（❌ 不在 LIS）

👉 移动 E 到 C 前面

A B E C D

4️⃣ 处理 A（在 LIS）

👉 不动

5️⃣ 处理 B（❌ 不在 LIS）

👉 移动 B 到 A 前面

B A E C D

最终 DOM 结构达到正确。

LIS 节点就像一排站得顺序已经对的柱子，Vue3 只需要把站错位置的挪到正确的位置。

五、Vue3 diff 的完整决策树

children diff │ ├─ 头部同步 ├─ 尾部同步 ├─ 纯新增 ├─ 纯删除 └─ 中间乱序 ├─ key → index 映射 ├─ 旧节点复用 / 卸载 ├─ 判断是否需要移动 ├─ LIS └─ 倒序 mount / move

复杂度分析：

​Vue3 diff 的最坏复杂度：O(n log n)，​但大部分真实场景接近 O(n)。

为什么 Vue3 diff 比 Vue2 强？

1. 阶段化 diff（不是全量递归）
2. LIS 最小移动
3. 编译期 patchFlag 极大减少进入 diff 的节点数量
4. Block Tree 让 diff 只遍历“动态节点”

六、Vue3 为什么比 Vue2 diff 快？

1. 编译期 patchFlag

模板：

<div>{{ count }}</div>

编译后：

createElementVNode("div", null, count, 1 /* TEXT */)

patchFlag 告诉 diff：“只需要比对文本”

跳过 props / children / key

2. dynamicProps 精确比对

<div :id="id" :class="cls"></div>

dynamicProps = ["id", "class"]

不再遍历所有 props

3. 静态提升（hoistStatic）

const _hoisted_1 = /*#__PURE__*/ createElementVNode(...)

• 静态节点不参与 diff
• 直接复用

4. Block Tree（块级优化）

Vue3 会把动态节点收集成一个 block：

openBlock() createElementBlock(...)

diff 只遍历动态子节点。