Vue 3 的快速 diff 是怎样用最长递增子序列减少移动的？

简答

列表从 a b c d e f g 变成 a b e c d h f g，开头的 a b 和结尾的 f g 都没变，真正要处理的只有中间那一段。Vue 3 的 patchKeyedChildren 就是先把两头相同的部分处理掉，再集中处理中间。判断“相同”用的是 isSameVNodeType：类型相同并且 key 相同。

具体分五步。第一步从头往后比，相同就更新，不同就停。第二步从尾往前比，同样处理。第三步，如果旧的已经比完、新的还有剩，剩下的全部挂载。第四步，如果新的已经比完、旧的还有剩，剩下的全部卸载。前面都处理不完的，才进入第五步：乱序比较。

第五步先给中间段的新节点建一张“key → 新下标”的表，遍历旧节点去查：查不到的卸载，查到的更新，并记下“新位置对应的旧下标”。这个数组里，旧下标递增的那些节点，彼此的相对顺序没有变，不用移动。所以 Vue 用 getSequence 求出最长递增子序列，子序列里的节点不动，其余节点从后往前移动到位，下标表里为 0 的则是新增，直接挂载。

要注意两点。一是只有检测到节点顺序真的变了，才会去算最长递增子序列，否则直接跳过。二是这套比较只在没有编译信息、或子节点顺序可能变化时才需要，比如 v-for 渲染的带 key 的列表；模板编译器能确定顺序不会变的地方，运行时会直接跳过子节点顺序的比较。

先处理两头

源码注释给的例子很直观。从头比：

text

(a b) c
(a b) d e

a b 相同，更新后指针 i 走到 2。从尾比：

text

a (b c)
d e (b c)

b c 相同，两个尾指针 e1、e2 往前退。

两头比完，有三种可能。旧的比完了，新的还剩，比如 (a b) 变成 (a b) c，就把 c 挂载上。新的比完了，旧的还剩，比如 (a b) c 变成 (a b)，就把 c 卸载掉。两边都还剩，就是中间乱序的情况。

为什么先处理两头？因为实际的列表更新大多是在头部或尾部增删几项，这两步就能处理完，根本走不到后面复杂的部分。

中间乱序时怎么判断谁要移动

还是 a b [c d e] f g 变成 a b [e c d h] f g，中间段是旧的 c d e 和新的 e c d h。

Vue 先为新的中间段建 keyToNewIndexMap，再建一个长度等于新中间段的数组 newIndexToOldIndexMap，初始全是 0。然后遍历旧的中间段，用 key 去查新下标，查到就把“旧下标 + 1”填进对应位置。加 1 是因为 0 被用来表示“这个新节点没有对应的旧节点”。

这个例子填完是 [5, 3, 4, 0]：e 原来在下标 4，c 在 2，d 在 3，h 是新增的。

遍历的同时还记录 maxNewIndexSoFar。如果某个旧节点查到的新下标比之前见过的最大值小，说明顺序乱了，就把 moved 设为 true。只有 moved 为真，才会去算最长递增子序列。

[5, 3, 4, 0] 里，3, 4 是递增的，对应 c d。它们原来的相对顺序没有变，不用动。只需要把 e 移到前面，再把 h 挂载上去。

getSequence 怎么求最长递增子序列

下面是 renderer.ts 中 getSequence 的逻辑，加上一个按五步处理 key 数组的简化版 diff，用来看结果。简化版只处理 key，没有真正的 DOM 操作。

JavaScript

function getSequence(arr) {
  const p = arr.slice();
  const result = [0];
  let i, j, u, v, c;
  const len = arr.length;
  for (i = 0; i < len; i++) {
    const arrI = arr[i];
    if (arrI !== 0) {
      j = result[result.length - 1];
      if (arr[j] < arrI) {
        p[i] = j;
        result.push(i);
        continue;
      }
      u = 0;
      v = result.length - 1;
      while (u < v) {
        c = (u + v) >> 1;
        if (arr[result[c]] < arrI) {
          u = c + 1;
        } else {
          v = c;
        }
      }
      if (arrI < arr[result[u]]) {
        if (u > 0) p[i] = result[u - 1];
        result[u] = i;
      }
    }
  }
  u = result.length;
  v = result[u - 1];
  while (u-- > 0) {
    result[u] = v;
    v = p[v];
  }
  return result;
}

