Diff算法对比深度解析

一句话概括

Vue3的Diff算法采用双端比较策略，以四个指针从数组两端向中间扫描，优先处理高效的节点复用；React采用单向遍历策略，以Fiber链表为基础从左侧开始单方向扫描，两者在key的处理机制和整体优化思路上体现了不同框架层的设计取舍。

背景与意义

虚拟DOM的核心价值不在于”比直接操作DOM快”——事实上直接操作DOM永远比虚拟DOM快。虚拟DOM真正的价值在于它提供了一个声明式的编程模型，同时在合理的性能开销下完成了UI更新的自动化。

而Diff算法就是虚拟DOM的心脏。当状态变化导致组件重新渲染时，新的虚拟DOM树需要与旧的虚拟DOM树进行比较，找出差异，然后只更新实际变化的部分。这个过程需要高效——如果每次比较都遍历整棵树，性能就无法接受。

Vue和React的Diff算法都基于三个相同的假设（这也是所有虚拟DOM Diff的通用优化策略）：

1. 只比较同层级节点，不跨层级比较
2. 不同类型的元素产生不同的树
3. 通过key标识子节点

但在这三个假设之上，两者的实现路径却大相径庭。Vue3选择了双端比较算法，而React选择了Fiber协调器+单向遍历。

概念与定义

虚拟DOM（Virtual DOM）

虚拟DOM是真实DOM的JavaScript对象表示。每个虚拟节点（VNode）对应一个真实的DOM节点：

// React Fiber节点（简化）
type Fiber = {
  tag: WorkTag        // 节点类型（函数组件、类组件、原生DOM等）
  key: string | null  // 标识key
  type: any           // 组件类型或DOM标签名
  stateNode: any      // 对应的真实DOM节点
  child: Fiber | null
  sibling: Fiber | null
  return: Fiber | null
  effectTag: SideEffectTag  // 标记需要执行的操作
  memoizedProps: any
  memoizedState: any
  alternate: Fiber | null   // 指向旧树的对应节点
}

// Vue3 VNode（简化）
type VNode = {
  type: any           // 标签名或组件
  props: any          // 属性
  children: any       // 子节点
  key: string | number | null
  el: Node | null     // 对应的真实DOM
  shapeFlag: number   // 节点形状标记
  dynamicChildren: VNode[] | null  // 动态子节点（Block Tree优化）
}

双端比较（Vue3）

从新旧子节点数组的两端同时进行，使用四个指针向中间扫描的算法策略。

单向遍历（React）

从新旧子节点列表的左侧开始，按索引顺序从左向右扫描，使用key进行节点匹配的算法策略。

最小示例

// 场景：子节点列表从 [A, B, C, D] 变为 [D, A, B, C]
// 即最后一个元素移到了最前面

// Vue3双端比较：只需移动D一个节点
// React单向遍历：可能会处理更多的移动操作

// 具体Diff过程见下文详细分析

核心知识点拆解

1. Vue3的双端比较算法

Vue3的Diff算法（patchKeyedChildren）使用四个指针：

