Diff 算法

2025-06-05 14:51

前面我们了解了虚拟 DOM，接下来我们就得了解Diff 算法了。

什么是 Diff 算法

Diff 算法是一种用于比较两个数据结构，并找出它们之间的差异的算法。在这里是对比旧的虚拟 DOM 和最新的虚拟 DOM，找出差异点，并更新这个虚拟节点到真实节点，而不用更新其他无需更新节点，实现精准地更新真实 DOM，进而提高效率。

可以看下列图：（是从掘金拿过来来的， 原文章链接）

图片加载中...

Diff 算法原理

Diff 对比

新旧虚拟 DOM 对比时，Diff 算法会从两个虚拟 DOM 的根节点开始，逐层比较，不会夸层比较，所以大多数使用的虚拟 DOM 框架都是基于深度优先算法和同层比较实现。时间复杂度为：0(n)。

图片加载中...

可能会想为什么使用深度优先算法，而不是广度优先算法？

递归是天然的深度优先：

React 的 Fiber 或者其他框架本身是递归遍历树，并且深度优先逻辑清晰:先处理父，再处理子，再处理孙, 递归完返回上一层。 如果改成广度优先就要：

• 在每一层先收集所有节点，排成队列，再一口气处理所有子节点。
• 对于树的递归，需要引入复杂的队列调度机制。 这并不是不可以，但复杂性和内存占用会显著增加。

生命周期顺序要求

如果采用广度优先，会破坏组件的生命周期顺序。 在 React 中，组件的生命周期依赖于“先父后子”的顺序，如果使用广度优先：

• 先处理所有第一层节点（可能是多个兄弟节点），再处理它们所有的孩子。
• 这会让不同分支的子组件先于父组件开始挂载。
• 生命周期钩子（如 componentDidMount）调用时机就会错乱。 这在很多场景下会带来严重问题：
• 父组件依赖子组件的 DOM。
• 父组件在 mount 中要读取子树状态。
  图片加载中...

  

内存和调度复杂性

• 深度优先递归时，每次只需要保留当前分支的状态。
• 广度优先要维护一个当前层所有节点的队列，在大型树上，内存压力更大。
• React Fiber 本身要支持中断和恢复（增量渲染），如果再改成广度优先，会让调度更复杂。

同层比较其实不依赖广度优先

• 很多人会以为“同层比较”必须用广度优先，其实不是。
• 在深度优先递归里，每层都先对比一遍同级的 children ，确定节点复用关系，再递归到下一层。
• 所以，同层比较 ≠ 广度优先遍历。

Diff 对比流程

关于对比流程，我希望通过 React 和 Vue 两大框架为例进行。

React Diff

React 的 Diff 算法主要基于以下三个假设（这是 React 官方文档也提到过的经典“Diff 策略假设”）：

1. 不同类型的元素会产生不同的树
   • 如果一个节点类型（如 <div> 和 <span>）不同，React 会直接销毁旧节点及其子树，再创建新节点及其子树，不做进一步比较。
   • 这个假设避免了跨类型的深度比较，提高性能。
2. 同一层级的子节点可以通过 key 唯一标识
   • 如果子节点使用了 key，React 会通过 key 建立映射关系，精准判断节点是否复用、移动或删除。
   • 没有 key 时，React 会按索引顺序对比。
3. 节点只会在同层级移动，不会跨层移动
   • 所以 React 的 Diff 只做同层比较，不做跨层 Diff。

Diff 流程分解

React 中，每次状态变更或父组件更新时，都会触发 Fiber 的 Diff 过程。具体流程大致如下：

1. 根节点开始对比
   • 判断节点类型是否相同。
     • 相同：保留节点，复用 DOM，继续比较属性和子节点。
     • 不同：销毁旧节点，创建新节点。
2. 属性比较
   • 遍历新旧 Props，找出差异（如 className、style 变了）。
   • 对应更新 DOM 属性。
3. 子节点比较（最重要的部分）
   • 如果子节点是数组，会先执行：
     • 判断是否有 key。
       • 有 key：根据 key 建立映射表，复用、插入或删除节点。
       • 无 key：按索引逐个比较。
4. 递归对子节点执行同样逻辑 - 深度优先递归，直至所有节点对比完毕。
   图片加载中...

   
   这个流程对应源码中最核心的函数是（React 中最核心的 Diff 逻辑在 reconcileChildFibers.js：）：

