前端小卒

Appearance

** 完整的 DOM Diff 流程是怎样的？（下）** ​

在上一节中，我们分析了 patchKeyedChildren （带 key 列表的 Diff）的前四个步骤。这四个步骤通过“双端同步”高效地处理了列表头部和尾部相同的节点，以及简单的添加和删除操作。

现在，我们分析最核心的步骤 5。当双端同步（步骤 1 和 2）完成后，如果新旧列表均有剩余，我们就必须处理中间的“未知序列”。

回顾我们的例子：

  • 旧列表: a b [c d e] f g
  • 新列表: a b [e d c h] f g

步骤 1 和 2 处理了相同的 a b 和 f g。现在，我们只剩下两个“jumbled”（混乱）的子列表：

  • 旧的中间序列: [c, d, e]
  • 新的中间序列: [e, d, c, h]

我们的任务是：用最小的 DOM 操作（移动、删除、添加），将 [c, d, e] 变为 [e, d, c, h]。 这就是 patchKeyedChildren 中 else 模块的全部使命。

** Diff 的核心基石：key 的真正作用** ​

在我们进入算法之前，我们必须先弄清楚 Vue 是如何识别“这就是同一个节点”的。答案就是 key。

Vue 的 isSameVNodeType 函数是整个 Diff 算法的判断基础：

typescript
// core/packages/runtime-core/src/vnode.ts
function isSameVNodeType(n1: VNode, n2: VNode): boolean {
  // 节点的类型必须相同 (比如都是 <div> 或都是 <ComponentA>)
  // 节点的 key 也必须相同
  return n1.type === n2.type && n1.key === n2.key
}

key 就像是 VNode 的“身份证”。如果没有 key，Vue 只能通过 type 来猜。如果 type 也一样，它就认为是同一个，这在列表渲染中会造成巨大的混乱。

2. 反面教材：没有 key 会怎样？(patchUnkeyedChildren) ​

为了理解 key 的重要性，我们先看看如果你不提供 key（或者 v-for 一个非对象/数组），Vue 会启用“简单模式”—— patchUnkeyedChildren。

它的策略非常简单粗暴，我称之为“按位置就地更新”：

  1. 取新旧列表的最短长度 commonLength。
  2. 循环 commonLength 次，无视 key，直接 patch(old[i], new[i])。它默认第 i 个位置的节点就是“同一个”。
  3. 如果新列表更长，就把多出来的挂载 (mount)。
  4. 如果旧列表更长，就把多出来的卸载 (unmount)。
typescript
// core/packages/runtime-core/src/renderer.ts
const patchUnkeyedChildren = (c1, c2, ...) => {
  const oldLength = c1.length
  const newLength = c2.length
  const commonLength = Math.min(oldLength, newLength)

  // 1. 就地 patch 公共部分
  for (i = 0; i < commonLength; i++) {
    patch(c1[i], c2[i], container, ...)
  }
  
  // 2. 卸载多余的
  if (oldLength > newLength) {
    unmountChildren(c1, ..., commonLength)
  } 
  // 3. 挂载新增的
  else {
    mountChildren(c2, ..., commonLength)
  }
}

这种策略的致命弱点是什么？ 如果你把列表 [A, B, C] 变成 [C, B, A]，它会天真地：

  • patch(A, C) （A 变成 C）
  • patch(B, B) （B 不变）
  • patch(C, A) （C 变成 A）

它无法识别“移动”，而是进行了两次代价高昂的“内容替换”。这就是为什么在 v-for 中必须使用 key。

深入“未知序列”：patchKeyedChildren 的核心 else 模块** ​

好了，回到我们带 key 的战场。我们正面对 [c, d, e] 和 [e, d, c, h]。算法将分四步走：

** 为新列表建立“身份证地图”** ​

算法的第一件事，是遍历新的中间序列 [e, d, c, h]，并创建一个 key 到 index（位置）的 Map。

typescript
// 5.1 为新列表构建 key:index 映射
const keyToNewIndexMap: Map<string | number | symbol, number> = new Map()
for (i = s2; i <= e2; i++) {
  const nextChild = c2[i]
  if (nextChild.key != null) {
    keyToNewIndexMap.set(nextChild.key, i) // 比如: {'e': 0, 'd': 1, 'c': 2, 'h': 3}
  }
}
  • 为什么这么做？ 这是一个性能优化。这为我们提供了一个 O(1) 的快速查找能力。稍后，当我们遍历旧列表时，我们可以立即知道某个旧节点是否还在新列表中，以及它在什么位置。

** 遍历旧列表，处理“删除”与“移动”** ​

接下来，算法遍历旧的中间序列 [c, d, e]，并拿着 keyToNewIndexMap 挨个“盘问”。

typescript
// 5.2 遍历旧列表
const toBePatched = e2 - s2 + 1 // 新序列的长度
let patched = 0 // 已 patch 的节点计数
let moved = false // 是否有节点移动
let maxNewIndexSoFar = 0 // 配合 LIS 算法使用

// 关键数组：用于 LIS 算法
const newIndexToOldIndexMap = new Array(toBePatched)
for (i = 0; i < toBePatched; i++) newIndexToOldIndexMap[i] = 0

for (i = s1; i <= e1; i++) {
  const prevChild = c1[i] // 当前旧节点 (c, d, e)

  // 1. 盘问：你在新列表里吗？
  let newIndex = keyToNewIndexMap.get(prevChild.key)

  if (newIndex === undefined) {
    // 1a. 不在新列表里 -> 卸载！
    unmount(prevChild, ...)
  } else {
    // 1b. 还在新列表里 -> 递归 patch
    patch(prevChild, c2[newIndex], container, ...)
    
    // 2. 关键记录：在 newIndexToOldIndexMap 中登记
    // 索引是新列表中的位置，值是旧列表中的位置+1
    newIndexToOldIndexMap[newIndex - s2] = i + 1

    // 3. 探测移动
    if (newIndex >= maxNewIndexSoFar) {
      maxNewIndexSoFar = newIndex
    } else {
      moved = true // 发生了“乱序”
    }
    
    patched++
  }
}