function patchKeyedChildren(
  oldChildren: VNode[],
  newChildren: VNode[],
  container: HostElement,
) {
  let i = 0                    // 左指针
  let oldEnd = oldChildren.length - 1  // 旧数组右指针
  let newEnd = newChildren.length - 1  // 新数组右指针

  // 第一阶段：从左向右同步（处理前缀相同的节点）
  while (i <= oldEnd && i <= newEnd) {
    if (isSameVNodeType(oldChildren[i], newChildren[i])) {
      patch(oldChildren[i], newChildren[i], container)
      i++
    } else {
      break
    }
  }

  // 第二阶段：从右向左同步（处理后缀相同的节点）
  while (i <= oldEnd && i <= newEnd) {
    if (isSameVNodeType(oldChildren[oldEnd], newChildren[newEnd])) {
      patch(oldChildren[oldEnd], newChildren[newEnd], container)
      oldEnd--
      newEnd--
    } else {
      break
    }
  }

  // 第三阶段：处理剩余的情况
  if (i > oldEnd) {
    // 情况1：旧节点已遍历完 → 新增剩余新节点
    while (i <= newEnd) {
      patch(null, newChildren[i], container)
      i++
    }
  } else if (i > newEnd) {
    // 情况2：新节点已遍历完 → 删除剩余旧节点
    while (i <= oldEnd) {
      unmount(oldChildren[i])
      i++
    }
  } else {
    // 情况3：新旧都有剩余
    // 构建新节点的key → 索引映射
    const keyToNewIndexMap = new Map<string | number, number>()
    for (let j = i; j <= newEnd; j++) {
      keyToNewIndexMap.set(newChildren[j].key, j)
    }

    // 遍历旧节点，找到可复用的节点并记录移动情况
    const toBePatched = newEnd - i + 1
    const newIndexToOldIndexMap = new Array(toBePatched).fill(0)

    for (let j = i; j <= oldEnd; j++) {
      const oldVNode = oldChildren[j]
      const newIndex = keyToNewIndexMap.get(oldVNode.key)

      if (newIndex === undefined) {
        unmount(oldVNode) // 删除不存在的旧节点
      } else {
        newIndexToOldIndexMap[newIndex - i] = j + 1
        patch(oldVNode, newChildren[newIndex], container)
      }
    }

    // 使用最长递增子序列计算最小移动次数
    const increasingNewIndexSequence = getSequence(newIndexToOldIndexMap)
    let sequenceIndex = increasingNewIndexSequence.length - 1

    for (let j = toBePatched - 1; j >= 0; j--) {
      if (newIndexToOldIndexMap[j] === 0) {
        // 全新的节点，需要挂载
        const newIndex = j + i
        const anchor = newChildren[newIndex + 1]?.el || null
        hostInsert(newChildren[newIndex].el, container, anchor)
      } else if (j !== increasingNewIndexSequence[sequenceIndex]) {
        // 需要移动的节点
        const newIndex = j + i
        const anchor = newChildren[newIndex + 1]?.el || null
        hostInsert(newChildren[newIndex].el, container, anchor)
      } else {
        sequenceIndex--
      }
    }
  }
}

关键优化点：使用最长递增子序列（LIS）算法来确定哪些节点不需要移动。LIS用于找出那些在最终顺序中已经保持了相对顺序的旧节点，这些节点不需要被移动，只需要移动剩下的节点。

2. React的单向遍历算法

React的Diff通过reconcileChildrenArray函数实现：

function reconcileChildrenArray(
  returnFiber: Fiber,
  currentFirstChild: Fiber | null,
  newChildren: Array<ReactNode>,
  lanes: Lanes,
): Fiber | null {
  // result链表构建
  let resultingFirstChild: Fiber | null = null
  let previousNewFiber: Fiber | null = null

  let oldFiber = currentFirstChild
  let lastPlacedIndex = 0
  let newIdx = 0
  let nextOldFiber: Fiber | null = null

  // 第一阶段：从左向右同步
  for (; oldFiber !== null && newIdx < newChildren.length; newIdx++) {
    if (oldFiber.index > newIdx) {
      nextOldFiber = oldFiber
      oldFiber = null
    } else {
      nextOldFiber = oldFiber.sibling
    }

    const newFiber = updateSlot(returnFiber, oldFiber, newChildren[newIdx], lanes)

    if (newFiber === null) {
      // key不匹配，退出第一阶段
      if (oldFiber === null) {
        oldFiber = nextOldFiber
      }
      break
    }

    // 处理节点是否移动
    if (shouldTrackSideEffects) {
      if (oldFiber && newFiber.alternate === null) {
        deleteChild(returnFiber, oldFiber)
      }
    }

    lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx)
    previousNewFiber = appendChild(resultingFirstChild, previousNewFiber, newFiber)

    oldFiber = nextOldFiber
  }

  // 第二阶段：新节点遍历完 → 删除旧节点
  if (newIdx === newChildren.length) {
    deleteRemainingChildren(returnFiber, oldFiber)
    return resultingFirstChild
  }

  // 第三阶段：旧节点遍历完 → 插入新节点
  if (oldFiber === null) {
    for (; newIdx < newChildren.length; newIdx++) {
      const newFiber = createChild(returnFiber, newChildren[newIdx], lanes)
      lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx)
      // ... 拼接newFiber
    }
    return resultingFirstChild
  }

  // 第四阶段：新旧都有剩余 → 使用key映射处理
  const existingChildren = mapRemainingChildren(returnFiber, oldFiber)

  for (; newIdx < newChildren.length; newIdx++) {
    const newFiber = updateFromMap(existingChildren, returnFiber, newIdx, newChildren[newIdx], lanes)
    if (newFiber !== null) {
      if (shouldTrackSideEffects) {
        if (newFiber.alternate !== null) {
          existingChildren.delete(newFiber.key === null ? newIdx : newFiber.key)
        }
      }
      lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx)
    }
  }

  // 删除剩余的旧节点
  existingChildren.forEach(child => deleteChild(returnFiber, child))

  return resultingFirstChild
}

