1. 什么是diff算法

通俗的说,diff算法就是进行差异比较的算法,传统的diff算法通过 循环递归 依次比较来计算一棵树到另一棵树的最少操作(复杂度为O(n^3)),当节点较多时,性能开销较大

2. React的diff算法

React的diff算法针对前端的渲染情况做了优化。主要基于以下3个策略

  1. dom节点的跨层级操作很少,可以忽略
  2. 拥有相同类的组件会生成相似的树形结构,拥有不同类的组件会生成不同的树形结构
  3. 对于同一层级下的一组子节点,通过唯一的id进行区分(即key)

以上三条策略分别对应tree diff、component diff、element diff

tree diff

  1. React通过 updateDepth 对 virtual Dom 层级控制
  2. 对树分层比较,两棵树 只对同一层级节点 进行比较。如果该节点不存在时,则该节点及其子节点会被完全删除,不会再进一步比较。

*如果DOM节点出现了跨层级操作,diff会咋办呢?

diff只简单考虑同层级的节点位置变换,如果是跨层级的话,只有创建节点和删除节点的操作。

component diff

  1. 如果是同类型组件,则按照原策略继续比较virtual DOM树;
  2. 如果不是,则将该组件判断为 dirty component(脏组件),然后整个 unmount(卸载) 这个组件下的子节点对其进行替换;
  • 对于同类型组件,virtual DOM可能并没有发生任何变化,这时我们可以通过 shouldCompoenentUpdate 钩子来告诉该组件是否进行diff,从而提高大量的性能。

element diff

当节点处于同一层级时,diff提供三种节点操作:删除、插入、移动。

  1. 插入:组件 C 不在集合(A,B)中,需要插入
  2. 删除:
    • (1)组件 D 在集合(A,B,D)中,但 D的节点已经更改,不能复用和更新,所以需要删除 旧的 D ,再创建新的。
    • (2)组件 D 之前在 集合(A,B,D)中,但集合变成新的集合(A,B)了,D 就需要被删除。
  3. 移动:组件D已经在集合(A,B,C,D)里了,且集合更新时,D没有发生更新,只是位置改变,如新集合(A,D,B,C),D在第二个,无须像传统diff,让旧集合的第二个B和新集合的第二个D 比较,并且删除第二个位置的B,再在第二个位置插入D,而是 (对同一层级的同组子节点) 添加唯一key进行区分,移动即可。
  • element diff主要是根据 mountIndex 和 lastIndex 进行比较,再确定是否移动 ,mountIndex 是A节点在旧节点集合中的位置,lastIndex 指访问过的节点,在旧节点集合中最右的位置,每次遍历都有可能会更新。

算法描述:

  1. 遍历新节点集合
  2. 如果旧节点集合中有与当前指针所指新节点A相同的节点,则通过 对比节点位置进行判断操作,对比 mountIndex 和 lastIndex :
    • 如果 mountIndex >= lastIndex:不做移动操作。并把lastIndex更新为mountIndex。
    • 如果mountIndex < lastIndex:移动。
  3. 如果新节点集合中有旧节点集合中不存在的节点,添加,更新lastIndex。
  4. 最后遍历旧节点集合,如果存在新节点集合上不存在的点,则将其删除。