React篇 ｜ Diff算法

篇章过渡：前面 6 章我们把 CSS 的高频考点过了一遍——盒模型、选择器优先级、BFC、回流与重绘、移动端适配、预处理器。接下来进入 React 篇。React 是目前前端面试中权重最高的框架，从 Diff 算法、合成事件到并发模式、Server Components，每一个话题都值得深入理解。让我们从 React 的核心——Diff 算法开始。

前言

“React 的 Diff 算法”是前端面试中的经典考题，几乎每个面试官都会问。但很多人的回答只停留在”React 用虚拟 DOM 做 diff，然后更新真实 DOM”这个层面。

面试官真正想听的是：

• 虚拟 DOM 存在的意义到底是什么？是为了”更快”吗？
• React 的 Diff 做了哪些策略来把 O(n³) 降到 O(n)？
• key 到底起什么作用？为什么不能用 index 做 key？
• 单节点 Diff 和多节点 Diff 有什么区别？
• React 的 Diff 和 Vue 的 Diff 有什么不同？

本章就来把 Diff 算法从设计思路到实现细节彻底讲清楚。

诊断自测

Q1：传统的树 Diff 算法时间复杂度是 O(n³)，React 是怎么把它降到 O(n) 的？做了哪些假设？

Q2：下面两种渲染方式，哪种性能更好？为什么？

// 方式 A
list.map((item, index) => <ListItem key={index} data={item} />)

// 方式 B
list.map(item => <ListItem key={item.id} data={item} />)

一、为什么需要 Diff：虚拟 DOM 的意义

1.1 虚拟 DOM 不是为了”更快”

很多人以为虚拟 DOM 存在的原因是”操作虚拟 DOM 比操作真实 DOM 快”。这个说法不完全准确。

直接操作 DOM 当然可以更快——如果你确切地知道哪个节点需要改变，直接用 element.textContent = 'new text' 肯定比先创建虚拟 DOM、做 diff、再更新 DOM 要快。

虚拟 DOM 的真正价值在于：

1. 声明式编程：你只需要描述”UI 应该长什么样”，React 帮你算出”从当前 UI 到目标 UI 需要做哪些 DOM 操作”。这比你手动跟踪每个状态变化并精确地操作 DOM 要简单得多
2. 最小化 DOM 操作：虽然 diff 本身有开销，但它能算出最少的 DOM 操作。在复杂的 UI 更新中，这通常比”全量替换”（innerHTML）更快
3. 跨平台：虚拟 DOM 是一个抽象层，不仅可以渲染到浏览器 DOM，还可以渲染到 Native（React Native）、Canvas 等

1.2 Diff 的本质

Diff 算法要解决的问题是：给定两棵树（旧虚拟 DOM 树和新虚拟 DOM 树），找出最少的操作将旧树转换为新树。

传统的树 diff 算法（编辑距离问题）的最优时间复杂度是 O(n³)——对于一个 1000 个节点的页面，需要 10 亿次比较，完全不可用。

React 通过三个启发式策略将复杂度降到了 O(n)。

二、React Diff 的三个策略

2.1 策略一：Tree Diff（树级别）

假设：跨层级的节点移动非常罕见。

React 只对同一层级的节点做 diff。如果一个节点从 DOM 树的一个位置移到了另一个位置（比如从左侧栏移到主内容区），React 不会去”找”它，而是直接在旧位置删除、在新位置创建。

// 旧
<div>
  <A>
    <B />
    <C />
  </A>
</div>

// 新：把 A 移到了另一个位置
<div>
  <D>
    <A>
      <B />
      <C />
    </A>
  </D>
</div>

React 的处理：不是”把 A 从 div 移到 D 里面”，而是”在 div 下删除 A（及其子树），在 D 下创建 A（及其子树）”。

这个假设合理吗？ 在实际的 UI 开发中，跨层级移动 DOM 节点的情况确实很少。大多数 UI 变化都是同一层级内的增删改。即使有跨层级移动，React 也能正确处理（只是不够”高效”，但不会出错）。

2.2 策略二：Component Diff（组件级别）

