1. 什么是diff算法
通俗的说,diff算法就是进行差异比较的算法,传统的diff算法通过 循环递归 依次比较来计算一棵树到另一棵树的最少操作(复杂度为O(n^3)),当节点较多时,性能开销较大
2. React的diff算法
React的diff算法针对前端的渲染情况做了优化。主要基于以下3个策略
- dom节点的跨层级操作很少,可以忽略
- 拥有相同类的组件会生成相似的树形结构,拥有不同类的组件会生成不同的树形结构
- 对于同一层级下的一组子节点,通过唯一的id进行区分(即key)
以上三条策略分别对应tree diff、component diff、element diff
tree diff
- React通过 updateDepth 对 virtual Dom 层级控制
- 对树分层比较,两棵树 只对同一层级节点 进行比较。如果该节点不存在时,则该节点及其子节点会被完全删除,不会再进一步比较。
*如果DOM节点出现了跨层级操作,diff会咋办呢?
diff只简单考虑同层级的节点位置变换,如果是跨层级的话,只有创建节点和删除节点的操作。
component diff
- 如果是同类型组件,则按照原策略继续比较virtual DOM树;
- 如果不是,则将该组件判断为 dirty component(脏组件),然后整个 unmount(卸载) 这个组件下的子节点对其进行替换;
- 对于同类型组件,virtual DOM可能并没有发生任何变化,这时我们可以通过 shouldCompoenentUpdate 钩子来告诉该组件是否进行diff,从而提高大量的性能。
element diff
当节点处于同一层级时,diff提供三种节点操作:删除、插入、移动。
- 插入:组件 C 不在集合(A,B)中,需要插入
- 删除:
- (1)组件 D 在集合(A,B,D)中,但 D的节点已经更改,不能复用和更新,所以需要删除 旧的 D ,再创建新的。
- (2)组件 D 之前在 集合(A,B,D)中,但集合变成新的集合(A,B)了,D 就需要被删除。
- 移动:组件D已经在集合(A,B,C,D)里了,且集合更新时,D没有发生更新,只是位置改变,如新集合(A,D,B,C),D在第二个,无须像传统diff,让旧集合的第二个B和新集合的第二个D 比较,并且删除第二个位置的B,再在第二个位置插入D,而是 (对同一层级的同组子节点) 添加唯一key进行区分,移动即可。
- element diff主要是根据 mountIndex 和 lastIndex 进行比较,再确定是否移动 ,mountIndex 是A节点在旧节点集合中的位置,lastIndex 指访问过的节点,在旧节点集合中最右的位置,每次遍历都有可能会更新。
算法描述:
- 遍历新节点集合
- 如果旧节点集合中有与当前指针所指新节点A相同的节点,则通过
对比节点位置进行判断操作,对比 mountIndex 和 lastIndex :
- 如果 mountIndex >= lastIndex:不做移动操作。并把lastIndex更新为mountIndex。
- 如果mountIndex < lastIndex:移动。
- 如果新节点集合中有旧节点集合中不存在的节点,添加,更新lastIndex。
- 最后遍历旧节点集合,如果存在新节点集合上不存在的点,则将其删除。