Vue 3 源码核心笔记：乱序 Diff (Unknown Sequence) 深度解析

1. 什么是“乱序 Diff”？
#

在 Vue 3 的 Diff 算法（patchKeyedChildren）中，Vue 会优先处理“头部同步”和“尾部同步”。当掐头去尾后，如果新旧列表都还有剩余节点，且顺序不一致，就会进入最复杂的 乱序 Diff (Unknown Sequence) 阶段。

场景示例：

旧列表 (Old): a b (c d e z) f g
新列表 (New): a b (e c d h) f g

去掉头部的 a b 和尾部的 f g，剩下的就是我们要处理的核心乱序区间：

Old 待处理: c d e z (索引: 2, 3, 4, 5)
New 待处理: e c d h (索引: 2, 3, 4, 5)

Vue 的目标是：复用能复用的，删除多余的，新增没有的，并用最少的步数移动 DOM。

2. 核心流程三部曲
#

乱序 Diff 的处理逻辑可以概括为三个核心步骤：

建立索引图 (Build Map)：为新节点建立查找表。
清理旧节点 (Clean Old)：遍历旧节点，进行打补丁 (Patch) 或删除 (Unmount)。
移动与挂载 (Move & Mount)：利用 LIS 算法，移动节点或挂载新节点。

乱序 Diff 流程图
#

flowchart TD
Start([开始乱序处理
Unknown Sequence]) --> Step1[步骤1: 建立索引图
Build keyToNewIndexMap]

    Step1 --> InitVars[初始化变量
patched=0, moved=false
maxNewIndexSoFar=0]
    InitVars --> Step2[步骤2: 遍历旧节点
oldStartIndex to oldEnd]

    Step2 --> CheckFull{patched 大于等于
toBePatched?}
    CheckFull -->|是
名额已满| UnmountB[Unmount
直接删除]
    CheckFull -->|否| FindInMap{在 Map 中
找到 Key?}

    FindInMap -->|未找到| UnmountA[Unmount
查无此人]
    FindInMap -->|找到| RecordMap[记录映射
newIndexToOldIndexMap]

    RecordMap --> CheckOrder{newIndex 大于等于
maxNewIndexSoFar?}
    CheckOrder -->|是
递增| UpdateMax[更新水位线
maxNewIndexSoFar = newIndex]
    CheckOrder -->|否
乱序| SetMoved[标记 moved = true]

    UpdateMax --> PatchNode[Patch 复用节点
patched++]
    SetMoved --> PatchNode

    PatchNode --> MoreOld{还有旧节点?}
    UnmountA --> MoreOld
    UnmountB --> MoreOld
    MoreOld -->|是| CheckFull
    MoreOld -->|否| Step3

    Step3[步骤3: 移动与挂载] --> CheckMoved{moved 等于 true?}
    CheckMoved -->|是| CalcLIS[计算 LIS
getSequence]
    CheckMoved -->|否| SkipLIS[跳过 LIS 计算
increasingNewIndexSequence = 空]

    CalcLIS --> ReverseLoop[倒序遍历新节点
toBePatched-1 to 0]
    SkipLIS --> ReverseLoop

    ReverseLoop --> CalcAnchor[计算锚点 Anchor
下一个节点的 el]
    CalcAnchor --> CheckValue{映射值
等于 0?}

    CheckValue -->|是
新节点| Mount[Mount
挂载新节点]
    CheckValue -->|否| CheckMovedAgain{需要移动?}

    CheckMovedAgain -->|moved=false| Skip[Skip
跳过不动]
    CheckMovedAgain -->|moved=true| InLIS{在 LIS 中?}

    InLIS -->|是| Skip
    InLIS -->|否| Move[Move
移动节点]

    Mount --> MoreNew{还有新节点?}
    Skip --> MoreNew
    Move --> MoreNew
    MoreNew -->|是| CalcAnchor
    MoreNew -->|否| End([结束])

    classDef startEnd stroke:#0ea5e9,stroke-width:3px
    classDef buildStep stroke:#8b5cf6,stroke-width:2px
    classDef cleanStep stroke:#f59e0b,stroke-width:2px
    classDef moveStep stroke:#06b6d4,stroke-width:2px
    classDef unmountNode stroke:#ef4444,stroke-width:2px
    classDef patchNode stroke:#10b981,stroke-width:2px
    classDef lisNode stroke:#8b5cf6,stroke-width:2px,stroke-dasharray:5 5

    class Start,End startEnd
    class Step1,InitVars,FindInMap buildStep
    class Step2,CheckFull,RecordMap,CheckOrder,UpdateMax,SetMoved cleanStep
    class Step3,CheckMoved,ReverseLoop,CalcAnchor,CheckValue,CheckMovedAgain,InLIS moveStep
    class UnmountA,UnmountB unmountNode
    class PatchNode,Mount,Move patchNode
    class CalcLIS,SkipLIS lisNode

