ReactJS中的DOM diff算法

翻译自:https://calendar.perfplanet.com/2013/diff/
万分感谢Christopher Chedeau！

React是Facebook开发的一个用于构建用户界面的JavaScript库。它从零开始设计的时候就考虑了性能的问题。在这篇文章中，我将介绍React中的diff算法和渲染过程。这样你就能够对自己的应用进行优化。

DIff算法

在介绍实现细节之前，先了解一下React是如何工作的

    var MyComponent = React.createClass({
        render: function() {
            if(this.props.first) {
                return
                         <div className="first">
                            <span>A Span</span>
                         </div>;
            } 
            else {
                return 
                         <div className="second">
                            <p> A paragraph </p>      
                         </div>;
            }
        }
    });

在任何时候，你都会描述你想要的界面。理解render的结果并不是真正的DOM节点是很重要。这些只是轻量级的javaScript对象。我们称之为虚拟DOM（Virtual DOM）

React将使用这种表示方法尝试从一个渲染结果切换到另一个渲染结果的最少步数。例如，从<MyComponent first={true} />开始，然后替换为<MyComponent first={false} />，最后将它们都删除。

渲染过程(简化)

1.初始renderA

创建节点：`<div className="first"><span>A Span</span></div>`

生命周期：Mounting

2.再次renderB

 2.1比较父节点div =>相同，跳过 进行下面操作
 2.2比较父节点div属性=>不相同,下面进行替换属性操作
     替换属性：替换`className="first"`为`className="second"`
 2.3比较子节点=>不相同，下面进行子节点替换操作
     替换节点：删除`<span>A Span</span>` 插入`<p>A Paragraph</p>`

生命状态：Updating

3.移除节点

移除节点：直接移除div父节点即可，子节点也会被完全删除`<div className="second"><p>A Paragraph</p></div>`

生命周期：Unmounting

上述的例子是为了讲述React的简单工作过程，下面开始介绍一些细节

不同节点类型的比较

为了在树之间进行比较，我们首先要能够比较两个节点，在React中即比较两个虚拟DOM节点，当两个节点不同时，应该如何处理。这分为两种情况：
（1）节点类型不同

renderA: <span />
renderB: <p />
=> [removeNode <span />], [insertNode <p />]

当在树中的同一位置前后输出了不同类型的节点，React直接删除前面的节点，然后创建并插入新的节点。

（2）节点类型相同，但是属性不同
第二种节点的比较是相同类型的节点，算法就相对简单而容易理解。React会对属性进行重设从而实现节点的转换。例如：

renderA: <div className="first" />
renderB: <div className="second" />
=> [replaceAttribute className second]

虚拟DOM的style属性稍有不同，其值并不是一个简单字符串而必须为一个对象，因此转换过程如下：

renderA: <div style={{color: 'red'}} />
renderB: <div style={{fontWeight: 'bold'}} />
=> [removeStyle color], [addStyle font-weight 'bold']

逐层进行节点比较

查找任意两棵树之间最少修改数的时间复杂度是O(n^3)。可以想象到，这很难处理。
React使用一种简单但强大的启发式方式来优化到了接近O(n)。

React只会按层比较两棵树。这样就显著的降低了问题的复杂度，并且由于Web应用中很少将一个组件在不同层之间的移动，从而产生太多负面影响。Web应用通常只会在子节点之间横向移动。

逐层比较

例如，考虑有下面的DOM结构转换

DOM结构转换1

A节点被整个移动到D节点下，直观的考虑DOM Diff操作应该是

A.parent.remove(A); 
D.append(A);

但因为React只会简单的考虑同层节点的位置变换，对于不同层的节点，知识简单的创建和删除。当根节点发现子节点A不见了，就会直接销毁A;而当D发现自己多了一个子节点Ａ，则会创建一个新的Ａ作为子节点。因此对于这种结构的转变的实际操作是：

A.destroy();
A = new A();
A.append(new B());
A.append(new C());
D.append(A);

可以看到，以A为根节点的树被整个重新创建。

虽然看上去这样的算法有些“简陋”，但是其基于的是第一个假设：两个不同组件一般产生不一样的DOM结构。根据React官方博客，这一假设至今为止没有导致严重的性能问题。这当然也给我们一个提示，在实现自己的组件时，保持稳定的DOM结构会有助于性能的提升。例如，我们有时可以通过CSS隐藏或显示某些节点，而不是真的移除或添加DOM节点。

列表节点的比较

上面介绍了对于不在同一层的节点的比较，即使他们完全一样，也会销毁并重新创建.那么当它们在同一层时，又是如何处理的呢？这就涉及到列表节点的Diff算法。相信很多使用React的同学大多遇到过这样的警告：

警告

这是React在遇到列表时却又找不到key时提示的警告。虽然无视这条警告大部分界面也会正确工作，但这通常意味着潜在的性能问题。因为React觉得自己可能无法高效地去更新这个列表

列表节点的操作通常包括添加、删除和排序。例如下图，我们需要往B和C直接插入节点F，在jQuery中我们可能会直接使用$(B).after(F)来实现。而在React中，我们只会告诉React新的界面应该是A-B-F-C-D-E，由Diff算法完成更新界面。

