React, vue2, vue3 Diff 算法的区别

React Diff

React 是 Fiber 架构的， Fiber 是一个链表的机构，但是没有设置反向指针，所以没有使用双端对比的方式去优化 Diff 算法 (ps: 在没有反向指针的情况下，从右往左遍历链表很困难)。

使用 Fiber 架构的原因是实现异步，不阻断页面的渲染。

由于 React 无法使用双端对比放方法来优化 Diff ，所以在进行多节点 Diff 的时候需要进行两轮遍历。

1. 处理更新的节点
2. 处理剩下不属于更新的节点

React 多节点的 Diff 算法的实现在 reconcileChildrenArray 函数中

vue2 Diff

Vue2 采用了双端 Diff 算法，算法流程主要是：

1. 对比头头、尾尾、头尾、尾头是否可以复用，如果可以复用，就进行节点的更新或移动操作。
2. 如果经过四个端点的比较，都没有可复用的节点，则将就的子序列保存为节点 key 为 key ，index 为 value 的 map 。
3. 拿新的一组子节点的头部节点去 map 中查找，如果找到可复用的节点，则将相应的节点进行更新，并将其移动到头部，然后头部指针右移。
4. 然而，拿新的一组子节点中的头部节点去旧的一组子节点中寻找可复用的节点，并非总能找到，这说明这个新的头部节点是新增节点，只需要将其挂载到头部即可。
5. 经过上述处理，最后还剩下新的节点就批量新增，剩下旧的节点就批量删除。

区别

Vue2 的 Diff 与 React 的 Diff 主要区别为：

1. Vue2 采用双端比对的方式优化了 Diff 算法，而 React 由于是 Fiber 架构，是单链表，没有使用双端比对的方式优化
2. Vue2 在 Diff 的时候与 React 在 Diff 的时候都采用了 map 来加快查找的效率，但是 Vue2 构造的 Diff 是 key -> index 的映射，而 React 构造的 Diff 是 key -> Fiber节点 的映射。

Vue3 Diff

Vue3 的 Diff 算法与 Vue2 的 Diff 算法一样，也会先进行双端比对，只是双端比对的方式不一样。Vue3 的 Diff 算法借鉴了字符串比对时的双端比对方式，即优先处理可复用的前置元素和后置元素。

Vue3 的 Diff 算法的流程如下

1. 处理前置节点
2. 处理后置节点
3. 新节点有剩余，则挂载剩余的新节点
4. 旧节点有剩余，则卸载剩余的旧节点
5. 乱序情况（新、旧节点都有剩余），则构建最长递增子序列
6. 节点在最长递增子序列中，则该节点不需移动
7. 节点不在最长递增子序列中，则移动该节点