Vue 3 快速 Diff 算法深度解析
Vue 3 采用了被称为"快速 Diff"的新算法来更新 DOM，相较于 Vue 2 的双端 diff，它在性能和策略上都有明显改进。核心思路是通过预处理边界、利用 key 映射，以及计算最长递增子序列（LIS）来最小化 DOM 操作次数。
1. 算法整体流程
快速 Diff 的核心函数是 patchKeyedChildren，它处理新旧两个 VNode 数组之间的差异。流程分为预处理和核心处理两阶段。
function performDiff(oldChildren, newChildren, parentContainer) {
let startIdx = 0
let oldEndIdx = oldChildren.length - 1
let newEndIdx = newChildren.length - 1
// 阶段1: 从前向后匹配
while (startIdx <= oldEndIdx && startIdx <= newEndIdx) {
if (isSameNode(oldChildren[startIdx], newChildren[startIdx])) {
updateNode(oldChildren[startIdx], newChildren[startIdx], parentContainer)
startIdx++
} else {
break
}
}
// 阶段2: 从后向前匹配
while (startIdx <= oldEndIdx && startIdx <= newEndIdx) {
if (isSameNode(oldChildren[oldEndIdx], newChildren[newEndIdx])) {
updateNode(oldChildren[oldEndIdx], newChildren[newEndIdx], parentContainer)
oldEndIdx--
newEndIdx--
} else {
break
}
}
// 阶段3: 处理纯新增或纯删除场景
if (startIdx > oldEndIdx) {
// 新节点数组还有剩余，插入新增节点
for (let pos = startIdx; pos <= newEndIdx; pos++) {
mountNode(null, newChildren[pos], parentContainer,
newEndIdx + 1 < newChildren.length ? newChildren[newEndIdx + 1].el : null)
}
} else if (startIdx > newEndIdx) {
// 旧节点数组还有剩余，卸载多余节点
for (let pos = startIdx; pos <= oldEndIdx; pos++) {
unmountNode(oldChildren[pos])
}
} else {
// 阶段4: 处理乱序部分，进行核心 diff
handleUnorderedSection(oldChildren, newChildren, startIdx, oldEndIdx, newEndIdx, parentContainer)
}
}
2. 乱序节点的处理
当预处理无法覆盖所有节点时，剩余的中间部分需要更复杂的比较。这段代码展示了如何通过 key 映射和位置数组来计算最小移动。
function handleUnorderedSection(oldKids, newKids, startPos, oldEnd, newEnd, container) {
const oldStart = startPos
const newStart = startPos
// 构建新节点 key 到索引的映射
const keyToIndexTable = new Map()
for (let i = newStart; i <= newEnd; i++) {
keyToIndexTable.set(newKids[i].key, i)
}
const totalNew = newEnd - newStart + 1
// 记录新节点在旧节点中的位置索引（偏移量+1，0 表示新节点）
const indexMapping = new Array(totalNew).fill(0)
// 遍历旧节点，同步或卸载
for (let i = oldStart; i <= oldEnd; i++) {
const oldNode = oldKids[i]
let newIdx
if (oldNode.key != null) {
newIdx = keyToIndexTable.get(oldNode.key)
} else {
// 无 key 时通过类型和内容匹配
for (let j = newStart; j <= newEnd; j++) {
if (areNodesEqual(oldNode, newKids[j])) {
newIdx = j
break
}
}
}
if (newIdx === undefined) {
unmountNode(oldNode)
} else {
indexMapping[newIdx - newStart] = i + 1
updateNode(oldNode, newKids[newIdx], container)
}
}
// 计算最长递增子序列，确定无需移动的节点
const lisIndices = findLongestIncreasingSubsequence(indexMapping)
let lisPointer = lisIndices.length - 1
// 从后向前遍历新节点，决定移动或挂载
for (let i = totalNew - 1; i >= 0; i--) {
const targetIdx = newStart + i
const targetNode = newKids[targetIdx]
const anchorNode = (targetIdx + 1 < newKids.length) ? newKids[targetIdx + 1].el : null
if (indexMapping[i] === 0) {
mountNode(null, targetNode, container, anchorNode)
} else {
if (i !== lisIndices[lisPointer]) {
insertNode(targetNode.el, container, anchorNode)
} else {
lisPointer--
}
}
}
}
3. 最长递增子序列（LIS）的实现
LIS 算法是快速 Diff 的核心，它帮助找到一批不需要移动的节点，从而降低 DOM 操作量。以下是一种经典实现：
function findLongestIncreasingSubsequence(nums) {
const predecessors = nums.slice()
const resultIndices = [0]
let i, left, right, mid, currentLen
for (i = 1; i < nums.length; i++) {
if (nums[i] === 0) continue
const lastIdx = resultIndices[resultIndices.length - 1]
if (nums[lastIdx] < nums[i]) {
predecessors[i] = lastIdx
resultIndices.push(i)
continue
}
// 二分查找插入位置
left = 0
right = resultIndices.length - 1
while (left < right) {
mid = (left + right) >> 1
if (nums[resultIndices[mid]] < nums[i]) {
left = mid + 1
} else {
right = mid
}
}
if (nums[i] < nums[resultIndices[left]]) {
if (left > 0) {
predecessors[i] = resultIndices[left - 1]
}
resultIndices[left] = i
}
}
// 回溯构建最终序列
currentLen = resultIndices.length
let last = resultIndices[currentLen - 1]
while (currentLen-- > 0) {
resultIndices[currentLen] = last
last = predecessors[last]
}
return resultIndices
}
4. 编译时优化对 Diff 的影响
Vue 3 在编译阶段做了大量工作，显著减少了运行时的比较负担。
4.1 静态内容提升
// 编译后，静态 VNode 被提升到渲染函数外部
const staticDiv = createVNode('div', { class: 'banner' }, 'Welcome')
function render() {
return createVNode('div', null, [
staticDiv,
createVNode('span', null, dynamicText)
])
}
静态节点在后续渲染中直接复用，不会进入 diff 过程。
4.2 Patch Flags 标记
// 编译时根据模板内容生成 patchFlag
const patchedVNode = {
type: 'span',
children: 'Hello',
patchFlag: 1 // 只标记文本动态
}
// 常用 flag 值
// 1: 仅文本变化
// 2: 仅 class 变化
// 4: 仅 style 变化
// 8: 动态属性
// 16: 需要全量 diff
运行时根据 patchFlag 直接执行对应更新操作，跳过无关检查。
4.3 Block Tree（区块树）
function render() {
// openBlock + createBlock 将动态节点收集在一起
return (openBlock(), createBlock('div', null, [
createVNode('p', null, '静态1'),
createVNode('p', null, dynamicText, 1), // 仅此节点参与 diff
createVNode('p', null, '静态2')
]))
}
Block Tree 使得动态节点被"拍平"，Diff 时只需遍历动态部分，静态节点完全不参与。
5. 示例分析
5.1 基本边界对齐
// 旧: [A, B, C, D]
// 新: [A, B, E, D]
// 前同步: A, B 匹配
// 后同步: D 匹配
// 中间: C vs E → 执行替换
5.2 乱序重排
// 旧: [A, B, C, D, E, F]
// 新: [A, E, C, B, D, F]
// 前同步: A
// 后同步: F
// 中间待处理: [B, C, D, E] vs [E, C, B, D]
// keyToIndexTable: {E:1, C:2, B:3, D:4}
// indexMapping: [4, 2, 1, 3] (旧节点索引+1)
// LIS 结果: [1, 3] 对应 C 和 D → 不移动
// 移动操作: 仅 B 和 E 需要调整位置
6. 实际应用建议
const ItemList = {
setup() {
const data = ref([
{ id: 'a', text: 'Alpha' },
{ id: 'b', text: 'Beta' },
{ id: 'c', text: 'Gamma' }
])
function shuffle() {
// 触发 diff 的最佳实践：新数组保留 key
data.value = data.value.sort(() => Math.random() - 0.5)
}
return { data, shuffle }
},
render() {
return h('ul', null,
this.data.map(item =>
h('li', { key: item.id }, item.text)
)
)
}
}
使用 稳定且唯一的 key 是让快速 Diff 发挥最大效能的前提。如果不用 key 或使用索引作为 key，算法会退化到更慢的匹配路径。
7. 关键要点
- 预处理阶段：从上和下两个方向同步同类型节点，跳过公共前缀和后缀
- 映射表构建：利用 key 快速找到新节点在旧数组中的位置
- LIS 核心：通过最长递增子序列识别出不需要移动的节点顺序
- 编译辅助：静态提升、Patch Flags、Block Tree 大幅减少运行时工作量
- 实际性能：在列表增删或节点重排场景下，DOM 移动次数接近理论最小值
