Vue

Vue3 Diff 算法与最长递增子序列详解

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

Vue
Vue3 Diff 算法与最长递增子序列详解文章封面

当前一、先说结论: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 就需要解决三个问题:

  1. 哪些节点还能复用?
  2. 哪些节点需要新增或删除?
  3. 哪些节点需要移动?

六、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 这一题基本就已经达到比较完整的回答水平了。