diff 算法解析

为何用 diff 算法

由于在浏览器中操作 DOM 的代价是非常“昂贵”的，所以才在 Vue 引入了 Virtual DOM，即使使用了 Virtual DOM 来进行真实 DOM 的渲染，在页面更新的时候，也不能全量地将整颗 Virtual DOM 进行渲染，而是去渲染改变的部分，这时候就需要一个计算 Virtual DOM 树改变部分的算法了。

传统 diff 算法

传统的 Diff 算法通过循环递归对节点进行比较，然后判断每个节点的状态以及要做的操作（add，remove，change），最后 根据 Virtual DOM 进行 DOM 的渲染

比如左侧树每个节点与右侧树每个节点依次进行遍历对比(A->A、A->D、A->B、A->C ……)，时间复杂度 O(n^2)，在每个循环中，还需要比较两个元素是否相等，这需要进行一次额外的循环，时间复杂度为 O(n)。因此，总时间复杂度为 O(n^2 * n) = O(n^3)。

vue2 diff 算法

vue 数据驱动

• 通过 Object.defineProperty 函数改写了数据的 getter 和 setter 函数，来实现依赖收集和派发更新
• 一个 key 值对应一个 Dep 实例，一个 Dep 实例可以包含多个 Watcher，一个 Wathcer 也可以包含多个 Dep
• Dep 用于依赖的收集与管理，并通知对应的 Watcher 执行相应的操作
• 依赖收集的时机是在执行 render 方法的时候，读取 vm 上的数据,触发 getter 函数。而派发更新即在变更数据的时候，触发 setter 函数，通过 dep.notify()，通知到所收集的 watcher，执行相应操作

diff 算法原理图

diff 算法的策略

深度优先，同层比较

1. 比较只会在同层进行，不会跨层比较
2. 比较的过程中，循环从两边向中间靠拢

updateChildren

1. 同级比较，减少对比次数，提高对比性能，时间复杂度在 O(n)

3. 首尾指针法
   1. 依次比对，当成功后退出当前比较
   2. 渲染结构以 newVnode 为准
   3. 每次比较成功后，start 点和 end 点向中间靠拢
   4. 当新旧节点中有一个 start 点跑到 end 点右侧时，终止比较
   5. 如果都匹配不到，则旧虚拟 dom key 只去对比新虚拟 dom 的 ke 值，如果 key 相同则服用，并移动到新虚拟 dom 的位置

比对顺序

1. 首先，旧虚拟节点的 start 和新虚拟节点的 start 做比对，如果没有比对成功，就用旧虚拟节点的 start 和新虚拟节点的 end 做比对

2. 如果依旧没有比对成功，就用旧虚拟节点的 end 和新虚拟节点的 start 做比对，如果依旧没有成功，就虚拟节点的 end 和新虚拟节点的 end 做比对

3. 当比对成功，就退出比对，渲染结果也会以新虚拟节点的结果为准
4. 每次比对成功后，比对成功的 start 会右移，end 会向左移动。在移动的过程中，当 start 点跑到 end 的右侧就终止比较

vue3 的 diff 算法

静态节点

Vue3 的编译器会在编译阶段对模板进行静态分析，将静态节点和动态节点分开，将静态节点标记为常量，并将其生成为一个单独的常量节点。在渲染时，Vue3 会直接使用常量节点，而不需要重新创建节点，从而提高渲染性能。可以手动标记静态节点：

<template v-slot:header>
    <h1>静态头部</h1>
</teamplate>

vue3 diff 算法是一种按序比较，在同层节点比较的基础上，将比较的范围延伸到新旧 DOM 树中，适用于更加复杂的节点结构。充分理由虚拟 dom 中节点的结构信息。如静态节点的优化，会将静态节点拆分出来单独处理。

当 Vue3 Patch 函数接收到新旧 VNode 后，会让新旧 VNode 树进行上述的 Profiling 过程，然后将标记过的节点传递过来。Patch 函数在得到标记后的两棵树后，首先递归比较新旧树的根节点是否相同。

