09.diff 算法

约 1690 字大约 6 分钟

2026-03-01

面试题

简要回答：Vue2 采用双端 diff，Vue3 采用快速 diff。快速 diff 通过最长递增子序列减少无效移动，最小化 DOM 操作。

diff 概念与特点

diff 算法用于比较两棵虚拟 DOM 树，找到差异并最小程度地更新真实 DOM。

为什么需要 diff？响应式不是已经能侦测变化了吗？

响应式能定位到组件需要重新渲染。组件重渲染会生成新的 VNode 树，但无法知道新树与旧树具体哪些节点不同，需依靠 diff 找出差异。

特点	说明
分层对比	逐层对比，避免全树对比
同层对比	假设节点同层级，不跨层比较

根节点比较：比较标签类型、key、input 的 type
- 相同：复用 DOM，更新属性，进入子节点对比
- 不同：卸载旧节点及子节点，根据新 VNode 递归创建 DOM
子节点对比：同层、深度优先、双端对比

新旧列表各有头、尾两个指针：

遍历结束（oldStart > oldEnd 或 newStart > newEnd）：

头头→尾尾→旧头新尾→新头旧尾→暴力对比→新头旧尾→暴力新建→删除旧剩余

双端 diff 可能产生多余的移动操作。如新旧列表为 [a,b,c,d] vs [e,b,c,d,a]：b、c、d 顺序一致，只需把 a 移到 d 后即可，但双端会移动 b、c、d。

与双端相同：头头比对 → 尾尾比对 → 一方结束则删除剩余或创建剩余

与双端不同：头尾比对后新旧都有剩余时：

初始化 keyToNewIndexMap：遍历未处理新节点，建立 key → index

const keyToNewIndexMap = new Map()
for (let i = newStartIdx; i <= newEndIdx; i++) {
  keyToNewIndexMap.set(newChildren[i].key, i)
}

初始化 newIndexToOldIndexMap：长度 = 未处理新节点数，初始为 0（0 表示在旧列表中不存在）

const toBePatched = newEndIdx - newStartIdx + 1
const newIndexToOldIndexMap = new Array(toBePatched).fill(0)

更新 newIndexToOldIndexMap：遍历旧节点，找到在新节点中的位置，patch 更新并记录映射（旧索引 +1 存入，避免与 0 冲突）
为什么旧索引要 +1 存储？
初始值为 0 表示「不存在」。若旧索引恰为 0，直接存 0 无法区分「索引 0」与「不存在」。
```
if (newIndex >= maxNewIndexSoFar) {
  maxNewIndexSoFar = newIndex
} else {
  moved = true  // 需要移动
}
```
计算最长递增子序列 (LIS)：基于 newIndexToOldIndexMap，得到「不需要移动」的索引序列
```
const increasingNewIndexSequence = moved ? getSequence(newIndexToOldIndexMap) : []
```
LIS 返回的是下标，可与前面 +1 抵消，恢复旧节点下标。
移动与挂载：倒序遍历未处理新节点，判断挂载或移动
为什么倒序？后续节点位置已确定，倒序可避免锚点引用出错。
- newIndexToOldIndexMap[i] === 0 → 新建并插入锚点前
- i 不在 LIS 中且 moved → 移动节点到锚点前

结果：仅移动必要节点，DOM 操作最小化。

Vue3 的 diff 相较 Vue2 有什么变化？做了哪些改变？

参考答案：

Vue2 用双端 diff，Vue3 用快速 diff。两者都会先做头头、尾尾比对；一方结束后，旧有剩余则删除，新有剩余则创建。

双端 diff 问题：旧头新尾、新头旧尾、暴力对比的策略可能产生多余移动。如 b、c、d 顺序未变，仍会被移动。

快速 diff 改进：头尾比对后，对剩余节点建立 key→index 映射和 newIndexToOldIndexMap，用最长递增子序列找出不需移动的节点，只移动必要节点，实现最少 DOM 操作。

-EOF-