Vue的Diff算法详解
在 Vue 框架的 render 阶段，虚拟 DOM 的创建是不可避免的。这也引出了 Diff 算法的问题，其目的是尽量复用真实 DOM 元素，因为新创建的真实 DOM 元素会耗费时间和内存。由于真实 DOM 的属性相比虚拟 DOM 元素更多（tips：实际上像 Chrome 浏览器已经做了很多优化，C++的运行速度比 javascript 快多了，所以未来再使用虚拟 DOM 实际上可能会变成负优化， 这点未来有待观察，如 Sevlte 就抛弃虚拟 DOM 了），Vue 倾向于选择复用，因此诞生了 Diff 算法。
Vue 的 Diff 算法与 React 有许多相似之处，但在实现上存在一些差异。以下是 Vue 的 Diff 算法的一些原则：
在 Vue 中，Diff 算法跟 React 非常相似，但实现上有所不同，Vue 的 diff 算法有以下原则：
# Diff 算法的基本原则：
- 同层级比较： 只比较同层级的节点，跨层级的节点不进行比较。
- 节点判断： 判断节点是否相同（通过 tag 和 key 判断）。
- 子节点比较： 如果节点相同，则比较它们的子节点。
# 不同情况下的 Diff 处理：
# 单节点改多节点
直接删除原有单节点，并创建新节点的孩子节点。
# 多节点改单节点
直接删除原有多节点，并创建新节点。
# 多节点改多节点
这是最复杂的情况，因为正常遍历比较的时间复杂度为 O(n^2)，因此 Vue 为这种情况引入了双指针算法。创建四个指针，分别指向新孩子数组的头尾和旧孩子数组的头尾，然后开始循环。
循环结束条件是双方孩子节点的头指针超过尾指针。
整个循环分为四种情况，其中前三种是优化方案，最后一种是兜底方案。这四种方案是互斥的，每次循环只执行其中一种方案。
# 第一种：头指针比较
如果两者的头指针所指向的节点是相同的（tag 和 key 相同），则递归比较它们的子节点，并将双方的头指针往后挪一位。
# 第二种：尾指针比较
与第一种情况类似，比较尾指针的节点，如果相同则递归比较子节点，尾指针向前挪一位。
# 第三种：交叉指针比较
这个比较方案也分两种情况，同时修改的是旧孩子的节点。
首先，比较旧头指针和新尾指针，如果两者相同，将旧头指针所指向的节点插入到旧尾指针指向节点的下一个前面。这种顺序是不会乱的，因为永远都是旧尾节点下一个的前面，如果没有下一个则使用 appendChild。同时，将旧头节点向前挪位，新尾指针向后挪位。
然后，比较旧尾指针和新头指针，如果两者相同，将旧尾指针所指向的节点插入到旧头指针所指节点的前面。同样，顺序也是不会乱的。
# 第四种：兜底方案
如果前面三种方案都不适用，为旧孩子的节点以 key 生成一个哈希表，然后让新头指针的节点使用 key 去哈希表中找到对应的旧节点，并将其插入到旧头指针的前面。如果找不到，则新创建一个新的节点插入到旧头指针的前面。同时，将新头指针向后挪一位。
# 最后
当循环结束后，如果旧头指针仍小于旧尾指针，则表示这些节点应该被删除。
如果新头指针仍小于新尾指针，则表示这些节点都应该新增。
Vue 就是根据以上这些方案来实现 Diff 算法。
# React 和 Vue 的 Diff 算法差异
- 数据结构差异： React 使用链表结构，Vue 使用树型结构。因此，React 是通过 while 循环先处理孩子节点，再处理 sibling；而 Vue 则通过递归处理节点，部分节点的比较会导致性能较差。
- DOM 修改时机： 在 React 中，Diff 算法只会为虚拟 DOM 打上 effect 标记，真实 DOM 的修改是在 commit 节点时进行的；而 Vue 在 Diff 算法中，边比较边修改真实 DOM。
- 多节点复用策略： React 采用双循环+哈希表的方式处理多节点的复用；Vue 采用双指针+哈希表的方式处理。
这些原则和优化策略使得 Vue 能够高效地进行 DOM 的 diff 和更新，以最小化更新的成本。Vue 的 Diff 算法是其高效性能的基石，这些原理的理解有助于更深入地了解 Vue 框架的内部工作原理。