1 篇博文 含有标签「调和」

上一篇我们讲了 React 19 把属性级 diff（prepareUpdate/updatePayload）挪进了 commit 阶段。但大家常说的"React diff 算法"，其实指的是另一个完全不同的东西——子节点调和（reconciliation）：比较同一层级的 children，决定哪些 fiber 复用、哪些删除、哪些新建、哪些移动。

本文从源码角度拆解这个算法，核心是 reconcileChildrenArray 的四大步骤（这四步直接写在 React 源码 ReactChildFiber.js 的注释里）。先概述全局，再逐步骤分论。

1. 概述：diff 到底 diff 什么​

触发链​

beginWork
  └─ reconcileChildren(current, workInProgress, nextChildren)
       ├─ current === null  → mountChildFibers     (shouldTrackSideEffects = false)
       └─ current !== null  → reconcileChildFibers (shouldTrackSideEffects = true)
            ├─ 单个元素  → reconcileSingleElement
            ├─ 数组     → reconcileChildrenArray    ★ 本文主角（四大步骤）
            └─ 可迭代   → reconcileChildrenIteratable

关键点：diff 不在 commit 阶段，也不直接操作 DOM。它发生在渲染阶段，是纯 JS 的结构计算——产出的是新的 fiber 树 + 副作用标记（flags），真正的 DOM 增删改要等 commit 阶段才落地：

三个设计前提​

React 的 diff 不是"通用 diff"，它做了三个刻意的简化，才把复杂度压到 O(n)：

1. 只比较同一层级的兄弟节点——树形结构天然分层，不做跨层比较（跨层移动 = 先删后建）；
2. 用 key 识别"同一个节点"——key 相同才认为可以复用，这是复用的唯一依据；
3. 类型（type）不同直接销毁重建——一旦 type 变了（比如 <div> → <span>），就不再深入 diff，整个旧 fiber 作废。

这三个前提决定了 diff 的行为边界，也是面试里"为什么 React diff 是 O(n)"的标准答案。

2. 四大步骤总览​

reconcileChildrenArray 从头到尾就是四步——它对应源码里 reconcileChildrenArray 的四个结构分支：

1. Reconcile the children in the same order with the same key   → 前缀扫描复用
2. Delete the remaining old children when the new children are exhausted → 删除
3. Create new fibers for the remaining new children when the old children are exhausted → 新建
4. Reconcile the remaining children and clean up the old children → map 移动 + 清理

整体决策流程：

四个步骤互相衔接：能省则省。前两步（前缀复用、整段删除）是最常见的场景，走的都是"不建 Map"的快速路径；只有真正出现乱序/中间插入时才落到第 4 步建 Map。

3. Step 1：前缀扫描——同序同 key 复用​

这是 diff 的快速路径。同时从左到右遍历旧 fiber 链表和新 children，只要 key 匹配就复用旧 fiber（updateElement 原地更新 props），key 一旦不匹配立即 break：

// ReactChildFiber.js（简化示意）
for (; oldFiber !== null && newIdx < newChildren.length; newIdx++) {
  const newFiber = updateSlot(returnFiber, oldFiber, newChildren[newIdx]);
  if (newFiber === null) {
    break;                                    // ★ key 不匹配，停止前缀扫描
  }
  lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
  // ... 链接 sibling
}

updateSlot 的匹配逻辑（ReactChildFiber.js:811）——key 相等才继续，否则返回 null 表示"这一位对不上"：

function updateSlot(returnFiber, oldFiber, newChild, lanes) {
  const key = oldFiber !== null ? oldFiber.key : null;
  // ...文本节点：key 必须为 null 才可复用
  if (typeof newChild === 'object' && newChild !== null) {
    switch (newChild.$$typeof) {
      case REACT_ELEMENT_TYPE: {
        if (newChild.key === key) {           // ★ key 匹配 → 进入 updateElement
          return updateElement(returnFiber, oldFiber, newChild, lanes);
        } else {
          return null;                        // ★ key 不匹配 → break
        }
      }
    }
  }
  // ...
}

例子：[A, B, C, D] → [A, B, C, X]

A 匹配 → 复用  |  B 匹配 → 复用  |  C 匹配 → 复用  |  X 与 D 的 key 不同 → break