React的核心判断指标是lastPlacedIndex——它记录了当前已处理的最新一个未被移动的节点在旧列表中的索引。当遇到一个旧索引小于lastPlacedIndex的节点时，说明该节点需要被移动：

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

  if (!shouldTrackSideEffects) {
    return lastPlacedIndex
  }

  const current = newFiber.alternate
  if (current !== null) {
    const oldIndex = current.index
    if (oldIndex < lastPlacedIndex) {
      // 需要移动
      newFiber.effectTag = Placement
      return lastPlacedIndex
    } else {
      // 不需要移动
      return oldIndex
    }
  } else {
    // 全新节点，需要插入
    newFiber.effectTag = Placement
    return lastPlacedIndex
  }
}

3. Key处理机制对比

React的key处理：

• key是一个字符串或数字，标记节点的唯一身份
• 在数组类型的子节点中，React通过key来匹配新旧节点
• 如果key相同且type相同，复用Fiber节点
• 没有显式的key时，React使用index作为隐式key

// React中key不匹配时视为新节点
function updateSlot(
  returnFiber: Fiber,
  oldFiber: Fiber | null,
  newChild: ReactNode,
  lanes: Lanes,
): Fiber | null {
  const key = oldFiber !== null ? oldFiber.key : null

  if (typeof newChild === 'object' && newChild !== null) {
    switch (newChild.$$typeof) {
      case REACT_ELEMENT_TYPE: {
        if (newChild.key === key) {
          // key匹配 → 复用更新
          return updateElement(returnFiber, oldFiber, newChild, lanes)
        } else {
          // key不匹配
          return null
        }
      }
    }
  }

  return null
}

Vue3的key处理：

• key可以是string或number
• 同样用于节点复用决策
• 但Vue3在key处理上多了一层优化：Block Tree

// Vue3中key匹配判断
function isSameVNodeType(n1: VNode, n2: VNode): boolean {
  return n1.type === n2.type && n1.key === n2.key
}

4. Block Tree（Vue3独有优化）

Vue3引入了一个React没有的优化机制：Block Tree。它的核心思想是跳过静态节点，只追踪动态节点：

<template>
  <div>                        <!-- Block根 -->
    <span>{{ name }}</span>    <!-- 动态节点 → 收集到dynamicChildren -->
    <p>静态文本</p>            <!-- 静态节点 → 跳过 -->
    <span>{{ age }}</span>     <!-- 动态节点 → 收集到dynamicChildren -->
  </div>
</template>

编译后：

// 生成的渲染函数
function render(_ctx, _cache) {
  return (_openBlock(), _createBlock('div', null, [
    _createVNode('span', null, _toDisplayString(_ctx.name), 1 /* TEXT */),
    _createVNode('p', null, '静态文本'),
    _createVNode('span', null, _toDisplayString(_ctx.age), 1 /* TEXT */),
  ]))
}

// 编译后的VNode中，dynamicChildren只包含动态节点
// 在patch过程中，直接比较dynamicChildren数组，跳过静态节点

这意味着Vue3的Diff在Block Tree优化下，复杂度从O(n)降到了O(m)，其中m远小于n（m是动态节点的数量）。对于静态节点占比高的模板，这个优化效果极其显著。

实战案例：列表排序的性能分析

考虑一个常见的列表拖拽排序场景。用户将最后一项拖拽到最前面：

const list = ['A', 'B', 'C', 'D', 'E']
// 拖拽后: ['E', 'A', 'B', 'C', 'D']

Vue3的双端比较过程

旧列表: [A, B, C, D, E]  新列表: [E, A, B, C, D]

第一阶段（从左同步）:
  A vs E → key不同，break
  此时: i=0, oldEnd=4, newEnd=4

第二阶段（从右同步）:
  E vs D → key不同，break
  此时: i=0, oldEnd=4, newEnd=4

第三阶段（剩余处理）:
  keyToNewIndexMap: {E:0, A:1, B:2, C:3, D:4}
  遍历旧节点[E]索引4 → newIndex=0
  newIndexToOldIndexMap: [5, 0, 0, 0, 0]
  最长递增子序列: [0] 即第一个位置
  从右向左遍历：
    j=4(D): 新节点，挂载
    j=3(C): 新节点，挂载
    j=2(B): 新节点，挂载
    j=1(A): 新节点，挂载
    j=0(E): 在LIS中，不需要移动

结果: 挂载A,B,C,D，E保持不动
DOM操作: 4次插入 + 0次移动

React的单向遍历过程

旧Fiber链表: A → B → C → D → E → null
新列表: [E, A, B, C, D]

第一阶段（从左同步）:
  newIdx=0: A vs E → key不同，break
  退出时: newIdx=0, oldFiber=A

