React之Diff算法

发布网友发布时间：2022-11-29 01:00

共1个回答

热心网友时间：2023-10-25 06:03

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

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

diff算法
React 通过制定大胆的策略，将 O(n^3) 复杂度的问题转换成 O(n) 复杂度的问题。

diff 策略

两棵树只会对同一层次的节点进行比较。
既然 DOM 节点跨层级的移动操作少到可以忽略不计，React只会对同级节点进行比较。当发现节点已经不存在，则该节点及其子节点会被完全删除掉，不会用于进一步的比较。这样只需要对树进行一次遍历，便能完成整个 DOM 树的比较。

最高效的算法应该是直接将 A 子树移动到 D 节点，但这样就涉及到跨层级比较，时间复杂度会陡然上升。React 的做法比较简单，它会先删除整个 A 子树，然后再重新创建一遍。结合到实际的使用场景，改变一个组件的从属关系的情况也是很少的。
注意：在开发组件时，保持稳定的 DOM 结构会有助于性能的提升。例如，可以通过 CSS 隐藏或显示节点，而不是真的移除或添加 DOM 节点。

同样道理，当 D 组件改为 G 组件时，整棵 D 子树也会被删掉，E、F 节点会重新创建。

三种方法：插入，移动，删除
INSERT_MARKUP插入，新的 component 类型不在老集合里，即是全新的节点，需要对新节点执行插入操作。

MOVE_EXISTING移动，在老集合有新 component 类型，且 element 是可更新的类型，这种情况下 prevChild=nextChild，就需要做移动操作，可以复用以前的 DOM 节点。

REMOVE_NODE删除，老 component 类型，在新集合里也有，但对应的 element 不同则不能直接复用和更新，需要执行删除操作，或者老 component 不在新集合里的，也需要执行删除操作。

对于列表的 Diff，节点的 key 有助于节点的重用：

如上图所示，当没有 key 的时候，如果中间插入一个新节点，Diff 过程中从第三个节点开始的节点都是删除旧节点，创建新节点。当有 key 的时候，除了第三个节点是新创建外，第四和第五个节点都是通过移动实现的。

为什么会有上述两种情况的区别呢？

对于第一种情况：

key = {index}在更新前后是相同的，都是1，2，3

但是对比，key相同时，元素不同，则删除插入

对于第二种情况;

key = {item} key分别是 'll','ww','kk' ，更新后虚拟dom key分别是kk ll ww，在进行element diff时，发现kk元素节点在更新前后是相同的，无需创建，会进行移动

说明：

对于第一种情况，其实和没有key是一样的，除非其顺序和key保持一致；

针对这一现象，React 提出优化策略：允许开发者对同一层级的同组子节点，添加唯一 key 进行区分，虽然只是小小的改动，性能上却发生了翻天覆地的变化！