第一步：建立新节点索引图 (KeyToNewIndexMap)
#

Vue 为了避免在遍历旧节点时使用双重循环（导致复杂度），首先会遍历一遍新节点列表，生成一个 Map。

目的：实现 O(1) 的快速查找。
输入：New: [e, c, d, h] (索引 2, 3, 4, 5)
输出结果 (Map)：

// key : newIndex
{ 'e': 2, 'c': 3, 'd': 4, 'h': 5 }

第二步：遍历旧节点 (核心：Patch 与 Unmount)
#

这是最繁忙的一步。Vue 遍历旧节点，拿着旧节点的 Key 去上面的 Map 里找。这里涉及多个核心逻辑的判断。

2.1 深度解析：`newIndexToOldIndexMap` 的秘密
#

Vue 创建了一个单纯的整数数组 newIndexToOldIndexMap，但它承载了新旧节点位置关系的全部信息。

它的“索引”和“值”到底代表什么？

数组定义：const newIndexToOldIndexMap = new Array(toBePatched) (初始化为 0)

数组的索引 (Index)：代表 新子节点 (New Children) 的相对位置。

Index 0：表示新列表乱序部分里的 第 1 个 节点。

数组的值 (Value)：代表该节点在 旧子节点 (Old Children) 列表中的 原始位置 + 1。

为什么要 +1？ 这是为了把 0 这个值空出来，专门用来标记 “这是一个全新节点”。

可视化填空演示：

Old 待处理: [c, d, e] (索引: 2, 3, 4)
New 待处理: [e, c, d, h] (索引: 2, 3, 4, 5)

数组索引 (i)	对应新节点	旧列表索引 (OldIdx)	填入的值 (OldIdx + 1)	含义解读
0	`e`	`4`	`5`	新列表第1个是 `e`，原旧列表第4位。
1	`c`	`2`	`3`	新列表第2个是 `c`，原旧列表第2位。
2	`d`	`3`	`4`	新列表第3个是 `d`，原旧列表第3位。
3	`h`	`undefined`	`0`	新列表第4个是 `h`，旧列表没有它。

最终数组状态： [5, 3, 4, 0]

2.2 什么时候执行 Unmount (删除)？
#

在遍历旧节点时，只有两种情况会触发 unmount：

情况 A：查无此人 (Lost Node)

逻辑：拿着旧节点的 Key 去 Map 里找，返回 undefined。
含义：新数据里没有这个节点了，说明用户把它删了。
操作：直接卸载。

情况 B：名额已满 (Overflow)

逻辑：patched >= toBePatched。
含义：新列表里一共只需要 4 个节点，我已经成功复用 4 个了。剩下的旧节点不管 Map 里有没有，都是多余的。
操作：直接卸载，不查 Map，节省性能。

2.3 深度解析：Move 的触发机制 (maxNewIndexSoFar)
#

在遍历旧节点时，Vue 维护了一个关键变量 maxNewIndexSoFar（目前为止遇到的最大新索引）。它的作用就像一条 “最高水位线”，用来检测节点顺序是否发生了变化。

核心逻辑：

理想情况（递增）：如果列表只是增加或删除了节点，但相对顺序没变，那么 newIndex 应该是 一直变大 的。
乱序情况（非递增）：一旦发现当前的 newIndex 比之前的“最高水位线”还要小，说明 这个节点“掉队”了（发生了乱序）。

场景演示：需要移动 (moved = true)

Old: [A, B, C]
New: [C, A, B] (C 跑到了最前面)

遍历旧节点	在新列表的索引 (newIndex)	水位线 (maxNewIndexSoFar)	判断逻辑	结果
A	`1`	`0` (初始)	`1 >= 0` (True)	更新水位线 -> `1`
B	`2`	`1`	`2 >= 1` (True)	更新水位线 -> `2`
C	`0`	`2`	`0 < 2` (False)	标记 `moved = true`