第四阶段（剩余处理）:
  key映射: {A: oldFiberA, B: oldFiberB, C: oldFiberC, D: oldFiberD, E: oldFiberE}

  newIdx=0: E → 找到oldFiberE, oldIndex=4, lastPlacedIndex=0, 4>0 → 不移
  newIdx=1: A → 找到oldFiberA, oldIndex=0, lastPlacedIndex=0, 0>=0 → 不移, lastPlacedIndex=0
  newIdx=2: B → 找到oldFiberB, oldIndex=1, lastPlacedIndex=0, 1>0 → 不移, lastPlacedIndex=1
  newIdx=3: C → 找到oldFiberC, oldIndex=2, lastPlacedIndex=1, 2>1 → 不移, lastPlacedIndex=2
  newIdx=4: D → 找到oldFiberD, oldIndex=3, lastPlacedIndex=2, 3>2 → 不移, lastPlacedIndex=3

结果: 没有需要移动的节点，仅插入E到最前面
DOM操作: 1次插入（E移到前面）

在这个特定场景下，两种算法的DOM操作次数接近。但在不同的场景下会有不同的表现：

场景	Vue3双端比较	React单向遍历
尾部移到头部	高效（一个LIS+挂载）	高效（仅插入一次）
头部移到尾部	高效（双端扫描快速处理）	低效（需要移动多个节点）
列表倒序	高效（使用LIS优化）	低效（所有节点都需要移动）
仅末尾新增	高效（前缀快速匹配）	高效（前缀快速匹配）
中间删除	适中	适中

底层原理

1. 最长递增子序列的运用（Vue3核心优化）

Vue3使用LIS来确定哪些节点在最终顺序中保持了相对顺序：

// 最长递增子序列（贪心+二分查找，O(nlogn)）
function getSequence(arr: number[]): number[] {
  const p = arr.slice() // 记录前驱
  const result = [0]
  let i: number, j: number, u: number, v: number, c: number

  for (i = 0; i < arr.length; i++) {
    const arrI = arr[i]
    if (arrI === 0) continue

    j = result[result.length - 1]
    if (arr[j] < arrI) {
      p[i] = j
      result.push(i)
      continue
    }

    u = 0
    v = result.length - 1
    while (u < v) {
      c = (u + v) >> 1
      if (arr[result[c]] < arrI) {
        u = c + 1
      } else {
        v = c
      }
    }

    if (arrI < arr[result[u]]) {
      if (u > 0) {
        p[i] = result[u - 1]
      }
      result[u] = i
    }
  }

  // 回溯构建实际序列
  u = result.length
  v = result[u - 1]
  while (u-- > 0) {
    result[u] = v
    v = p[v]
  }

  return result
}

举例说明：假设newIndexToOldIndexMap = [5, 3, 4, 0, 1]

• 5表示旧节点E（索引4+1）映射到新位置0
• 3表示旧节点C（索引2+1）映射到新位置1
• 4表示旧节点D（索引3+1）映射到新位置2
• 0表示新节点（索引3）没有对应的旧节点（需创建）
• 1表示旧节点A（索引0+1）映射到新位置4

LIS找出[3, 4]，即索引1和2对应的旧节点C和D在最终顺序中保持了递增关系（它们的旧索引2和3是递增的），表示C和D不需要移动。

2. React fiber链表结构的优势

React的Fiber架构使用链表结构，这是它与Vue3数组结构的关键差异：

// 单向链表的优势
// 1. 可中断遍历：React可以在遍历Fiber链表时暂停/恢复
function workLoopConcurrent() {
  while (workInProgress !== null && !shouldYield()) {
    performUnitOfWork(workInProgress)
  }
}

// 2. 支持pending状态：链表可以轻松管理优先级队列
// 3. 便于删除/插入操作：链表的O(1)删除/插入

// 这也是React能实现并发模式的基础
// Vue3的数组结构diff是一次性的、不可中断的

性能对比的结论：

• Vue3的双端比较在更新质量（最小DOM操作数）上通常更优
• React的Fiber链表在更新灵活性（可中断、优先级调度）上更优
• Vue3的Block Tree在静态节点优化上远优于React
• React的调度器在复杂交互的流畅度上更优

高频面试题解析

面试题1：为什么不建议用index作为key？

问题：React和Vue中，为什么用index作为key会导致性能问题甚至bug？

答案：当列表的顺序可能发生变化时，使用index作为key会导致两个问题：

性能问题：

