上一篇我们讲了 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)：
- 只比较同一层级的兄弟节点——树形结构天然分层，不做跨层比较（跨层移动 = 先删后建）；
- 用
key 识别"同一个节点"——key 相同才认为可以复用，这是复用的唯一依据；
- 类型（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：
for (; oldFiber !== null && newIdx < newChildren.length; newIdx++) {
const newFiber = updateSlot(returnFiber, oldFiber, newChildren[newIdx]);
if (newFiber === null) {
break;
}
lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
}
updateSlot 的匹配逻辑（ReactChildFiber.js:811）——key 相等才继续，否则返回 null 表示"这一位对不上"：
function updateSlot(returnFiber, oldFiber, newChild, lanes) {
const key = oldFiber !== null ? oldFiber.key : null;
if (typeof newChild === 'object' && newChild !== null) {
switch (newChild.$$typeof) {
case REACT_ELEMENT_TYPE: {
if (newChild.key === key) {
return updateElement(returnFiber, oldFiber, newChild, lanes);
} else {
return null;
}
}
}
}
}
例子：[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 全部无用，一次性删除：
if (newIdx === newChildren.length) {
deleteRemainingChildren(returnFiber, oldFiber);
return resultingFirstChild;
}
deleteRemainingChildren → 逐个 deleteChild：
function deleteChild(returnFiber, childToDelete) {
if (!shouldTrackSideEffects) return;
const deletions = returnFiber.deletions;
if (deletions === null) {
returnFiber.deletions = [childToDelete];
returnFiber.flags |= 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：
if (oldFiber === null) {
for (; newIdx < newChildren.length; newIdx++) {
const newFiber = createChild(returnFiber, newChildren[newIdx]);
if (newFiber === null) continue;
lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
}
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 索引），再逐个去"认领"：
const existingChildren = mapRemainingChildren(oldFiber);
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);
}
}
lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
}
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——已放置的最右位置：
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）。逻辑更直接——遍历旧链表找"对的那个"：
| 旧 child 的 key 与 type | 处理 |
|---|
| key 匹配 且 type 匹配 | useFiber 复用，删除其余 sibling |
| key 匹配 但 type 不同 | 整个旧链表不可复用 → 全部删除 → 新建 |
| key 不匹配 | 删掉当前 child，继续找下一个 sibling |
| 遍历完没找到 | 创建全新 fiber |
单节点不用建 Map，O(n) 线性扫一遍即可（旧链表通常很短）。
9. key 的意义与注意事项
Step 1 和 Step 4 都依赖 key，key 是整套算法的"身份标识"。两条铁律：
- key 要稳定且唯一——同一列表里不能重复，跨渲染不能变；
- 别用 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. 复杂度分析
| 场景 | 走哪条路 | 复杂度 |
|---|
| 前缀一致（append / 头部删除） | Step 1（可能 + Step 2/3） | O(n)，不建 Map |
| 乱序 / 中间插入 | Step 4 | O(n) 均摊（Map 构建 O(m) + 认领 O(k)，m/k 都是剩余量） |
| 单节点 | reconcileSingleElement | O(n)（旧链表长度） |
代价是 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)