结论：moved 为 true，必须启动 LIS 算法来计算最小移动次数。

2.4 深度解析：Patch (打补丁) 的触发时机
#

patch 是 Vue 渲染器的核心入口，在乱序 Diff 中，只有以下两种情况会调用它：

场景 A：老友重逢 (Reuse & Update)

触发：在遍历旧节点时，拿着 Key 在 Map 里 找到了 对应的新节点。
动作：patch(prevChild, nextChild, ...)。
作用：复用 DOM 元素，只更新变化的属性（Props/Children）。

场景 B：新生命诞生 (Mount)

触发：在倒序遍历时，发现 newIndexToOldIndexMap 的值为 0。
动作：patch(null, nextChild, ...)（第一个参数为 null）。
作用：创建全新的 DOM 元素并挂载。

第三步：移动与挂载 (LIS 算法登场)
#

现在旧节点处理完了，我们得到了关键数组 newIndexToOldIndexMap: [5, 3, 4, 0]。

3.1 计算最长递增子序列 (LIS)
#

Vue 对 [5, 3, 4] (去掉 0) 计算 LIS。

结果：[3, 4] (对应的索引是 1 和 2)。
含义：新列表里的第 2 个 (c) 和第 3 个 (d) 节点，相对顺序是对的，不需要移动。

3.2 深度解析：Move 逻辑与锚点 (Anchor) 的奥秘
#

你可能会好奇：“Vue 怎么知道要把这个节点移动到哪里？是插在谁前面，还是谁后面？”

这里隐藏着 Vue 3 算法设计的一个大智慧：倒序遍历 (Backwards Iteration)。

为什么必须倒序？ DOM 原生 API 只有 insertBefore（插入到某节点之前）。如果我们想把节点放到正确位置，必须先确定它“后面”的那个节点是谁，那个节点就是 锚点 (Anchor)。

倒序遍历：处理第 i 个节点时，第 i+1 个节点（右边的邻居）肯定已经处理完毕了（要么是刚挂载的新节点，要么是已经归位的旧节点）。

可视化移动推演： 假设 Old [B, C] -> New [C, B]。

处理最后一个节点 B：
- 它是新列表的最后一个。
- 计算锚点：后面没人了 -> anchor = null。
- 动作：insertBefore(B, null) -> 等同于 appendChild(B)。
- 此时 B 归位到最后。
处理倒数第二个节点 C：
- 它后面是 B。
- 计算锚点：newChildren[B的索引].el -> 即 DOM 中的 B 节点。
- 动作：insertBefore(C, B) -> 把 C 插到 B 前面。
- 此时 C 归位。

4. 源码详解与变量速查 (Source Code Deep Dive)
#

这一部分展示了 patchKeyedChildren 中处理乱序的核心代码，并附带了逐行注释。

