diff算法和react

react是一个高效的前端框架，它的高效体现在对于DOM元素的修改上面，对比直接操作DOM的原生或者jquery方法，它的优秀之处在于对DOM元素的查找上面。

想象一下，如果让你去查找老颜我在我们这个姓氏宗谱(祈求祖先们的原谅)从唐代到2018年我所在的位置，你会怎么查，指不准你会从我这个位置，去看我爸爸的位置，然后从我爸爸的位置再去看我爷爷的位置。。。。

但是，如果你只是知道有我这个人，却不知道我在我们家伟大的族谱中哪个位置，并且有个大佬告诉你我们这个姓氏在唐代的那个祖先，那想一想，你指不准会从我的祖先开始一个一个的遍历他的所有后代，想象一下，粗略算一下，假设从唐代开始，一共有n个人存在族谱树上，那么你大概需要O(n^3)的时间复杂度(你肯定没看过算法，所以你就忽略O()，看n^3就够了），假设这个 n=1000，再假设你每看一个人，你就能记住他的位置，而且你只需要1秒钟，那么你就需要1000*1000*1000=1000000000，10亿秒，(ง'-')ง加油，有兴趣你可以算算要多长时间:），可以说这就是我们实际用原生js方法去找一个元素的过程！

这太tnd可怕了，所以react提出了虚拟DOM这个东西！

好了我们来看看，diff

react diff算法

1. diff策略

下面介绍一下react diff算法的3个策略

Web UI 中DOM节点跨层级的移动操作特别少，可以忽略不计

拥有相同类的两个组件将会生成相似的树形结构，拥有不同类的两个组件将会生成不同的树形结构。

对于同一层级的一组子节点，它们可以通过唯一id进行区分。

对于以上三个策略，react分别对tree diff,component diff,element diff进行算法优化。

2.tree diff

基于策略一，WebUI中DOM节点跨层级的移动操作少的可以忽略不计，React对Virtual DOM树进行层级控制，只会对相同层级的DOM节点进行比较，即同一个父元素下的所有子节点，当发现节点已经不存在了，则会删除掉该节点下所有的子节点，不会再进行比较。这样只需要对DOM树进行一次遍历，就可以完成整个树的比较。复杂度变为O(n);

疑问：当我们的DOM节点进行跨层级操作时，diff会有怎么样的表现呢？

如下图所示，A节点及其子节点被整个移动到D节点下面去，由于React只会简单的考虑同级节点的位置变换，而对于不同层级的节点，只有创建和删除操作，所以当根节点发现A节点消失了，就会删除A节点及其子节点，当D发现多了一个子节点A，就会创建新的A作为其子节点。

此时，diff的执行情况是：

createA-->createB-->createC-->deleteA

diff算法和react

由此可以发现，当出现节点跨层级移动时，并不会出现想象中的移动操作，而是会进行删除，重新创建的动作，这是一种很影响React性能的操作。因此官方也不建议进行DOM节点跨层级的操作。

3.componnet diff

React是基于组件构建应用的，对于组件间的比较所采用的策略也是非常简洁和高效的。

如果是同一个类型的组件，则按照原策略进行Virtual DOM比较。

如果不是同一类型的组件，则将其判断为dirty component，从而替换整个组价下的所有子节点。

如果是同一个类型的组件，有可能经过一轮Virtual DOM比较下来，并没有发生变化。如果我们能够提前确切知道这一点，那么就可以省下大量的diff运算时间。因此，React允许用户通过shouldComponentUpdate()来判断该组件是否需要进行diff算法分析。

如下图所示，当组件D变为组件G时，即使这两个组件结构相似，一旦React判断D和G是不用类型的组件，就不会比较两者的结构，而是直接删除组件D，重新创建组件G及其子节点。虽然当两个组件是不同类型但结构相似时，进行diff算法分析会影响性能，但是毕竟不同类型的组件存在相似DOM树的情况在实际开发过程中很少出现，因此这种极端因素很难在实际开发过程中造成重大影响。

diff算法和react

4.element diff

当节点属于同一层级时，diff提供了3种节点操作，分别为INSERT_MARKUP(插入)，MOVE_EXISTING(移动),REMOVE_NODE(删除)。

INSERT_MARKUP:新的组件类型不在旧集合中，即全新的节点，需要对新节点进行插入操作。

MOVE_EXISTING:旧集合中有新组件类型，且element是可更新的类型，这时候就需要做移动操作，可以复用以前的DOM节点。

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

注:diff算法来源于https://blog.csdn.net/qq_26708777