React的diffing算法学习

本文作者：IMWeb llunnn 原文出处：IMWeb社区 未经同意，禁止转载

这段时间主要在学习React的使用，React是一个用于构建用户界面的框架，其使用了一些方式来使得视图渲染更加高效，这里主要记录一下学习期间了解到的Diffing方法相关的内容。

Virtual DOM

DOM对象是十分复杂的，一个简单的DOM元素也具有非常多的属性和方法，因此对DOM的操作其实是比较耗费时间的。使用原生的javascript进行编程时，我们总是手动地调用DOM操作来更新视图，这其中就可能会包含一些冗余的操作。React使用了Virtual DOM，将DOM状态以javascript对象的形式保存，并通过reconciliation来与真实的DOM保持同步。这种方式使得视图发生变化时，我们可以用尽量少的DOM操作来实现视图的更新。

可能的误区

这里并不是说使用了VirtualDOM方法可以加快DOM操作的速度，而是说React让页面在不同状态之间变化时，使用次数尽量少的DOM操作来完成。另外React如何进行这些DOM操作是不需要程序员去考虑的，我们只需要声明变化前后的状态，React就会去计算实际操作的过程。也由于包含了这个计算过程，React每次DOM操作的实际耗时一定是比我们执行原生的DOM操作要长的。

所以说React实际上是简化了程序员的工作，并用额外的计算过程尽可能地保持DOM操作的高效。

Diffing Algorithm

那么要如何去计算两个状态间DOM的变化呢？React使用了Reconciliation方法。Reconciliation其实就是一种对比的方法，用来比较两棵DOM树之间的差异。

在经典算法中，计算两棵树相互转换的最短距离的diff算法复杂度为O(n^3)，这意味着计算的时间会随着DOM增加以3次方的速度增长，基本是不可取的。因此React优化了经典的diff算法，实现了O(n)复杂度的对比算法。React基于两点假设来比较Virtual DOM树，以实现这种线性复杂度：

1. 将两个不同类型的根节点产生的子树视为不同的树。
2. 开发者为相同父元素的子节点设置key来帮助React判断元素是否稳定。

在这两个假设下，React这样来进行diff算法：

对两棵树进行层间的比较。从根节点开始，对比两棵树的根节点。若两节点为不同类型的节点，则直接将旧的树上该节点以及该节点下的子树删除，重新构建一颗DOM树。因此，如果元素发生了跨层的移动，如将A的兄弟节点B移动到A的子节点的位置，React将删除并重新构建B节点。另外，如果替换了子树的根节点，（如从

变为）那么即使子节点完全相同，则整棵树都会被重新渲染。

若进行比较的两节点是类型相同的HTML DOM元素，则对他们的属性进行比较，根据属性的差异对DOM进行修改，之后对子元素进行同样的比较和更新。若两元素是类型相同的React自定义组件，会触发组件实例的生命周期，若shouldComponentUpdate()返回了false，则会直接将两个组件和他们的子元素视为相同；否则会继续更新当前子树。

在同一层的节点（互为兄弟节点）中，React逐个进行比较。如果设置了key，会根据对相同key的元素成对比较，若没有设置key则按节点顺序进行比较。

基于Diff算法的性能优化思路

由于在O(n)复杂度下React的Diff算法计算出的编辑距离可能不是最短距离，我们可以通过遵循一些规则来帮助React计算出尽可能少的DOM操作。

为列表渲染设置唯一稳定的key

在使用map等进行列表渲染时需要设置key来帮助React寻找匹配元素，因此key在当前子树的同一层级中应该是唯一的，相同key的不同元素可能导致新旧节点的错误匹配。另外，这里稳定的key是指会在长时间保持不变的key。有时候为了方便会直接使用index作为key，然而如果列表中间插入了元素，就会造成key的改变，插入点之后的元素就会被删除并重新构建。

保持节点类型的稳定

这里有一个demo，其中list是一个非常大的DOM元素列表。点击按钮将section元素变为div元素。

render() {
    if (this.state.show) {
      return (
        <div>
          <button onClick={()=>{this.setState({show: !this.state.show})}}>click</button>
          <section>
            {list}
          </section>
        </div>
      );
    } else {
      return (
        <div>
          <button onClick={()=>{this.setState({show: !this.state.show})}}>click</button>
          <div>  // 这里section替换为div
            {list}
          </div>
        </div>
      );
    }
  }

这里根元素的类型发生了变化，尽管其子元素完全相同，React还是会选择移除整颗子树，重新渲染全部子节点。

谨慎删除节点元素

继续使用上一个demo，增加一个节点在section前，点击按钮控制span是否渲染。

render() {
    if (this.state.show) {
      return (
        <div>
          <button onClick={()=>{this.setState({show: !this.state.show})}}>click</button>
          <span>TEST</span>
          <section>
            {list}
          </section>
        </div>
      );
    } else {
      return (
        <div>
          <button onClick={()=>{this.setState({show: !this.state.show})}}>click</button>
          {false} // 这里移除了span后占位
          <section>
            {list}
          </section>
        </div>
      );
    }
  }

这里并不是一个列表的渲染，于是没有设置key。但由于React在同层对元素逐个比较，若在点击按钮后直接移除span元素，则会将新树的section和旧的span进行对比，之后直接移除旧的section和其中的list，重新渲染，导致巨大的开销。这里我们可以考虑用一个占位的false，使得React正确的让两个section进行比较。

合并相似组件

如果两个组件被交替渲染的不同组件有着一部分相似的输出，可以考虑将他们合并为相同的组件，并使用条件判断来返回内容不同的部分。这使得内容变化时组件不至于被整个移除（因为不同组件交替渲染时组件类型发生了变化），可以尽可能地保留不发生变化的部分。

提前阻止diff算法

虽然React将diff优化到了O(n)，但随着节点数量的增多，这还是一个大的开销。

有时候，不需要diff算法我们也可以判断组件不会被更新。在组件生命周期shouldComponentUpdate(nextProps, nextState)中，可以比较当前的props, state和新的props, state。若判断不需要更新组件，则直接return false;会阻止之后的render过程，当然也就不会进行diff算法的对比。

React.PureComponent就对shouldComponentUpdate做了一个简单的实现，会对props和state做一次浅比较。但是浅比较也是需要时间的，且其花费的时间可能不低于diff算法，因此适合较为复杂且在相同props和state下有相同展示内容的组件使用。