程序员布欧

简体中文

English

简体中文

English

外观

Diff 算法详解

约 1857 字大约 6 分钟

布欧-Lewyon

2026-05-15

首页 › React › 源码与架构 › Diff 算法详解

React 的 Diff 算法是 Virtual DOM 高性能的核心。它将"两棵树对比"的 O(n³) 复杂度优化到 O(n)，靠的是三个关键假设。

核心假设

  1. 不同类型的元素产生不同的树（<div> → <span> 直接替换）
  2. 通过 key 标识子元素是否稳定（列表渲染必须传 key）
  3. 同层比较，不跨层级移动（子树整体替换）

Diff 入口：beginWork 中的 reconcileChildren

单节点 Diff（reconcileSingleElement）

新旧节点比对：

// 简化逻辑
function reconcileSingleElement(
  returnFiber: Fiber,
  currentFirstChild: Fiber | null,
  element: ReactElement,
): Fiber {
  let child = currentFirstChild;
  while (child !== null) {
    if (child.key === element.key) {
      if (child.elementType === element.type) {
        // ✅ Key 和 Type 都相同 → 复用
        deleteRemainingChildren(returnFiber, child.sibling); // 删除多余的兄弟
        return useFiber(child, element.props);
      }
      // Key 相同但 Type 不同 → 删除旧的及其兄弟
      deleteRemainingChildren(returnFiber, child);
      break;
    }
    // Key 不同 → 删除当前旧 Fiber，继续对比下一个兄弟
    deleteChild(returnFiber, child);
    child = child.sibling;
  }
  // 没有可复用的 → 新建
  return createFiberFromElement(element, returnFiber);
}

场景示例：

// 旧: <div key="A" />  →  新: <p key="A" />
// key 相同 → type 不同 → 删除旧 <div>，创建新 <p>（不能复用 DOM）

// 旧: <div key="A" />  →  新: <div key="B" />
// key 不同 → 删除 <div key="A">，创建新的 <div key="B">

多节点 Diff（reconcileChildrenArray）

这是最复杂的部分。React 采用两轮遍历：

第一轮：从左到右遍历可复用节点

// 第一轮：从左向右匹配
function reconcileChildrenArray(
  returnFiber: Fiber,
  currentFirstChild: Fiber | null,
  newChildren: Array<ReactElement>,
): Fiber | null {
  let oldFiber = currentFirstChild; // 旧的第一个子节点
  let nextOldFiber = null;
  let newIdx = 0;
  let lastPlacedIndex = -1;
  let newFiber: Fiber | null = null;

  // 第一轮：尽量复用 key+type 匹配的节点
  for (; oldFiber !== null && newIdx < newChildren.length; newIdx++) {
    const newChild = newChildren[newIdx];
    if (oldFiber.key === newChild.key) {
      if (oldFiber.elementType === newChild.type) {
        // ✅ 完全匹配 → 复用
        newFiber = useFiber(oldFiber, newChild.props);
        lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
      } else {
        // key 同但 type 不同 → 删除旧的，新建
        newFiber = createFiberFromElement(newChild);
        deleteChild(returnFiber, oldFiber);
      }
      oldFiber = oldFiber.sibling;
    } else {
      // key 不同 → 第一轮结束
      break;
    }
  }

  // ...
}

第一轮结束有三种可能结果：

可复用情况对照

// 场景 1：节点保持相同顺序
// 旧: A B C D
// 新: A B C D
// ✅ 第一轮全部匹配，直接复用

// 场景 2：末尾新增
// 旧: A B C
// 新: A B C D
// ✅ 第一轮匹配 A B C，然后 D 标记 Placement

// 场景 3：末尾删除
// 旧: A B C D
// 新: A B C
// ✅ 第一轮匹配 A B C，然后 D 标记 Deletion

// 场景 4：头部删除
// 旧: A B C D
// 新: B C D
// ❌ 第一轮 A vs B key 不同 → break
// 进入第二轮（用 Map 查找）

第二轮：处理"移动"的情况——利用 existingKeyMap

当第一轮因 key 不匹配中断时，需要处理节点位置变化：

// 第二轮：用 Map 处理移动
function reconcileChildrenArray(/*...*/) {
  // ... 第一轮结束后 ...

  // 将剩余旧 Fiber 按 key 存入 Map
  const existingKeyMap = new Map<string, Fiber>();
  existingFiber = oldFiber;
  while (existingFiber) {
    if (existingFiber.key !== null) {
      existingKeyMap.set(existingFiber.key, existingFiber);
    }
    existingFiber = existingFiber.sibling;
  }

  // 遍历剩余新节点，从 Map 中查找
  for (; newIdx < newChildren.length; newIdx++) {
    const newChild = newChildren[newIdx];
    const matchedOldFiber = existingKeyMap.get(newChild.key);

    if (matchedOldFiber) {
      if (matchedOldFiber.elementType === newChild.type) {
        newFiber = useFiber(matchedOldFiber, newChild.props);
      }
      deleteChild(returnFiber, matchedOldFiber);
    } else {
      newFiber = createFiberFromElement(newChild);
    }

    // ⭐ 核心：lastPlacedIndex 决定是否需要移动
    lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
  }
}

