4.4 协调与 diff 策略

一句话：React 的 diff 只做「同层比较」「类型不同直接重建」「用 key 标识同一元素」三件事，把理论上 O(n³) 的树比较降到 O(n)——代价是放弃「跨层复用」。

一、为什么需要 diff，以及为什么是 O(n)

问题：如何把「旧元素树」变成「新元素树」？

理论最优（最小编辑距离）需要比较所有节点对：O(n³)
（n 个节点，两两比较是 O(n²)，每次比较还要递归子树）

对 1000 个节点的界面：O(n³) = 10^9 —— 完全不可接受

React 的策略是「放弃理论最优，换取可实现的高效」：
用三个【假设】把复杂度降到 O(n)

核心思想：
把「树与树的比较」降级为「同层数组的比较」——
因为「同层比较」后，问题变成「如何匹配两个数组的元素」，
而「用 key 匹配」让这个问题变成 O(n)。

二、单节点 diff

场景：父节点的新 children 是「单个元素」

比较逻辑（简化）：
① 先比较新元素与旧 fiber 的【key】
   · key 不同 → 认为「不是同一个」→ 删除旧节点，创建新节点
   · key 相同 → 继续比较
② key 相同 → 比较【type】
   · type 不同 → 删除旧的，创建新的
   · type 相同 → 复用 fiber（更新 props）

⚠️ 注意：React 在「单节点」情况下会做「key 与 type 的两轮比较」，
   目的是尽量复用（比如 key 相同但位置变了，依然可以复用）。

// 类型不同 → 整棵子树重建
function App({ isLink }) {
  return isLink ? <a href="/x">点击</a> : <button>点击</button>;
}
// <a> 与 <button> 类型不同 → 卸载前者、挂载后者
// ⚠️ 如果其中包含有状态的子组件，状态会丢失

// 一个经典的「类型不同导致状态丢失」的例子
function App({ isEditing }) {
  // ❌ 三元里两个分支的类型不同（两个不同的组件函数）→ 每次切换都重建
  return isEditing ? <EditForm /> : <ViewForm />;
}
// 这其实「符合预期」（确实是两个不同的东西）

// ⚠️ 真正的问题是「同一个组件但因为定义位置导致类型不同」
function Parent() {
  function Inner() {           // ❌ 每次渲染都是新的函数 → type 不同 → 重建
    const [x] = useState(0);
    return <div>{x}</div>;
  }
  return <Inner />;
}

三、多节点 diff（同层数组）

场景：父节点的 children 是一个【数组】（如 list.map(...)）

React 采用「两次遍历」的策略：

第一轮：处理「更新」（顺序不变或只是移动）
  · 从左到右遍历新旧数组
  · 用 key 匹配（没有 key 就用 index）
  · 遇到「没匹配上」或「key 不匹配」就跳出，进入第二轮

第二轮：处理「新增 / 删除 / 移动」
  · 遍历剩余的新节点 → 标记为「新增（Placement）」
  · 遍历剩余的旧节点 → 标记为「删除（Deletion）」

// React 多节点 diff 的核心逻辑（简化伪代码）
function reconcileChildrenArray(returnFiber, currentFirstChild, newChildren) {
  let oldFiber = currentFirstChild;
  let lastPlacedIndex = 0;          // ⭐ 记录「已复用的旧节点中最大的 index」
  let newIdx = 0;
  let nextOldFiber = null;

  // ===== 第一轮：按顺序匹配，处理「更新」=====
  for (; oldFiber !== null && newIdx < newChildren.length; newIdx++) {
    if (oldFiber.index > newIdx) {
      nextOldFiber = oldFiber;       // 位置不对，先留着
      oldFiber = null;
    } else {
      nextOldFiber = oldFiber.sibling;
    }

    const newFiber = updateSlot(returnFiber, oldFiber, newChildren[newIdx]);   // ⭐ 用 key 比较
    if (newFiber === null) break;    // key 不匹配 → 跳出，进入第二轮

    if (shouldTrackSideEffects) {
      if (oldFiber && newFiber.alternate === null) {
        deleteChild(returnFiber, oldFiber);     // 旧的没用上 → 删除
      }
    }
    lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);   // ⭐ 判断是否需要移动
    oldFiber = nextOldFiber;
  }

  // ===== 新增：新数组用完了，旧的还有 → 全部删除 =====
  if (newIdx === newChildren.length) {
    deleteRemainingChildren(returnFiber, oldFiber);
    return resultingFirstChild;
  }

  if (oldFiber === null) {
    // 旧的用完了，新的还有 → 全部新增
    for (; newIdx < newChildren.length; newIdx++) {
      const newFiber = createChild(returnFiber, newChildren[newIdx], newIdx);
      lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
    }
    return resultingFirstChild;
  }

  // ===== 第二轮：处理「移动」=====
  // 把剩余的旧节点放进 Map（key → fiber），方便 O(1) 查找
  const existingChildren = mapRemainingChildren(oldFiber);

  for (; newIdx < newChildren.length; newIdx++) {
    const newFiber = updateFromMap(existingChildren, returnFiber, newIdx, newChildren[newIdx]);
    if (newFiber !== null) {
      if (newFiber.alternate !== null) {
        existingChildren.delete(newFiber.key === null ? newIdx : newFiber.key);
      }
      lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);   // ⭐ 关键
    }
  }

  // 剩下的旧节点全部删除
  if (shouldTrackSideEffects) {
    existingChildren.forEach((child) => deleteChild(returnFiber, child));
  }

  return resultingFirstChild;
}