JAVASCRIPT复制
// 核心函数：比较新旧 Fiber 子节点，返回新 Fiber
function reconcileChildren(currentFiber, workInProgressFiber, nextChildren) {
  // 如果没有旧节点，直接创建所有新节点
  if (currentFiber === null) {
    // 创建所有新 Fiber
    workInProgressFiber.child = mountChildFibers(workInProgressFiber, null, nextChildren);
  } else {
    // 有旧节点，执行 Diff
    workInProgressFiber.child = reconcileChildFibers(workInProgressFiber, currentFiber.child, nextChildren);
  }
}
// mountChildFibers: 用于初次挂载。
// reconcileChildFibers: 用于更新对比（Diff）。
// 其中 reconcileChildFibers 里最关键的逻辑就是：
function reconcileChildFibers(returnFiber, currentFirstChild, newChildren) {
  // 1. 如果新Children是单节点
  if (typeof newChildren === "object" && newChildren !== null) {
    return placeSingleChild(reconcileSingleElement(returnFiber, currentFirstChild, newChildren));
  }

  // 2. 如果是数组
  if (Array.isArray(newChildren)) {
    return reconcileChildrenArray(returnFiber, currentFirstChild, newChildren);
  }

  // 3. 其他类型（string/number等）
  return null;
}

它就是执行“新旧子节点数组的对比”，并返回新的 Fiber 树。

Key 的作用

为什么 Key 特别重要？ 假设：

JSX复制
// 旧节点
[<li key="A">A</li>, <li key="B">B</li>, <li key="C">C</li>][
  // 新节点
  ((<li key="B">B</li>), (<li key="A">A</li>), (<li key="C">C</li>))
];

此时流程是：

1. 遍历旧节点建立映射：

   JAVASCRIPT复制
   map = {
     A: oldFiber(A),
     B: oldFiber(B),
     C: oldFiber(C),
   };

2. 遍历新节点：
   • key="B"：复用 oldFiber(B)
   • key="A"：复用 oldFiber(A)
   • key="C"：复用 oldFiber(C)
3. 判断顺序是否变化：是（B 和 A 顺序换了） - 标记需要移动。 - 最终只做 DOM 移动，不销毁重建。 没有 key 时：

• 只能按索引：
  • 第 0 个：旧 A vs 新 B => 类型相同？不相同，销毁重建。
  • 第 1 个：旧 B vs 新 A => 同理。
  • 第 2 个：旧 C vs 新 C => 复用。
• 产生大量不必要的销毁和重建。

Vue Diff

Vue 在虚拟 DOM 的 Diff 更新上，采取了动静结合的多层优化： - 静态提升 + PatchFlag：先标记哪些 VNode 需要比对、哪些是稳定的。 - 动态双端 Diff：四指针比对确定复用、移动、插入、删除。 - 最长递增子序列（LIS）：在大量移动场景下，最小化 DOM 操作。

PatchFlag：静态标记，减少不必要比对

在编译模板阶段，Vue 会分析每个 VNode 的属性和内容，给它打上PatchFlag。

PatchFlag 是一个数字 bit 标记，表示该 VNode 在更新时需要特别关心哪些变化。

常见的 PatchFlag 有：

• TEXT：只关心文本变化。
• CLASS：只关心 class 属性变化。
• STYLE：只关心 style 属性变化。
• PROPS：只关心 props 属性变化。
• NEED_PATCH：需要整体 patch。
• HOISTED：完全静态节点. 举个例子：

VUE复制
<div>
  <p class="title">Hello</p>
  <p :class="dynamicClass">World</p>
</div>

编译后： - 第一个 <p>：静态 VNode，直接复用。 - 第二个 <p>：打上 CLASS PatchFlag，只需比较 class 属性。 好处： - 静态 VNode 可以一次渲染多次复用。 - 更新时跳过无关节点，性能极高。 所以 Vue 先通过 PatchFlag排除大部分不需要比对的节点，只对真正有变化的 VNode 进入双端 Diff。

双端 Diff

Vue 在比较子节点时，采用了经典的双端指针算法，这种算法结合了局部性原理，针对新旧节点数组头尾同时比较，能够高效判断节点的复用、移动、插入或删除操作。

1. 双端 Diff 算法核心思想 假设有两个子节点数组：

JS复制
// 旧节点数组 oldChildren
[{ key: "A" }, { key: "B" }, { key: "C" }, { key: "D" }][
  // 新节点数组 newChildren
  ({ key: "B" }, { key: "C" }, { key: "A" }, { key: "E" })
];

比较过程中维护四个指针：

• oldStartIdx 指向旧数组头部
• oldEndIdx 指向旧数组尾部
• newStartIdx 指向新数组头部
• newEndIdx 指向新数组尾部 算法会在这四个指针之间不断做比较和移动。

