为什么需要 Diff 算法
上一节在处理新旧子节点都是数组的场景时，采用了"全卸载再全挂载"的粗暴策略。假设旧节点有 3 个子元素，新节点也有 3 个相同类型的子元素——仅仅是因为文本内容不同，就需要执行 3 次删除 + 3 次创建 = 6 次 DOM 操作。
但如果只更新 textContent 属性，只需 3 次属性修改。性能提升了一倍。
简单的数组更新策略
先从最简单的场景入手：新旧节点都是数组，但节点顺序不变。
function patchChildren(n1: VNode, n2: VNode, container: HTMLElement) {
const oldChildren = n1.children as VNode[]
const newChildren = n2.children as VNode[]
if (Array.isArray(oldChildren) && Array.isArray(newChildren)) {
// 新旧都是数组 → Diff 算法
const oldLen = oldChildren.length
const newLen = newChildren.length
const commonLen = Math.min(oldLen, newLen)
// 1. 更新公共长度的节点
for (let i = 0; i < commonLen; i++) {
patch(oldChildren[i], newChildren[i], container)
}
// 2. 新节点更多 → 创建多余的新节点
if (newLen > oldLen) {
for (let i = commonLen; i < newLen; i++) {
patch(null, newChildren[i], container)
}
}
// 3. 旧节点更多 → 删除多余的旧节点
else if (oldLen > newLen) {
for (let i = commonLen; i < oldLen; i++) {
unmount(oldChildren[i])
}
}
}
}
typescript
这段逻辑覆盖了三种情况：
| 场景 | 操作 |
|---|---|
| 新旧长度相同 | 只更新对应位置 |
| 新数组更长 | 更新公共部分 + 挂载新增部分 |
| 旧数组更长 | 更新公共部分 + 卸载多余部分 |
顺序变化带来的问题
上面的策略看起来没问题，但考虑这个场景：
旧节点: [P-1, DIV-2, SPAN-3]
新节点: [SPAN-3, P-1, DIV-2] // 只是顺序变了
text
按位置逐一更新，会变成：
- 位置 0：删除 P-1，创建 SPAN-3
- 位置 1：删除 DIV-2，创建 P-1
- 位置 2：删除 SPAN-3，创建 DIV-2
共 3 次删除 + 3 次创建 = 6 次 DOM 操作。但实际上这些节点只是位置变化了，理想情况应该只做 2 次移动操作。
这就是 Diff 算法要解决的核心问题：如何识别新旧节点之间的对应关系，尽可能复用已有 DOM，减少创建和删除操作。
key 属性：节点身份标识
Vue 引入了 key 属性来标识节点的身份。key 的作用是让 Diff 算法能够准确判断新旧节点中哪些是"同一个节点"：
// 旧节点
const oldVNodes = [
{ type: 'p', key: '1', children: 'hello' },
{ type: 'div', key: '2', children: 'world' },
{ type: 'span', key: '3', children: 'vue' },
]
// 新节点（顺序变了，但 key 不变）
const newVNodes = [
{ type: 'span', key: '3', children: 'vue' },
{ type: 'p', key: '1', children: 'hello' },
{ type: 'div', key: '2', children: 'world' },
]
typescript
有了 key，Diff 算法就可以：
- 通过 key 匹配新旧节点，而不是仅靠位置索引
- 识别出哪些节点是新增的、哪些被删除了、哪些只是移动了位置
- 对可复用的节点调用
patch更新属性，而不是销毁重建
Diff 算法要解决的三个核心问题
| 问题 | 说明 |
|---|---|
| 如何复用 | 通过 key 属性匹配新旧节点，找到可复用的 DOM |
| 如何移动 | 识别位置变化的节点，通过 insertBefore 移动真实 DOM |
| 如何增删 | 处理新增节点（挂载）和被移除的节点（卸载） |
Vue3 的 Diff 算法演进
Vue3 的 Diff 算法经历了多次优化，相比 Vue2 的双端对比有了显著改进：
| 版本 | 算法 | 时间复杂度 |
|---|---|---|
| Vue2 | 双端 Diff | O(n) |
| Vue3 | 快速 Diff（借鉴 inferno） | O(n)，平均更优 |
Vue3 的快速 Diff 算法核心步骤：
- 从头同步：从前往后对比，遇到不同 key 就停止
- 从尾同步：从后往前对比，遇到不同 key 就停止
- 处理中间部分：如果有剩余节点，构建 key-index 映射表
- 最长递增子序列：找到不需要移动的节点序列，只移动剩余节点
下一节将从简单 Diff 算法开始，逐步理解节点移动、新增和删除的实现逻辑。
↑