React学习（9）—— 高阶应用：虚拟Dom差异比对算法

React提供了一系列声明性的API接口，因此在使用时不必担心每次库的更新会修改API接口。这样可以降低编写应用的复杂度，但是带来的问题是无法很好的理解React是如何实现这些功能的。这篇文章会介绍React的差异比对算法——“融合算法”是如何执行的。

差异匹配算法实现的前提

我们先来看看第一个值得关注的我问题：render()方法的作用是创建React元素的树形结构，当state或props发生更新后，render()会返回一个与之前有差异的结构树。在这个机制下，React需要弄清楚如何匹配最近的树并有效的更新UI。

针对以上问题，有一些通用的算法可供参考，比如比对2颗树的差异，在前一个颗树的基础上生成最小操作树，但是这个算法的时间复杂度为n的三次方=O(n*n*n)，当树的节点较多时，这个算法的时间代价会导致算法几乎无法工作。

架设在我们使用React时，一共部署了1000个元素，那么使用上面的算法，我们要比对数亿次才能得到比对的结果，根本不可能在一个浏览器中短时间完成。React实现了一个计算复杂度是O(n)的算法来解决这个问题，这个算法基于2个假设：

不同类型的2个元素产生不同的树。
开发人员可以为不同的子节点在渲染之前设定一个“key”属性值。

实际上，这个假设对于几乎所有的实际用例都是有效的。

差异算法

对于2颗有差异的树，React首先比对2颗树的根节点。根据跟节点的类型是否相同，算法接下来会执行不同的操作。

Types不一样

一旦2棵树之间的根元素类型不一样，React会直接移除旧的树并构建出新的树。例如从<a>变更为<img>、<Article>变更为<Comment>、<Button>变更为<div>，所有的这些变化都会导致整颗树重构。

重构一棵新的树时，所有的旧节点都会移除。组件的componentWillUnmount()方法会被调用。然后到构建完成之后新的Dom会替换原来的Dom。此时组件的componentWillMount()和componentDidMount()会依次被调用。旧树Dom上的所有状态都会丢失。

根据这个特性，根节点之后的所有组件都会卸载并重建，状态也会随之改变。例如下面2个组件对比：

<div>
  <Counter />
</div>

<span>
  <Counter />
</span>

Counter组件会被销毁并重新安装一个新的组件。

Dom元素拥有相同的类型

当比较React元素为相同类型时，React会查看元素上的属性来比对。比对之后，React会保持的Dom节点不改变然后仅仅更新不同的属性值，例如：

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

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

在比对这2个元素之后，React知道仅仅需要修改当前Dom的className。在更新style时，React同样知道仅仅需要更新修改部分即可。例如：

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

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

在转换这2个组件时，React知道仅仅需要修改color的样式，而fontWeight不必发生变动。

在处理完当前Dom节点后，React依次对子节点进行递归。

组件元素拥有相同的类型

当一个组件发生更新后，实例依然是原来的实例，所以状态还是以前的状态。React通过属性值（props）的更新来影响需要更新组件，此时组件实例的componentWillReceiveProps()和componentWillUpdate()方法会被调用。

然后，render()方法会被调用并返回一个Dom，差异算法会递归比对之前返回Dom的差异。

递归子元素

默认情况下，在递归子元素的Dom节点时，React同时对2个子元素列表进行迭代比对，如果发现差异都会产生一个突变（关于突变的概念请见React学习第六篇性能优化介绍不可变数据结构部分）。

例如，当增加一个元素在子元素的队尾，这2颗树的转换效率很高：

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

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

React先匹配<li>first</li>2棵树，然后再匹配<li>second</li>。最后直接就添加<li>third</li>节点。

如果代码按下面的方式修改2颗树，执行的效率相对较差：

<ul>
  <li>Duke</li>
  <li>Villanova</li>
</ul>

<ul>
  <li>Connecticut</li>
  <li>Duke</li>
  <li>Villanova</li>
</ul>

React会突变修改所有的子节点，最终<li>Duke</li>and<li>Villanova</li>会被重新渲染。所以这种方式会带来很大的效率问题。

Keys

为了解决上面的问题，React提供了一个“key”属性。当所有的子元素都有一个key值，React直接使用key值来比对树形结构中的所有子节点列表。例如为上面的的例子增加一个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可以知道key='2014'的节点是一个新值另外2个节点仅仅需要移动一下位置。

在实际使用中，key值并不难找。在常规业务中，很多列表都自然包含业务相关的ID了：

<li key={item.id}>{item.name}</li>

当无法使用业务ID时，也可以额外增加一个ID值来标记列表差异，比如根据要使用的数据生成一个hash值，React不需要key值全局唯一，只需要在兄弟节点之间保持唯一即可。

最差情况下，你可以使用索引数据（0、1、2、....n）。使用索引需要注意的是，如果列表发生重新排序效率会很糟糕。