2. 双端 Diff 具体流程

   步骤	说明
   1. 旧头节点和新头节点对比	如果相同，则复用，指针向后移动
   2. 旧尾节点和新尾节点对比	如果相同，则复用，指针向前移动
   3. 旧头节点和新尾节点对比	如果相同，表示节点移动到末尾，移动 DOM，指针相应调整
   4. 旧尾节点和新头节点对比	如果相同，表示节点移动到开头，移动 DOM，指针相应调整
   5. 否则，尝试根据 key 查找新节点在旧节点中的位置，进行插入或删除操作

代码示例：

JAVASCRIPT复制
while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
  if (isSameVNode(oldChildren[oldStartIdx], newChildren[newStartIdx])) {
    patch(oldChildren[oldStartIdx], newChildren[newStartIdx]);
    oldStartIdx++;
    newStartIdx++;
  } else if (isSameVNode(oldChildren[oldEndIdx], newChildren[newEndIdx])) {
    patch(oldChildren[oldEndIdx], newChildren[newEndIdx]);
    oldEndIdx--;
    newEndIdx--;
  } else if (isSameVNode(oldChildren[oldStartIdx], newChildren[newEndIdx])) {
    patch(oldChildren[oldStartIdx], newChildren[newEndIdx]);
    moveNode(oldChildren[oldStartIdx], after oldChildren[oldEndIdx]);
    oldStartIdx++;
    newEndIdx--;
  } else if (isSameVNode(oldChildren[oldEndIdx], newChildren[newStartIdx])) {
    patch(oldChildren[oldEndIdx], newChildren[newStartIdx]);
    moveNode(oldChildren[oldEndIdx], before oldChildren[oldStartIdx]);
    oldEndIdx--;
    newStartIdx++;
  } else {
    // 通过 key 查找旧节点位置进行插入或删除
    const idxInOld = findIdxInOld(newChildren[newStartIdx], oldChildren);
    if (idxInOld === -1) {
      // 新增节点，直接插入
      insertNode(newChildren[newStartIdx], before oldChildren[oldStartIdx]);
    } else {
      // 复用节点，移动 DOM
      moveNode(oldChildren[idxInOld], before oldChildren[oldStartIdx]);
      patch(oldChildren[idxInOld], newChildren[newStartIdx]);
      oldChildren[idxInOld] = undefined; // 标记已处理
    }
    newStartIdx++;
  }
}

图片加载中...

最长递增子序列（LIS）

当存在大量节点移动时，简单的双端 Diff 会导致大量的 DOM 操作，Vue3 通过求最长递增子序列（LIS）来最小化移动次数。

1. 什么是最长递增子序列 给定一组数字，找到其中最长的递增子序列，序列中的元素不必连续，但顺序不能改变。 举例：

JAVASCRIPT复制
// 序列：[2, 5, 3, 7, 11, 8, 10, 13, 6]
// LIS：[2, 3, 7, 8, 10, 13]
// 长度为6

2. 在 Diff 中应用 LIS

   • 对比新旧节点时，找到哪些节点无需移动，这些节点的索引形成 LIS。
   • LIS 中的节点保持原位，其余节点执行移动操作。
   • 这样减少了大量不必要的 DOM 插入和删除。

3. 示例

JAVASCRIPT复制
// 假设新节点 key 索引映射到旧节点位置数组为：
// [2, 3, 1, 4, 5, 7, 6]
// LIS 找出最长递增子序列：
// [2, 3, 4, 5, 7]
// 对应的节点不移动，索引为1的节点需要移动。  O(n log n) 
function getLIS(arr) {
  const piles = [], predecessors = [], result = [];
  for(let i=0; i<arr.length; i++) {
    let left = 0, right = piles.length;
    while(left < right) {
      const mid = (left + right) >> 1;
      if(arr[piles[mid]] < arr[i]) left = mid + 1;
      else right = mid;
    }
    if(left > 0) predecessors[i] = piles[left-1];
    piles[left] = i;
  }
  let k = piles[piles.length -1];
  for(let i = piles.length-1; i>=0; i--) {
    result[i] = k;
    k = predecessors[k];
  }
  return result.map(i => arr[i]);
}

结合双端 Diff 和 LIS 的完整子节点更新流程

1. 使用双端指针快速过滤头尾相同节点。
2. 剩余中间部分通过 key 建立映射。
3. 生成新节点在旧节点的位置索引数组。
4. 计算 LIS，标记不移动的节点。
5. 对非 LIS 节点进行移动或插入操作。

React 与 Vue Diff区别

在上文里，我们介绍了 Vue 通过 PatchFlag、双端 Diff 和最长递增子序列（LIS）对比，尽量减少不必要的 DOM 操作。很多人会问：React 为什么没有采用完全一样的机制？ 其实，React 和 Vue 的设计哲学差异很大，直接影响了它们在 Diff 算法上的策略。

