详解diff 算法

1、 介绍和认识

Diff算法（差异算法）是一种用于比较两个文本或数据结构之间差异的算法。它主要用于计算出两个版本之间的增量更新，以便在更新时只传输或应用发生变化的部分，而不是整个数据或文本。Diff算法在软件开发、版本控制、文本处理等领域有广泛的应用。

diff 算法是渲染器中最重要的部分，用通俗一些的话来说，其实就是比较变化了哪些部分呗，应用到前端其实就是dom结构层部分的变化。

👉 这里我们主要是通过React和Vue在diff算法的应用方面简单来聊一聊，React和Vue都是基于vdom的框架,dom渲染过程如下：

• 组件渲染（返回 vdom）=>渲染器 (对比更改vdom 同步到 dom) 在dom变化的时候都是对比vdom
• 再次渲染 (产生新的 vdom)=> 渲染器(对比新旧 vdom 树)=> 更改部分更新到dom

👉 这里对比两棵vdom 树，找到有差异的部分的算法，就叫做 diff 算法,采用图的方式我们可以来看一下,这里我简单画了一个辅助我们理解。

- 作用

看完了diff算法的简单认识，那么在实际工作和框架场景之中对于采用的diff算法有什么作用呢

提升性能： diff算法最重要的就是在优化视图更新过程中进行使用的。通过比较新旧虚拟 DOM 树差异，可以精准地计算出需要更新的部分，从而避免不必要的 DOM 操作，大幅提高性能。

2、vue2的diff算法原理

vue2的diff算法原理

Vue2的 diff 算法基于 虚拟 DOM,本质上其实就是利用逐层比较（same-node diffing）和树形结构 diffing来优化性能的

（1）逐层比较

Vue在 diff 算法中逐层对比新旧虚拟 DOM 树的节点,如果新旧节点的标签（tag）、属性（props）、事件等都相同，Vue就不修改直接跳过。 如果节点类型不同（比如，标签类型、组件不同），则整个节点直接替换。

（2）通过节点的 key 属性优化节点比较

Vue通过每个节点的 key 属性来优化比较过程，尤其是当列表（如 v-for）渲染时，key能显著提高性能。

同一层级的节点有 key，根据key的值来追踪节点，实现高效的位置重排和节点复用。

没有 key，依赖节点的位置来进行比较，会导致性能问题（尤其是大型列表）

（3） 最小化 DOM 操作

比较差异之后，Vue 会计算出需要执行的最小 DOM ，然后批量更新来操作实际 DOM。利用文档碎片（DocumentFragment）来批量插入和删除节点，减少对DOM的频繁操作。

（4） 递归更新子树

对于差异节点，Vue递归更新子树。递归操作一直深入到树的叶子节点，直到所有节点都被比较和更新完成。

详细步骤

生成 => 比对 => 检查 => 更新

生成虚拟DOM:视图更新时,生成新的虚拟DOM树

开始比对：将新旧虚拟DOM树进行比对，从根节点开始对比，如果不同，则会递归地对比每一层的子节点。

检查变化：新旧节点相同，则不做更新；新旧节点不同，判断节点类型，如果节点类型变化，直接替换节点。如果是同类型的节点，则比较属性、事件等差异。

更新 DOM：根据差异生成最小的 DOM 更新（包括增、删、改节点等），然后批量更新到真实 DOM。

在diff算法上的优化

那么vue在diff算法之中有哪些地方比较有优势呢：

（1）key 的使用

列表中的节点每个列表项提供一个唯一的 key 值，Vue 会通过 key 来判断节点的变化位置，以避免全量重渲染（侧面证明了v-for过程之中key在渲染优化方面的不可或缺性）每个列表项提供一个唯一的 key 值。通过 key，框架可以追踪节点的位置，从而优化节点的重排和复用，避免因顺序变化而导致整个列表重渲染。

（2）双端对比

移动元素，Vue 采用双端对比策略，从两边同时比较，快速找到节点的位置和变化。

（3）静态节点提升

对于静态节点（不变化的节点），Vue 会缓存起来，避免不必要的比较和更新

案例

举个例子简单说明一下：

// 旧的虚拟 DOM
const oldVNode = {
  tag: 'div',
  children: [
    { tag: 'p', children: ['Hello'] },
    { tag: 'span', children: ['World'] }
  ]
};

// 新的虚拟 DOM
const newVNode = {
  tag: 'div',
  children: [
    { tag: 'p', children: ['Hello Vue'] },  // 内容发生了变化
    { tag: 'span', children: ['World'] },   // 没有变化
    { tag: 'span', children: ['!'] }        // 新增了一个 span
  ]
};

当vue对比上面的新旧diff结构的时候，分别顺序以下：

比较p标签的内容，发现变化了('Hello'=>'Hello Vue' )，更新该节点的内容。
比较 spa 标签，发现没有变化，所以保持原样。(span没有改变)
发现树中新增了有一个新的 span 节点，所以会在原来的 span 后面插入一个新的 span 标签。(插入了一个span元素))

3、vue3的diff算法

1. 虚拟 DOM 的实现变化

