diff算法的作用

计算出Virtual DOM中真正变化的部分，并只针对该部分进行原生DOM操作，而非重新渲染整个页面。

传统的diff算法

通过循环递归对节点进行依次对比，算法复杂度达到O(n^3)，n是树的节点数，这个就很可怕了———如果要展示1000个节点，得执行上亿次比较……即便是CPU快能执行30亿条命令，也很难在1s内计算出差异。

React 的diff算法

• 什么是调和？ 将Virtual DOM树转换成actual DOM树的最少操作的过程称为调和。

• 什么是React Diff算法？ diff算法是调和的具体实现。

React在传统Diff算法的基础之上，针对前端渲染的具体情况进行了具体分析，做出了相应的优化，从而实现了一个稳定高效的diff算法。

React Diff算法是将Virtual DOM树转换成真实DOM树的最少操作的过程，它用三种策略将传统Diff算法的复杂度从O(n^3) 降到了O(n)的复杂度。

• react diff算法的三种策略
  • 策略1: 虚拟DOM树分层比较（tree diff）： DOM节点跨层级的移动操作发生频率很低，可以忽略不计。
  • 策略2: 组件间的比较（component diff）： 拥有相同类的两个组件将会生成相似的树形结构； 拥有不同类的两个组件将会生成不同的树形结构。
  • 策略3: 元素间的比较（element diff）： 对于同一层级的一组子节点，通过唯一id进行区分。

React Diff算法三种策略实现原理

tree diff

• React通过updateDepth对Virtual DOM树进行层级控制
• 对树分层比较，两棵树 只对同一层次节点 进行比较。如果该节点不存在时，则该节点及其子节点会被完全删除，不会再进一步比较。
• 只需要对树进行一次遍历，就能完成整棵DOM树的比较。

这样，最直接的提升就是复杂度变为线型增长而不是原先的指数增长。

那么问题来了，如果DOM节点出现了跨层级操作,diff会咋办呢？

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

因此 官方建议不要进行DOM节点跨层级操作，可以通过CSS隐藏、显示节点，而不是真正地移除、添加DOM节点。

component diff

React对不同的组件间的比较，有三种策略:

• 同一类型的两个组件，按原策略（层级比较）继续比较Virtual DOM树即可。
• 同一类型的两个组件，组件A变化为组件B时，可能Virtual DOM没有任何变化，如果知道这点（变换的过程中，Virtual DOM没有改变），可节省大量计算时间，所以 用户 可以通过 shouldComponentUpdate() 来判断是否需要判断计算。
• 不同类型的组件，将一个（将被改变的）组件判断为dirty component（脏组件），从而替换 整个组件的所有节点。

注意：如果组件D和组件G的结构相似，但是 React判断是 不同类型的组件，则不会比较其结构，而是删除 组件D及其子节点，创建组件G及其子节点。

element diff

元素间的比较是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进行区分，移动即可。

总结

搞清楚diff算法对于我们理解react是如何进行高效的dom结构渲染是很有帮助的，能够帮助我们更好的理解react底层的一些实现原理。

我们在学习一些框架的时候，不仅要只学会如何使用这些框架，更应该学会它背后的实现逻辑，这样才会有本质的提升。