假设：不同类型的组件生成完全不同的 DOM 结构。

当同一位置的组件类型发生变化时，React 不会尝试复用任何内部节点，而是直接销毁旧组件树并重建：

// 旧
<div>
  <Header />   {/* 类型：Header */}
  <Content />
</div>

// 新
<div>
  <NavBar />   {/* 类型变了：Header → NavBar */}
  <Content />
</div>

React 会完全销毁 <Header /> 的 Fiber 子树（包括所有子组件、DOM 节点、state），重新创建 <NavBar />。即使 Header 和 NavBar 的渲染结果非常相似，React 也不会复用。

如果两个不同类型的组件渲染结果很像呢？ 可以用 React.memo 或者让它们共享同一个组件类型来优化。但 React 故意不做这个优化，因为在绝大多数情况下，不同类型的组件确实会生成不同的 DOM 结构，做深度比较的开销反而更大。

2.3 策略三：Element Diff（元素级别）

同一层级的子元素通过 key 来标识。

这是三个策略中最复杂也最重要的。React 通过 key 来判断哪些子元素是”同一个”：

// 旧
<ul>
  <li key="a">Alice</li>
  <li key="b">Bob</li>
  <li key="c">Carol</li>
</ul>

// 新：在头部插入一项
<ul>
  <li key="d">Dave</li>   {/* 新增 */}
  <li key="a">Alice</li>  {/* 移动 */}
  <li key="b">Bob</li>    {/* 移动 */}
  <li key="c">Carol</li>  {/* 移动 */}
</ul>

有了 key，React 知道 a、b、c 是原来的节点（只需要移动位置），d 是新节点（需要创建）。如果没有 key，React 只能按顺序比较，认为每个位置的节点都变了。

三、key 的作用与原理

3.1 key 解决了什么问题？

没有 key 时，React 只能按**位置（index）**比较同一层级的子元素：

// 旧
<ul>
  <li>Alice</li>   {/* index 0 */}
  <li>Bob</li>     {/* index 1 */}
</ul>

// 新：在头部插入
<ul>
  <li>Dave</li>    {/* index 0 - React 认为 Alice 变成了 Dave */}
  <li>Alice</li>   {/* index 1 - React 认为 Bob 变成了 Alice */}
  <li>Bob</li>     {/* index 2 - React 认为这是新增的 */}
</ul>

没有 key 时，React 按位置比较：第 0 项从 Alice 变成 Dave → 更新；第 1 项从 Bob 变成 Alice → 更新；第 2 项是新增 → 创建。三个 DOM 操作。

有了 key，React 知道 Alice 和 Bob 是原来的（只是位置变了），Dave 是新的。一个创建 + 一个移动。更高效，且不会出现状态错乱。

3.2 key 的匹配规则

React 用 key 来建立新旧子元素之间的对应关系：

1. key 相同 + 类型相同 → 复用节点，只更新 props
2. key 相同 + 类型不同 → 销毁旧节点，创建新节点
3. 新列表中有旧列表没有的 key → 创建新节点
4. 旧列表中有新列表没有的 key → 销毁旧节点

3.3 为什么不能用 index 做 key？

// 初始列表
[
  { id: 1, text: 'Apple' },   // index 0, key=0
  { id: 2, text: 'Banana' },  // index 1, key=1
  { id: 3, text: 'Cherry' },  // index 2, key=2
]

// 删除第一项后
[
  { id: 2, text: 'Banana' },  // index 0, key=0 ← React 认为这是原来的 Apple！
  { id: 3, text: 'Cherry' },  // index 1, key=1 ← React 认为这是原来的 Banana！
]

用 index 做 key 时，删除第一项后，key 重新分配了。React 认为 key=0 的节点从 Apple 变成了 Banana（更新 props），key=1 的节点从 Banana 变成了 Cherry（更新 props），key=2 的节点消失了（删除）。

结果：React 做了 2 次更新 + 1 次删除 = 3 次操作。如果用 id 做 key，React 只需要做 1 次删除。

更严重的问题是状态错乱：