Vue 2 使用的虚拟 DOM 是基于 JavaScript 对象 的形式，而 Vue 3 则使用了 Proxy 来创建虚拟 DOM，带来了一些性能上的改进，尤其是在依赖收集和响应式系统方面。

Vue 2：

• 在 Vue 2 中，虚拟 DOM 的节点通过 JavaScript 对象表示，节点的属性是直接在对象上定义的。
• Vue 2 采用了传统的 Object.defineProperty 方式来实现响应式，性能上相对较弱，特别是在处理大数据量时。

Vue 3：

• Vue 3 通过使用 Proxy 实现了更加高效的响应式系统，避免了 Vue 2 中在每个属性上添加 getter 和 setter 的性能开销。
• 虚拟 DOM 的处理也变得更加轻量，基于 Proxy 的代理对象可以直接更新属性，而不需要像 Vue 2 那样通过 getter/setter 进行拦截，提升了性能。

2. Diff 算法的优化

Vue 3 对 Diff 算法本身进行了一些优化，使其在复杂场景下的性能表现更加优秀。

Vue 2：

• 在 Vue 2 中，Diff 算法是基于 双指针算法 和 递归对比 的，它会递归比较两个虚拟 DOM 树的每个节点。
• 对于动态列表的渲染，Vue 2 会采用 “就地更新” 策略：如果列表中某个元素位置发生变化，Vue 会在 DOM 中移动元素，而不是销毁并重新创建节点。
• Vue 2 在列表渲染时，如果没有明确提供 key，它会使用索引作为默认 key，这在某些情况下可能导致性能问题。

Vue 3：

• Vue 3 对 Diff 算法进行了重构，优化了 最小 DOM 操作 的执行方式，特别是在处理列表更新和组件更新时表现更加高效。
• Vue 3 引入了 静态提升 和 静态节点缓存，它会尝试将不变的 DOM 树（即没有变化的节点）提升为静态节点，这样在后续的更新中可以避免对这些节点进行不必要的对比和更新。
• Vue 3 引入了更加智能的 块级更新，它能在更新时更加细粒度地判断哪些部分的节点需要更新，避免了无关部分的更新。

3. 组件 Diff 的改进

Vue 3 对组件的 Diff 算法做了进一步优化，尤其是在 组件的更新 和 复用 上。

Vue 2：

• 在 Vue 2 中，组件的比较依赖于父组件的更新和子组件的 key。如果没有合适的 key，Vue 2 会使用默认的比较方式，导致性能损失。
• Vue 2 需要通过 v-if 或 v-show 来控制组件的挂载和卸载，这会影响到组件的生命周期和 Diff 的效率。

Vue 3：

• Vue 3 对组件的更新进行了更多细致的优化，组件的 重渲染 在 Vue 3 中更加高效。
• 在 Vue 3 中，Fragment 支持（即组件可以返回多个根节点）使得组件的结构更加灵活。
• Vue 3 在组件更新时，会进行更多的 缓存和重用。组件实例会更加智能地复用，减少不必要的销毁和重建。

4. “Fragment” 支持和多个根节点

Vue 3 引入了对 Fragment 的支持，允许组件返回多个根节点。在 Vue 2 中，每个组件必须有一个单一的根节点，而这限制了组件的灵活性。引入 Fragment 后，Vue 3 可以更好地处理没有根节点的组件，减少了节点的拆分和合并的需要，从而优化了 Diff 的效率。

Vue 2：

• 每个组件只能有一个根节点，所有子节点都必须包裹在这个根节点内。
• 如果某个组件中需要渲染多个元素，Vue 2 需要通过额外的元素（如 <div>）来包裹。

Vue 3：

• 支持组件返回多个根节点（Fragment），这样可以避免不必要的 DOM 元素包裹，提升了渲染效率和代码的可读性。

5. 性能优化

Vue 3 引入了更多的性能优化措施，特别是在 初始化渲染 和 动态更新 的过程中。

Vue 2：

• Vue 2 在初始化时会先创建整个虚拟 DOM 树，然后再与实际 DOM 进行对比。这一过程中，所有的节点都会被创建并进行 Diff。
• 对于动态更新，Vue 2 会进行一些额外的检查，特别是在列表渲染和条件渲染时，可能导致性能下降。

Vue 3：

• Vue 3 在初始化渲染时，采用了 静态提升，将不变的节点提升到渲染函数外部，从而减少了不必要的重新渲染和 Diff。
• 在更新过程中，Vue 3 通过优化 动态更新的渲染逻辑，让 Diff 更加高效，特别是在大型应用中，性能提升非常明显。

总结

Vue 3 相对于 Vue 2 的 Diff 算法优化主要体现在以下几个方面：

1. 引入了 Proxy 响应式系统，提升了虚拟 DOM 和响应式的效率。
2. 优化了 Diff 算法，特别是通过 静态提升 和 静态节点缓存 来减少不必要的 DOM 更新。
3. 支持 Fragment 和多个根节点，提升了组件的灵活性和渲染效率。
4. 进一步优化了组件的更新和复用，减少了不必要的销毁和创建。

总体来说，Vue 3 在性能、灵活性和可维护性方面都有了显著的提升，特别是在大型应用的性能上，相比 Vue 2 更加高效。