lastPlacedIndex 的作用（判断「是否需要移动」）：

function placeChild(newFiber, lastPlacedIndex, newIndex) {
  newFiber.index = newIndex;

  const current = newFiber.alternate;
  if (current !== null) {
    const oldIndex = current.index;
    if (oldIndex < lastPlacedIndex) {
      // ⭐ 旧位置在「已复用节点的最右位置」之左 → 需要移动
      newFiber.flags |= Placement;
      return lastPlacedIndex;
    } else {
      // 不需要移动，更新 lastPlacedIndex
      return oldIndex;
    }
  } else {
    // 新节点 → 需要插入
    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 被移动

// 说明：React 的算法「只保证移动最少的一侧」——它不做「最长递增子序列」优化，
//       所以某些情况下的移动次数不是理论最少。

四、与 Vue 的 diff 对比

Vue 3 的多节点 diff（双端 + LIS）：

① 双端比较：先比较「旧头 vs 新头」「旧尾 vs 新尾」，
   再比较「旧头 vs 新尾」「旧尾 vs 新头」
   → 快速处理「只在头尾增删」这类常见场景

② 对「乱序」的中间部分：
   · 为新节点建 key → index 的 Map
   · 找出「在旧数组中位置递增」的最长子序列（LIS）
   · 这个子序列里的节点【不需要移动】，其余标记移动

→ 结果：移动次数接近理论最少。
   而 React 的 lastPlacedIndex 算法是「单指针贪心」，可能多移动一些节点。

但要注意两点：

① Vue 的 diff 更快不代表「Vue 一定比 React 快」——
   React 的优化点在「组件级记忆化（memo/useMemo）与 Compiler」，
   而 Vue 的优化点在「编译时静态分析与细粒度响应式」

② 两者的「优化哲学」不同：
   React：运行时 diff + 手动/自动记忆化（信任组件的纯函数模型）
   Vue：  编译时分析 + 响应式依赖追踪（精确知道谁依赖谁）

五、同层比较的代价

// ❌ 跨层移动 → 整棵子树重建（状态丢失）
function App({ showHeader }) {
  return (
    <div>
      {showHeader && <Header />}
      <Main />                      {/* ⚠️ 当 showHeader 变化时，Main 的位置变了 */}
    </div>
  );
}
// 实际上：{showHeader && <Header />} 的位置始终存在（渲染为 false/null）
//         所以 Main 的位置不会变 → 这里不会触发重建

// 真正的跨层问题：
function App2({ isNested }) {
  if (isNested) {
    return (
      <div>
        <section><Main /></section>        {/* Main 在第 2 层 */}
      </div>
    );
  }
  return (
    <div>
      <Main />                              {/* Main 在第 1 层 */}
    </div>
  );
}
// ⚠️ Main 的层级变了 → 旧 fiber 在新位置找不到对应 → 卸载重建 → 状态丢失

// 用 key 保证「跨条件分支时复用同一实例」
function App3({ mode }) {
  return mode === 'a'
    ? <div><Content key="content" /></div>
    : <section><Content key="content" /></section>;
  // ⚠️ 即使 key 相同，父节点类型不同（div vs section）→ 依然会重建
}
// 结论：跨类型的父节点变化一定会重建子树，key 也救不了

六、常见坑

// ① 用 index 作 key（在「增删/排序」时导致错误的复用与状态错位）
{items.map((item, i) => <Row key={i} item={item} />)}     // ⚠️

// ② key 加在「内层元素」上
{items.map((item) => <div><Row key={item.id} /></div>)}   // ❌ 无效

// ③ 用「随机值」作 key（每次渲染都重建整列）
{items.map((item) => <Row key={Math.random()} />)}        // ❌ 灾难

// ④ 认为「key 只是为了避免警告」
// → 它决定「复用还是重建」，直接影响性能与状态正确性

// ⑤ 在条件渲染切换时「以为是同一个组件」
{isEditing ? <Form /> : <Form />}                        // 其实是同一个（type 相同）
{isEditing ? <EditForm /> : <ViewForm />}                // 类型不同 → 重建

// ⑥ 在组件内部定义组件（每次渲染类型都不同 → 整棵重建）
function Parent() {
  function Child() { return <div />; }                   // ❌
  return <Child />;
}

// ⑦ 用 key 强行「重置」组件但没意识到会「卸载重建」
<Form key={userId} />                                    // ✅ 这是正确用法（需要重置时）

// ⑧ 认为「子组件没变就不会重渲染」
// → diff 是「先渲染子组件（调用函数）再比较」的：
//    默认情况下父组件重渲染会「先执行子组件函数」，除非用 memo 跳过

// ⑨ 认为「React 的 diff 会做最优的移动」
// → 它用的是单指针贪心，移动次数不保证最少

// ⑩ 大列表「整体重排」时性能差 → 应该考虑虚拟滚动而非优化 diff
// ⑪ 用「对象/数组」作 key（每次渲染都是新引用 → 全部重建）
{items.map((item) => <Row key={{ id: item.id }} />)}     // ❌

七、面试延伸

1. 「React 的 diff 为什么是 O(n)？」
   因为 React 用了三个大胆的假设来降低复杂度：① 同层比较——只比较同一层级的节点（放弃「跨层移动最小化」）；② 类型不同直接重建——type 变了就卸载旧的、挂载新的（不做「同类型内的深度匹配」）；③ 用 key 标识同一元素——同层数组靠 key 匹配，把「数组匹配」变成 O(n)。三者结合，把理论上 O(n³) 的树编辑距离问题降为 O(n)。

2. 「React 的 diff 具体怎么比较两个数组？」
   用两次遍历：第一轮从左到右按顺序匹配（用 key 比较，能匹配上就复用它并更新 props），一旦匹配失败就跳出；第二轮处理剩余节点——把剩余的旧节点放进 Map（key → fiber）方便 O(1) 查找，然后遍历剩余的新节点，能在 Map 里找到就复用、找不到就新建，最后把 Map 里剩下的旧节点全部删除。判断「是否需要移动」用的是 lastPlacedIndex 单指针。

3. 「lastPlacedIndex 是干什么的？」
   它记录「已复用的旧节点中最大的 index」。对每个复用节点，如果它的旧 index 小于 lastPlacedIndex，说明「它在旧数组中的位置在某个已复用节点的左边」，而现在要放到右边 → 需要移动（标记 Placement），否则不需要移动。这是 React 「判断移动」的核心逻辑。要注意：它是单指针贪心，不保证移动次数最少（这点与 Vue 的 LIS 优化不同）。

4. 「key 在 diff 里起什么作用？」
   key 是「同层元素的身份标识」——React 用「key 是否相同」判断「新旧两个元素是否是同一个」，从而决定「复用原有的 fiber（保留 DOM 与状态）」还是「销毁旧的、创建新的」。所以：用稳定唯一的 key → 正确的复用（性能与状态都对）；用 index 或随机值 → 导致错误的复用（状态错位）或全量重建（性能灾难）。

5. 「什么情况下 React 会重建整棵子树？」
   四种：① type 不同（div → span、A → B，包括「在组件内部定义组件」这种情况）；② key 不同；③ 跨层级移动（同层比较的代价——节点从第 1 层挪到第 2 层就找不到了）；④ 父节点的类型变化导致跳过了整棵子树的复用判断。重建的后果是「DOM 与组件状态全部丢弃重建」（输入框失焦、动画重置、请求重发）。

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

7. 「为什么说『同层比较』是 React diff 的代价？」
   因为它意味着「跨层级移动节点会被视为「删除 + 新建」」。例如把 <Main /> 从 <div> 的直接子节点移到 <div><section> 里——React 在第 2 层找不到对应的旧 fiber，于是卸载重建，子组件的状态全部丢失。这是「用 O(n) 换正确性」的代价：React 假设「开发者不会频繁地跨层移动节点」，而这个假设在绝大多数业务代码里成立。

8. 「怎么避免不必要的重建？」
   四条建议：① 列表用稳定唯一 key（不要用 index/随机值）；② 不要在组件内部定义组件（每次都是新 type → 整棵重建）；③ 避免跨层级移动节点（保持 DOM 结构稳定，用条件渲染而不是改变嵌套层级）；④ 需要重置状态时主动用 key（如 <Form key={userId} /> 是「有意的重建」，与「意外的重建」不同）。

一句话速记

React diff 靠三个假设降到 O(n)：同层比较、类型不同直接重建、用 key 标识同一元素；多节点 diff 是「两轮遍历」——第一轮按 key 顺序匹配「更新」，第二轮用 Map 处理「新增/删除/移动」，移动判定靠 lastPlacedIndex 单指针（不保证最少移动，而 Vue 用双端 + LIS 更优）；key 决定「复用还是重建」（index → 状态错位，随机值 → 全量重建）；type 变化、key 变化、跨层移动、组件内定义组件都会导致整棵子树重建（状态丢失）。