function diff(c1, c2) {
  const ops = [];
  let i = 0;
  let e1 = c1.length - 1;
  let e2 = c2.length - 1;
  while (i <= e1 && i <= e2 && c1[i] === c2[i]) i++;
  while (i <= e1 && i <= e2 && c1[e1] === c2[e2]) { e1--; e2--; }
  if (i > e1) {
    for (; i <= e2; i++) ops.push(`挂载${c2[i]}`);
  } else if (i > e2) {
    for (; i <= e1; i++) ops.push(`卸载${c1[i]}`);
  } else {
    const s = i;
    const keyToNewIndex = new Map();
    for (let k = s; k <= e2; k++) keyToNewIndex.set(c2[k], k);
    const toBePatched = e2 - s + 1;
    const newIndexToOldIndex = new Array(toBePatched).fill(0);
    let moved = false;
    let maxNewIndexSoFar = 0;
    for (let k = s; k <= e1; k++) {
      const newIndex = keyToNewIndex.get(c1[k]);
      if (newIndex === undefined) {
        ops.push(`卸载${c1[k]}`);
        continue;
      }
      newIndexToOldIndex[newIndex - s] = k + 1;
      if (newIndex >= maxNewIndexSoFar) maxNewIndexSoFar = newIndex;
      else moved = true;
    }
    const seq = moved ? getSequence(newIndexToOldIndex) : [];
    let j = seq.length - 1;
    for (let k = toBePatched - 1; k >= 0; k--) {
      const key = c2[s + k];
      if (newIndexToOldIndex[k] === 0) ops.push(`挂载${key}`);
      else if (moved) {
        if (j < 0 || k !== seq[j]) ops.push(`移动${key}`);
        else j--;
      }
    }
  }
  return ops.join(' ') || '无操作';
}

console.log(getSequence([5, 3, 4, 0])); // [ 1, 2 ]
console.log(diff(['a', 'b', 'c', 'd', 'e', 'f', 'g'], ['a', 'b', 'e', 'c', 'd', 'h', 'f', 'g'])); // 挂载h 移动e
console.log(diff(['A', 'B', 'C', 'D'], ['D', 'A', 'B', 'C'])); // 移动D
console.log(diff(['a', 'b'], ['a', 'b', 'c'])); // 挂载c
console.log(diff(['a', 'b', 'c'], ['c', 'b', 'a'])); // 移动b 移动c

getSequence 返回的是下标，不是值。[5, 3, 4, 0] 的结果 [1, 2] 指的是第 1 和第 2 个位置，也就是 c 和 d。值为 0 的位置是新增节点，算法会直接跳过。

算法本身是经典的“贪心 + 二分”。result 保存当前找到的递增序列的下标，新值比末尾大就接在后面；否则用二分找到第一个不小于它的位置替换掉，让序列末尾尽量小，后面才更容易接上。p 记录每个元素接在谁后面，最后从末尾倒着走一遍，还原出真正的序列。整体复杂度是 O(n log n)。

第三个例子是把最后的 D 挪到最前面，只移动了一次 D。同样的变化，React 只往右走的策略会移动 A、B、C 三个，见《React 的 diff 算法怎样处理单节点和多节点？key 起什么作用？和 Vue 有什么不同？》。

最后一个是整体反转，最长递增子序列只有一个元素，所以三个节点里有两个要移动。

为什么要从后往前移动

移动和挂载都要用 insertBefore 插到某个节点前面，这个参照节点叫锚点。Vue 用的锚点是新列表里当前节点的下一个节点的 DOM。

从后往前处理时，后面的节点已经放到正确位置了，拿它当锚点一定是对的。如果从前往后，后面的节点可能还没归位，锚点就不可靠。源码注释写的也是这个原因：倒着循环，才能用上一个处理好的节点做锚点。

和 Vue 2 的双端比较有什么不同

Vue 2 每轮尝试旧头对新头、旧尾对新尾、旧头对新尾、旧尾对新头四种配对，配不上再用 key 查表，遇到能复用的就当场移动。Vue 3 只从两端各同步一次，中间部分统一算出哪些节点不用动，再一次性移动其余节点，移动次数更少，详见《Vue 2 的 diff 算法是怎样比较子节点的？》。

还有一点更重要。Vue 3 的编译器会给节点打上 PatchFlags，并用 Block 收集动态节点，模板里结构固定的部分运行时根本不进入这套子节点比较，见《Vue 模板编译如何减少运行时更新工作？》。

常见追问

没写 key 的子节点会怎样？

patchKeyedChildren 在第五步遇到没有 key 的旧节点时，会在新节点里找一个同样没有 key、类型相同、还没被匹配的节点来复用，相当于按顺序就地复用。所以列表项有自己的状态时，应该写稳定且唯一的 key。key 重复时，开发环境会发出 Duplicate keys found during update 的警告。

“移动”是重新创建 DOM 吗？

不是。移动是把已有的 DOM 节点用 insertBefore 挪到新位置，节点本身和里面的状态都保留。只有新增的节点才会创建，找不到对应新节点的旧节点才会卸载。