// 初始: ['A', 'B', 'C'] → key: 0,1,2
// 方案一：使用唯一id作为key
// 新增 'D' 到头部: ['D', 'A', 'B', 'C'] → key: d, a, b, c
// 只需要在index[0]之前插入D

// 方案二：使用index作为key
// 新增 'D' 到头部: ['D', 'A', 'B', 'C'] → key: 0,1,2,3
// React认为: key=0从A变成D（类型相同被视为同一个节点）
// 关键问题是DOM text content更新了但节点没有移动
// 然后 key=1从B变成A，key=2从C变成B，key=3插入C
// 导致：A变D(更新)、B变A(更新)、C变B(更新)、插入C(新增)
// 性能极差！原本只需要1次插入，变成了3次更新+1次插入

bug问题：

// 一个包含input的列表
const [items, setItems] = useState([
  { id: 1, text: 'A' },
  { id: 2, text: 'B' },
])

// 用户修改了第一个input的值为'X'
// 然后在头部插入新项: [{ id: 3, text: 'C' }, { id: 1, text: 'A' }, { id: 2, text: 'B' }]
// 
// 用index作为key:
// key=0 → 原本id=1(A)的input，但react认为这是新项id=3(C) → input被复用，值还是'X'
// 第二个key=1 → 原本id=2(B)的input被复用在id=1(A)上 → 值也有问题
// bug: input内容错位！

// 用id作为key:
// key=3 → 全新的input
// key=1 → input被正确复用在原本的A上
// key=2 → input被正确复用在原本的B上

正确做法：除非列表是静态的且不会排序/过滤/新增/删除，否则永远用唯一的id作为key。

面试题2：Vue3的双端比较和React的Diff哪个效率更高？

问题：从算法层面对比，Vue3和React的Diff谁更优？

答案：没有绝对的答案，取决于具体的场景和数据特征。

Vue3优势场景：

1. 头/尾部的交换操作：双端比较可以快速处理头尾的变化
2. 静态内容多的页面：Block Tree跳过静态节点，实际diff节点数大大减少
3. 频繁的属性更新（class/style变化）：Vue3通过patchFlags精准标记动态节点

React优势场景：

1. 高度动态的列表操作（频繁插入/删除/排序）：Fiber链表的增删操作是O(1)
2. 复杂的交互相应场景：Fiber的可中断渲染保证了高优先级交互的响应性
3. 组件树深度深且结构变化大的场景：React的Tree-based递归可以处理

一个合理的技术判断是：Vue3在”更新质量”上更优（更少的DOM操作），而React在”更新灵活性”上更优（可中断、可调度）。实际应用中，两者在大多数场景下的性能差距在10%以内，远小于开发者代码质量带来的性能差异。

面试题3：Vue3的Block Tree和React的哪些优化技术对应？

问题：Vue3的Block Tree在React中有没有对应的技术？

答案：没有直接对应的技术，但React有自己独特的编译时优化策略：

Vue3 Block Tree：

• 将模板编译成”块”（Block），每个块中仅追踪动态节点
• 这是模板编译最大的优势——React的JSX灵活性使其难以进行类似的编译时优化

React对应的优化技术：

1. React Compiler（React 19）：能够在编译时推断组件的依赖关系，自动插入memoization代码。虽然不是跳过静态节点，但减少了不必要的重渲染。

2. React Forget（已合并入React Compiler）：自动优化hook的依赖追踪。

3. Keyed Fragments：React通过Fiber链表结构可以实现细粒度的节点更新追踪。

两者路径不同：Vue3通过编译时分析模板结构来减少Diff范围，React通过运行时调度来优化Diff过程。

总结与扩展

Vue3和React的Diff算法代表了两种不同的优化哲学：

维度	Vue3	React
基础数据结构	数组	链表（Fiber）
遍历策略	双端四指针扫描	单向遍历+lastPlacedIndex
移动判定	最长递增子序列	lastPlacedIndex比较
编译时优化	Block Tree	React Compiler
运行时优化	patchFlags	可中断调度
时间复杂度	O(n) + LIS O(nlogn)	O(n)

扩展思考：

Vue3的Vapor Mode计划完全抛弃虚拟DOM，直接基于响应式系统更新真实DOM。这将使Diff算法在Vue3中逐渐变得不再重要，因为无需比较就能知道哪里变了。

React也在探索更高效的路径：React Forget在编译时做更多的工作，减少运行时的计算负担。两个框架在这一点上殊途同归——尽可能将工作从运行时挪到编译时。

Diff算法本身可能正在走向”被淘汰”的道路上，但理解它的原理，尤其是双端比较、LIS、Fiber链表这些核心概念，对于掌握框架的内部机制仍然不可替代。