Vue3 Diff 算法与最长递增子序列详解
从源码视角理解 Vue3 Diff 算法、双端比较以及最长递增子序列优化。

一、先说结论:Diff 算法解决什么问题?
Vue 更新页面时,并不会每次都把真实 DOM 全部删除再重新创建,而是先比较新旧两棵虚拟 DOM:
旧 Virtual DOM
↓
Diff
↓
新 Virtual DOM
↓
找出真正发生变化的部分
↓
只更新必要的真实 DOM
所以 Diff 算法的核心目的就是:
尽可能复用已有 DOM,减少真实 DOM 的创建、删除和移动。
Vue3 中比较关键的是 patchKeyedChildren,也就是处理带 key 的一组子节点。
二、Vue3 Diff 整体流程
假设旧节点:
A B C D E
新节点:
A B D C E
Vue3 不会一上来就暴力比较全部节点,而是大致分成 5 步。
1. 从头开始比较
旧:A B C D E
新:A B D C E
先比较:
A === A ✅
B === B ✅
C !== D ❌
前面的 A、B 可以直接复用。
2. 从尾部开始比较
然后从后往前:
E === E ✅
D !== C ❌
于是 E 也确定不需要动。
最后真正需要处理的只剩:
旧:C D
新:D C
所以 Vue3 会尽量先处理两边完全相同的节点,把复杂问题缩小。
注意:这里通常说“头尾比较”,但 Vue3 并不是 Vue2 那种经典的四指针双端 Diff,而是从头同步 + 从尾同步。
三、如果新节点更多
例如:
旧:A B
新:A B C D
前面的 A、B 比较完成之后,旧节点已经全部处理完。
说明:
C D
都是新增节点。
直接执行挂载即可。
四、如果旧节点更多
例如:
旧:A B C D
新:A B
前面的 A、B 相同。
但是旧节点还剩:
C D
说明这些节点已经不存在了。
直接卸载:
remove C
remove D
五、真正困难的情况:节点乱序
例如:
旧:
A B C D E F G
新:
A B E C D H F G
先进行头尾比较。
头部:
A A ✅
B B ✅
尾部:
G G ✅
F F ✅
最后复杂区域变成:
旧:C D E
新:E C D H
这时候 Vue 就需要解决三个问题:
- 哪些节点还能复用?
- 哪些节点需要新增或删除?
- 哪些节点需要移动?
六、key 为什么非常重要?
Vue 会先给新的节点建立一个 Map:
// key -> 新节点位置
{
E: 0,
C: 1,
D: 2,
H: 3
}
然后遍历旧节点:
旧:C D E
拿着旧节点的 key 去 Map 中查。
例如:
C → 找到了 → 可以复用
D → 找到了 → 可以复用
E → 找到了 → 可以复用
如果旧节点:
X
在新节点里找不到:
X → undefined
说明:
X 已经被删除。
所以会执行卸载。
这也是为什么写 v-for 时要给稳定的 key:
<div
v-for="item in list"
:key="item.id"
>
{{ item.name }}
</div>
最好不要随便使用数组下标:
:key="index"
因为列表发生插入、删除、排序时,index 对应的数据可能发生变化,Vue 就无法准确判断:
这个节点到底是原来的节点,还是一个新的节点?
七、最长递增子序列 LIS 是干嘛的?
这部分是 Vue3 Diff 最容易问到的地方。
假设经过比较后,Vue 得到一组节点位置关系:
[2, 3, 1, 5, 6]
其中一个最长递增子序列可能是:
2 3 5 6
只有:
1
破坏了原来的递增顺序。
这意味着:
2 3 5 6
对应的节点原本相对顺序就是正确的。
所以:
这些节点不用移动,只移动不在最长递增子序列里的节点。
于是原本可能需要移动很多 DOM:
移动 A
移动 B
移动 C
移动 D
经过 LIS 优化以后可能只需要:
移动 C
这就是最长递增子序列在 Vue3 中最大的作用:
找出可以保持不动的最大节点集合,从而减少真实 DOM 移动。
八、为什么一定要减少 DOM 移动?
因为 JavaScript 里面修改一个数组很便宜:
arr.splice(...)
但操作真实 DOM 相对昂贵:
parent.insertBefore(...)
可能会涉及:
DOM 修改
↓
样式重新计算
↓
Layout
↓
Paint
所以 Vue 会尽可能:
多计算一点
换
少操作真实 DOM
这是虚拟 DOM 优化很重要的思想。
九、Vue3 Diff 可以记成这个流程
我自己记成:
1. 头部比较
2. 尾部比较
3. 新节点多了 → 挂载
4. 旧节点多了 → 删除
5. 中间乱序:
建立 key Map
↓
找节点复用关系
↓
判断是否发生移动
↓
LIS 找到不需要移动的节点
↓
只移动剩余节点
一句口诀:
头头比,尾尾比,多的增,少的删,中间乱序靠 key,移动优化靠 LIS。
十、面试标准回答
面试官如果问:
讲一下 Vue3 Diff 算法。
可以这样回答:
Vue3 更新组件时会对新旧 Virtual DOM 进行 Diff,对于带 key 的子节点主要通过 patchKeyedChildren 处理。
首先 Vue 会进行从头同步和从尾同步,快速复用两端相同的节点。
如果比较之后旧节点已经遍历完,但是新节点还有剩余,就说明剩余节点需要新增;反过来,如果新节点遍历完而旧节点还有剩余,就删除这些旧节点。
如果新旧节点中间都还有剩余,就进入乱序比较阶段。
Vue 会根据新节点的 key 建立 keyToNewIndexMap,然后遍历旧节点,通过 key 找到节点在新列表中的位置。找不到的旧节点会被卸载,找到的节点继续执行 patch。
同时 Vue 会生成 newIndexToOldIndexMap,记录新旧节点之间的位置映射,并判断节点是否发生移动。
如果发生移动,Vue3 会对这个数组求最长递增子序列 LIS。最长递增子序列对应的节点说明相对顺序本来就是正确的,因此这些节点不需要移动,只移动不在 LIS 中的节点,从而减少真实 DOM 操作。
所以 Vue3 Diff 的核心思想就是:
最大程度复用节点,并通过 key 和最长递增子序列减少 DOM 的新增、删除和移动。
十一、面试官常见追问
1. 为什么不能直接用 index 当 key?
因为数组发生插入、删除或者排序以后:
index 不变
数据却变了
Vue 可能错误地复用 DOM。
例如:
原来:
0 → 张三
1 → 李四
2 → 王五
在最前面插入赵六:
0 → 赵六
1 → 张三
2 → 李四
3 → 王五
所有 index 都发生了对应关系变化。
如果使用:
:key="item.id"
Vue 就能通过唯一 id 判断:
张三还是张三
李四还是李四
王五还是王五
因此列表需要增删、排序时,应该使用稳定唯一的 id。
2. LIS 本身是为了排序吗?
不是。
Vue 并不是为了把数组排好序。
LIS 的作用是:
找出哪些旧节点在新列表中的相对顺序没有发生变化。
这些节点可以留在原位。
剩下的节点再移动。
3. Vue3 为什么比 Vue2 Diff 更好?
Vue2 的核心是经典的双端比较:
旧头 ↔ 新头
旧尾 ↔ 新尾
旧头 ↔ 新尾
旧尾 ↔ 新头
Vue3 的核心思路变成:
头部同步
+
尾部同步
+
key Map
+
最长递增子序列
对于复杂列表乱序的情况,可以更准确地找到:
最少需要移动哪些节点。
除此之外,Vue3 编译阶段还有:
PatchFlag
Block Tree
静态提升
等优化。
所以 Vue3 的性能优化并不只是 Diff 算法本身,而是:
编译时优化 + 运行时 Diff 优化一起完成。
十二、最后总结
Vue3 Diff 不需要死背源码,真正需要理解的是三个核心思想:
1. 能不比较就不比较
头部相同 → 跳过
尾部相同 → 跳过
2. 能复用就复用
通过:
key
快速判断节点身份。
3. 能不移动就不移动
通过:
最长递增子序列 LIS
找到已经处于正确相对顺序的节点。
最终目的只有一个:
用尽可能少的真实 DOM 操作完成页面更新。
面试时如果能把:
头尾同步
→ keyToNewIndexMap
→ newIndexToOldIndexMap
→ 判断 moved
→ LIS
→ 最小化 DOM 移动
这条链路讲清楚,Vue3 Diff 这一题基本就已经达到比较完整的回答水平了。