前三项零成本复用，只有 X 进入后面的步骤。append / 前缀删除这类最常见的操作，在 Step 1 就结束了，这也是 React 刻意保留"先正向扫描"的原因（源码注释里提到：先走 forward-only 路径，只有发现需要大量前瞻时才用 Map）。

4. Step 2：删除——新 children 耗尽，剩余旧的全删​

前缀扫描 break 时，如果 newIdx 已经等于新 children 长度，说明新列表走完了但旧列表还剩——剩下的旧 fiber 全部无用，一次性删除：

// ReactChildFiber.js（简化示意）
if (newIdx === newChildren.length) {
  deleteRemainingChildren(returnFiber, oldFiber);
  return resultingFirstChild;
}

deleteRemainingChildren → 逐个 deleteChild：

function deleteChild(returnFiber, childToDelete) {
  if (!shouldTrackSideEffects) return;        // mount 阶段不追踪
  const deletions = returnFiber.deletions;
  if (deletions === null) {
    returnFiber.deletions = [childToDelete];  // 挂在父 fiber 上
    returnFiber.flags |= ChildDeletion;      // ★ 打 ChildDeletion 标记
  } else {
    deletions.push(childToDelete);
  }
}

注意删除是"记账"不是真删：被删的 fiber 收集到 returnFiber.deletions 数组 + 打 ChildDeletion flag，commit 阶段才真正卸载 DOM 并执行 unmount effect。

例子：[A, B, C] → [A]：A 复用，B、C 在 Step 2 被标记删除。

5. Step 3：新建——旧 children 耗尽，剩余新的全建​

反过来，如果 break 时 oldFiber === null（旧链表走完了但新 children 还有），说明剩下的全是新增，走快路径批量 createChild：

// ReactChildFiber.js（简化示意）
if (oldFiber === null) {
  for (; newIdx < newChildren.length; newIdx++) {
    const newFiber = createChild(returnFiber, newChildren[newIdx]);
    if (newFiber === null) continue;
    lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
    // ... 链接 sibling
  }
  return resultingFirstChild;
}

createChild 按元素类型生成全新 fiber（createFiberFromElement / createFiberFromFragment / createFiberFromText），placeChild 会给它打 Placement 标记（commit 时插入 DOM）。

例子：[A] → [A, B, C]：A 复用，B、C 在 Step 3 新建并打 Placement。

6. Step 4：map 移动 + 清理——乱序 / 中间差异的核心​

走到这里说明新旧都还有剩余——要么 key 顺序乱了，要么中间插了东西。React 不能再线性对齐，于是把剩余旧 fiber 塞进一个 Map（按 key 索引），再逐个去"认领"：

// ReactChildFiber.js（简化示意）—— Step 4
const existingChildren = mapRemainingChildren(oldFiber);   // key → fiber（无 key 用 index）
for (; newIdx < newChildren.length; newIdx++) {
  const newFiber = updateFromMap(existingChildren, returnFiber, newIdx, newChildren[newIdx]);
  if (newFiber === null) continue;
  if (shouldTrackSideEffects) {
    if (newFiber.alternate !== null) {
      existingChildren.delete(newFiber.key == null ? newFiber.index : newFiber.key); // 认领后从 Map 删
    }
  }
  lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
  // ... 链接 sibling
}
// 遍历完，Map 里剩下的都是"新列表里已经不要了"的旧 fiber → 全部删除
existingChildren.forEach(child => deleteChild(returnFiber, child));

mapRemainingChildren 建 Map（ReactChildFiber.js:463）：有 key 用 key，没 key 用 index 兜底。

updateFromMap 负责"认领"（ReactChildFiber.js:941）：按 key（或 index）在 Map 里找匹配的旧 fiber → 找到且 type 匹配就 updateElement 原地复用；找不到就 createChild 新建。

例子：[A, B, C] → [C, A, D]

前缀扫描：A 对 C，key 不匹配 → break（进 Step 4）
建 Map：{A, B, C}
遍历新列表：
  C → Map 命中 → 复用 C，删 Map 里的 C，placeChild 判定移动
  A → Map 命中 → 复用 A，删 Map 里的 A，placeChild 判定移动
  D → Map 未命中 → createChild 新建
