在了解 Vue2 和 Vue3 Diff 算法之前，我们先简单的想想这几个问题

• Vue2 的 Diff 算法存在什么弊端？
• Vue3 为什么引入最长递增子序列？目的是什么？
• Vue3 的 Diff 算法还做了哪些优化？
• 为什么 Vue3 移除了 头尾/尾头 对比？

相同点
通过对比新旧虚拟Dom树的差异，最小化操作真实Dom

不同点
Vue2 的 Diff 算法

• 编译时无预处理、运行时全量对比同层节点所有属性；对于 长列表/频繁重排 场景性能较差

Vue3 的 Diff 算法

• 编译时标记静态节点，运行时不参与对比直接复用
• 编译时为动态节点添加PatchFlags(补丁标记如：文本变化、属性变化)，运行时仅对比标记部分，精准比对，减少无效对比
• 引入 最长递增子序列（LIS） 算法，针对长列表和列表重排场景大幅优化，减少 DOM 移动次数

列表节点 v-for 是 Diff 算法的核心优化场景，Vue2 和 Vue3 的处理逻辑差异最大。因此我们通过演示 v-for 来说明 Vue2 和 Vue3 的 Diff 算法的运行流程

初始数据

  // 旧列表
  const oldChildren = [
    { key: 'a', tag: 'div' }, // 索引 0
    { key: 'b', tag: 'div' }, // 索引 1
    { key: 'c', tag: 'div' }, // 索引 2
    { key: 'd', tag: 'div' }  // 索引 3
  ]
  
  // 新列表（节点顺序变为 b、a、d、c）
  const newChildren = [
    { key: 'b', tag: 'div' },
    { key: 'a', tag: 'div' },
    { key: 'd', tag: 'div' },
    { key: 'c', tag: 'div' }
  ]

Vue2对比流程

Vue2 采用 双指针对比法，先尝试 旧头新头、旧尾新尾、旧头新尾、旧尾新头 四种对比方法，若都不匹配，则通过遍历旧节点列表查找可复用节点，找到后移动节点；否则新增节点。

初始化状态

旧列表（oldChildren）：索引 0 (a)、1 (b)、2 (‌c)、3 (d)
新列表（newChildren）：索引 0 (b)、1 (a)、2 (d)、3 (‌c)

双指针初始位置：
旧列表：oldStartIdx = 0（a），oldEndIdx = 3（d）
新列表：newStartIdx = 0（b），newEndIdx = 4（c）

步骤1：匹配 b 节点并移动

第 1 次移动：将 b 从旧列表索引 1 移到新列表索引 0 位置

对比

• 头头： old[0](a) vs new[0](b) → 不匹配
• 尾尾： old[3](d) vs new[3](‌c) → 不匹配
• 头尾： old[0](a) vs new[3](‌c) → 不匹配
• 尾头： old[3](d) vs new[0](b) → 不匹配

操作： 遍历旧列表查找 new[0](b)：在 old[1] 找到可复用节点，将 old[1](b) 移动到当前 newStartIdx（0）的位置（即列表头部）
指针更新： newStartIdx++（变为 1），old[1] 标记为已处理

步骤2：匹配 a 节点并移动

第 2 次移动：将 a 从旧列表索引 0 移到新列表索引 1 位置

旧列表节点： old[0](a)、old[1](b)、old[2](‌c)、old[3](d)（old[1] 已处理）
新列表待匹配节点：new[1](a)、new[2](d)、new[3](‌c)（new[0] 已匹配）

对比

• 头头： old[0](a) vs new[1](a) → 匹配（key 和类型一致）

操作： a 在旧列表索引 0，但新列表需要它在索引 1（newStartIdx=1），因此需将 a 移动到 newStartIdx 位置。
指针更新： oldStartIdx++（变为 1），newStartIdx++（变为 2）

注意
虽然此时 old[0](a) 已在 d 的后面了，已经在目标位置了，但这里也需要做移动操作(即便没有变化)

为什么 old[0] 的 a 已经在新列表的目标位置了还需要移动？

因为新旧指针内都还剩很多元素待比较，所以必须需要做移动操作，即便没有变化

