Skip to main content

Diff 算法

面试高频问题概览：

  • React 如何把 diff 的复杂度从 O(n³) 降到 O(n)？
  • key 的作用是什么？为什么不能用 index 作 key？
  • React 的多节点 diff 为什么要遍历两轮？
  • React 和 Vue 的 diff 有什么异同？

1. 为什么需要 diff？复杂度怎么降下来的​

直接对比两棵树，传统树 diff 算法的复杂度高达 O(n³)（n 个节点两两对比再加上排序），完全无法满足前端频繁更新的性能要求。

React 基于「Web UI 中跨层级移动节点极少」的现实，制定了三条策略，把问题简化为 O(n)：

策略含义
tree diff（同层对比）只比较同一层级的节点，不跨层级比较。节点跨层移动时直接「删除 + 新建」而非移动
component diff（按类型）同类型组件继续 diff；类型不同直接整棵替换（不再深入比较）
element diff（同层节点）同层级的一组子节点，通过 key 识别复用，做插入/移动/删除

正因为「类型不同就整棵替换」，所以开发中不要随意改变组件的嵌套类型/层级，否则会导致整棵子树重建、状态丢失。

2. element diff 与 key​

同一层级有多个子节点时，React 用 key 作为节点的唯一标识来判断「是不是同一个节点」：

  • 遍历前用旧节点构建一个 key -> oldFiber 的 map，复用一个就从 map 中删除。
  • 只有 key 相同且节点类型相同 时才复用旧节点（仅做移动），否则删除重建。

lastPlacedIndex：尽量少移动​

lastPlacedIndex 表示「最后一个不需要移动的节点在旧列表中的位置」。遍历新列表时：

  • 若复用的旧节点 oldIndex >= lastPlacedIndex：说明它相对位置没变，不动，并更新 lastPlacedIndex = oldIndex。
  • 若 oldIndex < lastPlacedIndex：说明它需要往后移动，标记 Placement。

原则就是：新位置靠后的（地位高的）尽量不动，让靠前的动，从而最小化 DOM 移动。

为什么不能用 index 作 key​

当列表发生插入、删除、排序时，元素与 index 的对应关系会错位，导致 React 复用了「错误的」旧节点：

  • 引发状态错乱（如带输入框的列表，内容串位）。
  • 失去复用意义甚至更慢（本可移动却变成大量更新/重建）。

应使用稳定、唯一的业务 id 作 key。

3. React 的 diff 入口（结合 Fiber）​

React 16+ 是 Fiber 树与新 ReactElement 的对比，diff 发生在 Render 阶段的 reconcileChildren 中：

  • 单节点（reconcileSingleElement）：遍历旧的子节点链表，找 key + type 匹配的复用，其余删除。
  • 多节点（reconcileChildrenArray）：两轮遍历
    1. 第一轮：按顺序逐个比较新旧节点，能复用就继续，一旦 key 不匹配就停止。
    2. 第二轮：把剩余旧节点放进 key -> fiber 的 map，遍历剩余新节点从 map 里找复用（用 lastPlacedIndex 判断移动），最后删除 map 中未被复用的旧节点。

为什么两轮？因为最常见的更新是「末尾追加/局部更新」而非乱序，第一轮顺序对比能用最快路径覆盖大多数场景，第二轮才处理移动这种复杂情况。源码细节见 更新的三个阶段。

4. Vue 的 diff​

Vue 的 diff 基于 snabbdom 演进而来。

Vue2：双端 diff​

  • 设新旧两组子节点各有头尾两个指针，依次做 头头、尾尾、头尾、尾头 四种对比。
  • 命中则复用并移动指针，从两端向中间收拢，指针交叉即结束。
  • 四种都没命中，再用 key 建 map 查找复用。

Vue3：快速 diff（最长递增子序列）​

  1. 先处理两组子节点相同的前置节点和后置节点（头部、尾部预处理）。
  2. 剩余节点若不能简单地通过新增/删除完成，则根据新旧索引关系求出最长递增子序列（LIS）。
  3. LIS 中的节点是「相对顺序不变」的，不动；其余节点按需移动，从而最小化移动次数。
  4. 配合编译期静态标记（PatchFlag / Block Tree）：只对动态节点做 diff，跳过静态节点。

5. React vs Vue diff 对比​

相同点

  • 都是两组虚拟 DOM 的对比（React 16+ 是 Fiber 与 ReactElement 的对比）。
  • 都只对同层级节点对比，简化复杂度到 O(n)。
  • 都用 key + 类型 作为复用判断依据，遍历前建立 keyMap。

不同点

维度ReactVue
遍历方式单指针从左向右Vue2 双端双指针 / Vue3 前后预处理 + LIS
DOM 操作时机先收集变更成 effectList，commit 阶段统一处理（先删除，再更新/移动，最后插入）遍历过程中直接用 insertBefore 等操作真实 DOM，最后做删除
优化思路运行时 diff，配合 Fiber 可中断调度编译期静态标记 + 运行时 LIS，整体更「聪明」、效率更高

一句话总结：React 的 diff 更朴素但配合 Fiber 调度；Vue 借助编译期信息做了更激进的运行时优化。

参考​