Map 剩余 {B} → B 已不在新列表 → deleteChild(B)

Step 4 用 O(1) 的 Map 查询替代了 O(n) 的线性查找，这是乱序场景下 diff 依然保持 O(n) 均摊的关键。

7. 移动判定：placeChild 与 lastPlacedIndex（最精妙的一步）​

四大步骤反复调用 placeChild，它决定一个复用节点是"待在原位"还是"要移动"。判据是 lastPlacedIndex——已放置的最右位置：

// ReactChildFiber.js（简化示意）
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 {
      return oldIndex;                        // 顺序保持 → 不动，更新最右位置
    }
  } else {
    newFiber.flags |= Placement;              // 全新 → 插入
    return lastPlacedIndex;
  }
}

直觉：我们从左到右扫描新列表，lastPlacedIndex 记录"已经就位的最靠右的旧位置"。如果一个节点旧的 index 比这个还小，说明它原本在左边、现在排到了右边——相对顺序变了，必须移动。

例子：[a, b, c, d] → [d, a, b, c]

d：oldIndex=3, lastPlacedIndex=0 → 3≥0 → 不动，lastPlacedIndex=3
a：oldIndex=0, lastPlacedIndex=3 → 0<3 → 移动（打 Placement）
b：oldIndex=1, lastPlacedIndex=3 → 1<3 → 移动
c：oldIndex=2, lastPlacedIndex=3 → 2<3 → 移动

结果：d 原位，a/b/c 各移动一次。这是 "只向前移动"的贪心（源码注释明确写了这个 limitation）：[d, a, b, c] 明明最优只需移 1 次（把 d 挪到末尾），React 却选择移 3 次（a/b/c 挪到 d 后面）。代价是"移动次数可能不是最优"，换来的是单次遍历、无需回溯的 O(n) 复杂度。源码注释：

"we only support moving a fiber forward, not backward… So we have to move 3 times to place a, b, c instead of moving 1 time to place d."

8. 单节点情况：reconcileSingleElement​

当新 children 是单个元素（不是数组）时走 reconcileSingleElement（ReactChildFiber.js:1634）。逻辑更直接——遍历旧链表找"对的那个"：

单节点不用建 Map，O(n) 线性扫一遍即可（旧链表通常很短）。

9. key 的意义与注意事项​

Step 1 和 Step 4 都依赖 key，key 是整套算法的"身份标识"。两条铁律：

1. key 要稳定且唯一——同一列表里不能重复，跨渲染不能变；
2. 别用 index 当 key——一旦在中间插入/删除元素，index 会整体位移，Step 1 的"同序同 key"匹配会认错节点，导致复用错乱的 fiber（state/DOM 对不上）。

反例：[A, B] → [X, A, B]，若用 index 当 key：

Step 1：X(index0) 对 A(index0) → key 都是 0 → 复用 A 的 fiber 渲染 X！❌ 状态错乱
        A(index1) 对 B(index1) → key 都是 1 → 复用 B 的 fiber 渲染 A！

而用稳定 key 时：X 找不到匹配 → 新建；A、B 的 key 匹配 → 正确复用，只有 X 一次插入。

10. 复杂度分析​

代价是 Step 1 的前缀扫描在"开头就乱序"的场景下白扫一部分，以及移动是贪心（非最优步数）——但换来的是绝对的单次遍历，这正是 React diff 敢声称 O(n) 的原因。

11. 一句话总结​

React 的 diff = 子节点调和：渲染阶段用 reconcileChildFibers 比较同层兄弟，通过前缀扫描复用 → 整段删除 → 整段新建 → Map 认领移动四大步骤，产出新的 fiber 树 + Placement/ChildDeletion 标记，commit 阶段才落地 DOM。O(n) 的秘密是"单次遍历 + key 的 O(1) 匹配 + 只向前移动的贪心"，而这一切都建立在三个前提上：只比同层、key 定身份、type 不同即重建。

参考​

• React 19.2.7 ReactChildFiber.js：reconcileChildrenArray(1124) / reconcileSingleElement(1634) / updateSlot(811) / placeChild(492) / mapRemainingChildren(463) / updateFromMap(941)