// 5. unknown sequence (乱序处理核心逻辑)
else {
  const oldStartIndex = i
  const newStartIndex = i

  // -------------------------------------------------------------
  // 5.1 建立索引图 (Build Map)
  // -------------------------------------------------------------
  const keyToNewIndexMap = new Map()
  for (i = newStartIndex; i <= newChildrenEnd; i++) {
    const nextChild = (newChildren[i] = normalizeVNode(newChildren[i]))
    if (nextChild.key != null) {
      keyToNewIndexMap.set(nextChild.key, i)
    }
  }

  // -------------------------------------------------------------
  // 5.2 遍历旧节点: Patch (打补丁) 或 Unmount (删除)
  // -------------------------------------------------------------
  let j
  let patched = 0 // 已复用/更新的新节点数量
  const toBePatched = newChildrenEnd - newStartIndex + 1
  let moved = false // 标记位：是否需要移动节点
  let maxNewIndexSoFar = 0 // “水位线”：记录遇到的最大新索引

  // newIndexToOldIndexMap: 核心映射数组 (值 = oldIndex + 1)
  const newIndexToOldIndexMap = new Array(toBePatched)
  for (i = 0; i < toBePatched; i++) newIndexToOldIndexMap[i] = 0

  // 遍历旧节点列表
  for (i = oldStartIndex; i <= oldChildrenEnd; i++) {
    const prevChild = oldChildren[i]

    // 【Unmount 优化】: 新节点已满，剩余旧节点直接删除
    if (patched >= toBePatched) {
      unmount(prevChild, parentComponent, parentSuspense, true)
      continue
    }

    let newIndex
    if (prevChild.key != null) {
      newIndex = keyToNewIndexMap.get(prevChild.key)
    } else {
      // 无 key 查找逻辑 (省略)
    }

    // 【Unmount】: 查无此人，删除
    if (newIndex === undefined) {
      unmount(prevChild, parentComponent, parentSuspense, true)
    }
    // 【Patch】: 找到了，复用
    else {
      newIndexToOldIndexMap[newIndex - newStartIndex] = i + 1

      // 【Move 触发判断】: 检查是否递增
      if (newIndex >= maxNewIndexSoFar) {
        maxNewIndexSoFar = newIndex
      } else {
        moved = true // 出现了乱序 (当前索引 < 水位线)
      }

      // 触发更新逻辑 (复用 DOM)
      patch(prevChild, newChildren[newIndex], container, null, ...)
      patched++
    }
  }

  // -------------------------------------------------------------
  // 5.3 移动与挂载 (Move & Mount)
  // -------------------------------------------------------------
  // 仅当 moved 为 true 时，才计算 LIS
  const increasingNewIndexSequence = moved
    ? getSequence(newIndexToOldIndexMap)
    : []

  j = increasingNewIndexSequence.length - 1

  // 【倒序遍历】
  for (i = toBePatched - 1; i >= 0; i--) {
    const nextIndex = newStartIndex + i
    const nextChild = newChildren[nextIndex]

    // 【计算锚点】: 取后一个节点的 el
    const anchor = nextIndex + 1 < newChildrenLength ? newChildren[nextIndex + 1].el : parentAnchor

    // 【Patch (Mount)】: 映射值为 0，说明是新节点，执行挂载
    if (newIndexToOldIndexMap[i] === 0) {
      patch(null, nextChild, container, anchor, ...)
    }
    // 【Move】: 需要移动 (moved=true)
    else if (moved) {
      // 如果 j < 0 (LIS 用完了) 或 当前索引不等于 LIS 中的值
      if (j < 0 || i !== increasingNewIndexSequence[j]) {
        move(nextChild, container, anchor, 2)
      } else {
        // 在 LIS 里，不动
        j--
      }
    }
  }
}

关键变量速查表
#

变量名	类型	作用解释
`keyToNewIndexMap`	`Map`	查找表。存 `{ key: index }`，用于在遍历旧节点时，以 `O(1)` 的速度查到它在新列表中的位置。
`newIndexToOldIndexMap`	`Array`	映射表。索引代表新节点相对位置，值代表旧节点索引+1。用于后续计算 LIS。
`patched`	`Number`	计数器。记录当前已经有多少个旧节点被成功复用到新列表中了。
`toBePatched`	`Number`	总目标数。新列表乱序部分总共有多少个节点需要处理。
`moved`	`Boolean`	开关。如果新节点索引一直递增，说明顺序没乱，此值为 false，后续不需要计算 LIS，极大提升性能。
`maxNewIndexSoFar`	`Number`	水位线。记录遍历过程中遇到的最大索引。如果下一个索引比它小，说明顺序乱了 (`moved = true`)。
`increasingNewIndexSequence`	`Array`	LIS 结果。保存的是不需要移动的节点在新列表中的相对索引。

5. 进阶：算法复杂度分析 (Complexity Analysis)
#

Vue 3 的乱序 Diff 算法在追求“最小 DOM 操作”的同时，也极好地控制了计算成本。我们来拆解每一步的时间和空间消耗。

5.1 时间复杂度 (Time Complexity)
#

假设旧节点数量为 n，新节点乱序部分数量为 m。

建立索引图 (Build Map)
- 操作：遍历新节点列表，写入 Map。
- 复杂度：O(m)。
遍历旧节点 (Clean Old)
- 操作：遍历旧节点列表，查 Map (查找为 O(1))，填充数组。
- 复杂度：O(n)。
计算最长递增子序列 (LIS)
- 操作：这是纯计算部分最耗时的步骤。Vue 使用了 贪心 + 二分查找 的策略。
- 细节：遍历数组 (O(m))，对每个元素进行二分查找 (O(log m))。
- 复杂度：O(m log m)。
- 注：如果是朴素的动态规划 O(m²)，在节点多时会卡顿，Vue 优化到了 O(m log m)。
倒序遍历与移动 (Move & Mount)
- 操作：再次遍历新节点列表，进行 DOM 插入。
- 复杂度：O(m)。

