12.5 diff 为什么是 O(n)

一句话：React 用三个假设——「只做同层比较」「type 不同直接重建」「用 key 标识同层元素」——把「树的最小编辑距离」的理论复杂度 O(n³) 降到了 O(n)，代价是放弃「跨层复用」。

一、结论先行

问题：React 的 diff 为什么是 O(n)？

一句话回答：
  因为 React 用三个假设把「树比较」降级成了「同层数组比较」：
  ① 只比较同一层级的节点（不跨层移动）
  ② type 不同就直接卸载重建（不做深比较）
  ③ 同层数组用 key 匹配（把「数组匹配」变成「用 key 查表」）
  → 三者结合，复杂度从 O(n³) 降到 O(n)。

⭐ 关键词：三句话 = 同层比较 + 类型不同重建 + key 匹配

二、为什么朴素的树比较是 O(n³)

问题：如何把「旧树」变成「新树」，且操作最少？

理论上这是「树的编辑距离」问题：
① 需要枚举「旧树中的任一节点」与「新树中的任一节点」的对应关系
   → 两两组合是 O(n²)
② 对每一对候选节点，还要「递归比较它们的子树」
   → 每次 O(n)
→ 总共 O(n³)

对 1000 个节点的界面：1000³ = 10⁹ 次操作 → 完全不可接受（一帧只有 16ms）

⭐ 所以 React 的策略是「放弃理论最优，换取可实现的高效」：
  用「工程假设」把问题简化，代价是「某些场景下复用不够充分」。
  这是典型的「工程权衡」——不是「算法最优」，而是「在真实场景下足够好用」。

三、三个假设（逐个说清）

假设一：同层比较

只比较「同一层级」的节点，不跨层移动。

✅ 成立场景：绝大多数业务代码「节点不会跨层移动」
❌ 代价：跨层移动会被视为「删除 + 新建」

例：
  <div><Main /></div>           →   <div><section><Main /></section></div>
  Main 从「第 1 层」挪到「第 2 层」→ 旧 fiber 在新位置找不到 → 卸载重建 → 状态丢失

⭐ 为什么能降到 O(n)？
  因为「只在同层比较」后，问题变成「两个同层数组的比较」——
  而「数组比较」可以在 O(n) 内完成（见假设三）。

假设二：type 不同直接重建

`type`（字符串 'div' 或 组件函数）不同 → 直接卸载旧节点、创建新节点。

✅ 成立场景：`div` → `span`、组件 A → 组件 B 确实「是不同东西」
❌ 代价：「同类型内的深度匹配」被放弃

例：
  {isLink ? <a>点击</a> : <button>点击</button>}
  → type 不同 → 重建（如果里面有状态，状态丢失）

⭐ 为什么这样设计？
  ① 「复用」在这种情况下意义不大（属性、行为、子结构都可能完全不同）
  ② 「深度匹配」成本高、收益不确定
  ③ 简单 = 可预测（开发者容易理解「什么时候会重建」）

假设三：key 标识同层元素

同层数组用 `key` 判断「是否是同一个元素」：
· key 相同 + type 相同 → 复用
· 否则 → 重建

✅ 效率：用「key → fiber」的 Map 查找，把「数组匹配」变成 O(n)
❌ 代价：需要开发者提供「稳定唯一的 key」（用 index 会出 bug）

⭐ 三者结合的效果：
  ① 同层比较 → 把「树比较」变成「数组比较」
  ② type 判断 → 快速决定「能否复用」
  ③ key 匹配 → 把「数组匹配」变成 O(n) 的查表

  → 总复杂度 O(n)（每层 O(该层节点数)，加起来 O(n)）

四、多节点 diff 的具体流程

⭐ 真实 React 用「两轮遍历」：

第一轮：从左到右「按顺序用 key 比较」（处理「更新」）
  · 能匹配上 → 复用并更新 props
  · 一旦匹配失败（key 不同 / 新的用完了）→ 跳出，进入第二轮

第二轮：处理「新增 / 删除 / 移动」
  · 把「剩余的旧节点」放进 Map（key → fiber）
  · 遍历「剩余的新节点」：
      - Map 里能找到 → 复用（并按 lastPlacedIndex 判断是否需要移动）
      - 找不到 → 新建
      - Map 里剩余的 → 最后统一删除

// 移动判定的核心（简化）
function placeChild(newFiber, lastPlacedIndex, newIndex) {
  newFiber.index = newIndex;

  const oldIndex = newFiber.alternate?.index;
  if (oldIndex !== undefined) {
    if (oldIndex < lastPlacedIndex) {
      // ⭐ 旧位置在「已复用节点的最右位置」之左 → 需要移动
      newFiber.flags |= Placement;
      return lastPlacedIndex;              // 不更新
    }
    return oldIndex;                        // 不需要移动 → 更新 lastPlacedIndex
  }

  // 新节点 → 插入
  newFiber.flags |= Placement;
  return lastPlacedIndex;
}

