虚拟 DOM Diff 算法
在 Vue 中，当响应式数据变化时，框架需要高效地更新 DOM。Diff 算法的核心任务就是：对比新旧两组子节点，以最少的 DOM 操作完成更新。
本文将从简单 Diff 入手，逐步讲解 双端 Diff 和 快速 Diff 算法的原理。
1. 为什么需要 Diff 算法？
假设我们有一组旧子节点和一组新子节点：
旧: [A, B, C]
新: [C, A, B]
最暴力的方式是：卸载所有旧节点，挂载所有新节点。这需要 6 次 DOM 操作（3 次卸载 + 3 次挂载）。
但如果我们能识别出节点只是换了位置，只需要 移动 即可，DOM 操作可以大幅减少。这就是 Diff 算法的价值。
Diff 算法通过 key 属性来判断新旧节点是否是"同一个节点"。这就是为什么 v-for 必须绑定 key，且不推荐用 index 作为 key。
2. 简单 Diff 算法
简单 Diff 是最基础的思路：遍历新子节点，在旧子节点中查找可复用的节点。
2.1 核心思路
旧子节点: A(0) B(1) C(2)
新子节点: C A B
遍历新子节点，记录一个 lastIndex（上一次在旧列表中找到的最大索引）：
┌─────────────────────────────────────────────────────┐
│ 遍历新节点，在旧节点中查找 │
│ │
│ 新节点 C → 在旧列表中索引为 2, lastIndex=0 │
│ 2 >= 0 ✅ 不需要移动, lastIndex 更新为 2 │
│ │
│ 新节点 A → 在旧列表中索引为 0, lastIndex=2 │
│ 0 < 2 ⚠️ 需要移动！移到 C 后面 │
│ │
│ 新节点 B → 在旧列表中索引为 1, lastIndex=2 │
│ 1 < 2 ⚠️ 需要移动！移到 A 后面 │
└─────────────────────────────────────────────────────┘
判断规则：如果当前节点在旧列表中的索引 < lastIndex，说明它相对顺序发生了变化，需要移动。
2.2 局限性
简单 Diff 的时间复杂度为 O(n²)（双重循环查找），且在某些场景下移动次数不是最优的。例如：
旧: [A, B, C, D]
新: [D, A, B, C]
简单 Diff 会移动 A、B、C 三个节点，但实际上只需要把 D 移到最前面即可（1 次操作）。
3. 双端 Diff 算法（Vue 2）
双端 Diff 是 Vue 2 采用的算法，通过 四个指针 从两端向中间收缩比较，能更高效地处理节点移动。
3.1 四个指针
旧子节点: A B C D
↑ ↑
oldStart oldEnd
新子节点: D A B C
↑ ↑
newStart newEnd
3.2 四步比较
每一轮循环进行四次比较：
3.3 完整图解示例
以 旧: [A, B, C, D] → 新: [D, A, B, C] 为例：
第 1 轮：
旧: [A] B C [D]
↑ oldStart ↑ oldEnd
新: [D] A B [C]
↑ newStart ↑ newEnd
第 1 步: A vs D → ❌ 不同
第 2 步: D vs C → ❌ 不同
第 3 步: A vs C → ❌ 不同
第 4 步: D vs D → ✅ 命中！
第 4 步命中意味着：旧尾节点 = 新头节点，说明 D 需要从尾部移到头部。
操作: 将 D 移动到 oldStart(A) 前面
移动指针: oldEnd--, newStart++
DOM: D A B C
旧: [A] B [C] D(已处理)
↑ oldStart ↑ oldEnd
新: D(已处理) [A] B [C]
↑ newStart ↑ newEnd
第 2 轮：
第 1 步: A vs A → ✅ 命中！
头头命中，节点位置不变，无需移动 DOM，直接移动指针。
移动指针: oldStart++, newStart++
旧: A(已处理) [B] [C]
↑os ↑oe
新: [B] [C]
↑ns ↑ne
第 3 轮：
第 1 步: B vs B → ✅ 命中！
移动指针: oldStart++, newStart++
旧: [C] ← oldStart = oldEnd
↑os/oe
新: [C] ← newStart = newEnd
↑ns/ne
第 4 轮：
第 1 步: C vs C → ✅ 命中！
移动指针后: oldStart > oldEnd → 循环结束 ✅
结果：只进行了 1 次 DOM 移动（把 D 移到最前面），比简单 Diff 的 3 次移动高效得多。
3.4 非理想情况处理
当四步比较都未命中时，需要在旧子节点中搜索 newStart 对应的节点：
旧: [A] B C [D]
↑os ↑oe
新: [B] D A [C]
↑ns ↑ne
四步比较:
A vs B → ❌
D vs C → ❌
A vs C → ❌
D vs B → ❌
→ 在旧列表中查找 newStart(B)
→ 找到 B 在旧列表索引 1 的位置
→ 将 B 移动到 oldStart(A) 前面
→ 旧列表中 B 的位置标记为 undefined（已处理）
→ newStart++
旧: [A] undefined C [D]
↑os ↑oe
新: B(已处理) [D] A [C]
↑ns ↑ne
后续遍历遇到 undefined 时直接跳过。
3.5 新增与删除节点
新增节点：当循环结束后，如果 oldStart > oldEnd 但 newStart <= newEnd，说明新列表中有未处理的节点需要挂载。
循环结束后:
oldStart > oldEnd → 旧节点已全部处理
newStart <= newEnd → 新节点还有剩余
┌─────────────────────────────┐
│ newStart ──→ newEnd │
│ 这些节点是新增的，逐个挂载 │
└─────────────────────────────┘
删除节点：当循环结束后，如果 newStart > newEnd 但 oldStart <= oldEnd，说明旧列表中有多余节点需要卸载。
循环结束后:
newStart > newEnd → 新节点已全部处理
oldStart <= oldEnd → 旧节点还有剩余
┌─────────────────────────────┐
│ oldStart ──→ oldEnd │
│ 这些节点是多余的，逐个卸载 │
└─────────────────────────────┘
4. 快速 Diff 算法（Vue 3）
快速 Diff 是 Vue 3 采用的算法，借鉴了 ivi 和 inferno 框架的思路，结合了预处理优化和最长递增子序列（LIS），在大多数实际场景下性能最优。
4.1 算法总览
快速 Diff 分为三个阶段：
4.2 阶段 1：预处理（前置 / 后置节点）
从头部和尾部分别向中间扫描，跳过相同的节点。这一步利用了实际开发中常见的场景：列表头尾通常不变，变化集中在中间。
旧: A B C D E F G
新: A B E D C H F G
第 1 步: 从头部开始比较
A vs A → ✅ 相同，patch 更新，j++
B vs B → ✅ 相同，patch 更新，j++
C vs E → ❌ 不同，停止
j=2
↓
旧: a b [C D E F] G
新: a b [E D C H F] G
(小写 = 已处理)
第 2 步: 从尾部开始比较
G vs G → ✅ 相同，patch 更新，oldEnd--, newEnd--
F vs F → ✅ 相同，patch 更新，oldEnd--, newEnd--
E vs H → ❌ 不同，停止
j=2 oldEnd=4
↓ ↓
旧: a b [C D E] f g
↑ newEnd=5
新: a b [E D C H] f g
4.3 阶段 2：简单情况判断
预处理后，检查是否属于纯新增或纯删除的简单情况：
情况 A — 仅新增：j > oldEnd 且 j <= newEnd
旧: A B C
新: A D E B C
预处理后: j=1, oldEnd=0, newEnd=2
j(1) > oldEnd(0) ✅ 且 j(1) <= newEnd(2) ✅
→ 新节点 D、E 是新增的，直接挂载
┌───────────────────────────┐
│ j=1 ──→ newEnd=2 │
│ [D, E] 全部挂载 │
└───────────────────────────┘
情况 B — 仅删除：j > newEnd 且 j <= oldEnd
旧: A D E B C
新: A B C
预处理后: j=1, oldEnd=2, newEnd=0
j(1) > newEnd(0) ✅ 且 j(1) <= oldEnd(2) ✅
→ 旧节点 D、E 是多余的，直接卸载
┌───────────────────────────┐
│ j=1 ──→ oldEnd=2 │
│ [D, E] 全部卸载 │
└───────────────────────────┘
4.4 阶段 3：核心处理（最长递增子序列）
当既有新增、又有删除和移动时，进入核心处理阶段。
以 旧: [A, B, C, D, E, F, G] → 新: [A, B, E, D, C, H, F, G] 为例，预处理后剩余：
旧剩余: C(2) D(3) E(4) 索引: 2, 3, 4
新剩余: E D C H 索引: 2, 3, 4, 5
步骤 1：构建索引映射表
为新剩余节点建立 key → newIndex 的映射：
keyIndex = { E: 2, D: 3, C: 4, H: 5 }
步骤 2：构建 source 数组
source 数组记录新节点在旧列表中的对应索引（-1 表示新增）：
新剩余: E D C H
source: [ 4, 3, 2, -1 ]
↑ ↑ ↑ ↑
旧E=4 旧D=3 旧C=2 新增
遍历旧剩余节点填充 source:
旧 C(索引2) → keyIndex[C]=4 → source[4-2]=source[2]=2
旧 D(索引3) → keyIndex[D]=3 → source[3-2]=source[1]=3
旧 E(索引4) → keyIndex[E]=2 → source[2-2]=source[0]=4
旧节点不在 keyIndex 中 → 卸载该节点
同时检测是否需要移动：如果遍历过程中索引不是递增的，则 moved = true。
步骤 3：计算最长递增子序列（LIS）
对 source = [4, 3, 2, -1] 计算 LIS：
source: [4, 3, 2, -1]
递增子序列（按值）: 没有长度 > 1 的递增子序列
LIS 索引: [] (每个元素单独就是长度 1)
实际上取不含 -1 的部分:
有效 source: [4, 3, 2]
LIS: [4] 或 [3] 或 [2] → 长度为 1
LIS 索引: [0] (选择 source[0]=4，即新节点 E 不需要移动)
LIS 找出 source 中最长的递增子序列的索引。这些索引对应的节点在新旧列表中的相对顺序没有变化，不需要移动。其余节点则需要移动或新增。
步骤 4：倒序遍历，移动和挂载
从后向前遍历新剩余节点，利用 LIS 判断哪些节点需要移动：
LIS 索引: [0] → source 中索引 0 的节点(E)不需要移动
倒序遍历新剩余: H(i=3) C(i=2) D(i=1) E(i=0)
┌──────────────────────────────────────────────────┐
│ i=3, 节点 H: │
│ source[3] = -1 → 新增节点，挂载到 F 前面 │
│ │
│ i=2, 节点 C: │
│ i=2 不在 LIS[0] 中 → 需要移动，移到 H 前面 │
│ │
│ i=1, 节点 D: │
│ i=1 不在 LIS[0] 中 → 需要移动，移到 C 前面 │
│ │
│ i=0, 节点 E: │
│ i=0 在 LIS 中 ✅ → 不移动 │
└──────────────────────────────────────────────────┘
最终 DOM: A B E D C H F G ✅
4.5 再看一个典型示例
旧: A B C D E
新: A C D B E
预处理: A 和 E 相同，跳过
j=1, oldEnd=3, newEnd=3
旧剩余: B(1) C(2) D(3)
新剩余: C D B
keyIndex = { C:1, D:2, B:3 }
source 构建:
旧 B(1) → keyIndex[B]=3 → source[2] = 1
旧 C(2) → keyIndex[C]=1 → source[0] = 2
旧 D(3) → keyIndex[D]=2 → source[1] = 3
source = [2, 3, 1]
LIS of [2, 3, 1] → [2, 3] → 索引 [0, 1]
即 C(i=0) 和 D(i=1) 不需要移动
倒序遍历:
┌──────────────────────────────────────────┐
│ i=2, 节点 B: │
│ i=2 不在 LIS 中 → 移动到 E 前面 │
│ │
│ i=1, 节点 D: │
│ i=1 在 LIS 中 ✅ → 不移动 │
│ │
│ i=0, 节点 C: │
│ i=0 在 LIS 中 ✅ → 不移动 │
└──────────────────────────────────────────┘
结果: 只移动了 B 一个节点！ DOM: A C D B E ✅
5. 三种算法对比
| 特性 | 简单 Diff | 双端 Diff (Vue 2) | 快速 Diff (Vue 3) |
|---|---|---|---|
| 比较方式 | 单向遍历 | 四指针双端收缩 | 预处理 + LIS |
| 时间复杂度 | O(n²) | O(n) ~ O(n²) | O(n log n) |
| 移动策略 | 逐个判断移动 | 双端匹配减少移动 | LIS 最小化移动次数 |
| 新增/删除 | 额外遍历处理 | 循环结束后处理 | 预处理阶段快速识别 |
| 适用场景 | 教学理解 | 通用场景 | 大列表、复杂变更 |
6. 总结
核心优化思路：
- 通过
key复用节点，避免不必要的创建/销毁 - 预处理头尾相同节点，缩小比较范围
- 利用 LIS 找出最多不需要移动的节点
- 只移动必须移动的节点，最小化 DOM 操作
- 始终为
v-for提供唯一且稳定的key（如id），不要用index - 避免在列表头部频繁插入元素（简单 Diff 和双端 Diff 对此效率较低）
- 尽量保持列表项组件的稳定结构，减少 patch 开销
7. 为什么不能用 index 作为 key？
核心原因：index 和元素没有绑定关系，当列表发生变化时，index 会重新分配，导致 Diff 算法错误地复用节点。
7.1 图解错误复用
假设有一个待办列表，现在删除第一项"买菜"：
删除前: 删除后（用 index 作 key）:
key=0: 买菜 key=0: 做饭 ← Diff 认为是"买菜"更新了文本
key=1: 做饭 key=1: 洗碗 ← Diff 认为是"做饭"更新了文本
key=2: 洗碗 key=2: ??? ← Diff 认为这个节点被删除了
Diff 通过 key 判断"同一个节点"。它看到 key=0 还在、key=1 还在、key=2 消失了，于是：
┌──────────────────────────────────────────────────────┐
│ 实际只需: 删除第 1 个节点（1 次 DOM 操作） │
│ │
│ index 导致: │
│ patch key=0 的文本: "买菜" → "做饭" （多余操作） │
│ patch key=1 的文本: "做饭" → "洗碗" （多余操作） │
│ 删除 key=2 节点 （删错目标） │
│ │
│ 共 3 次 DOM 操作，且删除目标错误 │
└──────────────────────────────────────────────────────┘
如果用唯一 id 作为 key：
删除前: 删除后（用 id 作 key）:
key="a": 买菜 key="b": 做饭 ← Diff 知道这是原来的"做饭"
key="b": 做饭 key="c": 洗碗 ← Diff 知道这是原来的"洗碗"
key="c": 洗碗
→ Diff 发现 key="a" 消失了，直接删除，其余节点不动（1 次操作）✅
7.2 状态错乱问题（最严重）
如果列表项包含组件内部状态（input 输入值、checkbox 选中状态等），这些状态会跟着 key 走，而不是跟着数据走：
<div v-for="(item, index) in list" :key="index">
<span>{{ item.name }}</span>
<input v-model="item.note" />
</div>
场景: 用户在"买菜"的 input 中输入了"去超市"，然后删除"买菜"
┌─────────────────────────────────────────────────┐
│ 删除前: │
│ key=0: 买菜 [input: "去超市"] │
│ key=1: 做饭 [input: ""] │
│ │
│ 删除"买菜"后: │
│ key=0: 做饭 [input: "去超市"] ← 状态错乱！ │
│ │
│ input 的值"去超市"留在了 key=0 上 │
│ 但 key=0 现在对应的是"做饭" │
└─────────────────────────────────────────────────┘
7.3 什么时候 index 不会出问题？
只有同时满足以下条件时，index 才"碰巧"没问题：
- 列表是纯展示的（没有组件内部状态）
- 列表不会重新排序、不会在中间插入/删除
但这种场景很少，且需求随时可能变化，所以始终用唯一稳定的标识（如数据库 id）作为 key。