diff 算法

1. 什么是 diff 算法

diff 算法是一种通过同层的树节点进行比较的高效算法。

其有两个特点：

  • 比较只会在同层级进行，不会跨层比较。
  • 在 diff 比较的过程中，循环从两边向中间收拢。

diff 算法在很多场景下都有应用，在 vue 中，作用于虚拟 dom 渲染成真实 dom 的新旧 VNode 节点比较。

2. 比较策略

整体策略为：深度优先，同层比较。

双端比较流程（带 key 的子节点 diff）

通过四个指针（oldStartIdx、oldEndIdx、newStartIdx、newEndIdx）从两端向中间靠拢，有以下几种判断规则：

  1. 使用 oldStartVnode 与 newStartVnode 直接比较：相同则 patch 并后移。
  2. 使用 oldEndVnode 与 newEndVnode 直接比较：相同则 patch 并前移。
  3. 使用 oldStartVnode 与 newEndVnode 直接比较：相同则 patch 并把节点移到尾部。
  4. 使用 oldEndVnode 与 newStartVnode 直接比较：相同则 patch 并把节点移到头部。
  5. 以上都不满足：在旧节点列表中通过 key 查找匹配节点，找到了则 patch 并移动，找不到则新建。

图解流程示例

新旧 VNode 节点按以下顺序比较：

  • 第一次循环：旧节点 D 与新节点 D 相同，直接复用旧节点 D 作为 diff 后的第一个真实节点。oldEndIndex 移到 C，新节点 startIndex 移到 C。
  • 第二次循环：旧节点末尾 C 与新节点开头 C 相同，diff 后创建 C 真实节点插入到 B 节点之后。
  • 第三次循环：E 没找到，只能直接创建新的真实节点 E，插入到 C 节点之后。
  • 第四次循环：新旧节点开头 A 相同，diff 后创建 A 真实节点插入到前一次创建的 E 节点之后。
  • 第五次循环：同第四次，diff 后创建 B 真实节点插入到 A 节点之后。
  • 最后新节点 startIndex 已大于 endIndex，创建 startIndex 与 endIndex 之间的所有节点（即 F），直接创建 F 节点对应的真实节点放到 B 节点后面。

3. 原理

(1) 数据变更触发更新

当数据发生改变时，订阅者 watcher 就会调用 patch 给真实的 DOM 打补丁。

(2) patch 函数

patch 函数前两个参数为 oldVnode 和 Vnode，分别代表旧节点和新节点，主要做了四个判断：

  1. 两个节点是同一个对象（引用相等），直接 return。
  2. 两个节点都是文本节点且内容不同：直接替换文本。
  3. 两个节点都是元素节点且标签名相同：递归比较子节点，更新属性。
  4. 标签名不同：直接卸载旧节点，创建新节点替换。

(3) patchVnode

当两个节点是相同节点时，会调用 patchVnode 做以下操作：

  1. 复制真实 DOM 元素到新节点。
  2. 更新属性。
  3. 处理子节点：
    • 都有文本子节点且文本不同：替换文本。
    • 新节点有子节点，旧节点没有：在真实 DOM 上添加子节点。
    • 新节点没有子节点，旧节点有：删除真实 DOM 上的子节点。
    • 都有子节点：递归调用 updateChildren。

(4) updateChildren

updateChildren 是 diff 算法的核心，主要做了以下操作：

  • 通过四个指针对新旧两组子节点的首尾两端进行双端比较。
  • 配合 key 在 map 中查找可复用的节点。
  • 尽量复用已有节点，减少 DOM 移动和创建。
  • 当无法复用时，根据指针关系插入 / 删除 DOM。

来源整理自：vue3js.cn 面试官系列