react diff算法

diff算法的作用？

计算出虚拟dom中变化的部分，并只针对该部分进行原生dom的操作，而不是对整个页面重新渲染。

传统的diff算法就是使用循环递归的方式，时间复杂度是O（n^3)

React diff算法:调和是diff算法的具体实现。

调和是react将虚拟dom转换成真实dom的最少操作过程。

react用三大策略将O（n^3)变成O（n)复杂度。

1、tree diff 2、component diff 3、element diff

tree diff

1、react通过updateDepth对虚拟dom树进行层级控制。

2、对树分层比较，两棵树只对同一层节点进行比较。如果该节点不存在时，则该节点和其子节点会完全被删除，不会在进一步比较。

3、只需遍历一次，就可完成整棵DOM树的比较。如果跨层级的话,只有创建节点和删除节点的情况。

component tree

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

1、同一类型的2个组件，按照原策略（层级比较）继续比较虚拟dom树即可。

2、同一类型的两个组件，组件A变化为组件B时,可能虚拟dom没有任何变化，如果知道这点（变换的过程中，Virtual DOM没有改变），可节省大量计算时间，所以 用户 可以通过 shouldComponentUpdate() 来判断是否需要 判断计算。

3、不同类型的组件，将被改变的组件判定为dirty component组件，从而替换整个组件的所有节点。

element diff

当节点处于同一层级时，diff提供了3种节点的操作，插入、移动、删除。

插入操作：新的component 类型不在老集合里， 即是全新的节点，需要对新节点执行插入操作。

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

移动操作：

1、新旧集合中存在相同节点但位置不同时，如何移动节点。

2、新集合中有新加入的节点，旧集合中有删除的节点。

下标index移动，先从新的中取出B元素,然后在看旧的里面是否存在B，如存在,就去判断是否移动。B在旧的里面index=1,它的lastIndex=0,不满足index<lastIndex，所以B不一定，此时lastIndex= Math.max(index,lastIndex)较大数 = 1;下面的元素依次这样移动。