第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 三条启发式假设

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

tsx

// 假设一：类型改变 = 整棵子树重建
// 当 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` 区分

tsx

// 假设二：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：

typescript

// 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）：

typescript

// 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;
}

5.3 单节点 Diff

单节点 Diff 处理的是 children 为单个 ReactElement 的情况。这是最简单的场景，但其中的细节依然值得深究。

typescript

function reconcileSingleElement(
  returnFiber: Fiber,
  currentFirstChild: Fiber | null,
  element: ReactElement,
  lanes: Lanes
): Fiber {
  const key = element.key;
  let child = currentFirstChild;

  // 遍历旧的所有同级 Fiber，尝试找到可复用的
  while (child !== null) {
    if (child.key === key) {
      // key 匹配
      const elementType = element.type;

      if (child.elementType === elementType) {
        // key 和 type 都匹配 → 找到了！
        // 删除剩余的旧兄弟节点（因为新的只有一个）
        deleteRemainingChildren(returnFiber, child.sibling);

        // 复用这个 Fiber，更新 props
        const existing = useFiber(child, element.props);
        existing.ref = coerceRef(returnFiber, child, element);
        existing.return = returnFiber;
        return existing;
      }

      // key 匹配但 type 不匹配
      // 说明这个位置的节点类型变了，旧节点和它的所有兄弟都不可能被复用
      deleteRemainingChildren(returnFiber, child);
      break;
    } else {
      // key 不匹配，标记这个旧节点为删除，继续查找下一个
      deleteChild(returnFiber, child);
    }
    child = child.sibling;
  }

  // 没有找到可复用的 Fiber，创建新的
  const created = createFiberFromElement(element, returnFiber.mode, lanes);
  created.ref = coerceRef(returnFiber, currentFirstChild, element);
  created.return = returnFiber;
  return created;
}

这段代码的逻辑可以用一个决策树来表示：

图 5-2：单节点 Diff 的决策流程

key 匹配但 type 不匹配的特殊处理

注意一个重要的细节：当 key 匹配但 type 不匹配时，React 会删除所有旧的子节点（包括尚未遍历到的兄弟节点）。为什么？

tsx

// 场景：key 匹配但 type 不同
// 旧的 children
<>
  <div key="main">Hello</div>
  <span>World</span>
</>

// 新的 children（单个元素）
<section key="main">Hi</section>

// React 的推理：
// 1. 新的只有一个元素，key="main"
// 2. 旧的第一个 child key="main"，匹配！
// 3. 但 type 从 div → section，不匹配
// 4. 既然 key 相同但 type 变了，说明这个节点被"就地替换"了
// 5. 那么旧的其他兄弟节点（<span>）也一定不再需要了
// 6. 所以 deleteRemainingChildren 删除所有剩余旧节点

第5章 Reconciliation：Diff 算法的真相 ​

5.1 三条启发式假设 ​

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

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

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

5.2 Diff 算法的入口：reconcileChildren ​

5.3 单节点 Diff ​

key 匹配但 type 不匹配的特殊处理 ​

第5章 Reconciliation：Diff 算法的真相

5.1 三条启发式假设

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

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

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

5.2 Diff 算法的入口：`reconcileChildren`

5.3 单节点 Diff

key 匹配但 type 不匹配的特殊处理