Vue 3 Diff 算法源码解析与优化

前言

在 Vue 的响应式系统中，diff 算法是 Virtual DOM 更新的核心。它通过对比新旧虚拟节点树，找到需要变更的部分，并高效地进行最小化更新，确保性能与用户体验的平衡。
Vue2 中的 diff 算法采用了“双端比较”策略，而在 Vue3 中，随着虚拟节点结构的简化和优化，diff 算法也进行了重构。其核心逻辑更加模块化，同时结合了一些现代浏览器的性能特性（如 patchFlag 和 keyed children 优化），使得渲染性能进一步提升。
本篇文章将结合 Vue3 的源码，深入解析其 diff 算法的实现原理和优化策略，帮助你理解它背后的设计哲学以及对性能的提升是如何达成的。

patch 函数整体结构

在 Vue 3 的源码中，patch 函数是虚拟 DOM 的核心入口之一，它负责对比两个虚拟节点（VNode）并将差异反映到真实 DOM 上。它的定义在 packages/runtime-core/src/renderer.ts 文件中。

1. 函数签名

const patch: PatchFn = (
  n1,     // 旧 vnode
  n2,     // 新 vnode
  container,  // 容器元素（真实 DOM）
  anchor = null, // 锚点：用于插入位置控制
  parentComponent = null,
  parentSuspense = null,
  isSVG = false,
  slotScopeIds = null,
  optimized = false
) => { ... }

这个函数是递归调用的核心，每个 vnode 的更新都会调用它，它会根据 vnode 类型决定如何更新。

2. patch 函数结构（简化逻辑）

源码中，patch 函数大致流程如下（可理解为一个调度器）：

if (n1 === n2) {
  return
}

if (n1 && !isSameVNodeType(n1, n2)) {
  // 如果新旧节点类型不同，先卸载旧节点
  unmount(n1, ...)
  n1 = null
}

// 判断 vnode 的类型（ShapeFlag）
const { type, shapeFlag } = n2

switch (type) {
  case Text:
    processText(n1, n2, container, ...)
    break
  case Comment:
    processCommentNode(n1, n2, container, ...)
    break
  case Fragment:
    processFragment(n1, n2, container, ...)
    break
  default:
    if (shapeFlag & ShapeFlags.ELEMENT) {
      processElement(n1, n2, container, ...)
    } else if (shapeFlag & ShapeFlags.COMPONENT) {
      processComponent(n1, n2, container, ...)
    }
}

3. 类型处理分支

Text 文本节点 → processText
Comment 注释节点 → processCommentNode
Fragment 多子节点容器 → processFragment
Element 普通 HTML 元素 → processElement
Component Vue 组件 → processComponent
每个 processX 函数内部再调用更细粒度的函数处理更新、挂载等逻辑。例如 processElement 会进一步调用 mountElement 或 patchElement。

4. patch 函数的特点

递归更新：patch 会对子节点递归调用自己。
类型分发：根据 vnode 的类型走不同处理逻辑，符合开放封闭原则。
局部优化：通过 patchFlag 和 key 优化更新效率。
异构替换：如果新旧 vnode 类型不同，直接卸载旧的，挂载新的。

patchKeyedChildren 的核心逻辑

1. 背景

在更新子节点列表时，Vue 会优先使用 key 属性来判断节点是否可以复用（比位置更可靠）。如果新旧子节点都包含 key，就会走 patchKeyedChildren 逻辑。

patchKeyedChildren(c1, c2, container, parentAnchor, ...)

2. 核心目标

实现最小化 DOM 操作的更新策略：

能复用就复用
能移动就移动
不存在的就新增
旧的没了就卸载

3. 核心流程（简化版）

Step 1：前置对比（从头部开始）

比较新旧列表的开头部分，遇到相同的 key 就 patch，直到不匹配为止。

while (i <= e1 && i <= e2) {
  if (isSameVNodeType(c1[i], c2[i])) {
    patch(c1[i], c2[i], container, ...)
  } else {
    break
  }
  i++
}

Step 2：后置对比（从尾部开始）

while (i <= e1 && i <= e2) {
  if (isSameVNodeType(c1[e1], c2[e2])) {
    patch(c1[e1], c2[e2], container, ...)
  } else {
    break
  }
  e1--
  e2--
}

Step 3：新增节点（新节点比旧节点多）

if (i > e1) {
  // 所有旧节点都处理完了，新增剩下的新节点
  const nextPos = e2 + 1
  const anchor = nextPos < l2 ? c2[nextPos].el : parentAnchor
  while (i <= e2) {
    patch(null, c2[i], container, anchor, ...)
    i++
  }
}

Step 4：卸载多余节点（旧节点比新节点多）

else if (i > e2) {
  while (i <= e1) {
    unmount(c1[i], ...)
    i++
  }
}

Step 5：复杂对比（中间乱序部分）

这是关键部分，处理乱序、移动、复用等情况。
主要流程：

建立新 children 的 key -> index 映射表
遍历旧 children，看能不能复用（即在映射表中找 key）
新建一个 source 数组（长度为新 children 剩余部分），记录旧节点在新 children 中的位置
根据 source 判断是否需要移动节点（非递增位置即需移动）
使用最长递增子序列 (LIS) 来尽量减少移动次数
插入或移动新节点到正确位置
源码中的核心优化点在于：

const seq = getSequence(source); // 计算 LIS