React 把模板视为纯 JavaScript 代码，运行时动态决定

React 的核心理念是一切都是 JavaScript，JSX 是 JavaScript 的语法糖，渲染过程本质是一个函数调用，所有结构和内容都在运行时计算。因此，React 在编译阶段无法像 Vue 那样进行静态分析和打标记，因为模板中的数据和逻辑只有运行时才能确定。

JSX复制
{list.map((item, index) => (
  index % 2 === 0
    ? <div>{item.name}</div>
    : <span>{item.name}</span>
))}

这个逻辑无法静态分析出哪些节点是稳定的，哪些是动态的。只有运行时才能知道list和index的值，渲染逻辑本质是纯JS，不是模板。 而Vue依赖模板编译器进行静态分析优化，Vue 把模板看作声明式语言，通过编译器提前解析模板结构、标记静态节点，利用 PatchFlag 精准更新，避免运行时大量不必要的比对。这让 Vue 在运行时能跳过静态内容的 Diff，极大提升效率，但对模板写法有一定限制。

React 为什么不使用双端 Diff + 最长递增子序列（LIS）？

Vue 的双端 Diff + LIS 能有效减少 DOM 移动。但 React 并没有引入这种方式，而是「基于 key 的简单映射 +最小操作集」，主要原因：

1. React 默认假设：子节点重排是罕见的
   • React 的设计哲学更接近「immutable data + key 显式标识」。
   • 如果需要频繁排序或重排，React 官方建议用 key 且尽量替换数组，而不是在同一数组里移动大量元素。
   • 所以对节点顺序的极致优化，React 没有放到最前。
2. 实现复杂度和可维护性
   • 双端 Diff + LIS 要比简单的「key 对应 +索引 diff」复杂很多，带来的性能收益只有在「大量节点重排」的场景才显著。
   • 大多数中小型应用不需要这么做。
3. Fiber 优先解决「可中断性」而不是「极致重排优化」
   • React 的核心痛点不是 Diff 性能瓶颈，而是一次性递归大树带来的主线程阻塞。
   • 所以 React 优先把精力投入到 Fiber（增量渲染）和调度，而不是先把 Diff 做到极致。

为什么 Vue 不需要 Fiber，而 React 需要？

Fiber 是 React 在 16 版本重构时提出的一种新架构，主要目标并不是让 Diff 性能极致，而是让渲染过程具备可中断、可恢复、可分片的能力，从而解决以下问题：

• 当组件树非常大时，React 一次递归整棵树会阻塞主线程，导致页面掉帧、卡顿。
• 当有高优先级更新（如输入、动画）时，React 无法中断当前的渲染任务立即响应。 所以 Fiber 本质上是一个基于链表的数据结构和调度器，把渲染拆分为很多小任务（Unit of Work），在浏览器空闲时间逐步执行（time slicing），必要时可以暂停和恢复，避免主线程长时间阻塞。 相比之下，Vue 并不需要 Fiber，原因主要有两点：

1. 相比之下，Vue 并不需要 Fiber，原因主要有两点： Vue 的核心是依赖追踪：每个响应式数据都知道哪些组件依赖它，一旦变更，只会更新对应的组件及其子树，而不是整个树。这样：
   • 更新粒度非常小。
   • 单次渲染的节点数量有限。
   • 同步递归的代价很低。 所以即使 Vue 没有中断机制，依然能在大多数情况下保持流畅。
2. 编译期优化（静态提升 + PatchFlag） Vue 的模板在编译阶段会标记哪些节点是静态的，哪些是动态的。渲染时只比对动态节点，进一步减少了需要递归的部分。 这就意味着：
   • 绝大多数节点根本不需要参与更新。
   • 更新工作非常轻量。

换句话说，Vue 通过依赖追踪 + 编译优化，把更新控制在非常小的范围，避免了“全量渲染 +全量 Diff”带来的性能压力，从根本上就不需要 Fiber 这种复杂的调度架构。 而 React 的理念是“每次状态变更都重新 render 整棵 Virtual DOM，再通过 Diff 找出变化”，所以在大型应用中，渲染和 Diff 的工作量都不可避免地增加。为了在保证一致性的同时避免阻塞，React 选择了 Fiber 架构，让 Diff 和渲染可以增量执行。

总结： Vue：通过依赖追踪精准定位需要更新的组件，避免全局 Diff，无需 Fiber。 React：以全量 render Virtual DOM 为核心，更新粒度较粗，需要 Fiber 来分片调度和中断渲染。