React：虚拟DOM Diff算法

父组件每次render方法被调用，或者组件自己每次调用setState方法，都会触发组件的render方法（前提是shouldComponentUpdate使用默认行为，总是返回true）。那么组件每次render，是不是都会导致实体DOM的重新创建呢？答案是，不是！

React之所以比直接操作DOM的JS库快，原因是：

1.React在实体DOM之上，抽象出一层虚拟DOM，render方法执行后，得到的是虚拟DOM，React会把组将当前的虚拟DOM结构和前一次的虚拟DOM结构做比较，只有存在差异性，React才会把差异的内容同步到实体DOM上。如果两次render后的虚拟DOM结构保持一致，并不会触发实体DOM的修改。

2.React速度快的原因，还有一个是它出色的Diff算法。标准的比较两棵树的Diff算法的时间复杂是 O(n3) 。而React基于非常符合实际场景的两个假设，就将Diff算法的时间复杂度降到了接近O(n)。这两个假设是：

• 两个相同组件产生类似的DOM结构，不同的组件产生不同的DOM结构。如果两个组件或元素类型不同，那么他们就是完全不同的树，不需要再比较他们的子节点。

  例如，<Article>和<Comment>将产生是两个完全不同的树状结构；<div>children</div>和<p>children</p>也是两个完全不同的树。

  这种情况下，组件会被完全重建，旧的DOM节点被销毁，组件经历componentWillUnmount()，然后重新创建一棵新树， 组件经历 componentWillMount() 和 componentDidMount()。

• 对于同一层次的一组子节点，它们可以通过唯一的id进行区分。

  可以为组件或元素设置key属性，key用来标识这个组件或元素。key不需要全局唯一，只需要在兄弟组件或兄弟元素间保证唯一性就可以。key常用到集合（List）元素中。例如：

  <ul>
    <li key='a'>Book A</li>
    <li key='b'>Book B</li>
  </ul>
  

  当在第一个位置插入一条记录Book C时，

  <ul>
    <li key='c'>Book C</li>
    <li key='a'>Book A</li>
    <li key='b'>Book B</li>
  </ul>
  

  由于有key的标识，React知道此时新增了一条记录，会创建一个新的<li>元素，并把它插入到列表中的第一个位置。

  如果没有设置key，React并不知道是新增了一条记录，还是原 来的两条记录完全替换成新的三条记录，或者其他更加复杂的修改场景。React需要自上而下的比较每一条记录，这样每次比较节点都不同，所以需要修改两次节点，然后再新增一个节点，效率明显要差很多。

  所以，不要使用元素在集合中的索引值作为key，因为一旦集合中元素顺序发生改变，就可能导致大量的key失效，进而引起大量的修改操作。

参考资料：
深入浅出React（四）：虚拟DOM Diff算法解析(推介)
用好React，你必须知道的事情