如果不相同，那么同 React Diff 算法一样，查找新 VNode 在旧 VNode 数组中是否存在。如果旧 VNode 中不存在，代表这是一个新增节点，直接使用 createVNode 创建 newNode 并插入到旧 VNode 的 DOM 中；否则的话，可能是新 VNode 与某个旧 VNode 是同个父节点下的兄弟节点，也可能是新 VNode 嵌套在某个旧 VNode 的子树中。

对于这两种情况分别进行处理：

情况 1：新旧 VNode 是兄弟节点

在这种情况下，Vue3 Diff 算法会采用“按序比较”的策略。会生成新旧 VNode 的 keys 数组，然后对两个 keys 数组做一次 fuzzy 的匹配，得到一个新旧 keys 数组的映射表（Map）。根据映射表的数据可以知道新旧 VNode 的映射关系，从而知道该做什么来完成更新。

举个例子：

<!-- before -->
<div>
  <!-- 旧 VNode -->
  <p key="a">A</p>
  <p key="b">B</p>
  <p key="c">C</p>
</div>

<!-- after -->
<div>
  <!-- 新 VNode -->
  <p key="c">C</p>
  <p key="b">B</p>
  <p key="d">D</p>
</div>

<!-- 首先生成新旧 VNode 的 keys 数组： -->
<!-- Old: ["a", "b", "c"] -->
<!-- New: ["c", "b", "d"] -->
<!-- 通过 fuzzy 匹配得到以下的映射表： -->
<!-- M: {a: undefined, b: 1, c: 0, d: undefined} -->

<!-- 此时将新 VNode 映射为 [C, B, D]，而旧 VNode 映射为 [A, B, C]。 -->
<!-- 接下来的工作，就是根据映射关系，在旧节点中进行增删改操作。 -->
<!-- 最终完成的 DOM 如下： -->
<div>
  <p key="c">C</p>
  <!-- 旧的节点 b 变成了新的 b -->
  <p key="b">B</p>
  <!-- 新增了一个节点 d -->
  <p key="d">D</p>
</div>

情况 2：新 VNode 在旧 VNode 中的子节点里

如果新 VNode 在旧 VNode 子树中间，那么需要将它递归更新。

在遍历新旧 VNode 期间，Vue3 Diff 算法会按照 key 值或 index 值优先匹配新旧 VNode，这样可以显著地优化性能。同时，出于优化的目的，Vue3 Diff 算法还对一些特定情况做了特殊处理，例如处理静态节点，处理数组时的优化，等等。

综上所述，Vue3 Diff 算法采用了更为高效且灵活的“按序比较”策略，提高了数据处理的速度和效率，从而实现更快的页面渲染并更好地回应用户的操作。

vue 和 react 的 diff 算法比较

1. vue 和 react 的 diff 算法，都是忽略跨级比较，只做同级比较。vue diff 时调动 patch 函数，参数是 vnode 和 oldVnode，分别代表新旧节点。
2. vue 对比节点。当节点元素相同，但是 classname 不同，认为是不同类型的元素，删除重建，而 react 认为是同类型节点，只是修改节点属性。
3. vue 的列表对比，采用的是两端到中间比对的方式，而 react 采用的是从左到右依次对比的方式。当一个集合只是把最后一个节点移到了第一个，react 会把前面的节点依次移动，而 vue 只会把最后一个节点移到第一个

总结

1. react-diff: 双端对比（列表顺序变化会损失性能）
2. vue-diff: 双指针方式对比（潜逃过深的节点结果会导致算法性能下降）
3. 总体来讲 vue 的 diff 算法更佳,总体规律就是找到新节点所对应的旧节点列表中的节点,而后给真实的对应的 dom 移动到正确的位置

参考

• vue 中的 diff 算法
• vue 算法详解