⭐ 举例：[A, B, C] → [C, A, B]（都有稳定 key）

C：旧 index = 2 ≥ lastPlacedIndex(0) → 不移动，lastPlacedIndex = 2
A：旧 index = 0 < lastPlacedIndex(2)  → 标记移动（Placement）
B：旧 index = 1 < lastPlacedIndex(2)  → 标记移动（Placement）

结果：C 留在原位（复用），A、B 被移动。

⚠️ 关键理解：这是「单指针贪心」——**不保证移动次数最少**。
   （Vue 3 用「双端比较 + 最长递增子序列（LIS）」更接近最少移动。）

五、与 Vue 的 diff 对比

⭐ 一句话区分两者的优化哲学：
· React：运行时 diff + 记忆化（memo/useMemo/Compiler）
· Vue：  编译时静态分析（知道哪个节点是动态的）+ 响应式依赖追踪

⚠️ 但「Vue 的 diff 更快」≠「Vue 一定比 React 快」——
   两者优化点不同（React 的收益在「组件级记忆化与 Compiler」）。

六、这个设计的代价

① 跨层移动 → 整棵子树重建（状态丢失）
   例：把 <Main /> 从 <div> 挪到 <div><section> 里面

② `type` 变化 → 重建
   例：三元里两个不同的组件、在组件内部定义组件

③ 需要「开发者提供正确的 key」
   例：用 index 作 key → 状态错位（见 12.4）

⭐ 但这三个「代价」在真实业务代码里都「很少发生」——
   所以 React 的假设是「实用的」：
   「开发者不会频繁跨层移动节点、不会频繁改 type、会提供正确的 key」。

七、常见追问

Q: 为什么不能「跨层比较」？
A: 因为「跨层匹配」需要「把每个节点与其它层级的每个节点比较」（O(n²) 的组合），
   再加上递归子树 → O(n³)。React 选择「不做」，换来 O(n)。

Q: 「同层」是指「同一个父元素的直接子元素」吗？
A: 是。React 比较的是「某个父元素的 children 数组」。
   所以「跨层」= 「同一个节点出现在不同父元素的 children 里」。

Q: keys 相同但 type 不同会怎样？
A: 仍然重建（type 是更强的判断依据）。

Q: 为什么第一轮要「跳出」？
A: 因为「顺序匹配失败」意味着后面可能有「插入/删除/移动」，
   用「顺序匹配」已经无法正确处理（需要 key → fiber 的 Map）。

Q: 移动判定为什么要用「旧 index」而不是「新 index」？
A: 因为我们要判断「这个节点是否需要从原位移走」——
   如果它的「旧位置」在「已复用节点的最右位置」的左边，
   而它现在要渲染到右边 → 必须移动。

Q: React 的 diff 会「保证最少移动」吗？
A: 不会。它是「单指针贪心」——在「倒序」等场景下会移动更多节点。
   Vue 3 的 LIS 优化才接近「最少移动」。

Q: DOM 操作的数量级是多少？
A: O(n) 次「比较」，但「移动」的次数取决于具体情况（最坏 O(n)）。
   由于「移动」比「创建」便宜（复用 DOM、只改顺序），所以整体是可接受的。

Q: Fragment 会影响 diff 吗？
A: 会（但影响很小）。Fragment 是「不产生 DOM 的包装」，
   它的 children 会「提升」到父层进行比较；
   多包一层 Fragment 有时会让「同层比较」的范围变化。

八、常见坑

// ① 在渲染中「跨层移动节点」（导致整棵子树重建）
// ② 用 index 作 key（状态错位）
// ③ 用随机值作 key（整列重建）
// ④ 在组件内部定义组件（type 每次都是新的 → 重建）
// ⑤ 认为「key 相同就一定复用」（type 也要相同）
// ⑥ 认为「React 的 diff 保证最少移动」（它是贪心）
// ⑦ 为了「避免重建」而用 key 强行保持身份（但语义上确实是不同的东西）
//    → 会导致「状态串味」（如两个不同的文档共用同一个编辑器的状态）
// ⑧ 在大列表里「整体重排」却期待高性能（应该考虑虚拟滚动）
// ⑨ 认为「虚拟 DOM 让 DOM 操作最少」（它只是「不手动优化时的好默认」）
// ⑩ 把「diff」与「虚拟 DOM」混为一谈（diff 是「比较算法」，
//    虚拟 DOM 是「用对象描述 UI」的手段；两者配合但要分开说）

九、面试延伸