最长递增子序列 (LIS)

1. 什么是最长递增子序列（LIS）？

最长递增子序列（Longest Increasing Subsequence，简称 LIS）是指在一个数组中找到一个最长的子序列，使得子序列中的元素保持严格递增顺序。
例如：

序列: [2, 5, 3, 7, 11, 8, 10, 13, 6]
最长递增子序列可能是: [2, 3, 7, 8, 10, 13]

2. 为什么 Vue3 diff 算法需要用到 LIS？

在 patchKeyedChildren 里，Vue 会将新旧节点做对比，特别是中间乱序部分的节点。为了把旧节点尽量复用且减少 DOM 移动，Vue 需要找出哪些节点的相对位置是保持不变的，哪些节点需要被移动。

LIS 就是用来找出在新节点序列中，旧节点能保持顺序不变的最长子序列。

3. 具体场景

举个例子，假设有旧节点/新节点顺序：

const oldNodes = [A, B, C, D, E];
const newNodes = [B, A, E, C, D];

经过 key 映射，转换成旧节点在新序列的索引数组：

const newIndexToOldIndexMap = [1, 0, 4, 2, 3];

数字表示旧节点对应新节点的位置。
Vue 需要找出这个数组的最长递增子序列（LIS），即不需要移动的节点集合。
对于这个例子，LIS 是 [1, 4]，对应的是节点 A、C、D，表示这两个节点在新列表中顺序是正确的，无需移动。
其他节点 B 和 E 则需要移动。

4. 使用 LIS 的好处

减少 DOM 操作：只移动真正位置变化的节点，避免大量无谓的节点移动。
提升性能：插入和删除 DOM 节点开销大，减少这些操作能够显著提升渲染性能。
稳定性更好：顺序保持的节点避免重复销毁和创建，提升用户体验。

延伸最长递增子序列 (LIS) 的 getSequence 实现

基础版 — 时间复杂度 O(n²)

通过遍历数组，从每个元素开始，逐步构建递增序列，记录所有递增子序列，最后返回最长的那个。

function getLIS(arr) {
  const length = arr.length;
  const newArr = arr.slice();
  const results = []; // 保存所有递增数组

  for (let i = 0; i < length; i++) {
    // 单个递增数组保存
    const result = [];
    for (let j = i; j < length; j++) {
      if (!result.length) {
        result.push(arr[j]);
        continue;
      }
      const prev = result[result.length - 1];
      const count = arr[j];
      // 当前数量大于当前递增数字最后一位， 则将当前数字push进数组
      if (prev < count) {
        result.push(count);
      }
    }
    results.push(result);
  }
  results.sort((a, b) => b.length - a.length);
  return results[0];
}

特点：

实现简单直观
通过两层循环穷举，效率较低

进阶版 — 时间复杂度 O(n²)，优化查找方式

使用一个辅助数组 tails 维护递增子序列的末尾元素，逐步更新 tails，其长度即为 LIS 长度。

function getLIS(nums) {
  const tails = []; // tails[i] 表示长度为 i+1 的递增子序列的最小末尾值

  for (let num of nums) {
    // 找到第一个 >= num 的位置
    let i = 0;
    while (i < tails.length && tails[i] < num) {
      i++;
    }

    // 如果没找到，说明 num 比所有尾部值都大，直接加到数组末尾
    if (i === tails.length) {
      tails.push(num);
    } else {
      // 否则替换当前的位置，保持尾部尽可能小（贪心）
      tails[i] = num;
    }

    // 观察每一步的变化（可选）
    // console.log(`处理 ${num}，tails: `, tails);
  }

  return tails;
}

特点：

维护 tails 数组，贪心策略保持递增子序列的末尾最小
使用线性查找替代遍历，提高部分效率

3. 终极版(Vue实现版本简化)

function getLIS(nums) {
  // tails[i] 表示长度为 i+1 的递增子序列的最小结尾值
  const tails = [];

  for (const num of nums) {
    /** 搜索范围的左边 */
    let left = 0;
    /** 搜索范围的右边 */
    let right = tails.length;

    // 二分查找：找第一个 ≥ num 的位置
    while (left < right) {
      /** 中间位置下标 */
      const mid = Math.floor((left + right) / 2);
      /** 如果 当前的数值大于 tails 中间位置的数 搜索范围的左边往中间位置右移 */
      if (tails[mid] < num) {
        left = mid + 1;
        /** 当前的数值小于 tails  中间位置的数  */
      } else {
        right = mid;
      }
    }

    // 如果 num 比 tails 中所有值都大，left 会等于 tails.length，直接 push
    // 否则，用 num 替换第一个 ≥ num 的值（贪心地用更小的值替换）
    if (left < tails.length) {
      tails[left] = num;
    } else {
      tails.push(num);
    }

    // 你可以取消注释这一行，观察每次 tails 的变化：
    // console.log(`num=${num}, tails=`, tails);
  }

  // 最终 tails.length 就是最长递增子序列的长度
  return tails;
}

特点：

利用二分查找优化查找过程
时间复杂度降为 O(n log n)

对比

版本	时间复杂度	返回结果	主要思路
基础版	O(n²)	最长递增子序列本身	暴力枚举所有递增序列
进阶版	O(n²)	LIS 长度	用 `tails` 贪心维护序列末尾值
终极版	O(n log n)	LIS 长度	在进阶版基础上用二分查找优化

前言