Vue2、Vue3、React之间的diff算法区别是什么！

提示💡

• 同层比较
• React（仅右移动）、Vue2(双端比较)、Vue3(剩余节点-最长递增子序列、静态标记)

Diff 的发展

严格 Diff

diff 优化

提示💡

原则是尽量减少 DOM 操作，能不动就不动，能复用不创建。

React diff：仅右移动

从左到右，用新节点依次对比旧节点，如果相同就将旧节点向右移动，否则继续向后遍历所有旧节点。

Vue 2 ：双端比较

• 一共四个指针，新旧指针之间按顺序进行两两比较，如果比对成功，就向中间移动指针，继续按上述顺序进行比较。
• 直到新旧节点的任意头尾指针发生交叉，就终止比较。
• 如果没匹配到就使用 key 进行比较，key 相同则复用并移动到新虚拟 Dom 的位置，否则丢弃。

Vue 3： 最长递增子序列

最长递增子序列的特征是递增顺序并且连续，下面的例子则是 3、5、7 。

先进行指针比较，如果相同位置的节点不动，在不同节点中找出最小子序列，整体复用，其余节点进行删除或新增，减少中间的比较次数。

为什么要使用 key

如果不使用 key，下面的节点回全部删除重建，有 key 就可以进行复用相同节点。

总结

虚拟 DOM 的 Diff 算法

• 将新旧虚拟 DOM 看作两棵节点树，节点个数为 n
  • 左侧树的节点需要与右侧树的节点一一对比，需要 O (n²) 复杂度
  • 删除未找到的节点，需要再找合适节点放到被删除位置，需要 O (n) 复杂度
  • 添加新节点，需要 O (n) 复杂度
• 综上，Diff 虚拟 DOM 的复杂度是 O (n³)

Vue 2 、 Vue 3、React

React 基于以下两个假设的基础之上提出 O (n) 的启发式算法

• 两个不同类型的元素会产生不同的树
• 可以通过设置 key 属性，来告知渲染哪些子元素在不同的渲染下可以保存不变

React Diffing 算法

• Tree Diff
  • 对比两棵树时，首选比较两棵树的根节点。不同类型的根节点元素会有不同的形态
    • 根节点为不同类型的元素
      • React 会拆卸原有的树并且建立起新的树
      • 当卸载一棵树时
        • 对应的 DOM 节点会被销毁
          • 建立一棵新的树时，对应的 DOM 节点会被创建以及插入到 DOM 中
        • 组件实例将执行 componentWillUnmount() 方法
    • 根节点为相同类型的元素
      • React 会保留节点
      • 仅比对及更新有改变的属性
    • 处理完根节点，React 继续对子节点进行递归
  • 通过 updateDepth 控制 Virtual Dom 树层级
  • 只比较同一个父节点的子节点
  • 通过删除和创建节点实现跨层级移动
  • 避免跨层级移动，优先 CSS 控制显示隐藏
• Component Diff
  • 同类型组件
    • 组件实例会保持不变，因此可以在不同的渲染时保持 state 一致
    • React 将更新该组件实例的 props 以及保证与最新的元素保持一致
    • 调用该实例的 UNSAFE_componentWillReceiveProps、 UNSAFE_componentWillUpdate() 以及 componentDidUpdate() 方法
    • 调用 render() 方法，diff 算法将在之前的结果以及新的结果中进行递归
    • 通过 shouldComponentUpdate、useMemo、useCallback 手动优化
    • 不同类型组件，输出内容相似
      • 建议改成同一类型，避免重新渲染组件
  • 不同类型组件
    • 删除和创建
• Element Diff
  • 默认情况下，React 会同时遍历两个子元素的列表，递归 DOM 节点的子元素
    • 产生差异时，生成一个 mutation
  • 用 key 标识节点
    • 避免使用索引 index，而应使用例如 id 唯一标识来作为 key
  • 只顺序移动位置变到前面的节点
  • 相同类型 React 元素，保留 DOM 节点，仅对比及更新改变的属性

Vue 2. x 优化 Diff 算法

• 基本优化与 React 相同
• pathNode
  • 新老节点相同，不更新
  • 新老节点都是静态节点，key 相同
    • 新节点. elm = 老节点. elm
    • 新节点. componentInstance = 老节点. componentInstance
  • 新老节点存在，不相同
    • 用 updateChildren 更新
• updateChildren
  • 虚拟 DOM 双指针，真实 DOM 双指针，一一对应
  • 两端到中间，直到虚拟 DOM 或真实 DOM，左指针 > 右指针

Vue 3. x 优化 Diff 算法

• 创建 VNode 确定类型，内容不会变化的 DOM 添加静态标记
• 在 mount / patch 中用位运算判断 VNode 类型
  • 静态提升 hoistStatic
    • 不参与更新的元素，只创建一次，渲染时直接复用
  • 事件侦听器缓存 cacheHandlers
    • 缓存函数，不追踪变化，提升性能

Vue 2 和 Vue3

Vue 2 和 Vue 3 在 diff 算法方面的差异主要体现在：在处理完可复用节点后对剩余节点的处理方式。Vue 2 是通过创建一个存放 key 和对应虚拟 DOM 节点的映射列表 {key, oldVnode}，然后遍历新节点列表的剩余节点，根据新的虚拟 DOM 节点的 key 查看它是否可以在映射表中找到可复用的节点的方式来处理剩余节点，并把这个可复用节点移动到正确的位置。

而 Vue 3 则是创建了一个映射关系数组，这个映射关系数组存放了新节点数组中的剩余节点在旧节点数组上的索引的映射关系。建立完这个数组时随即也就知道了哪些节点是可复用的，然后通过这个数组计算最长递增子序列，这个序列中的节点位置不动，然后将新节点数组中的剩余节点移动到正确的位置。

扩展阅读

• 你了解vue的diff算法吗！说说看
• 说说React diff的原理是什么！
• 使用 key 属性有哪些注意事项！
• 你知道vue中key的原理吗！说说你对它的理解
• React中的key有什么作用！
• 【【前端面试】Vue 3 DOM Diff】
• 【【尚硅谷】Vue 源码解析之虚拟 DOM 和 diff 算法】 【[5.17]—5-19-Vue 2 和 Vue 3 和 React 三者的 diff 算法有什么】
• 【75. 说说 Vue 2 和 Vue 3 中 diff 算法的区别】
• 虚拟DOM（下）：想看懂虚拟DOM算法，先刷个算法题
• @深度对比 React 与 Vue 的 Diff 算法