React 中的 diff 算法

React diff

1. 为什么使用虚拟 DOM ？
   浏览器在处理 DOM 的时候会很慢，处理 JavaScript 会很快，页面复杂的时候，频繁操作 DOM 会有很大的性能开销（每次数据变化都会引起整个 DOM 树的重绘和重排）。
   为了避免频繁操作 DOM，React 会维护两个虚拟 DOM，如果有数据更新，会借此计算出所有修改的状态集中到一起，统一更新一次虚拟 DOM。
2. diff 是什么？
   React 会维护两个虚拟 DOM，如果有数据更新，会借此计算出所有修改的状态，然后将这些变化更新到真实 DOM 上，diff 算法就是比较两个虚拟 DOM 树的策略。
3. 虚拟 DOM 一定会提高性能吗？
   不一定。
   因为虚拟 DOM 虽然会减少 DOM 操作，但也无法避免 DOM 操作。
   它的优势是在于 diff 算法和批量处理策略,将所有的 DOM 操作搜集起来，一次性去改变真实的 DOM,但在首次渲染上，虚拟 DOM 会多了一层计算，消耗一些性能，所以有可能会比 html 渲染的要慢

传统 diff 算法

通过循环递归对节点进行依此对比，其算法复杂度达到了O(n^ 3)，也就是说，如果展示一千个节点，就要计算十亿次。

React v16 优化

React通过三大策略完成了优化：

Web UI 中 DOM 节点跨层级的移动操作特别少，可以忽略不计。
拥有相同类的两个组件将会生成相似的树形结构，拥有不同类的两个组件将会生成不同的树形结构。
对于同一层级的一组子节点，它们可以通过唯一 id 进行区分。

分别对应：tree diff、component diff、element diff

tree diff

同级比较：在对比的过程中，如果发现节点不在了，会完全删除不会对其他地方进行比较，这样只需要对树遍历一次就OK了

component diff

两种策略：

1. 相同类型的组件

按照层级比较继续比较虚拟DOM树即可。

特殊情况：当组件A如果变化为组件B的时候，有可能虚拟DOM并没有任何变化，所以用户可以通过shouldComponentUpdate() 来判断是否需要更新，判断是否计算

2. 不同类型的组件

React会直接判定该组件为dirty component（脏组件），无论结构是否相似，只要判断为脏组件就会直接替换整个组件的所有节点

element diff

节点比较，对于同一层级的一子自节点，通过唯一的key进行比较

当所有节点处以同一层级时，React 提供了三种节点操作：

1. 插入（INSERT_MARKUP）：新的 component 类型不在老集合里， 即是全新的节点，需要对新节点执行插入操作。
2. 移动（MOVE_EXISTING）：在老集合有新 component 类型，且 element 是可更新的类型，generateComponentChildren 已调用 receiveComponent，这种情况下prevChild=nextChild，就需要做移动操作，可以复用以前的 DOM 节点。（传统 diff 检测到不相同就直接删除重建）
3. 删除（REMOVE_NODE）：老 component 类型，在新集合里也有，但对应的 element 不同则不能直接复用和更新，需要执行删除操作，或者老 component 不在新集合里的，也需要执行删除操作。

具体的 diff 过程
遍历新的一层节点，使用 lastIndex 记录每次比较后的节点最新索引，使用 index 表示在旧的一层中该节点的索引。

在新的一层中，如果发现该节点存在过，通过 key 找到该节点在旧的一层中的坐标 index，如果 index < lastIndex 就移动该节点，否则不动，然后更新 lastIndex = max(lastIndex, index)

如果该节点没有存在过，就新建，但是不更新 lastIndex

相同位置

插入新节点

当最后一个节点移动到第一个位置时，可能出现的问题（所有节点都需要移动）

为什么不能使用 index 作为 key 值？
因为通过 key 找到的两个节点不相同，需要删除重建，使用唯一值（比如id）描述每个节点，这样起到 diff 算法的作用。
下面的例子中的节点全都需要重建，因为每次通过 key 找到的节点都不相同，无法发挥 diff 算法的作用

参考

https://juejin.cn/post/7116326409961734152