步骤3：匹配 c 节点并移动

第 3 次移动：将 c 从旧列表索引 2 移到新列表索引 3 位置

旧列表节点： old[1](b)、old[2](‌c)、old[3](d)（old[1] 已处理）
新列表待匹配节点： new[2](d)、new[3](‌c) (new[0]、new[1] 已匹配）

对比

• 头头： old[2](‌c) vs new[2](d) → 不匹配
• 尾尾： old[3](d) vs new[3](‌c) → 不匹配
• 头尾： old[2](‌c) vs new[3](‌c) → 匹配

操作： c 在旧列表索引 2，新列表需要它在索引 3（newEndIdx=3），因此需将 c 移动到 newEndIdx 位置
指针更新： oldStartIdx++（变为 2），newEndIdx–（变为 2）
此时 oldStartIdx=2，oldEndIdx=3；newStartIdx=2，newEndIdx=2

为什么 oldStartIdx 从角标2开始比较呢？

在 Vue2 的双指针算法中，“节点已处理” 仅表示该节点已被匹配并复用，不会直接删除或跳过旧列表的索引
但在进行头头、尾尾等比较时，双指针算法会自动忽略已处理的节点，即使指针指向该索引，也不会参与对比，会通过移动 oldStartIdx 和 oldEndIdx 来 “跳过” 已处理的节点，仅比较剩余未匹配的节点

步骤4：无需移动，直接复用

旧列表节点： old[2](‌c)、old[3](d)（old[2] 已处理）
新列表待匹配节点： new[2](d)

对比

• 头头对比：old[3](d) vs new[2](d) → 匹配

操作： 无需移动，直接复用
指针操作： oldStartIdx=3，oldEndIdx=3；newStartIdx=3，newEndIdx=2，循环结束

为什么 old[3] 和 new[2] 的 d 角标不一样而不需要移动直接复用呢？

在 Vue2 双指针算法中，元素移动并非严格按 旧索引 -> 新索引 对应移动
经过前面步骤的移动索引已变成 oldStartIdx=2，oldEndIdx=3；newStartIdx=2，newEndIdx=2 但因old[2](‌c)已处理，实际上是 oldStartIdx=3，oldEndIdx=3；newStartIdx=2，newEndIdx=2
旧列表剩余节点是唯一的 old[3](d)，而新列表待匹配的节点是唯一的 new[2](d)，当新旧列表都只剩 d 时，双指针算法会直接判定两者自然对齐，因为此时没有其它节点需要插入或移动，d 的位置已通过前面节点的移动被挤到目标位置，因此可直接复用

哪什么情况下需要移动呢？

当旧列表剩余 old3 而新列表剩余 new2 old3 时，或**类似这样的情况时，**此时需要移动

Vue2 双指针算法共执行 3 次 DOM 移动：

1. 将 b 从旧索引 1 移动到新索引 0
2. 将 a 从旧索引 0 移动到新索引 1
3. 将 c 从旧索引 2 移动到新索引 3

Vue3 对比流程

初始化状态

旧列表（oldChildren）：索引 0 (a)、1 (b)、2 (‌c)、3 (d)
新列表（newChildren）：索引 0 (b)、1 (a)、2 (d)、3 (‌c)

双指针初始位置
旧列表：oldStartIdx = 0（a），oldEndIdx = 3（d）
新列表：newStartIdx = 0（b），newEndIdx = 4（c）

步骤1：头头尾尾快速对比

对比

• 头头：old[0](a) vs new[0](b) → 不匹配
• 尾尾：old[3](d) vs new[3](‌c) → 不匹配

都不匹配，指针未移动

为什么 Vue3 移除了 头尾/尾头 对比？

因为场景占比低，即便头尾/尾头匹配上了，也还是需要移动，且源码维护成本高。Vue3 用 LIS(最长递增子序列) 算法覆盖了 Vue2 所有对比策略的功能，且效率更优

步骤2：乱序比对

构建 keyToNewIndexMap 新节点 key -> 索引映射映射

通过 Map 生成 keyToNewIndexMap 新节点 key → 索引映射表，用于开始判断旧节点是否在新列表中

  // 类似于对象的 key → 索引映射
  { b:0, a:1, d:2, c:3 }
  
  // keyToNewIndexMap Map结构
  const keyToNewIndexMap = Map([['b', 0], ['a', 1], ['d', 2], ['c', 3]])

构建 newIndexToOldIndexMap 标记新节点的旧索引（判断新增 / 可复用）

遍历旧节点列表，通过 keyToNewIndexMap 查找旧节点是否在新列表中

• 若存在：记录旧列表元素在新列表中的索引值到 newIndexToOldIndexMap
• 若不存在：标记旧节点为「待删除」（后续统一删除）

  // -1 表示新增节点
  const newIndexToOldIndexMap = [1, 0, 3, 2]
  
  // 待删除旧节点集合 所有旧节点都在新列表中，此时代表无删除节点
  let toBeRemoved = []

计算最长递增子序列（LIS）→ 确定无需移动的节点

通过 newIndexToOldIndexMap 获取最长递增子序列。说明这些节点在新旧列表中的顺序是一致的，无需移动。仅移动非递增子序列的节点，从而达到最小化移动次数

本示例通过 newIndexToOldIndexMap = [1, 0, 3, 2]，获取的最长递增子序列有这些 [1,3]、[1,2]、[0,3]、[0,2]（长度 2），LIS 为 [0,2] (其它也可以)（源码通过「贪心 + 二分查找」计算，确保最长且稳定）。

计算的最长递增子序列

• const sequence = [ 0, 2 ]
• 对应 newIndexToOldIndexMap 的索引 0 和 2，即 新节点 相对索引 0（b）和 2（d）

结论

• 无需移动的节点：新节点 b（相对索引 0）和 d（相对索引 2）→ 它们在新旧列表中的相对顺序一致（旧：b→d；新：b→d）。
• 需移动的节点：新节点 a（相对索引 1）和 c（相对索引 3）→ 它们在新旧列表中的相对顺序不一致

为什么引入最长递增索引序列？

如果新列表中存在一个最长子序列，使得新列表中的元素顺序与旧列表中的元素顺序一致，那么这个子序列中的元素就不需要移动。这样就可以最大限度的减少 DOM 移动次数，提高性能

反向遍历 + 锚点复用 → 执行 DOM 操作

Vue3 采用反向遍历新节点列表的方式，结合 LIS 标记，通过 insertBefore 执行移动/新增操作，核心是 用已处理节点作为锚点，避免锚点漂移

接下来我们分步看看执行流程

分步执行（反向遍历顺序：c → d → a → b）

初始状态：旧 DOM = abcd，新DOM = badc

处理新节点 c

经过判断，节点 c 不在 LIS 中，需要移动。通过 insertBefore(c.el, null) 插入到父容器末尾（锚点为 null 时，会插入到末尾）

DOM更新为：abdc

处理新节点 d

经过判断，节点 d 在 LIS 中，不需要移动，仅更新 d 的属性（无变化）

DOM不变：abdc

处理新节点 a

经过判断，节点 a 不在 LIS 中，需要移动。通过 insertBefore(a.el, d.el) 插入到 d 前面

DOM更新为：badc

处理新节点 b

经过判断，节点 b 在 LIS 中，不需要移动，仅更新 b 的属性（无变化）

DOM不变：badc

为什么反向遍历而不是正向遍历？

Vue3 中节点的新增/移动都是通过 insertBefore 完成，如果正向遍历，每次插入都需遍历列表查找锚点位置,且锚点依赖未处理的节点，而未处理的节点位置可能因前面的插入操作而改变，导致锚点不稳定（漂移），导致 DOM 结构错乱，效率低下

反向遍历则无需额外查询锚点，并且用已处理节点作为锚点，锚点绝对稳定，确保 DOM 插入位置准确，从根源上避免了错乱

Vue3 LIS算法共执行 2 次 DOM 移动：

1. 将 c 从旧索引 2 移动到 新列表末尾
2. 将 a 从旧索引 0 移动到 d 前面