面试题 -- Diff 算法的原理?
# 为什么要用Diff算法
由于在浏览器中操作 DOM 是很昂贵的，频繁的操作 DOM，会产生一定的性能问题，这就是虚拟 DOM 的产生原因。虚拟 DOM 本质上是 JavaScript 对象，是对真实 DOM 的抽象状态变更时，记录新树与旧树的差异，最后把差异更新到真正的 DOM 中。
即使使用了 Virtual DOM 来进行真实DOM的渲染，在页面更新的时候，也不能全量地将整颗 Virtual DOM 进行渲染，而是去渲染改变的部分，这时候就需要一个计算 Virtual DOM 树改变部分的算法了，这个算法就是 Diff算法。
diff算法的作用：用来修改DOM的一小段，不会引起dom树的重绘。
# Vue Diff算法
Diff算法将 虚拟DOM 的某个节点数据改变后生成的新的node节点与旧节点进行比较，并替换为新的节点，具体过程就是调用 Patch 方法，比较新旧节点，一边比较一边给真实 DOM 打补丁进行替换
简单来说，Diff算法有以下过程
- 同级比较，再比较子节点
- 如果节点类型不同，直接干掉前面的节点，再创建并插入新节点，不会再比较这个节点以后的子节点。
- 子节点：先判断一方有子节点，一方没有子节点的情况(如果新的children没有子节点，将旧的节点移除)）
- 比较都有子节点的情况(核心diff)，递归比较子节点
正常diff两个树的时间复杂度是 O(n^3)， 但实际情况下我们很少会进行跨层级的移动DOM，所以vue将diff进行了优化，从 O(n^3) –> O(n) ，只有当新旧children都为多个子节点时才需要用核心的diff算法进行同层级比较。
# Vue 2
Vue2.x 的核心 Diff算法 采用了 双端比较算法，同时从新旧children的两端开始进行比较，借助Key值找到可复用的节点，再进行相关操作。
新旧children中的节点只有顺序是不同的时候，最佳的操作应该是通过移动元素的位置来达到更新的目的，需要在新旧children的节点中保存映射关系，以便能够在旧children的节点中找到可复用的节点。key也就是children中节点的唯一标识。
相比 React 的 Diff算法，同样情况下可以减少移动节点的次数，减少不必要的性能损耗，更加的优雅。
# Vue 3
Vue3.x 借鉴了 ivi算法 和 inferno算法。
在创建 VNode 时就确定其类型，以及在 mount/patch 的过程中采用位运算来判断一个 VNode 的类型，在这个基础之上再配合核心的 Diff算法，使得性能上较 Vue2.x有了提升(实际的实现可以结合Vue3.x的源码看)
该算法中还运用了动态规划的思想求解最长递归子序列。