1. 「React 的 diff 为什么是 O(n)？」
   因为 React 用了三个工程假设：① 同层比较——只比较「同一个父元素的 children」，不做跨层匹配（跨层移动会被当成「删除 + 新建」）；② type 不同直接重建——div→span、组件 A→组件 B 就卸载重挂（不做「同类型内的深度匹配」）；③ 用 key 标识同层元素——把「数组匹配」变成「用 key 查 Map」。三者结合把「树编辑距离」的理论 O(n³) 降到了 O(n)。

2. 「为什么朴素的树比较是 O(n³)？」
   因为它需要「枚举新旧树中任意两个节点的对应关系」（两两组合是 O(n²)），并且对每一对候选还要「递归比较它们的子树」（每次 O(n)）——乘起来是 O(n³)。对 1000 个节点就是 10⁹ 次操作，远超一帧的 16ms 预算。所以 React 选择了「放弃理论最优、换取可实现的高效」——这是工程权衡而不是算法最优。

3. 「多节点 diff 具体怎么做？」
   两轮遍历：① 第一轮——从左到右「按顺序用 key 比较」，能匹配就复用并更新 props（处理「更新」场景），一旦匹配失败就跳出；② 第二轮——把「剩余的旧节点」放进 Map（key → fiber），遍历「剩余的新节点」：能在 Map 里找到就复用（并按 lastPlacedIndex 判断是否需要移动），找不到就新建；最后把 Map 里剩余未复用的旧节点全部删除。

4. 「lastPlacedIndex 是干什么的？」
   它记录「已经复用的旧节点中最大的 index」。对一个「本轮复用」的节点：如果它的旧 index 小于 lastPlacedIndex，说明「它在旧数组里的位置在某个已复用节点的左边」，而现在要渲染到右边 → 需要移动（insertBefore），否则不需要。这是 React「判断移动」的核心逻辑，是单指针贪心（不保证移动次数最少）。

5. 「React 和 Vue 的 diff 有什么区别？」
   三方面：① 移动判定——React 用 lastPlacedIndex 单指针贪心（不保证最少），Vue 3 用「双端比较 + 最长递增子序列（LIS）」（接近最少移动）；② 编译时优化——Vue 3 有 PatchFlags / Block Tree / 静态提升（编译时就知道「哪些节点是动态的」），React 主要靠运行时（memo/useMemo，以及新的 Compiler）；③ 更新粒度——Vue 是「细粒度响应式」（精确知道「哪个节点依赖哪个数据」），React 是「组件级」（默认「整棵未被 memo 拦住的子树都会重新执行」）。

6. 「同层比较的代价是什么？」
   代价是「跨层移动会被视为『删除 + 新建』」——例如把 <Main /> 从 <div> 的直接子节点移到 <div><section> 里，React 在第 2 层找不到对应的旧 fiber，于是卸载重建，Main 的所有状态丢失（输入内容、滚动位置、动画进度）。这是「用 O(n) 换正确性」的代价：React 假设「开发者不会频繁跨层移动节点」，这个假设在业务代码里基本成立。

7. 「为什么 React 不做『最优移动』？」
   因为「最优移动」（如 LIS）需要「更复杂的预处理与数据结构」（在运行时计算最长递增子序列），这对「JS 执行时间」有成本，而收益只体现在「特定场景」（如整体倒序）。React 的取舍是「算法简单 + 结果够用」——因为「移动 DOM」本身比「计算最少移动序列」更便宜（移动只是改顺序，不创建节点），所以在多数场景下「多移动几次」比「多算一会儿」划算。Vue 3 选择了另一条路（把 LIS 放在编译时/运行时的一小段里，换取更少移动）。

8. 「这些假设在什么情况下会『不成立』？」
   三种：① 跨层移动——如果代码里频繁把节点在不同层间转移（比如用「条件渲染 + 不同嵌套」），会导致「大量无谓重建」；② type 频繁变化——如在渲染中根据条件切换「完全不同的组件」（这通常是对的，但会丢状态）；③ key 不稳定——用 index/随机值，让 React 无法正确判断身份。最实用的改进是「保持结构稳定 + 提供稳定唯一 key」——绝大多数性能问题都能靠这两条解决（剩下的交给虚拟滚动/记忆化）。

一句话速记

React 的 diff 靠三个假设降到 O(n)：同层比较（不做跨层匹配） + type 不同直接重建 + 用 key 标识同层元素（把数组匹配变成查 Map）；朴素树比较是 O(n³)（节点两两组合 O(n²) × 递归子树 O(n)），React 用「工程假设换可实现的高效」；多节点 diff 是两轮遍历（第一轮顺序 key 匹配 + 第二轮 Map 处理增删移），移动判定用 lastPlacedIndex（单指针贪心，不保证最少移动）；Vue 3 用「双端 + LIS」更接近最少移动，并有大量编译时优化（PatchFlags/Block Tree）；代价是「跨层移动 → 重建」与「type 变化 → 重建」；实用改进只有两条：保持结构稳定 + 提供稳定唯一 key。