React Diff | GeniusFunny的个人博客

计算一棵树形结构转换成另一棵树形结构，传统的diff算法算法复杂度达到O(n^3)。React通过制定策略，将O(n^3)复杂度的问题转换成O(n)复杂度。

Diff 策略

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

Tree Diff

对树进行分层比较，两棵树只会对同一层次的节点进行比较。

当节点跨层级移动时，并不会出现想象中的移动操作，而是进行create-delete操作（影响性能）。

Component Diff

1. 如果是同类型的组件，按原策略继续比较Virtual DOM tree。
2. 如果不是同类型的组件，则将组件判断为dirty component，从而替换整个组件下的所有子节点。
3. 如果是同一类型的组件，并且Virtual DOM没有发生变化，那么将会省下大量的diff运算时间，因此React允许用户通过shouldComponentUpdate()来判断组件是否需要进行diff。

Element Diff

当节点处于同一层级时，React Diff提供了三种节点操作，分别为：INSERT_MARKUP、MOVE_EXISTING、REMOVE_NODE

• INSERT_MARKUP: 原集合不包含新的component类型，新节点需执行插入操作
• MOVE_EXISTING: 原集合包含新的component类型，且element时可更新的类型，generateComponentChildren已调用receiveComponet，这种情况下prevChild=nextChild，就需要做移动操作，可以复用以前的DOM节点。
• REMOVE_NODE: 老compone类型，在新集合也有，但对应的element不同则不能直接复用和更新，需执行删除操作，或者老component不在新集合中，也需要执行删除操作。

允许开发者对同一层级的同组子节点添加唯一key作为标识。