react 虚拟DOM的diff算法

今天对diff算法（React16之前）进行了一些学习。

浅谈传统 diff和React diff（16之前的diff）

关于树转换成另一颗树的最小操作数这个问题，最前沿的算法（循环递归比较节点是否相同）的时间复杂度是O（n³）。即对两颗树的节点进行时间复杂度为O（n²）的两两比较，比较结束之后，计算节点到节点的编辑距离（类似海明距离的概念，对节点进行增加、删除、修改等等），这一步需要O（n）的时间，所以最后是O（n³）。

传统diff最大的劣势就是太慢了，尽管它能够适应所有形状的树。React基于两种假设，提出了一套O（n）的启发式算法：

假设一：两种不同类型（type）的元素会产生不同的树；

假设二：开发者可以通过 key prop 来暗示哪些子元素在不同的渲染下能保持稳定。

类型比较

React中针对假设一的策略，就是对不同的根节点进行比较，假如类型不同（比如说div变成了span），就进行拆卸，对整颗树进行重建。例如：

<div>
  <Counter />
</div>

<span>
  <Counter />
</span>

Counter或许是同一个Counter，但因为根节点的不同，会被销毁并重新mount一个新的。

那么类型相同又何如？针对两个相同类型的React元素，原先的DOM节点将被保留，仅对比和更新发生了改变的属性：

<div className="before" title="stuff" />

<div className="after" title="stuff" />

style同理，只更新有变化的属性（下面的color）：

<div style={{color: 'red', fontWeight: 'bold'}} />

<div style={{color: 'green', fontWeight: 'bold'}} />

处理完当前节点，就继续递归子节点。

针对组件元素的比较

组件更新时，实例将保持不变，进而state数据也会保持一致，会更新的是组件实例的props，触发调用组件元素实例的componentWillReceiveProps() 和 componentWillUpdate() 方法（比如说用redux传递props的时候，组件中仅props发生了更新，这时需要依赖着两个生命周期函数去监听组件发生了什么变化）。

接下来，调用render()方法，diff算法开始比较。

对子节点进行递归

在默认条件下，当递归 DOM 节点的子元素时，React 会同时遍历两个子元素的列表；当产生差异时，生成一个 mutation。比如说下面的例子，列表尾部新增一个元素，只会有一个mutation，更新开销很小：

<ul>
  <li>first</li>
  <li>second</li>
</ul>

<ul>
  <li>first</li>
  <li>second</li>
  <li>third</li> <!-- mutation -->
</ul>

假如是插入到表头，React是不会意识到的，它会认为前两次比较有两个mutation，进而重建前两个元素，这种情况下就会有性能问题了。

<ul>
  <li>first</li>
  <li>second</li>
</ul>

<ul>
  <li>second</li> <!-- mutation -->
  <li>third</li>  <!-- mutation -->
  <li>first</li>  <!-- mutation -->
</ul>

在React和Vue中，都有通过key的策略来解决这种低效的情况，下面来讲讲key属性的作用。

key

React 支持 key 属性。当子元素拥有 key 时，React 使用 key 来匹配原有树上的子元素以及最新树上的子元素。

<ul>
  <li key="2015">Duke</li>
  <li key="2016">Villanova</li>
</ul>

<ul>
  <li key="2014">Connecticut</li>
  <li key="2015">Duke</li>
  <li key="2016">Villanova</li>
</ul>

在上面的例子中，React知道2014这个新增到表头的元素是新元素，而2015和2016是原来的元素，只不过移动了位置，所以只发生一个mutation（增加元素）。

在开发中，vscode经常会进行语法提示，比如说vue中，建议我们在v-for中使用唯一ID作为:key。

需要注意的是，在使用元素在数组中的下标作为key，比较适合元素不发生重新排序的时候。因为进行重新排序的时候，组件state会遇到一些问题：组件实例根据key来决定是否更新/复用，而排序将改变实例当前的key，导致非受控组件的state（比如说输入框）可能互相篡改，导致无法预料的变动。

官方文档给出了以下标为key和以id为key的两个例子：

以下标为key导致的问题（非受控组件）

使用id为key的例子

所以要谨慎使用数组下标作为key。

React中应该如何去配合diff算法提高性能？

基于React diff的假设一，我们知道，应该尽可能在有变化的地方使用同一类型的组件，还有更新props，这应该也是我们推荐高阶组件的原因。

基于假设二，用唯一的key来避免DOM节点发生不必要的销毁和创建，key必须要稳定。

三大策略

上面的是围绕官方文档的分析，同学说周日面试的时候被问及React diff的三大策略，其实三大策略就是官方文档上面提到的两个假设（type不同就重建，使用key进行复用），只不过更有针对性，三大策略分别是：

• tree diff
• component diff
• element diff

tree diff

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

基于这一假设，React对VDOM树进行层级比较，一旦发现节点不存在，就会将它的子树删除掉，这样一来就可以在O（n）时间内遍历完整颗树。

所以在使用React开发的时候，官方建议我们不要进行DOM节点跨层级的移动操作，这与React diff的设计思路相悖。在React diff中，移动会被拆分成两个动作，一个是删除原子树，另一个是新增一颗子树，这将会大大影响React应用的性能。

那么平时开发中，跨层级的移动操作如何避免？这要求我们保持稳定的DOM结构，比如说在展示某个元素时，采用css隐藏的方式去控制节点的显示与否，而不对节点进行销毁和创建。

component diff