placeChild——移动决策算法

let lastPlacedIndex = -1; // 记录"最右侧已匹配"的旧节点索引

function placeChild(
  newFiber: Fiber,
  lastPlacedIndex: number,
  newIdx: number,
): number {
  newFiber.index = newIdx;

  const current = newFiber.alternate; // 指向旧 Fiber
  if (current === null) {
    // 全新节点 → 不需要移动判断
    return lastPlacedIndex;
  }

  const oldIndex = current.index; // 旧位置的索引
  if (oldIndex < lastPlacedIndex) {
    // 旧位置在"最右侧已匹配"的左边 → 需要移动
    newFiber.flags |= Placement;
    return lastPlacedIndex;
  }

  // 旧位置在右侧或相等 → 无需移动，更新 lastPlacedIndex
  return oldIndex;
}
// 示例：旧 A(0) B(1) C(2) D(3) → 新 A D B C
//
// 第一轮（从左匹配 key）：
//   A vs A ✅ 复用，oldIndex=0 ≥ lastPlacedIndex(-1) → 不移，lastPlacedIndex=0
//   B vs D ❌ key 不同 → break
//
// 第二轮（Map 查找）：
//   D: Map 中找到 → oldIndex=3 ≥ lastPlacedIndex(0) → 不移，lastPlacedIndex=3
//   B: Map 中找到 → oldIndex=1 < lastPlacedIndex(3) → ⚠️ 移动！
//   C: Map 中找到 → oldIndex=2 < lastPlacedIndex(3) → ⚠️ 移动！
//
// 结果：A(不动) D(不动) B(向右移) C(向右移)

完整的 Diff 示例流程

// 旧：<ul><li key="a">A</li><li key="b">B</li><li key="c">C</li></ul>
// 新：<ul><li key="c">C</li><li key="a">A</li><li key="b">B</li><li key="d">D</li></ul>

// Step 1: 第一轮
//   li[a] vs li[c] → key 不同 → break
//
// Step 2: 构建 Map { a: Fiber_A, b: Fiber_B, c: Fiber_C }
//
// Step 3: 遍历新节点
//   c → Map 命中，复用 Fiber_C，oldIndex=2 ≥ lastPlacedIndex(-1) → 不动，lastPlacedIndex=2
//   a → Map 命中，复用 Fiber_A，oldIndex=0 < lastPlacedIndex(2) → ⚠️ 移动！
//   b → Map 命中，复用 Fiber_B，oldIndex=1 < lastPlacedIndex(2) → ⚠️ 移动！
//   d → Map 未命中 → 新建 Fiber_D，标记 Placement
//
// Step 4: 删除 Map 剩余节点（无）
// 结果：C(不动) A(移动) B(移动) D(新增)

key 的作用

// ❌ 不用 key（或使用 index）
{todos.map((todo, index) => (
  <TodoItem key={index} todo={todo} />
))}
// 中间插入一条时，后面所有 Todo 的 key 变化 → 全部重建

// ✅ 用稳定唯一 id
{todos.map(todo => (
  <TodoItem key={todo.id} todo={todo} />
))}
// 中间插入一条 → 其他节点 key 不变 → 仅新增一条

Fragment 与 Diff

// <></> 的 key 直接挂到子元素上
<>
  <Child key="a" />
  <Child key="b" />
</>

性能优化建议

  1. 列表必须传稳定的 key，不传时 React 用 index 兜底（导致插入/删除时全量重建）
  2. key 不要用 Math.random()，每次 render 都变导致永远无法复用
  3. 类型不同的组件不要放在同一列表位置，React 会整树替换
  4. 保持子组件结构稳定，尽量减少"重新挂载"
  5. 移动节点时尽量利用第一轮匹配（移动范围小的场景）

小结

概念要点
时间复杂度O(n)（基于三个关键假设）
单节点判断key → type → 复用/替换
多节点第一轮从左向右匹配 key+type，直到 key 不匹配
多节点第二轮用 Map 查找旧节点，placeChild 决定是否移动
placeChildoldIndex < lastPlacedIndex → 移动
key 的最佳实践稳定的唯一 ID，不使用 index 或随机值

上一节：React 源码架构解析 下一节：协调与渲染流程

贡献者: 布欧-Lewyon