主题
实现 Diff 算法
本节对标 Vue 3 源码
@vue/runtime-core中的renderer.ts—— patchKeyedChildren
Vue 3 Diff vs React Diff
| 维度 | Vue 3 | React |
|---|---|---|
| 策略 | 双端比较 + 最长递增子序列 | 单向遍历 |
| 移动判断 | 基于 LIS 最小化移动 | 基于 lastIndex |
| 时间复杂度 | O(n) + O(n log n) LIS | O(n) |
| 优化效果 | 对反转、首尾交换等场景更优 | 某些场景移动次数更多 |
Diff 的前提
Diff 算法处理的是新旧子节点都是数组的情况。核心目标：以最少的 DOM 操作，将旧子节点序列转换为新子节点序列。
可能的操作：
- 新增（Placement）
- 删除（Unmount）
- 移动（Move）
- 更新（Patch）
Vue 3 Diff 的五步流程
第一步：从头部开始同步
ts
// patchKeyedChildren 实现了 Vue 3 的核心 Diff 算法
// 通过五步流程高效比较新旧子节点数组，最小化 DOM 操作
function patchKeyedChildren(
c1: VNode[], // 旧子节点数组
c2: VNode[], // 新子节点数组
container: any, // 父容器 DOM 节点
) {
let i = 0 // 从头部开始同步的游标
const l2 = c2.length // 新子节点总长度
let e1 = c1.length - 1 // 旧子节点末尾索引（从尾部同步时使用）
let e2 = l2 - 1 // 新子节点末尾索引
// ===== 第 1 步：从头部开始同步 =====
// 从左向右遍历，遇到类型相同的节点就复用（patch），遇到不同就停止
while (i <= e1 && i <= e2) {
const n1 = c1[i]
const n2 = c2[i]
if (isSameVNodeType(n1, n2)) {
// type 和 key 都相同 → 可复用，递归更新差异
patch(n1, n2, container)
} else {
// 不同类型 → 停止头部同步，剩余部分交给后续步骤
break
}
i++
}例如：(A B) C → (A B) D E，A 和 B 可以直接复用，只需处理 C → D E。
第二步：从尾部开始同步
ts
// ===== 第 2 步：从尾部开始同步 =====
// 从右向左遍历，处理尾部相同的节点
while (i <= e1 && i <= e2) {
const n1 = c1[e1]
const n2 = c2[e2]
if (isSameVNodeType(n1, n2)) {
// 尾部节点类型相同 → 复用并更新
patch(n1, n2, container)
} else {
break
}
// 尾部指针向前移动
e1--
e2--
}例如：A (B C) → D E (B C)，B 和 C 从尾部匹配复用。
第三步：仅有新增节点
ts
// ===== 第 3 步：旧节点已遍历完，剩余新节点全部需要挂载 =====
// i > e1 说明旧节点处理完了；i <= e2 说明新节点中还有未处理的
if (i > e1) {
if (i <= e2) {
// 确定插入锚点：新节点之后的节点的 el，用于 insertBefore
const nextPos = e2 + 1
const anchor = nextPos < l2 ? c2[nextPos].el : null
// 逐个挂载新增的节点
while (i <= e2) {
patch(null, c2[i], container, anchor) // n1 为 null 表示新建
i++
}
}
}当 i > e1 且 i <= e2，说明旧节点已遍历完，剩余的新节点都是需要新增的。
例如：A B → A B C D（新增 C D）
第四步：仅有删除节点
ts
// ===== 第 4 步：新节点已遍历完，剩余旧节点全部需要删除 =====
// i > e2 说明新节点处理完了；i <= e1 说明旧节点中还有多余的
else if (i > e2) {
while (i <= e1) {
unmount(c1[i]) // 逐个卸载多余的旧节点
i++
}
}当 i > e2 且 i <= e1，说明新节点已遍历完，剩余的旧节点都需要删除。
例如：A B C D → A B（删除 C D）
第五步：乱序比较 —— 最长递增子序列
ts
// ===== 第 5 步：乱序比较 —— 处理中间无法通过首尾同步解决的部分 =====
else {
const s1 = i // 旧子节点乱序区间起点
const s2 = i // 新子节点乱序区间起点
// 5.1 为新子节点建立 key → index 映射表
// 后续通过 key 快速查找旧节点在新序列中的位置
const keyToNewIndexMap = new Map<any, number>()
for (let i = s2; i <= e2; i++) {
const nextChild = c2[i]
if (nextChild.key != null) {
keyToNewIndexMap.set(nextChild.key, i) // key → 新索引
}
}
// 5.2 遍历旧子节点，尝试通过 key 或类型匹配复用
let patched = 0 // 已匹配的节点计数
const toBePatched = e2 - s2 + 1 // 需要处理的新节点总数
let moved = false // 是否存在需要移动的节点
let maxNewIndexSoFar = 0 // 记录当前遍历到的最大新索引
// newIndexToOldIndexMap 用于记录新节点对应的旧索引（+1 偏移，0 表示新增）
// 例如 newIndexToOldIndexMap[i] = 3 表示新节点 i 对应旧数组的索引 2
const newIndexToOldIndexMap = new Array(toBePatched).fill(0)
for (let i = s1; i <= e1; i++) {
const prevChild = c1[i]
if (patched >= toBePatched) {
// 所有新节点都已匹配完毕，剩余旧节点都是多余的，直接删除
unmount(prevChild)
continue
}
let newIndex: number | undefined
if (prevChild.key != null) {
// 有 key → 通过 Map 快速查找（O(1)）
newIndex = keyToNewIndexMap.get(prevChild.key)
} else {
// 没有 key → 遍历新节点，按类型逐个匹配（O(n)，效率较低）
for (let j = s2; j <= e2; j++) {
if (
newIndexToOldIndexMap[j - s2] === 0 &&
isSameVNodeType(prevChild, c2[j])
) {
newIndex = j
break
}
}
}
if (newIndex === undefined) {
// 旧节点在新序列中找不到对应 → 该节点被删除
unmount(prevChild)
} else {
// 记录新位置对应的旧索引（+1 是为了区分索引 0 和"未匹配"的 0）
newIndexToOldIndexMap[newIndex - s2] = i + 1
// 判断是否需要移动：如果新索引不是递增的，说明存在顺序变化
if (newIndex >= maxNewIndexSoFar) {
maxNewIndexSoFar = newIndex // 更新最大索引
} else {
moved = true // 发现逆序，标记需要移动
}
// 递归更新匹配到的节点（属性和子节点可能变了）
patch(prevChild, c2[newIndex], container)
patched++
}
}
// 5.3 移动节点和挂载新增节点
// 如果存在移动，计算最长递增子序列（LIS），LIS 中的节点不需要移动
const increasingNewIndexSequence = moved
? getSequence(newIndexToOldIndexMap) // 返回 LIS 对应的索引数组
: []
let j = increasingNewIndexSequence.length - 1
// 从后向前遍历，确保每次插入时 anchor 节点已经就位
for (let i = toBePatched - 1; i >= 0; i--) {
const nextIndex = s2 + i // 当前新节点在 c2 中的实际索引
const nextChild = c2[nextIndex] // 当前新节点
// 插入锚点：当前节点之后的节点的 el，如果是最后一个则为 null（追加到末尾）
const anchor = nextIndex + 1 < l2 ? c2[nextIndex + 1].el : null
if (newIndexToOldIndexMap[i] === 0) {
// 值为 0 表示这是一个全新的节点，需要挂载
patch(null, nextChild, container, anchor)
} else if (moved) {
// 有节点需要移动的情况下，判断当前节点是否在 LIS 中
if (j < 0 || i !== increasingNewIndexSequence[j]) {
// 不在 LIS 中 → 需要移动到正确位置
insert(nextChild.el!, container, anchor)
} else {
// 在 LIS 中 → 位置正确，不需要移动，指针前移
j--
}
}
}
}
}最长递增子序列（LIS）
为什么需要 LIS？
给定旧序列在新序列中的位置映射 [5, 3, 4, 0]（0 表示新增），我们需要找出哪些节点不需要移动。
不需要移动的节点就是 newIndexToOldIndexMap 中的最长递增子序列。这些节点的相对顺序在新旧序列中保持一致。
newIndexToOldIndexMap = [5, 3, 4, 0]
LIS = [3, 4]（索引 [1, 2]）只有不在 LIS 中的节点才需要移动，这样可以最小化 DOM 移动操作。
getSequence 实现
ts
// getSequence 计算最长递增子序列（LIS）的索引数组
// 使用贪心 + 二分查找 + 前驱回溯，时间复杂度 O(n log n)
// 返回值是 LIS 元素在原数组中的索引，而非值本身
function getSequence(arr: number[]): number[] {
const p = arr.slice() // p[i] 保存 arr[i] 在 LIS 中的前驱索引，用于最终回溯
const result = [0] // result 存储当前 LIS 的索引，初始化为第一个元素
let i, j, u, v, c
const len = arr.length
for (i = 0; i < len; i++) {
const arrI = arr[i]
if (arrI !== 0) { // 跳过 0（0 表示新增节点，不参与 LIS 计算）
j = result[result.length - 1] // j 是当前 LIS 最后一个元素的索引
if (arr[j] < arrI) {
// 当前值比 LIS 末尾值大 → 直接追加到 LIS 末尾（递增序列延长）
p[i] = j // 记录前驱
result.push(i)
continue
}
// 当前值不比末尾大 → 用二分查找找到 LIS 中第一个 >= arrI 的位置并替换
// 这样可以让 LIS 末尾尽量小，为后续更长的递增序列创造机会
u = 0
v = result.length - 1
while (u < v) {
c = (u + v) >> 1 // 取中间位置（位运算右移 1 等价于除以 2 取整）
if (arr[result[c]] < arrI) {
u = c + 1 // 目标在右半区
} else {
v = c // 目标在左半区或就是 c
}
}
// u 现在指向第一个 >= arrI 的位置
if (arrI < arr[result[u]]) {
if (u > 0) {
p[i] = result[u - 1] // 记录前驱为被替换位置的前一个
}
result[u] = i // 替换为当前索引（贪心：保持 LIS 中间值尽量小）
}
}
}
// 回溯阶段：通过前驱数组 p 从 LIS 末尾向前追溯，还原正确的索引序列
// 因为上面的贪心替换可能导致 result 中的值不连续，需要回溯修正
u = result.length
v = result[u - 1] // 从 LIS 的最后一个元素开始
while (u-- > 0) {
result[u] = v // 填入正确的索引
v = p[v] // 跳转到前驱
}
return result // 返回 LIS 对应的索引数组
}使用二分查找 + 回溯，时间复杂度 O(n log n)。
图解示例
旧: A B C D E F G
新: A D B G F E C
第一步（头部同步）: A 匹配
第二步（尾部同步）: 无匹配
乱序区间:
旧: B C D E F G
新: D B G F E C
keyToNewIndexMap: { D:1, B:2, G:3, F:4, E:5, C:6 }
newIndexToOldIndexMap: [3, 1, 6, 5, 4, 2]
D B G F E C
LIS: [1, 6] → 索引 [1, 2]（B 和 G 不需要移动）
需要移动: D, F, E, C测试用例
ts
describe('diff', () => {
// 测试头部插入场景：在已有节点前面新增节点
it('should handle prepend', () => {
// 初始状态：A B
render(h('div', null, [
h('span', { key: 'a' }, 'A'),
h('span', { key: 'b' }, 'B'),
]), root)
// 更新为：C A B → C 是新增的，A B 通过 key 匹配复用
render(h('div', null, [
h('span', { key: 'c' }, 'C'),
h('span', { key: 'a' }, 'A'),
h('span', { key: 'b' }, 'B'),
]), root)
})
// 测试节点重排序场景：已有节点顺序发生变化
it('should handle reorder', () => {
// 初始状态：A B C
render(h('div', null, [
h('span', { key: 'a' }, 'A'),
h('span', { key: 'b' }, 'B'),
h('span', { key: 'c' }, 'C'),
]), root)
// 更新为：C A B → C 从末尾移到头部，A B 保持相对顺序不变
// Diff 算法通过 LIS 识别出 A B 不需要移动，只需移动 C
render(h('div', null, [
h('span', { key: 'c' }, 'C'),
h('span', { key: 'a' }, 'A'),
h('span', { key: 'b' }, 'B'),
]), root)
})
})本节小结
- 五步流程 — 头部同步 → 尾部同步 → 仅新增 → 仅删除 → 乱序 Diff
- 双端比较 — 处理常见的首尾添加/删除场景，O(n)
- 最长递增子序列 — 最小化 DOM 移动操作，O(n log n)
- key 的重要性 — 没有 key，只能按类型逐个匹配，无法识别移动
下一节实现自定义渲染器。