React中的diff算法

谈React离不开Virtual DOM,而说到Virtual DOM不得不提diff算法,正是diff算法与Virtual DOM的完美结合,才能让开发者不用时时刻刻担心React的性能问题。

传统diff算法

将一棵树形结构转换成另一棵树形结构,传统diff算法通过循环递归对节点进行依次对比,算法复杂度达到O(n^3),其中n为树中节点的总数。但React不是单纯地引入diff算法,而是引入之后加上自己的“策略”后实现的diff算法。

React diff算法策略

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

基于以上策略,React分别对tree diff、component diff和element diff进行算法优化。

tree diff

基于策略一,React对树进行分层比较,两棵树只对同一层次的节点进行比较。对于出现DOM节点跨层次移动的操作,React是不会进行移动操作的。发现节点不存在时,则该节点及其子节点会被完全删除掉,不会用于进一步的比较,发现了新增的节点时,会直接创建。因此,不要随意进行DOM节点跨层级的操作。

component diff

基于策略二,不同类型的组件很少存在相似的DOM树的情况。当组件A变为组件B时,即使这两个组件结构相似,一旦React认为B和A是不同类型的组件,不会比较两者的结构,而是直接删除组件A,重新创建组件B。对于同一类型的组件,则继续按照原策略比较Virtual DOM树。

element diff

当节点处于同一层级时,分别有3种节点操作:

  • 插入:新的组件类型不在旧集合里,需要对新节点执行插入操作。
  • 移动:旧集合中有新组件类型,且element是可更新的类型,就做移动操作,复用以前的DOM节点。
  • 删除:新集合中有旧组件,但对应的element不同不能直接复用和更新,又或者旧组件不在新集合里,都需要执行删除操作。

总结

知道diff算法工作的原理,就可以有所针对性优化性能。