react diff算法

diff算法作为Virtual DOM的加速器，其算法的改进优化是React整个界面渲染的基础和性能的保障，同时也是React源码中最神秘的，最不可思议的部分

1.传统diff算法

计算一棵树形结构转换为另一棵树形结构需要最少步骤，如果使用传统的diff算法通过循环递归遍历节点进行对比，其复杂度要达到O(n^3)，其中n是节点总数，效率十分低下，假设我们要展示1000个节点，那么我们就要依次执行上十亿次的比较。

下面附上一则简单的传统diff算法：

let result = [];
// 比较叶子节点
const diffLeafs = function (beforeLeaf, afterLeaf) {
    // 获取较大节点树的长度
    let count = Math.max(beforeLeaf.children.length, afterLeaf.children.length);
    // 循环遍历
    for (let i = 0; i < count; i++) {
        const beforeTag = beforeLeaf.children[i];
        const afterTag = afterLeaf.children[i];
        // 添加 afterTag 节点
        if (beforeTag === undefined) {
            result.push({ type: "add", element: afterTag });
            // 删除 beforeTag 节点
        } else if (afterTag === undefined) {
            result.push({ type: "remove", element: beforeTag });
            // 节点名改变时，删除 beforeTag 节点，添加 afterTag 节点
        } else if (beforeTag.tagName !== afterTag.tagName) {
            result.push({ type: "remove", element: beforeTag });
            result.push({ type: "add", element: afterTag });
            // 节点不变而内容改变时，改变节点
        } else if (beforeTag.innerHTML !== afterTag.innerHTML) {
            if (beforeTag.children.length === 0) {
                result.push({
                    type: "changed",
                    beforeElement: beforeTag,
                    afterElement: afterTag,
                    html: afterTag.innerHTML
                });
            } else {
                // 递归比较
                diffLeafs(beforeTag, afterTag);
            }
        }
    }
    return result;
}

2.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（先创建再删除）

由此可以发现，当出现节点跨层级移动时，并不会出现想象中的移动操作，而是会进行删除，重新创建的动作，这是一种很影响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树的情况在实际开发过程中很少出现，因此这种极端因素很难在实际开发过程中造成重大影响

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

INSERT_MARKUP:新的组件类型不在旧集合中，即全新的节点，需要对新节点进行插入操作。
MOVE_EXISTING:旧集合中有新组件类型，且element是可更新的类型，这时候就需要做移动操作，可以复用以前的DOM节点。
REMOVE_NODE:旧组件类型，在新集合里也有，但对应的element不同则不能直接复用和更新，需要执行删除操作，或者旧组件不在新集合里的，也需要执行删除操作。
插入：组件 C 不在集合（A,B）中，需要插入

删除：（1）组件 D 在集合（A,B,D）中，但 D的节点已经更改，不能复用和更新，所以需要删除 旧的 D ，再创建新的。

（2）组件 D 之前在 集合（A,B,D）中，但集合变成新的集合（A,B）了，D 就需要被删除。

移动：组件D已经在集合（A,B,C,D）里了，且集合更新时，D没有发生更新，只是位置改变，如新集合（A,D,B,C），D在第二个，无须像传统diff，让旧集合的第二个B和新集合的第二个D 比较，并且删除第二个位置的B，再在第二个位置插入D，而是 （对同一层级的同组子节点） 添加唯一key进行区分，移动即可。

重点说下移动的逻辑：

情形一：新旧集合中存在相同节点但位置不同时，如何移动节点

1）看着上图的 B，React先从新中取得B，然后判断旧中是否存在相同节点B，当发现存在节点B后，就去判断是否移动B。
B在旧 中的index=1，它的lastIndex=0，不满足 index < lastIndex 的条件，因此 B 不做移动操作。此时，一个操作是，lastIndex=(index,lastIndex)中的较大数=1.

注意：lastIndex有点像浮标，或者说是一个map的索引，一开始默认值是0，它会与map中的元素进行比较，比较完后，会改变自己的值的（取index和lastIndex的较大数）。

（2）看着 A，A在旧的index=0，此时的lastIndex=1（因为先前与新的B比较过了），满足index<lastIndex，因此，对A进行移动操作，此时lastIndex=max(index,lastIndex)=1。

（3）看着D，同（1），不移动，由于D在旧的index=3，比较时，lastIndex=1，所以改变lastIndex=max(index,lastIndex)=3

（4）看着C，同（2），移动，C在旧的index=2，满足index<lastIndex（lastIndex=3），所以移动。

由于C已经是最后一个节点，所以diff操作结束。
情形二：新集合中有新加入的节点，旧集合中有删除的节点

1）B不移动，不赘述，更新l astIndex=1

（2）新集合取得 E，发现旧不存在，故在lastIndex=1的位置 创建E，更新lastIndex=1

（3）新集合取得C，C不移动，更新lastIndex=2

（4）新集合取得A，A移动，同上，更新lastIndex=2

（5）新集合对比后，再对旧集合遍历。判断 新集合 没有，但 旧集合 有的元素（如D，新集合没有，旧集合有），发现 D，删除D，diff操作结束。

diff的不足与待优化的地方

看图的 D，此时D不移动，但它的index是最大的，导致更新lastIndex=3，从而使得其他元素A,B,C的index<lastIndex，导致A,B,C都要去移动。

理想情况是只移动D，不移动A,B,C。因此，在开发过程中，尽量减少类似将最后一个节点移动到列表首部的操作，当节点数量过大或更新操作过于频繁时，会影响React的渲染性能。

参考原文链接：https://blog.csdn.net/qq_26708777/article/details/78107577
https://www.jianshu.com/p/3ba0822018cf