第5章 Reconciliation：Diff 算法的真相

本章要点

• Reconciliation 的本质：将树的 O(n³) 比较降低到 O(n) 的工程权衡
• React 的三条 Diff 启发式假设及其背后的统计学依据
• 单节点 Diff：type 和 key 的双重匹配策略
• 多节点 Diff：两轮遍历算法的完整实现
• key 的真正作用：不只是消除警告，而是 Diff 算法的核心线索
• beginWork 中各类组件的协调策略差异
• Diff 算法的局限性与常见的性能陷阱

---

每当你调用 setState 触发一次更新，React 都会面临一个看似简单实则极其复杂的问题：如何高效地找出新旧两棵树之间的差异？

在计算机科学中，这个问题被称为"树的编辑距离"（Tree Edit Distance），它的最优通用解法的时间复杂度是 O(n³)——其中 n 是树中的节点数。对于一个拥有 1000 个节点的 React 组件树（这在实际应用中并不罕见），O(n³) 意味着需要进行 10 亿次比较。在 60fps 的帧预算内，这显然是不可接受的。

React 的解决方案不是找到一个更好的通用算法，而是改变问题本身。通过引入三条基于 UI 开发实践的启发式假设，React 将 O(n³) 的问题降低为了 O(n)——代价是在极少数违反假设的场景下，更新不是最优的。但在 99.9% 的实际场景中，这些假设都是成立的。

这就是 Reconciliation——React 最核心的算法。

5.1 三条启发式假设

假设一：不同类型的元素产生不同的树

// 假设一：类型改变 = 整棵子树重建
// 当 type 从 div 变为 span，React 不会尝试复用任何子节点

// 更新前
<div>
  <Counter />
  <UserProfile name="Alice" />
</div>

// 更新后（div → section）
<section>
  <Counter />
  <UserProfile name="Alice" />
</section>

// React 的处理：
// 1. 销毁整个 <div> 子树（包括 Counter 和 UserProfile 的状态）
// 2. 从零开始创建 <section> 子树
// 3. Counter 的 state 被重置，UserProfile 被重新挂载

为什么不尝试复用？因为在实际开发中，类型改变几乎总是意味着 UI 结构发生了本质变化。<div> 变成 <article> 可能只是标签换了，但 <Input> 变成 <Select> 则意味着完全不同的行为和状态模型。React 选择用"偶尔多做一点工作"来换取"算法实现的简单性和可预测性"。

假设二：同一层级的子元素通过 key 区分

// 假设二：React 只在同一层级内进行 Diff，不跨层级比较

// 更新前
<div>
  <A />
  <B />
  <C />
</div>

// 更新后
<div>
  <A />
  <C />
  <B />
</div>

// React 不会发现"B 和 C 交换了位置"（没有 key 的情况下）
// 它会按位置逐个比较：
// 位置 0: A → A ✓ 复用
// 位置 1: B → C ✗ 类型不同，销毁 B，创建 C
// 位置 2: C → B ✗ 类型不同，销毁 C，创建 B

// 但如果有 key：
<div>
  <A key="a" />
  <C key="c" />
  <B key="b" />
</div>

// React 通过 key 识别出这是顺序变化：
// key="a": A → A ✓ 复用
// key="c": C 移到位置 1 → 复用
// key="b": B 移到位置 2 → 复用
// 没有任何组件被销毁和重建

假设三：同类型组件的子树结构通常相似

这条假设是隐含的：如果两个元素的 type 和 key 都相同，React 假设它们的子树结构大致相同，值得递归进去做 Diff。这避免了在发现节点匹配后还要评估"是否值得复用"的额外开销。

图 5-1：通用 Diff vs React Diff 的复杂度对比

5.2 Diff 算法的入口：reconcileChildren

在 Fiber 架构中，Diff 算法发生在 beginWork 阶段。每个 Fiber 节点在处理时会调用 reconcileChildren 来比较新旧 children：

// packages/react-reconciler/src/ReactFiberBeginWork.js
function reconcileChildren(
  current: Fiber | null,
  workInProgress: Fiber,
  nextChildren: any, // ReactElement | ReactElement[] | string | number | ...
  renderLanes: Lanes
) {
  if (current === null) {
    // 首次挂载：没有旧 Fiber，所有子节点都是新建
    workInProgress.child = mountChildFibers(
      workInProgress,
      null,
      nextChildren,
      renderLanes
    );
  } else {
    // 更新：有旧 Fiber，需要 Diff
    workInProgress.child = reconcileChildFibers(
      workInProgress,
      current.child, // 旧的第一个子 Fiber
      nextChildren,  // 新的 children（ReactElement）
      renderLanes
    );
  }
}

mountChildFibers 和 reconcileChildFibers 实际上是同一个函数 createChildReconciler 的两个实例，区别在于是否标记副作用（side effects）：

// packages/react-reconciler/src/ReactChildFiber.js
export const reconcileChildFibers = createChildReconciler(true);  // 标记副作用
export const mountChildFibers = createChildReconciler(false);     // 不标记副作用

function createChildReconciler(shouldTrackSideEffects: boolean) {
  // 返回一个闭包，内部包含所有 Diff 相关的函数

  function reconcileChildFibers(
    returnFiber: Fiber,
    currentFirstChild: Fiber | null,
    newChild: any,
    lanes: Lanes
  ): Fiber | null {
    // 根据 newChild 的类型分发到不同的处理逻辑
    if (typeof newChild === 'object' && newChild !== null) {
      switch (newChild.$$typeof) {
        case REACT_ELEMENT_TYPE:
          // 单个 ReactElement
          return placeSingleChild(
            reconcileSingleElement(returnFiber, currentFirstChild, newChild, lanes)
          );
        case REACT_PORTAL_TYPE:
          // Portal
          return placeSingleChild(
            reconcileSinglePortal(returnFiber, currentFirstChild, newChild, lanes)
          );
        case REACT_LAZY_TYPE:
          // Lazy 组件
          // ...
      }

      if (isArray(newChild)) {
        // 多个子节点（数组）
        return reconcileChildrenArray(returnFiber, currentFirstChild, newChild, lanes);
      }

      if (getIteratorFn(newChild)) {
        // 可迭代对象
        return reconcileChildrenIterator(returnFiber, currentFirstChild, newChild, lanes);
      }
    }

    if (typeof newChild === 'string' || typeof newChild === 'number') {
      // 文本节点
      return placeSingleChild(
        reconcileSingleTextNode(returnFiber, currentFirstChild, '' + newChild, lanes)
      );
    }

    // 其他情况（null, undefined, boolean）：删除所有旧子节点
    return deleteRemainingChildren(returnFiber, currentFirstChild);
  }

  return reconcileChildFibers;
}