多节点Diff第二轮处理

一句话概括

React 第一轮 Diff 按序匹配失败后进入第二轮——把剩余旧 Fiber 塞进 Map，用 lastPlacedIndex 算法判断每个节点该复用还是移动，复用不了的旧节点在第三轮删除。这套机制用 O(n) 时间解决了列表乱序更新的最小 DOM 操作问题。

核心知识点

1. 第一轮为什么会跳出？

// 旧: A B C D E
// 新: A B D E C
// 第一轮: newIdx=0 → A匹配, 1 → B匹配, 2 → D vs C → key不同的那一刻立即跳出

第一轮是”乐观扫描”——假设列表头部不变。一旦 updateSlot 返回 null（key 不匹配或 type 不同），直接 break，进入第二轮。

2. 剩余节点 → Map（O(1) 查找）

// 把旧链表转成 HashMap
function mapRemainingChildren(returnFiber, currentFirstChild) {
  const existingChildren = new Map();
  let existingChild = currentFirstChild;
  while (existingChild !== null) {
    // key 非 null → 用 key；否则用 index
    existingChildren.set(
      existingChild.key ?? existingChild.index,
      existingChild
    );
    existingChild = existingChild.sibling;
  }
  return existingChildren;
}

为什么用 Map？因为第二轮剩余节点是乱序的，如果还是逐个遍历旧链表去找匹配，就是 O(n²)。Map 把查找降到 O(1)。

3. lastPlacedIndex — 判断是否需要移动

let lastPlacedIndex = 0;
// 遍历剩余新节点，在 Map 中查找
for (; newIdx < newChildren.length; newIdx++) {
  const newFiber = updateFromMap(existingChildren, ...);
  const oldIndex = newFiber.alternate?.index;

  if (oldIndex < lastPlacedIndex) {
    newFiber.flags |= Placement; // 需要移动！
  } else {
    lastPlacedIndex = oldIndex;
  }
}

手动演算：旧 [A,B,C,D,E] 变成 [E,D,C,B,A]

lastPlacedIndex = 0
处理 E: oldIndex=4 >= 0 → 不移, lastPlacedIndex=4
处理 D: oldIndex=3 < 4  → 移动 🔄
处理 C: oldIndex=2 < 4  → 移动 🔄
处理 B: oldIndex=1 < 4  → 移动 🔄
处理 A: oldIndex=0 < 4  → 移动 🔄

这个贪心算法等价于找”最长递增子序列”——不用移动的节点就是递增子序列的成员。Vue 3 用精确 LIS，React 用贪心近似，日常差距可忽略。

4. 第三轮 — 删除未被匹配的旧节点

// Map 中遍历过的节点会被 delete，剩下的就是该删的
existingChildren.forEach(child => deleteChild(returnFiber, child));

deleteChild 不立即删 DOM，而是在 Fiber 上打 flag。真正的 DOM 操作延迟到 commit 阶段执行。

5. 无 key 的灾难

// 旧: [A, B, C] → 新: [B, C, A]，无 key
// Map 构建: {0: A, 1: B, 2: C}
// newIdx=0: 查 Map(0) → 找到 A → 错误复用！（应该是 B）
// newIdx=1: 查 Map(1) → 找到 B → 错误复用！（应该是 C）
// newIdx=2: 查 Map(2) → 找到 C → 错误复用！（应该是 A）
// 结果：全部内容错位，输入框状态全乱

其实你每天都在用

• 拖拽排序：看板任务从第 5 位拖到第 2 位，第一轮匹配到第 1 个就跳出，剩余全靠第二轮 Map 查找 + lastPlacedIndex 移动
• 表格按列排序：点击表头排序，列表前几项大概率变，第一轮几乎立刻跳出
• 两个 API 数据合并：[...list1, ...list2] 后顺序变了，Diff 必然进入第二轮
• 搜索过滤后重新渲染：过滤后列表变小，第一轮匹配几个后旧节点还有剩余 → 第二轮 Map 查找 + 第三轮删除

常见误解

• ❌ 误区：「key 用 index 也没事，反正 React 会优化」 大错。无 key 时 Map 键是 index，导致旧索引 0 的节点被错误复用到新索引 0（内容完全不对），输入框状态错乱就是这么来的。

• ❌ 误区：「lastPlacedIndex 能保证最少移动次数」 不一定。React 用的是贪心，不是真正的 LIS 算法。极端场景下比理论最小值多 1-2 次移动，但换来代码简洁和可维护性。

• ❌ 误区：「第二轮只处理移动，不处理新增」 错。updateFromMap 在 Map 中找不到对应 key 时，直接 createFiberFromElement 新建。新增和移动在同一个循环里处理。

• ❌ 误区：「Placement flag 就是 insertBefore」 不完全是。Placement 表示”这个节点在 commit 阶段需要插入到 DOM 的正确位置”，可能是 insertBefore 也可能是 appendChild。React 会找到正确的参考节点再决定。

一句话总结

第二轮 Diff = Map 查找（O(1)匹配）+ lastPlacedIndex（判断移动）+ 第三轮（删除残余），三招搞定列表乱序更新——这就是 key 为什么是 React 列表渲染的生命线。