function TodoItem({ text }) {
  const [checked, setChecked] = useState(false);
  return (
    <li>
      <input type="checkbox" checked={checked} onChange={() => setChecked(!checked)} />
      {text}
    </li>
  );
}

如果用 index 做 key，删除第一项后，key=0 从 Apple 变成 Banana。但 key=0 的组件实例被复用了——它的 checked 状态还是 Apple 原来的值！用户看到的就是 Banana 的 checkbox 莫名其妙地被选中了。

3.4 什么时候可以用 index 做 key？

只有当列表满足以下所有条件时：

1. 列表不会重排序
2. 列表不会在头部或中间插入/删除
3. 列表项没有组件内部状态（纯展示）

在这种情况下，index 做 key 是安全的。但大多数情况下还是推荐用唯一标识符。

四、单节点 Diff vs 多节点 Diff

4.1 单节点 Diff

当新子节点是单个元素时（不是列表），React 的逻辑比较简单：

// 旧：多个子节点
<div>
  <p key="a">A</p>
  <p key="b">B</p>
</div>

// 新：单个子节点
<div>
  <p key="a">A updated</p>
</div>

单节点 Diff 的流程：

1. 新节点 key=“a”，遍历旧节点列表：
   • 旧节点 key=“a”，key 相同！检查类型：都是 p，类型也相同 → 复用
   • 旧节点 key=“b”，不需要了 → 删除
2. 如果 key 相同但类型不同：删除旧节点，创建新节点
3. 如果所有旧节点的 key 都不匹配：创建新节点，删除所有旧节点

4.2 多节点 Diff（两轮遍历）

当新子节点是列表时，React 使用一个两轮遍历的算法。这是 Diff 算法中最复杂的部分。

第一轮遍历：处理更新

React 同时遍历新旧列表，按位置一一比较：

