React之Diff算法

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

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

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

diff 策略

• Web UI 中 DOM 节点跨层级的移动操作特别少，可以忽略不计。（tree diff）
• 拥有相同类的两个组件将会生成相似的树形结构，拥有不同类的两个组件将会生成不同的树形结构。（component diff）
• 对于同一层级的一组子节点，它们可以通过唯一 id 进行区分。（element diff）

1、tree diff

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

image.png

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

2、component diff

• 如果是同一类型的组件，按照原策略继续比较 virtual DOM tree。

• 如果不是，替换整个组件下的所有子节点。

  
  image.png

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

3、element diff

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

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

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

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

image.png

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

state = {
  testList:[
    'll','ww','kk'
  ]
}
componentDidMount = () => {
    this.backgroundDraw();
    setTimeout( () => {this.setState({
      bannerText:'我改变了',
      testList:[
        'kk','ll','ww'
      ]
  })},5000)
}
  
//render两种情况
//一种key = {index}
<div className="strategy-position">
 {
   this.state.testList.map( (item,index) => <li key={index}>{item}</li>)
 }
</div>
  
//一种key = {item}
<div className="strategy-position">
 {
   this.state.testList.map( (item,index) => <li key={item}>{item}</li>)
 }
</div>

image.png

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

对于第一种情况：

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

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

对于第二种情况;

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

说明：

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

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