Vue Diff 算法：Vue2 vs Vue3
Vue2 双端比较与 Vue3 最长递增子序列算法对比
问题
Vue 在更新虚拟 DOM 时如何高效地比较新旧节点？Vue2 和 Vue3 的 Diff 算法有什么区别？
解答
Vue2 双端比较算法
Vue2 使用双端比较，同时从新旧节点列表的两端向中间比较：
// Vue2 双端比较简化实现
function patchChildren(oldChildren, newChildren, parent) {
let oldStartIdx = 0
let oldEndIdx = oldChildren.length - 1
let newStartIdx = 0
let newEndIdx = newChildren.length - 1
let oldStartVNode = oldChildren[oldStartIdx]
let oldEndVNode = oldChildren[oldEndIdx]
let newStartVNode = newChildren[newStartIdx]
let newEndVNode = newChildren[newEndIdx]
while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
if (!oldStartVNode) {
// 节点已被移动，跳过
oldStartVNode = oldChildren[++oldStartIdx]
} else if (!oldEndVNode) {
oldEndVNode = oldChildren[--oldEndIdx]
} else if (isSameVNode(oldStartVNode, newStartVNode)) {
// 情况1: 旧头 vs 新头
patch(oldStartVNode, newStartVNode)
oldStartVNode = oldChildren[++oldStartIdx]
newStartVNode = newChildren[++newStartIdx]
} else if (isSameVNode(oldEndVNode, newEndVNode)) {
// 情况2: 旧尾 vs 新尾
patch(oldEndVNode, newEndVNode)
oldEndVNode = oldChildren[--oldEndIdx]
newEndVNode = newChildren[--newEndIdx]
} else if (isSameVNode(oldStartVNode, newEndVNode)) {
// 情况3: 旧头 vs 新尾，需要移动节点
patch(oldStartVNode, newEndVNode)
parent.insertBefore(oldStartVNode.el, oldEndVNode.el.nextSibling)
oldStartVNode = oldChildren[++oldStartIdx]
newEndVNode = newChildren[--newEndIdx]
} else if (isSameVNode(oldEndVNode, newStartVNode)) {
// 情况4: 旧尾 vs 新头，需要移动节点
patch(oldEndVNode, newStartVNode)
parent.insertBefore(oldEndVNode.el, oldStartVNode.el)
oldEndVNode = oldChildren[--oldEndIdx]
newStartVNode = newChildren[++newStartIdx]
} else {
// 情况5: 四端都不匹配，在旧节点中查找
const idxInOld = oldChildren.findIndex(
(node, idx) =>
idx >= oldStartIdx &&
idx <= oldEndIdx &&
isSameVNode(node, newStartVNode)
)
if (idxInOld > 0) {
// 找到了，移动节点
const vnodeToMove = oldChildren[idxInOld]
patch(vnodeToMove, newStartVNode)
parent.insertBefore(vnodeToMove.el, oldStartVNode.el)
oldChildren[idxInOld] = undefined // 标记为已处理
} else {
// 没找到，创建新节点
const el = createElm(newStartVNode)
parent.insertBefore(el, oldStartVNode.el)
}
newStartVNode = newChildren[++newStartIdx]
}
}
// 处理剩余节点
if (oldStartIdx > oldEndIdx) {
// 旧节点遍历完，新节点有剩余，批量添加
const refElm = newChildren[newEndIdx + 1]?.el || null
for (let i = newStartIdx; i <= newEndIdx; i++) {
parent.insertBefore(createElm(newChildren[i]), refElm)
}
} else if (newStartIdx > newEndIdx) {
// 新节点遍历完，旧节点有剩余，批量删除
for (let i = oldStartIdx; i <= oldEndIdx; i++) {
if (oldChildren[i]) {
parent.removeChild(oldChildren[i].el)
}
}
}
}
function isSameVNode(a, b) {
return a.key === b.key && a.type === b.type
}Vue3 最长递增子序列优化
Vue3 在双端比较的基础上，对中间乱序部分使用最长递增子序列（LIS）来最小化 DOM 移动：
// Vue3 Diff 简化实现
function patchKeyedChildren(oldChildren, newChildren, parent) {
let i = 0
let e1 = oldChildren.length - 1
let e2 = newChildren.length - 1
// 1. 从头部开始同步
while (i <= e1 && i <= e2) {
if (isSameVNode(oldChildren[i], newChildren[i])) {
patch(oldChildren[i], newChildren[i])
i++
} else {
break
}
}
// 2. 从尾部开始同步
while (i <= e1 && i <= e2) {
if (isSameVNode(oldChildren[e1], newChildren[e2])) {
patch(oldChildren[e1], newChildren[e2])
e1--
e2--
} else {
break
}
}
// 3. 旧节点遍历完，挂载新节点
if (i > e1 && i <= e2) {
const anchor = newChildren[e2 + 1]?.el || null
while (i <= e2) {
parent.insertBefore(createElm(newChildren[i]), anchor)
i++
}
}
// 4. 新节点遍历完，卸载旧节点
else if (i > e2 && i <= e1) {
while (i <= e1) {
parent.removeChild(oldChildren[i].el)
i++
}
}
// 5. 中间乱序部分，使用 LIS 优化
else {
const s1 = i
const s2 = i
// 建立新节点 key -> index 映射
const keyToNewIndexMap = new Map()
for (let j = s2; j <= e2; j++) {
keyToNewIndexMap.set(newChildren[j].key, j)
}
// 记录新节点在旧节点中的位置
const toBePatched = e2 - s2 + 1
const newIndexToOldIndexMap = new Array(toBePatched).fill(0)
let moved = false
let maxNewIndexSoFar = 0
// 遍历旧节点，更新/删除
for (let j = s1; j <= e1; j++) {
const oldVNode = oldChildren[j]
const newIndex = keyToNewIndexMap.get(oldVNode.key)
if (newIndex === undefined) {
// 旧节点不在新列表中，删除
parent.removeChild(oldVNode.el)
} else {
// 记录位置映射（+1 是为了区分 0 和未匹配）
newIndexToOldIndexMap[newIndex - s2] = j + 1
// 判断是否需要移动
if (newIndex >= maxNewIndexSoFar) {
maxNewIndexSoFar = newIndex
} else {
moved = true
}
patch(oldVNode, newChildren[newIndex])
}
}
// 计算最长递增子序列，确定哪些节点不需要移动
const increasingNewIndexSequence = moved
? getSequence(newIndexToOldIndexMap)
: []
// 从后向前遍历，移动和挂载节点
let lastIndex = increasingNewIndexSequence.length - 1
for (let j = toBePatched - 1; j >= 0; j--) {
const nextIndex = s2 + j
const anchor = newChildren[nextIndex + 1]?.el || null
if (newIndexToOldIndexMap[j] === 0) {
// 新节点，挂载
parent.insertBefore(createElm(newChildren[nextIndex]), anchor)
} else if (moved) {
// 不在 LIS 中的节点需要移动
if (lastIndex < 0 || j !== increasingNewIndexSequence[lastIndex]) {
parent.insertBefore(newChildren[nextIndex].el, anchor)
} else {
lastIndex--
}
}
}
}
}
// 计算最长递增子序列的索引
function getSequence(arr) {
const p = arr.slice() // 前驱索引
const result = [0]
for (let i = 1; i < arr.length; i++) {
const current = arr[i]
if (current === 0) continue // 跳过新增节点
const lastIndex = result[result.length - 1]
if (arr[lastIndex] < current) {
// 当前值大于结果最后一个，直接追加
p[i] = lastIndex
result.push(i)
} else {
// 二分查找，找到第一个大于等于 current 的位置
let left = 0
let right = result.length - 1
while (left < right) {
const mid = (left + right) >> 1
if (arr[result[mid]] < current) {
left = mid + 1
} else {
right = mid
}
}
// 替换
if (current < arr[result[left]]) {
if (left > 0) {
p[i] = result[left - 1]
}
result[left] = i
}
}
}
// 回溯，得到正确的 LIS 索引序列
let len = result.length
let idx = result[len - 1]
while (len-- > 0) {
result[len] = idx
idx = p[idx]
}
return result
}算法对比示例
// 假设有以下变化：
// 旧: [A, B, C, D, E, F, G]
// 新: [A, B, F, C, D, E, H, G]
// Vue2 双端比较过程：
// 1. A-A 匹配 ✓
// 2. B-B 匹配 ✓
// 3. G-G 匹配 ✓
// 4. 进入乱序处理，逐个查找移动
// Vue3 处理过程：
// 1. 头部同步: A, B
// 2. 尾部同步: G
// 3. 中间乱序: [C, D, E, F] -> [F, C, D, E, H]
// 4. 计算 LIS: C, D, E 位置递增，不需要移动
// 5. 只移动 F，新增 H关键点
- Vue2 双端比较：同时从两端向中间比较，有 5 种匹配情况，最坏时间复杂度 O(n²)
- Vue3 预处理优化：先处理头尾相同的节点，减少需要 Diff 的范围
- 最长递增子序列：找出不需要移动的最长序列，其他节点才需要移动，时间复杂度 O(nlogn)
- key 的作用：通过 key 建立映射，快速定位节点，避免不必要的 DOM 操作
- Vue3 优势：在大量节点乱序时，DOM 操作次数更少，性能更好
目录