react--diff算法

1、算法复杂度
传统的diff算法是通过循递归对节点进行一次比较；算法复杂度O（n^3）;
react 引入了virtualDOM；并制定了大胆的策略；算法复杂度O（n）；
2、react diff策略
1）Web UI中DOM节点跨层级的移动操作特别少；可以忽略不计
2）拥有相同类的两个组件将会生成相似的树形结构，拥有不同类的两个组件将会生成不同的树形结构
3）对于同一层级的一组子节点，他们可以通过唯一ID进行区分
3、tree diff（策略一）
两棵树只会对同一层次的节点进行比较；对于不同层级的节点，只有创建和删除操作
注：
官方建议：不要进行DOM节点跨层级的操作
4、component diff（策略二）
1）如果是同一类型的组件，按照原策略继续比较virtualDOM树即可
2）如果不是，则将该组件判断为dirty component，从而替换整个组件下的所有子节点
3）对于同一类型的组件，有可能其VirtualDOM没有任何变化，如果能够确切知道这点，那么就可以节省大量的diff运算时间。因此，react允许用户通过shouldComponentUpdate()来判断该组件是否需要进行diff算法分析；
注：
官方建议：不同类型的组件很少存在组件相似DOM树的情况
5、element diff
diff比较重对节点的操作
1）插入
2）移动
3）删除
举个例子：

例1.png

diff差异化比较分析：
初始化：
lastIndex=0：旧队列比较的元素的最大index
nextIndex=0：新队列中的当前比较的index
1）取新队列中的B元素与旧队列比较，此时B在旧队列中的curIndex值为1；lastIndex=0；由于curIndex>lastIndex;B不移动；并将lastIndex=max（lastIndex，curIndex）=1；nextIndex++；
2）取新队列中的E元素与旧队列比较，此时E在旧队列中不存在；则将该元素插入比较队列中；nextIndex++；
3）取新队列中的C元素与旧队列比较，此时C在旧队列中的curIndex值为2；lastIndex=1；由于curIndex>lastIndex;C不移动；并将lastIndex=max（lastIndex，curIndex）=2；nextIndex++；
4）取新队列中的A元素与旧队列比较，此时A在旧队列中的curIndex值为0；lastIndex=2；由于curIndex<lastIndex;A移动；并将lastIndex=max（lastIndex，curIndex）=2；nextIndex++；
5)当完成新元素队列的差异化比较后，需要对旧队列进行循环遍历；判断是否存在新集合中没有单旧集合存在的节点，此时发现存在这样的节点D，因此删除节点D，到此diff操作全部完成。
6、建议
如果队列ABCD变成DABC；这样还是会每一个都要遍历对比；
建议：
在开发过程中，尽量减少类似将最后一个节点移动到列表首部的操作。
当节点数量过大或操作过于频繁时，在一定程度上会影响React渲染性能