🔴 总时间复杂度： O(n + m log m)

5.2 空间复杂度 (Space Complexity)
#

我们需要额外的内存来存储辅助结构，以换取时间效率（空间换时间）。

keyToNewIndexMap：存储新节点的 Key 和 Index。
- 消耗：O(m)。
newIndexToOldIndexMap：存储新旧位置映射。
- 消耗：O(m)。
LIS 算法辅助数组：p 数组（前驱）和 result 数组（结果）。
- 消耗：O(m)。

🔵 总空间复杂度： O(m)

5.3 核心权衡：为什么要用 `O(m log m)`？
#

你可能会问：“简单粗暴地移动不是更快吗？为什么要花 O(m log m) 的 CPU 时间去算 LIS？”

这是一个经典的 计算成本 vs 渲染成本 的博弈：

JS 计算 (CPU)：非常快。现代浏览器执行 O(m log m) 的 JS 计算几乎是可以忽略不计的（即使 m = 1000，也只是几微秒）。
DOM 操作 (GPU/Layout)：非常慢。每一次 insertBefore 或 appendChild 都可能触发浏览器的 重排 (Reflow) 和 重绘 (Repaint)。

结论： Vue 3 选择多花一点点 JS 计算时间，算出"最完美的移动方案"，从而最大程度地减少昂贵的 DOM 操作。这在处理大型列表更新时，能带来肉眼可见的性能提升。

6. 附录：LIS 算法原理 (隐式树与贪心)
#

在 getSequence 函数中，Vue 3 使用了 贪心 + 二分 + 回溯 的策略。

隐式树结构 (p 数组)：p[i] = j 表示节点 i 的前驱是 j。这实际上在数组中构建了一棵倒置的树。
回溯：最后通过 result 的末尾元素（HEAD 指针），利用 p 数组一步步往回找，还原出那条最长的路径。
贪心抉择：算法总是倾向于选择“结尾更小”的序列，因为结尾越小，后面能接纳的数字就越多（潜力越大）。例如选择 2, 3, 4, 9 而不是 2, 5, 8, 9，因为 4 < 8，4 的潜力比 8 大。

Vue 3 源码核心解析：最长递增子序列 (LIS) 算法全景图

2026-02-12·3295 字·7 分钟

笔记 Vue3 算法源码分析 LIS

7. 总结
#

为什么 Vue 3 的 Diff 这么快？
#

Map 查找：将遍历查找的 O(n × m) 降为 O(n)。
Unmount 优化：一旦新节点名额 (toBePatched) 填满，剩余旧节点批量删除，不走查找逻辑。
LIS 算法：这是最精髓的部分。通过计算最长递增子序列，保证了 DOM 移动次数最少。
倒序插入：通过倒序遍历，利用已处理的节点作为锚点，巧妙解决了 insertBefore 需要参照物的问题。

1. 什么是“乱序 Diff”？#

2. 核心流程三部曲#

乱序 Diff 流程图#

第一步：建立新节点索引图 (KeyToNewIndexMap)#

第二步：遍历旧节点 (核心：Patch 与 Unmount)#

2.1 深度解析：newIndexToOldIndexMap 的秘密#

2.2 什么时候执行 Unmount (删除)？#

2.3 深度解析：Move 的触发机制 (maxNewIndexSoFar)#

2.4 深度解析：Patch (打补丁) 的触发时机#

第三步：移动与挂载 (LIS 算法登场)#

3.1 计算最长递增子序列 (LIS)#

3.2 深度解析：Move 逻辑与锚点 (Anchor) 的奥秘#

4. 源码详解与变量速查 (Source Code Deep Dive)#

关键变量速查表#

5. 进阶：算法复杂度分析 (Complexity Analysis)#

5.1 时间复杂度 (Time Complexity)#

5.2 空间复杂度 (Space Complexity)#

5.3 核心权衡：为什么要用 O(m log m)？#

6. 附录：LIS 算法原理 (隐式树与贪心)#

7. 总结#

为什么 Vue 3 的 Diff 这么快？#

相关文章