Diff算法

React 采用声明式的 API 描述 UI 结构，每次组件的状态或属性更新，组件的 render 方法都会返回一个新的虚拟 DOM 对象，用来表述新的 UI 结构。如果每次 render 都直接使用新的虚拟 DOM 来生成真实 DOM 结构，那么会带来大量对真实 DOM 的操作，影响程序执行效率。事实上，React 会通过比较两次虚拟 DOM 结构的变化找出差异部分，更新到真实 DOM 上，从而减少最终要在真实 DOM 上执行的操作，提高程序执行效率。这一过程就是 React 的调和过程（Reconciliation），其中的关键是比较两个树形结构的 Diff 算法。

在 Diff 算法中，比较的两方是新的虚拟 DOM 和旧的虚拟 DOM，而不是虚拟 DOM 和真实 DOM，只不过 Diff 的结果会更新到真实 DOM 上。

正常情况下，比较两个树形结构差异的算法的时间复杂度是 O(N^3)，这个效率显然是无法接受的。React 通过总结 DOM 的实际使用场景提出了两个在绝大多数实践场景下都成立的假设，基于这两个假设，React 实现了在 O(N) 时间复杂度内完成两棵虚拟 DOM 树的比较。这两个假设是：

  1. 如果两个元素的类型不同，那么它们将生成两棵不同的树。

  2. 为列表中的元素设置 key 属性，用 key 标识对应的元素在多次 render 过程中是否发生变化。

下面介绍在不同情况下，React 具体是如何比较两棵树的差异的。React 比较两棵树是从树的根节点开始比较的，根节点的类型不同，React 执行的操作也不同。

当根节点是不同类型时

从 div 变成 p、从 ComponentA 变成 ComponentB，或者从 ComponentA 变成 div，这些都是节点类型发生变化的情况。根节点类型的变化是一个很大的变化，React 会认为新的树和旧的树完全不同，不会再继续比较其他属性和子节点，而是把整棵树拆掉重建（包括虚拟 DOM 树和真实 DOM 树）。这里需要注意，虚拟 DOM 的节点类型分为两类：一类是 DOM 元素类型，比如 div、p 等；一类是 React 组件类型，比如自定义的 React 组件。在旧的虚拟 DOM 树被拆除的过程中，旧的 DOM 元素类型的节点会被销毁，旧的 React 组件实例的 componentWillUnmount 会被调用；在重建的过程中，新的 DOM 元素会被插入 DOM 树中，新的组件实例的 componentWillMount 和 componentDidMount 方法会被调用。重建后的新的虚拟 DOM 树又会被整体更新到真实 DOM 树中。这种情况下，需要大量 DOM 操作，更新效率最低。

当根节点是相同的DOM元素类型时

如果两个根节点是相同类型的 DOM 元素，React 会保留根节点，而比较根节点的属性，然后只更新那些变化了的属性。例如：

<div className="foo" title="React" />
<div className="bar" title="React" />

React 比较这两个元素，发现只有 className 属性发生了变化，然后只更新虚拟 DOM 树和真实 DOM 树中对应节点的这一属性。

当根节点是相同的组件类型时

如果两个根节点是相同类型的组件，对应的组件实例不会被销毁，只是会执行更新操作，同步变化的属性到虚拟 DOM 树上，这一过程组件实例的 componentWillReceiveProps() 和 componentWillUpdate() 会被调用。注意，对于组件类型的节点，React 是无法直接知道如何更新真实 DOM 树的，需要在组件更新并且 render 方法执行完成后，根据 render 返回的虚拟 DOM 结构决定如何更新真实 DOM 树。

比较完根节点后，React 会以同样的原则继续递归比较子节点，每一个子节点相对于其层级以下的节点来说又是一个根节点。如此递归比较，直到比较完两棵树上的所有节点，计算得到最终的差异，更新到 DOM 树中。

当一个节点有多个子节点时，默认情况下，React 只会按照顺序逐一比较两棵树上对应的子节点。例如，比较下面的两个节点，两棵树上的 <li>first</li> 和 <li>second</li> 子节点会分别被匹配，最终只会插入一个新的节点 <li>third</li>。

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

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

但如果在子节点的开始位置新增一个节点，情况就会变得截然不同。例如下面的例子，<li>third<li> 插入子节点的第一个位置，React 会把第一棵树的 <li>first</li> 和第二棵树的 <li>third</li> 进行比较，把第一棵树的 <li>second</li> 和第二棵树的 <li>first</li> 进行比较，最后发现新增了一个 <li>second</li> 节点。这种比较方式会导致每一个节点都被修改。

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

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

为了解决这种低效的更新方式，React 提供了一个 key 属性。在 2.4 节已经介绍过，当渲染列表元素时，需要为每一个元素定义一个 key。这个 key 就是为了帮助 React 提高 Diff 算法的效率。当一组子节点定义了 key，React 会根据 key 来匹配子节点，在每次渲染之后，只要子节点的 key 值没有变化，React 就认为这是同一个节点。例如，为前面的例子定义 key：

<ul>
    <li key="first">first</li>
    <li key="second">second</li>
</ul>

<ul>
    <li key="third">third</li>
    <li key="first">first</li>
    <li key="second">second</li>
</ul>

定义 key 之后，React 就能判断出 <li key="third">third</li> 这个节点是新增节点，<li key="first">first</li> 和 <li key="second">second</li> 两个节点并没有发生改变，只是位置发生了变化而已。如此一来，React 只需要执行一次插入新节点的操作。这里同时揭露了另一个问题，尽量不要使用元素在列表中的索引值作为 key，因为列表中的元素顺序一旦发生改变，就可能导致大量的 key 失效，进而引起大量的修改操作。例如，下面的写法应该尽量避免：

<ul>
    {list.map((item,index) => <li key={index}>{item}</li>)
</ul>

最后，需要提醒读者，本章介绍的 Diff 算法是 React 当前采用的实现方式，React 会不断改进 Diff 算法，以提高 DOM 比较和更新的效率。