⚡ 30 秒速记

• 差异比较以类型与身份判断复用
• Vue 2 常见双端比较，Vue 3 策略有所变化
• 新版列表可借旧索引序列减少移动
• 编译标记帮助跳过静态内容
• 最少移动与整体最快不是同一个指标

理解差异算法，要先分清识别同一个节点和安排怎么移动这两件事。 稳定键找到身份，类型决定能否复用，之后才比较内容与顺序。Vue 2 常用双端比较处理列表，Vue 3 在相应路径中结合前后缀、索引映射和递增子序列，并利用编译信息缩小更新范围。算法细节有版本前提，最终性能仍由比较、节点操作和浏览器渲染共同决定。

版本校准： 原理文章中的代码代表特定实现与写作时间。应用到当前项目时，应先确认浏览器、框架或工具的主版本，再区分稳定的规范语义、可变化的内部实现和项目自身约束。

一、前言

有同学问：能否详细说一下 diff 算法。

简单说：diff 算法是一种优化手段，将前后两个模块进行差异化比较，修补(更新)差异的过程叫做 patch，也叫打补丁。

详细的说，请阅读这篇文章，有疑问的地方欢迎联系「松宝写代码」一起讨论。

文章主要解决的问题：

• 1、为什么要说这个 diff 算法？
• 2、虚拟 dom 的 diff 算法
• 3、为什么使用虚拟 dom？
• 4、diff 算法的复杂度和特点？
• 5、vue 的模板文件是如何被编译渲染的？
• 6、vue2.x 和 vue3.x 中的 diff 有区别吗
• 7、diff 算法的源头 snabbdom 算法
• 8、diff 算法与 snabbdom 算法的差异地方？

二、为什么要说这个 diff 算法？

因为 diff 算法是 vue2.x ， vue3.x 以及 react 中关键核心点，理解 diff 算法，更有助于理解各个框架本质。

说到「diff 算法」，不得不说「虚拟 Dom」，因为这两个息息相关。

比如：

• vue 的响应式原理？
• vue 的 template 文件是如何被编译的？
• 介绍一下 Virtual Dom 算法？
• 为什么要用 virtual dom 呢？
• diff 算法复杂度以及最大的特点？
• vue2.x 的 diff 算法中节点比较情况？

等等

三、虚拟 dom 的 diff 算法

我们先来说说虚拟 Dom，就是通过 JS 模拟实现 DOM ，接下来难点就是如何判断旧对象和新对象之间的差异。

Dom 是多叉树结构，如果需要完整的对比两棵树的差异，那么算法的时间复杂度 O(n ^ 3)，这个复杂度很难让人接收，尤其在 n 很大的情况下，于是 React 团队优化了算法，实现了 O(n) 的复杂度来对比差异。

实现 O(n) 复杂度的关键就是只对比同层的节点，而不是跨层对比，这也是考虑到在实际业务中很少会去跨层的移动 DOM 元素。

虚拟 DOM 差异算法的步骤分为 2 步：

• 首先从上至下，从左往右遍历对象，也就是树的深度遍历，这一步中会给每个节点添加索引，便于最后渲染差异
• 一旦节点有子元素，就去判断子元素是否有不同