component diff策略基于的假设，就是前面所说的type比较。

• 针对同类型的组件，将会向下递归；如果不是同类型的组件，就会将组件认为是 dirty component，从而替换整个组件下的所有子节点。
• 针对同类型的组件，有可能VDOM没有变化，在确切知道这一点的情况下，可以通过shouldComponentUpdate() 来判断该组件是否需要进行 diff，节省大量的 diff 运算时间。

element diff

当节点处于同一层级时，可以通过唯一id（key）进行区分。

React中，当节点处于同一层级的时候，可以做三件事，分别是INSERT_MARKUP（插入）、MOVE_EXISTING（移动）和 REMOVE_NODE（删除）。

React在没有key的情况下，会对新老两个节点列表进行遍历，一一比对，一旦发生差异，就会选择删除老的/插入新的，这种情况下会造成很多次冗余的操作。

React diff在面对这种情况，是怎么用key去工作的呢？

先来讲一个比较有用的属性，它叫做lastIndex，它表示访问过的节点在老集合中最右的位置（即最大的位置），进而判定元素是否有必要移动，是一种顺序优化的手段。

1. 它在初始化的时候为0，之后会和旧集合中的元素位置index进行比较。
2. 假如index > lastIndex，就可以认为元素对集合中其他元素的位置没有影响，进而保持其在旧集合中的相对位置，不发生移动，并更新lastIndex为max(index, lastIndex)。
3. 假如index < lastIndex，则需要对旧元素进行移动操作到lastIndex，并更新lastIndex为max(index, lastIndex)。

diff的运行过程：

1. 首先，初始化nextIndex为0，表示当前进行到了哪一个元素的位置；除此之外还有lastIndex也初始化为0，它用来减少移动次数；
2. 对新集合的节点遍历，利用key去判断老集合有没有一样的节点。有的话，拿出老集合中节点下标index，和lastIndex比较，判断是否会发生移动的操作。假如发生了移动，移动到新集合的nextIndex上面；否则不进行移动。没有一样的节点的话，就会在nextIndex的位置创建一个新节点。
3. 遍历完新集合所有节点后，假如旧集合中还有剩余的节点，将它们删除。

网上有很多相关的分析，就不举例了。需要注意的是列表尾部移到头部这种情况，lastIndex会被提前赋为较大值，导致其他节点都会发生移动。在这种情况下，diff效率就不太行了。所以，官方建议我们尽量减少将尾节点移动到列表首部这种操作。

看下diff过程的源码：

_updateChildren: function(nextNestedChildrenElements, transaction, context) {
    var prevChildren = this._renderedChildren;
    var removedNodes = {};
    var mountImages = [];

    // 获取新的子元素数组
    var nextChildren = this._reconcilerUpdateChildren(
        prevChildren,
        nextNestedChildrenElements,
        mountImages,
        removedNodes,
        transaction,
        context
    );

    // 数组为空就提前退出
    if (!nextChildren && !prevChildren) {
        return;
    }

    var updates = null;
    var name;
    var nextIndex = 0;
    var lastIndex = 0;
    var nextMountIndex = 0;
    var lastPlacedNode = null;

    for (name in nextChildren) {
        if (!nextChildren.hasOwnProperty(name)) {
            continue;
        }
        var prevChild = prevChildren && prevChildren[name];
        var nextChild = nextChildren[name];
        if (prevChild === nextChild) {
            // 同一个引用，说明是使用的同一个component,所以我们需要做移动的操作
            // 移动已有的子节点
            // 这里根据nextIndex, lastIndex决定是否移动
            updates = enqueue(
                updates,
                this.moveChild(prevChild, lastPlacedNode, nextIndex, lastIndex)
            );

            // 更新lastIndex
            lastIndex = Math.max(prevChild._mountIndex, lastIndex);
            // 更新component的mountIndex属性
            prevChild._mountIndex = nextIndex;

        } else {
            if (prevChild) {
                // 更新lastIndex
                lastIndex = Math.max(prevChild._mountIndex, lastIndex);
            }

            // 添加新的子节点在指定的位置上
            updates = enqueue(
                updates,
                this._mountChildAtIndex(
                    nextChild,
                    mountImages[nextMountIndex],
                    lastPlacedNode,
                    nextIndex,
                    transaction,
                    context
                )
            );

            nextMountIndex++;
        }

        // 更新nextIndex
        nextIndex++;
        // 存当前处理完的节点，下次位置移动会使用到
        lastPlacedNode = ReactReconciler.getHostNode(nextChild);
    }

    // 移除掉不存在的旧子节点，和旧子节点与新子节点不同的旧子节点
    for (name in removedNodes) {
        if (removedNodes.hasOwnProperty(name)) {
            updates = enqueue(
                updates,
                this._unmountChild(prevChildren[name], removedNodes[name])
            );
        }
    }
}

小结

本文围绕虚拟DOM的diff算法展开分析，我们知道16以后的React已经使用了Fiber Node的概念，将整体的数据结构从树改为了链表结构。但不得不说，16以前的diff算法是React框架具有突破意义的一点，学习了解也是有意义的，之后会再对React16 的 diff 策略进行学习，有兴趣的同学可以先参考一下2和3两篇文章对React16 的 diff 策略进行学习。

参考文章

1. https://segmentfault.com/a/1190000018914249?utm_source=tag-newest
2. https://segmentfault.com/a/1190000016539430
3. https://blog.csdn.net/VhWfR2u02Q/article/details/100011830