Diff 算法概述

首先要问的是：当数据变化时，如何以最少的 DOM 操作完成视图更新？

这就是 Diff 算法要解决的核心问题。DOM 操作是昂贵的——每次创建、删除或移动 DOM 节点都会触发浏览器的重排和重绘。一个优秀的 Diff 算法可以将更新性能提升数倍甚至数十倍——这就是为什么值得深入理解它。

本章将带你从宏观视角理解 Diff 算法的设计目标、核心思想以及 Vue 3 采用的策略。

为什么需要 Diff 算法

首先要问一个问题：当列表数据变化时，最简单的更新方式是什么？

答案很直接——暴力替换：清空容器，重新创建所有节点。

javascript

// 场景：列表从 [A, B, C] 变为 [A, C, B]

// 方案一：暴力替换
container.innerHTML = ''
newList.forEach(item => container.appendChild(createDOM(item)))
// 成本：3 次删除 + 3 次创建 = 6 次 DOM 操作

这种方式简单粗暴，但问题也很明显：即使只是两个元素交换了位置，也要销毁所有节点再重建。

现在我要问第二个问题：有没有更好的方式？

javascript

// 方案二：Diff + 复用
// 发现 A 不变，B 和 C 只是位置变了
// 只需要移动 B 到 C 后面即可
container.insertBefore(nodeB, null)
// 成本：1 次移动操作

核心洞察：相邻两次渲染的差异通常很小，复用已有 DOM 节点是关键。

Diff 算法的本质就是比较新旧虚拟 DOM 树的差异，找出最小的更新路径。

Diff 算法的核心思想

传统的树 Diff 算法（计算最小编辑距离）时间复杂度是 O(n³)——对于包含 1000 个节点的页面，需要进行 10 亿次比较，这显然不可接受。

前端框架采用了一种启发式策略，将复杂度降到 O(n)。这种策略基于三个核心假设：

假设一：不同类型的节点产生不同的树

如果节点类型变了（比如 <div> 变成 <span>），直接销毁旧节点及其子树，创建新节点。不进行深度比较。

javascript

// 类型不同，直接替换
const oldVNode = { type: 'div', children: [/* 复杂子树 */] }
const newVNode = { type: 'span', children: [/* 另一个子树 */] }

// 不会尝试复用子节点，直接：
// 1. 卸载 div 及其子树
// 2. 挂载 span 及其子树

假设二：同一层级的节点可以通过 key 区分

key 是节点的身份标识。相同 key 和类型的节点被认为是"同一个节点"，可以复用。

javascript

// key 用于判断节点是否可复用
function isSameVNodeType(n1, n2) {
  return n1.type === n2.type && n1.key === n2.key
}

假设三：只比较同一层级的节点

不跨层级移动节点。如果某个节点在新树中换了父节点，会被视为删除+新增。

    A           A'
    │           │
  ┌─┴─┐       ┌─┴─┐
  B   C   =>  B   D     只比较同一层级
  │                     B 的子节点 E 不会移动到 A' 下
  E

这三个假设牺牲了一定的"最优性"（理论上可能存在更少操作的方案），但换来了可接受的性能。在实际场景中，这些假设几乎总是成立。

Diff 策略的演进

Vue 在不同版本采用了不同的 Diff 策略，这个演进过程反映了对实际场景的深入理解：

Vue 1.x：无虚拟 DOM

Vue 1.x 采用细粒度的依赖追踪——每个绑定都有独立的 Watcher 直接更新 DOM。这种方式在小型应用中效率很高，但随着应用规模增长，Watcher 数量爆炸式增长，内存和性能都成问题。

Vue 2.x：双端 Diff

Vue 2.x 引入虚拟 DOM，采用双端 Diff 算法：同时从新旧列表的头尾进行比较。这种方式在处理列表首尾变化时效率很高。

Vue 3.x：快速 Diff

Vue 3 进一步优化，采用快速 Diff 算法：先预处理公共前缀和后缀，再使用最长递增子序列（LIS）确定最小移动方案。这是当前最先进的 Diff 策略之一。

各种 Diff 策略预览

在深入每种算法之前，先从宏观上了解它们的核心差异：

简单 Diff

最直观的策略：遍历新列表，在旧列表中查找可复用节点。使用 lastIndex 标记判断是否需要移动。

特点：

实现简单，容易理解
O(n) 时间复杂度
移动次数可能较多，不是最优

双端 Diff

同时从两端进行比较：头头、尾尾、头尾、尾头四种情况。利用了实际场景中列表变化往往发生在两端的特点。

特点：

减少不必要的移动
Vue 2 采用的方案
对首尾操作非常高效

快速 Diff

分三个阶段：

预处理：跳过公共前缀和后缀
处理简单情况：仅新增或仅删除
处理乱序部分：使用 LIS 确定最小移动

特点：

Vue 3 采用的方案
移动次数最少
利用编译时信息进一步优化

本章小结

本章建立了 Diff 算法的宏观认知：

核心目标：最小化 DOM 操作，复用已有节点
基本假设：同类型比较、key 标识、同层比较
复杂度权衡：O(n³) → O(n)，牺牲最优性换取可接受性能
策略演进：简单 Diff → 双端 Diff → 快速 Diff

思考一下：这三个假设在什么场景下会失效？

当跨层级移动节点时（比如将某个子树移动到另一个父节点下），Diff 算法会认为是删除+新增。但这种场景在实际开发中非常罕见，所以这个权衡是值得的。

下一章，我们将从最简单的 Diff 算法开始，逐步理解每种策略的实现细节和优化思路。

在 GitHub 上编辑此页

Diff 算法概述 ​

为什么需要 Diff 算法 ​

Diff 算法的核心思想 ​

Diff 策略的演进 ​

各种 Diff 策略预览 ​

本章小结 ​

Diff 算法概述

为什么需要 Diff 算法

Diff 算法的核心思想

Diff 策略的演进

各种 Diff 策略预览

本章小结