这一步是算法的核心，我们来拆解一下：

  1. 盘问 c：在 Map 中找到 c，它在新列表的索引是 2。patch(c_old, c_new)。
  2. 盘问 d：在 Map 中找到 d，它在新列表的索引是 1。patch(d_old, d_new)。
  3. 盘问 e：在 Map 中找到 e，它在新列表的索引是 0。patch(e_old, e_new)。

newIndexToOldIndexMap 这个数组是最关键的产物。它是一个只看新列表的数组，记录了新列表中的每个节点分别来自旧列表的哪个位置（0 代表是全新的）。

在我们的例子中，它会变成：[ (e)来自旧位置3, (d)来自旧位置2, (c)来自旧位置1, (h)来自旧位置0 ] （注：值为 i+1，0 代表新） 简化后就是：[3, 2, 1, 0]

** 找出“最长不动组” (最长递增子序列 LIS)** ​

我们现在有了一个神奇的数组：[3, 2, 1, 0]。 还有一个 moved = true 的标记（因为 d 的新索引 1 小于 c 的新索引 2）。

这个 moved 标记告诉我们，DOM 需要被移动。但是，我们不想移动所有节点，那太蠢了。我们想移动最少的节点。

如何移动最少？ 答案是：找出那些“相对顺序”没变的节点，让它们“保持不动”，只移动其他节点。

[3, 2, 1] 这个序列中，最长的“递增”子序列是什么？是 [3] 或 [2] 或 [1]。

  • （换个例子，如果是 [1, 5, 2, 3, 6]，最长递增子序列就是 [1, 2, 3, 6]。）

getSequence(newIndexToOldIndexMap) 这个函数就是用来干这个的。它使用一种高效的 O(n log n) 算法找出这个最长递增子序列 (LIS)。

typescript
// 5.3 移动和挂载
const increasingNewIndexSequence = moved
  ? getSequence(newIndexToOldIndexMap) // 我们的例子中，LIS 结果是 [0] (代表 'e')
  : EMPTY_ARR

这个 increasingNewIndexSequence 数组中包含的索引，就是那些不需要移动的“稳定节点”。

** 倒序遍历，执行“移动”与“挂载”** ​

我们拿到了“稳定组” LIS。最后一步是从后向前遍历新列表 [e, d, c, h]，并执行最终的 DOM 操作。

typescript
let j = increasingNewIndexSequence.length - 1 // LIS 数组的指针

// 倒序遍历新列表
for (i = toBePatched - 1; i >= 0; i--) {
  const nextIndex = s2 + i
  const nextChild = c2[nextIndex] // (h, c, d, e)
  
  // 1. 找到锚点
  const anchor = nextIndex + 1 < l2 ? c2[nextIndex + 1].el : parentAnchor

  // 2. 检查是否是全新节点
  if (newIndexToOldIndexMap[i] === 0) {
    // 例子中的 'h' 会在这里被挂载
    patch(null, nextChild, container, anchor)
  }
  // 3. 检查是否需要移动
  else if (moved) {
    // j < 0 (LIS 已用完) 或 当前索引不在 LIS 中
    if (j < 0 || i !== increasingNewIndexSequence[j]) {
      // 例子中的 'c' 和 'd' 会在这里被移动
      move(nextChild, container, anchor, MoveType.REORDER)
    } else {
      // 匹配 LIS，不动，j--
      // 例子中的 'e' 会在这里匹配上，不动
      j--
    }
  }
}
  • 为什么是倒序遍历？ 这是一个绝妙的技巧。因为我们是“插入”操作（insertBefore），我们需要一个锚点 (anchor)。倒序遍历时，我们先处理的节点（如 h）会成为后处理节点（如 c）的锚点。这保证了我们总有一个稳定的、已就位的锚点可供使用，极大地简化了逻辑。

至此，[c, d, e] 通过最少的操作（1 次挂载 h，2 次移动 c 和 d，e 不动）变成了 [e, d, c, h]。

** 性能对比：Vue 3 为什么比 Vue 2 更快？** ​

  • Vue 2 (双端 Diff)： Vue 2 也是双端比较。但在处理“未知序列”时，它会为旧列表创建 key:index 映射。然后遍历新列表，在旧列表中查找。这个过程虽然也是 O(n)，但在某些复杂 shuffle（洗牌）场景下，它需要移动所有不在正确位置的节点，DOM 操作可能不是最优的。

  • Vue 3 (LIS Diff)： Vue 3（借鉴自 inferno.js）的策略更进一步。它不只是“找到并移动”，它是**“找到最长不动组，只移动其他”。LIS 算法 O(n log n) 被证明是最小化 DOM 移动次数**的最优解。

    更重要的是，得益于编译时优化 (Patch Flags)，Vue 3 经常可以完全跳过这个复杂的 patchKeyedChildren 算法，直接进行靶向更新，这是 Vue 2 无法做到的。

总结 ​

Vue 3 的 DOM Diff 算法是一个编译时和运行时协同的系统。它通过“双端同步”快速处理简单情况，并保留了基于“最长递增子序列（LIS）”的算法来高效、智能地处理最复杂的列表重排序，从而以最小的 DOM 操作代价完成界面更新。

微信公众号二维码

Last updated: