diff算法

传统计算一棵树结构转换成另一棵树结构的最少操作，算法复杂度达到 O($n^3$)。

React 通过制定大胆的策略，将 O($n^3$) 复杂度的问题转换成 O(n) 复杂度的问题

1. Web UI 中 DOM 节点跨层级的移动操作特别少，可以忽略不计

基于这个策略，React 对树的算法进行了简洁明了的优化，即对树进行分层比较，两棵树只会对同一层级的节点进行比较。

如果出现 DOM 节点跨层级的移动操作，diff 算法表现？

表现为删除和新增整个子树，并不会有移动操作。

React 官方建议不要进行 DOM 节点的跨层级操作

2. 相同类的两个组件才会生成相似的树形结构

• 如果是同一类型的组件，按照原策略继续比较 Virtual DOM 树即可。
• 如果不是，将会替换整个组件下的所有子节点。

3. 对于同一层级的一组节点，可以通过唯一的 key 值进行区分

对于同一层级的节点，diff 提供了 3 中操作，分别是 插入、移动、删除。

整个过程用文字描述为：

在新的节点列表中，以第一个复用的节点为开始，保留在这个节点之后，和它相对顺序不变的那些节点；

对于新列表中其他复用节点，标记为移动；

对于新列表中的新的节点，标记为新增；

对于旧的列表中不再出现的节点，标记为删除。

官方建议

在开发过程中，尽量减少类似将最后一个节点移动到列表首部的操作（注：会引起 n - 1 个节点移动，而不是 1 个）。当节点数量过大或者更新操作过于频繁时，这在一定程度上会影响 React 的渲染性能。

4. 总结

基于以上三个策略，React 分别对 tree diff、 component diff、 element diff 进行了算法优化