React进阶篇——六、Diff算法

六、Diff算法

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

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

正常情况下，比较两个树形结构差异的算法的时间复杂度是O(N^3)，React提出了两个在绝大多数场景下都成立的假设，基于这两个假设，实现了在O(N)时间复杂度内完成两棵虚拟DOM树的比较：

• 如果两个元素的类型不同，那么它们将生成两棵不同的树
• 为列表中的元素设置key属性，用key标识对应的元素在多次render过程中是否发生变化

React比较两棵树是从树的根节点开始比较的，根节点类型不同，React执行的操作也不同。

1，根节点是不同类型时

根节点类型的变化是很大的变化，React会认为新树和旧树完全不同，不再继续比较，而是把整棵树拆掉重建（包括虚拟DOM和真实DOM）。

虚拟DOM分为DOM元素类型和React组件类型。在旧的虚拟DOM树被拆除的过程中，旧的DOM元素类型的节点会被销毁，旧的React组件实例的componentWillUnmount会被调用；在重建的过程中，新的实例的componentWillMount和componentDidMount会被调用。重建后的新的虚拟DOM树又会被整体更新到真实DOM树中。这种情况下，需要大量的DOM操作，更新效率最低。

2，根节点是相同的DOM元素类型

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

<div className="foo" title="react"/>

<div className="bar" title="react"/>

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

3，根节点是相同的组件类型

如果两个根节点是相同类型的组件，对应的组件实例不会被销毁，只是会执行更新操作， 同步变化的属性到虚拟DOM树上，这一过程组件实例的componentWillReceiveProps和componentWillUpdate会被调用，根据render返回的虚拟DOM结构决定如何更新真实DOM树。

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

当一个节点有多个节点时，默认情况下，React只会按照顺序逐一比较两棵树上对应的子节点，最终插入一个新节点

但是如果要在子节点的开始位置新增一个节点，这种方式会导致每一个节点都被修改。

为了解决这种低效的更新方式，React提供了一个key属性，帮助提高Diff效率。只要子节点的key值没有变化，React就认为是同一个节点。