Vue 3 学习体系

主题

D11 · Diff 算法深入 ​

对应主课： L33 Virtual DOM 实现基线： Vue 3.5.43；React 对照为 19.3.0 最后核对： 2026-09-23

1. 为什么不全量替换 ​

把新 HTML 整体赋给 container.innerHTML 会销毁原有子节点。输入框的未保存输入、元素上的监听器和焦点可能随之丢失；容器本身的所有状态却不一定重置，不能笼统称为“丢失所有状态”。

VNode patch 会按类型、key 和位置判断哪些节点可以复用，再更新其内容。它采用具体的协调策略，不求任意两棵树之间的全局最少编辑。复用也不意味着不更新：同一个商品节点的价格改变，仍需 patch 文本。

2. Vue 3 的五步 Diff ​

以下解释 patchKeyedChildren 的分支，假定同层列表的 key 稳定且唯一、对应节点的类型一致。步骤 3、4、5 是根据剩余区间选择的分支，不会在每次更新中全部执行。源码另有无 key 节点的匹配回退，不在这个例子中展开。Vue 3.5.43 renderer.ts

text
旧: [A, B, C, D, E, F, G]
新: [A, B, F, C, D, G]

Step 1: 从头比较 ​

text
旧: [A, B, C, D, E, F, G]
新: [A, B, F, C, D, G]
     ^  ^
A、B 的类型与 key 相同 → 分别 patch，再前进
遇到 C 与 F 不同，停止头部扫描

Step 2: 从尾比较 ​

text
旧尾: G
新尾: G
G 匹配 → patch，再向前
接下来 F 与 D 不同，停止尾部扫描

Step 3: 旧区间已空 → mount 剩余新节点 ​

text
旧剩余: []
新剩余: [X, Y]
→ 在正确的后继锚点前插入 X、Y

Step 4: 新区间已空 → unmount 剩余旧节点 ​

text
旧剩余: [E, F]
新剩余: []
→ 卸载 E、F

Step 5: 两边都有剩余 → key 映射与 LIS ​

本例进入这个分支：

text
旧未知区间: [C, D, E, F]（在完整旧列表中的索引为 2、3、4、5）
新未知区间: [F, C, D]   （在完整新列表中的索引为 2、3、4）

1. 新区间 key → 完整新列表索引
   F → 2，C → 3，D → 4

2. 依旧区间顺序扫描：匹配到的节点 patch，没有匹配的 E 卸载
   同时按“新区间顺序”填写对应旧索引 + 1：
   F → 6，C → 3，D → 4
   newIndexToOldIndexMap = [6, 3, 4]

3. 发现旧节点映射到的新位置不是递增的，需要移动
   对 [6, 3, 4] 求 LIS，得到数组位置 [1, 2]，对应 C、D

4. 从新区间末尾向前处理，以后继节点为锚点
   C、D 保留相对顺序；把 F 移到 C 前面

数组保存的是新位置对应的旧索引 + 1，不是“按旧顺序列出新索引”。值 0 留给新增节点，不能与旧列表索引 0 混淆。新增节点没有参与旧节点的相对次序，因此求 LIS 时跳过 0。只有检测到顺序变化时，源码才计算 LIS。

这里的“一次移动”针对复用的单元素节点。Fragment、组件子树和过渡都有自己的宿主操作细节，不能把一次 VNode move 恒等为一次浏览器 DOM API 调用。

3. 为什么需要 key ​

下面两种模板都合法；区别在于列表发生增删或排序时，身份如何对应：

vue
<!-- 无 key：主要按位置协调，适合无需保存项目身份的简单输出 -->
<div v-for="item in list">{{ item.name }}</div>

<!-- 稳定业务 key：身份跟随 item.id -->
<div v-for="item in list" :key="item.id">{{ item.name }}</div>

删除 A 时：

text
旧: [A, B, C]
新: [B, C]

无 key：
旧位置 0 的节点更新为 B
旧位置 1 的节点更新为 C
旧位置 2 的节点卸载
若节点含本地组件状态或未受控输入，状态可能仍跟随原位置

稳定 key：
A 卸载
B、C 匹配后继续 patch，复用各自节点与组件实例
它们的内容是否产生 DOM 写入，取决于数据有没有变