旧: [A, B, C, D]
新: [A, B', E, D]
     ↓  ↓   ↓  ↓
     同  同  不同 → 退出第一轮

规则：

• 如果 key 相同且类型相同 → 复用节点，更新 props，继续
• 如果 key 相同但类型不同 → 标记为需要删除+创建，继续
• 如果 key 不同 → 立即停止第一轮遍历

第一轮遍历处理的是”头部连续相同部分”——这在实际场景中覆盖了大部分情况（比如只在尾部追加元素）。

第二轮遍历：处理新增、删除、移动

第一轮结束后，有几种情况：

情况一：旧列表遍历完了，新列表还有剩余 → 剩余的都是新增节点

旧: [A, B]      ← 遍历完了
新: [A, B, C, D]
              ^ ^
              新增

情况二：新列表遍历完了，旧列表还有剩余 → 剩余的都是需要删除的节点

旧: [A, B, C, D]
              ^ ^
              删除
新: [A, B]      ← 遍历完了

情况三：两边都还有剩余 → 需要处理移动。React 把旧列表的剩余部分放入一个 Map（key → Fiber），然后遍历新列表的剩余部分，逐个在 Map 中查找：

旧剩余: { C: FiberC, D: FiberD, E: FiberE }
新剩余: [D, C, F]

D → 在 Map 中找到 → 复用，标记移动
C → 在 Map 中找到 → 复用，标记移动
F → 在 Map 中没找到 → 创建新节点
E → Map 中剩余 → 删除

4.3 移动判断的细节

React 怎么判断一个节点需要”移动”？它维护一个 lastPlacedIndex（最后一个不需要移动的旧节点的索引）：

旧: [A(0), B(1), C(2), D(3)]
新: [A, C, B, D]

处理 A: 旧 index=0, lastPlacedIndex=0 → 不需要移动, lastPlacedIndex=0
处理 C: 旧 index=2, 2 >= 0 → 不需要移动, lastPlacedIndex=2
处理 B: 旧 index=1, 1 < 2 → 需要移动！（向右移动）
处理 D: 旧 index=3, 3 >= 2 → 不需要移动, lastPlacedIndex=3

规则：如果当前节点在旧列表中的 index < lastPlacedIndex，说明它相对于其他节点”向左”移了，需要一次 DOM 移动操作。

五、Vue Diff 对比

面试中经常会问到 React 和 Vue 的 Diff 有什么区别。两者的核心策略相似（同层比较、key 标识），但在多节点 Diff 的算法实现上有明显不同。

5.1 Vue 2 的双端对比算法

Vue 2 使用**双端对比（double-ended comparison）**算法。它同时从新旧列表的头和尾开始比较，有四个指针：

旧:  [A, B, C, D]
      ↑           ↑
    oldStart    oldEnd

新:  [D, A, B, C]
      ↑           ↑
    newStart    newEnd

四种比较：

1. oldStart vs newStart（头-头）
2. oldEnd vs newEnd（尾-尾）
3. oldStart vs newEnd（头-尾）
4. oldEnd vs newStart（尾-头）

如果上述四种都不匹配，才通过 key 在旧列表中查找。

5.2 Vue 3 的最长递增子序列

Vue 3 在双端对比的基础上，引入了**最长递增子序列（Longest Increasing Subsequence，LIS）**算法来最小化 DOM 移动操作。

旧: [A, B, C, D, E]
新: [A, D, B, E, C]

LIS = [D, E] (在旧列表中 index 为 [3, 4]，递增序列)
D 和 E 不需要移动，只需要移动 B 和 C

LIS 算法能找到最少的移动操作数。

5.3 React vs Vue Diff 对比

React 为什么不用双端比较？ React 的 Fiber 架构使用单向链表（child → sibling），不方便从尾部向前遍历。而 Vue 的 VNode 子节点是数组，可以直接从两端访问。React 团队认为单向遍历加上 Map 查找已经够用了，且在实际场景中性能差距很小。

常见误区

误区一：“虚拟 DOM 比真实 DOM 快”

不准确。单次精确的 DOM 操作永远比”创建虚拟 DOM → diff → 操作 DOM”这个过程快。虚拟 DOM 的价值在于自动化——你不需要手动跟踪哪些 DOM 需要更新，React 帮你算出最小的更新集合。在复杂的 UI 中，手动跟踪所有变化几乎不可能做到又正确又高效，虚拟 DOM 提供了一个性能足够好的自动化方案。

误区二：“不写 key 就会有 Bug”

不一定。如果列表是静态的（不增删、不重排），不写 key（或用 index 做 key）不会出问题。但如果列表有动态变化，没有稳定的 key 会导致性能下降和状态错乱。养成写 key 的习惯是好的，但要理解它具体解决什么问题。

误区三：“key 必须全局唯一”

不需要。key 只需要在同一层级的兄弟节点中唯一就行。不同列表、不同组件中的 key 互不影响。

// ✅ 这是合法的：两个列表中都有 key="1"
<ul>
  {users.map(u => <li key={u.id}>{u.name}</li>)}
</ul>
<ul>
  {teams.map(t => <li key={t.id}>{t.name}</li>)}
</ul>

误区四：“React 的 Diff 一定比 Vue 的差”

不能简单地这么说。在大多数实际场景中（尤其是尾部追加、少量更新），两者性能差距很小。Vue 的 LIS 算法在”大量乱序移动”的场景中确实更优，但这种场景在实际项目中并不常见。选择框架不应该基于 Diff 算法的理论差异。

小结

本章我们从虚拟 DOM 的意义出发，深入讲解了 React Diff 算法的三个核心策略和实现细节。

核心要点

1. 虚拟 DOM 的意义不是”更快”，而是声明式编程 + 自动化最小更新
2. 三个策略：Tree Diff（同层比较）、Component Diff（类型变化直接重建）、Element Diff（key 标识）
3. key 的作用：标识同层子元素的身份，实现高效的增删移动
4. 不要用 index 做 key（动态列表中），会导致性能下降和状态错乱
5. 单节点 Diff：在旧子节点中找 key 匹配且类型相同的节点复用
6. 多节点 Diff：两轮遍历——先处理头部相同部分，再用 Map 处理剩余的增删移动
7. Vue 对比：双端比较 + LIS 算法，在特定场景下移动操作更少，但实际差距通常很小

本章思维导图

练习挑战

第一题 ⭐（基础）：预测 Diff 行为

给定新旧列表，说出 React 会执行哪些 DOM 操作：

// 旧
<ul>
  <li key="a">Apple</li>
  <li key="b">Banana</li>
  <li key="c">Cherry</li>
</ul>

// 新
<ul>
  <li key="b">Banana</li>
  <li key="a">Apple (updated)</li>
  <li key="d">Date</li>
</ul>

第二题 ⭐⭐（进阶）：解释为什么这段代码有 Bug

function TodoList() {
  const [todos, setTodos] = useState([
    { text: 'Learn React' },
    { text: 'Build App' },
    { text: 'Deploy' },
  ]);

  const removeTodo = (index) => {
    setTodos(todos.filter((_, i) => i !== index));
  };

  return (
    <ul>
      {todos.map((todo, index) => (
        <li key={index}>
          <input type="text" defaultValue={todo.text} />
          <button onClick={() => removeTodo(index)}>Delete</button>
        </li>
      ))}
    </ul>
  );
}

用户操作：修改第一个 input 的值为 “Learn Vue”，然后点击第一项的 Delete。预期行为 vs 实际行为？

const [todos, setTodos] = useState([
  { id: crypto.randomUUID(), text: 'Learn React' },
  { id: crypto.randomUUID(), text: 'Build App' },
  { id: crypto.randomUUID(), text: 'Deploy' },
]);

// ...
{todos.map(todo => (
  <li key={todo.id}>
    {/* ... */}
  </li>
))}

第三题 ⭐⭐⭐（综合）：手写简化版 Diff

实现一个简化版的 list diff 算法，给定旧列表和新列表（每项有 key），输出需要执行的操作序列（INSERT / DELETE / MOVE）。

// 输入
const oldList = [{ key: 'a' }, { key: 'b' }, { key: 'c' }, { key: 'd' }];
const newList = [{ key: 'b' }, { key: 'a' }, { key: 'd' }, { key: 'e' }];

// 期望输出（操作顺序可能不同，但效果一致）
// DELETE key='c'
// MOVE key='a' (after 'b')
// INSERT key='e' (at end)

function diff(oldList, newList) {
  const operations = [];
  const oldMap = new Map(oldList.map((item, i) => [item.key, i]));
  const newMap = new Map(newList.map((item, i) => [item.key, i]));

  // 1. 找出需要删除的（在旧列表中但不在新列表中）
  for (const item of oldList) {
    if (!newMap.has(item.key)) {
      operations.push({ type: 'DELETE', key: item.key });
    }
  }

  // 2. 遍历新列表，找出需要插入和移动的
  let lastPlacedIndex = 0;
  for (let i = 0; i < newList.length; i++) {
    const key = newList[i].key;
    if (!oldMap.has(key)) {
      // 新增
      operations.push({
        type: 'INSERT',
        key,
        position: i,
      });
    } else {
      // 已存在，判断是否需要移动
      const oldIndex = oldMap.get(key);
      if (oldIndex < lastPlacedIndex) {
        operations.push({
          type: 'MOVE',
          key,
          position: i,
        });
      } else {
        lastPlacedIndex = oldIndex;
      }
    }
  }

  return operations;
}

const result = diff(oldList, newList);
console.log(result);
// [
//   { type: 'DELETE', key: 'c' },
//   { type: 'MOVE', key: 'a', position: 1 },
//   { type: 'INSERT', key: 'e', position: 3 },
// ]

自我检测

读完本章后，对照下面的清单检验一下自己的掌握程度。

• 能解释虚拟 DOM 存在的真正意义（不只是”更快”）
• 能说出 React Diff 的三个核心策略，以及它们背后的假设
• 能解释 key 的作用，并说出为什么不能用 index 做 key（包括性能和状态错乱两个角度）
• 能描述多节点 Diff 的两轮遍历流程
• 能用 lastPlacedIndex 判断哪些节点需要移动
• 能对比 React 和 Vue 的 Diff 算法差异（至少说出两点）
• 给定新旧列表，能预测 React 会执行哪些 DOM 操作