列表节点比较1

这时如果每个节点都没有唯一的标识，React无法识别每一个节点，那么更新过程会很低效，即，将C更新成F，D更新成C，E更新成D，最后再插入一个E节点。效果如下图所示：

列表节点比较2

可以看到，React会逐个对节点进行更新，转换到目标节点。而最后插入新的节点E，涉及到的DOM操作非常多。diff总共就是移动、删除、增加三个操作，而如果给每个节点唯一的标识（key），那么React优先采用移动的方式，能够找到正确的位置去插入新的节点，如下图所示：

列表节点比较3

对于列表节点顺序的调整其实也类似于插入或删除，下面结合示例代码我们看下其转换的过程。仍然使用前面提到的示例：
https://supnate.github.io/react-dom-diff/index.html ，我们将树的形态从shape5转换到shape6：

DOM结构转换3

题外话：如果你之前接触vue.js，那么你将会很容易理解这个所谓的key，在vue.js中组件复用中使用的就是这个key,如果你对vue.js也敢兴趣的话，请自行去Vue.js官方网站进行学习

组件的比较

React应用一般由许多用户定义的组件构成。这些组件最终会转换为一个主要由div组成的树。这些附加信息被diff算法利用了。React只会匹配类型相同的组件。

如果一个<Header>被<Other>替换，React将删除Header组件然后创建一个Other组件。我们不需要花费宝贵的时间来匹配两个不一样的组件。

组件比较

事件代理

给DOM节点增加事件监听器是一个既慢又消耗内存的事情。React实现了一个叫“事件代理”的技术，并且重新实现了一个W3C兼容的事件系统。因此使得IE 8的事件处理不再是一个问题，所有的事件都能够跨浏览器使用。

下面让我解释一下它的实现。首先将单个事件监听器添加到文档的根节点上。当事件被触发后，浏览器给出目标DOM节点。为了在整个DOM树上传递事件。React不是在虚拟DOM进行迭代，而是利用每个React组件的唯一ID。我们可以使用一个简单的字符串来获取所有父节点的ID。通过将事件监听器存储在一个Hash表中，我们发现比将事件添加到虚拟DOM效率更高。下面是事件在虚拟DOM中分发的过程。

//dispatchEvent('click', 'a.b.c', event)
clickCaptureListeners['a'](event);
clickCaptureListeners['a.b'](event);
clickCaptureListeners['a.b.c'](event);
clickBubbleListeners['a.b.c'](event);
clickBubbleListeners['a.b'](event);
clickBubbleListeners['a'](event);

浏览器为每个事件和监听器创建一个新的事件对象。该对象有一个原始事件对象的引用，并且能够进行修改。这样做会占用更多的内存，因此React专门为这些对象创建了一个对象池。当需要一个事件对象时，直接从对象池中重用。这样显著的降低了垃圾回收。

渲染批处理

当需要调用一个组件的setState时，React将它标记为脏节点。在事件循环的最后才重新渲染所有的脏节点

这种批处理意味着在一个事件循环event-loop，准确地说是一次事件循环中对DOM进行更新。这个特性对构建高性能的JavaScript应用一般来说非常难。但在React中，我们默认就可以利用这个特性。

渲染批处理

渲染子树

当调用setState时，组件会重建子节点的虚拟DOM。如果在根元素上通用setState，整个React应用都会被重新渲染。所有的组件，包括没有发生改变的组件都会调用自己的render方法。这样做效率低的相当可怕，但在实际应用的时候还是可以很好的工作的。因为我们不需要直接操作DOM

首先，我们讨论的是如何显示用户界面。因为屏幕空间的限制，我们通常需要一次性按顺序显示成千上完个元素。由于整个界面都可以管理，JavaScript能够足够快地处理业务逻辑

其次，在编写React代码时，我们不需要在每次发生改变后就调用根元素的setState方法。我们只需要在接收到改变事件的节点或者它的一些上层节点调用该方法，很少需要上溯到顶部。这意味着变化被局限在用户交互的地方

渲染子树

选择性渲染子树

最后，我们还能够组件一些子树的重新渲染。如果一个组件实现了下面的方法

boolean shouldComponentUpdate(object nextProps, object nextState)

我们可以基于组件之前的状态或者下一个状态决定它是否需要重新渲染。如果实现合理的话，这样做能够极大的提高程序的性能

为了使用这个功能，我们需要能够比较JavaScript对象。但比较爱哦的时候又会引发许多事情，比如是“深比较”还是“浅比较”，是否应该使用不可变数据结构或深拷贝

需要注意的是，这个方法会不断调用，因此需要确保它的计算尽可能耗时较少。

选择性渲染子树

总结

这种技术能够使React变得更快已经不是一件新鲜事。我们也已经知道，DOM的处理非常耗时、应该批量进行读写操作、时间处理效率更高...

大家现在还经常讨论他们，因为在正常的JavaScript代码中很难达到这些目标。React让这些优化默认就会发生，高性能应用的开发变得更简单

React的性能模型非常易于理解：每个setState重新渲染一棵子树。如果想尽量压榨性能，应该尽可能减少调用setState或使用shouldComponentUpdate阻止重新渲染大的子树