key 应在兄弟节点间唯一，并在同一数据项的生命周期内稳定。随机 key 会不断重建；index key 在排序、头部插入或删除时容易错配身份。静态列表或仅尾部追加且身份始终与索引一致的场景，不能一概判为错误。类型变了，即使 key 相同，也需要替换节点。React 的列表同样要求稳定身份。React 的 key 说明

4. 与 React diff 的区别 ​

对比范围Vue 3.5.43React 19.3.0
有 key 的同层数组先头尾同步，再映射未知区间；必要时计算 LIS前向匹配，必要时建立剩余旧 Fiber 映射；根据旧索引与 lastPlacedIndex 标记放置
移动策略LIS 保留可复用序列的相对次序此路径不使用 LIS，也不承诺全局最少移动
静态内容优化模板编译器的缓存、PatchFlag、Block 等memo、元素复用及启用 React Compiler 时的缓存等，不能概括为“全量比较”
身份判断类型、key、所在结构共同影响复用类型、key、在父树中的位置共同影响状态保留

React 这一列只概括数组协调路径，不是整个 Fiber 调度器；两种列表策略也不能直接推导应用谁更快。React 19.3.0 ReactChildFiber.js

5. 时间复杂度 ​

设同层列表规模为 n，未被头尾匹配消掉的新区间规模为 m。在 key 唯一、Map 查找按通常常数成本估算的条件下：

工作估算
头尾扫描、建 key 映射、扫描旧区间O(n)
未知区间需要移动时求 LISO(m log m)
同层 keyed 列表的协调工作O(n + m log m)，不含递归 patch 与宿主操作
L33 教学版逐个查找的列表算法最坏 O(n²)，用于说明复用流程

PatchFlag 与 Block 可以跳过部分不必比较的内容，但动态结构、子组件、实际 DOM 写入仍有各自成本。不能把整个 Vue 更新统一写成 O(动态节点数)，也不应拿无约束树编辑距离的复杂度当作每次框架更新的基线。

6. 动手实验：LIS 算法实现 ​

下面是独立教学实现，使用与上述映射一致的 0 哨兵，返回输入数组中的位置。它不包含 renderer，只展示二分维护最小尾值与前驱回溯；可保存为 lis-demo.mjs 后执行 node lis-demo.mjs。

javascript
// lis-demo.mjs
import assert from 'node:assert/strict'

function getSequence(values) {
  const tails = []
  const predecessor = new Array(values.length).fill(-1)

  for (let i = 0; i < values.length; i++) {
    if (values[i] === 0) continue
    let lo = 0
    let hi = tails.length
    while (lo < hi) {
      const mid = (lo + hi) >>> 1
      if (values[tails[mid]] < values[i]) lo = mid + 1
      else hi = mid
    }
    if (lo > 0) predecessor[i] = tails[lo - 1]
    tails[lo] = i
  }

  const result = new Array(tails.length)
  let cursor = tails.length ? tails[tails.length - 1] : -1
  for (let i = result.length - 1; i >= 0; i--) {
    result[i] = cursor
    cursor = predecessor[cursor]
  }
  return result
}

const newIndexToOldIndexMap = [6, 3, 4]
const positions = getSequence(newIndexToOldIndexMap)
console.log('旧索引 + 1：', newIndexToOldIndexMap)
console.log('LIS 数组位置：', positions) // [1, 2]
console.log('保留相对次序：', positions.map(i => ['F', 'C', 'D'][i])) // C、D

assert.deepEqual(positions, [1, 2])
assert.deepEqual(getSequence([]), [])
assert.deepEqual(getSequence([0, 0]), [])
assert.deepEqual(getSequence([0, 3, 4]), [1, 2])
assert.deepEqual(getSequence([1, 2, 3]), [0, 1, 2])
assert.deepEqual(getSequence([3, 2, 1]), [2])
assert.deepEqual(getSequence([2, 2]), [1]) // 严格递增，重复值不能同时入列

合法的旧索引映射不会重复非零值；最后一条只检查这个通用 LIS 函数的严格递增语义。LIS 不一定唯一，测试一般应核对长度、索引次序和值的递增关系，而不强制所有输入都得到某一条唯一答案。

7. 回到节点身份 ​

LIS 减少的是这类重排中的移动，不负责决定应用数据的身份。先给节点稳定的 key，再区分“匹配并 patch”“新增”“卸载”“移动”四种工作，才能正确解释 Diff 日志和 DOM 行为。