十九、彻底理解React如何重新处理DOM(Diffing算法)
React提供了一个声明式的API，所以你不必担心每次DOM更新时内部会修改哪些东西。虽然在React中并不是那么明显地告诉你具体如何实现的，不过这也让编写应用变得更加容易。
本文会详细解释在React中的“diffing”算法是怎么做的，以便组件更新是可预测的，从而让高性能应用变得足够快。
动机
当使用React时，在单个时间点，您可以将render()函数看做是在创建React元素树。 在下一个state或props更新时render()函数将返回一个不同的React元素树。 React需要弄清楚如何高效地更新UI去匹配上最新的元素树。
对于将一个树变换成另一个树的最小操作数的算法问题，现在已经存在一些比较通用的解决方案。 然而，那些现有的最先进的技术算法都有O(n^3)的复杂度（n是树中的元素的数量）。
如果在React中使用这些算法，显示1000个元素将需要大约十亿次比较。 这个真的代价太昂贵了。 相反，React实现了一个基于两个假设直观推断出的O(n)算法：
不同类型的两个元素将产生不同的树。
开发人员可以在不同渲染之间使用
key属性来表示哪些子元素是稳定的。
实际上，这两条假设对几乎所有的实际使用都是有效的。
Diffing算法
当比较两棵DOM树的差异时，React首先比较两个根元素。 如果根元素的类型不同，那么行为也是不同的。
不同类型的DOM元素
每当根元素是不同的类型时，React将删除旧的DOM树并从头开始重新构建新的DOM树。 从<a>到<img>、从<Article>到<Comment>、从<Button>到<div> ，只要不一样就会完全重新构建。
当删除就的DOM树时，旧的DOM节点也被删掉。 这个时候组件实例触发componentWillUnmount()函数 。当构建一个新的DOM树时，新的DOM节点会被插入到DOM中。 组件实例触发componentWillMoun()和componentDidMount()。 与之前旧的DOM树相关联的任何state也都将丢失。
在根元素之下的任何组件将被卸载并且它们的state也会全部丢失。 例如：
// 从
<div>
<Counter />
</div>
// 变为
<span>
<Counter />
</span>
因为根元素从div变为了span，所以旧的Counter组件将被销毁，然后再重新构建一个新的。
相同类型的DOM元素
当比较相同类型的两个React DOM元素时，React会先查看两者的属性差异，然后保留相同的底层DOM节点，仅仅去更新那些被更改的属性。 例如：
<div className="before" title="hello" /> <div className="after" title="hello" />
通过比较这两个元素属性，React就会知道只需要修改底层DOM节点上的className即可。
当更新style属性时，React也会知道只需要更新style中的那些已更改的属性。 例如：
<div style={{color: 'red',width: '300px'}} />
<div style={{color: 'red',width: '400px'}} />
当在这两个元素之间转换时，React知道只需修改width，而不是color。
处理根DOM节点后，React会根据上面的判断逻辑对子节点进行递归扫描。
相同类型的组件元素
当组件更新时，实例保持不变，因此在不同的渲染之间组件内的state是保持不变的。 React会更新底层组件实例的props来匹配新元素，并在底层实例上调用componentWillReceiveProps()和componentWillUpdate()。
接下来，调用render()方法，diff算法就会对上一个结果和新结果进行递归比较。
递归子元素
默认情况下，当对DOM节点的子元素进行递归时，React只是同时迭代两个子元素lists，并在有差异时产生变化。
例如，当在子元素的末尾再添加一个元素时，这两个树之间就会有一个的很好转换效果：
<ul>
<l1>one</li>
<li>two</li>
</ul>
<ul>
<li>one</li>
<li>two</li>
<li>three</li>
</ul>
React将匹配两个<li>one</li>树，匹配两个<li>two</li>树，然后插入一个<li>three</li>树。
但是，不要太天真了。如果在子元素的开头部分插入一个元素的话，性能会便的很差。 例如，这两棵树之间的转换效果就很差：
<ul>
<li>one</li>
<li>two</li>
<ul>
<ul>
<li>zero</li>
<li>one</li>
<li>two</li>
<ul>
这种情况React将更改每个子元素 ，而不会意识到它可以保持<li>one</li>和<li>two</li>子元素树完好无损。 这种低效率的情况是一个必须注意的问题。
keys
为了解决上面的问题，React提供了一个key属性。 当子元素有key属性时，React使用key将原始树中的子元素与后续树中的子元素进行匹配。 例如，上面的那个低效例子添加一个key就可以让子元素树转换变的很有效：
<ul>
<li key="1">one</li>
<li key="2">two</li>
<ul>
<ul>
<li key="0">zero</li>
<li key="1">one</li>
<li key="2">two</li>
<ul>
现在React就可以知道key="0"的元素是新的，并且key="1"和key="2"的元素只需移动即可。
在实践中，使用一个唯一的key并不难。 您要显示的元素可能已具有唯一的ID，因此key可以来自你自己的数据中：
<li key={item.id>{item.name}</li>
如果不是这样，你可以向数据模型中给每一项数据添加一个新的ID属性，或者对内容的某些部分进行哈希生成key。 key属性只有在其兄弟元素之间是唯一的，并不是全局唯一的。
最后一种方式是可以将数组中的索引作为key。 如果数组中的每一项不需要重新排序，同样也可以很好地工作，但是万一需要重新排序的话，这会变的很慢。
权衡利弊
要记住重要的是，diffing算法是一个具体的实现细节。 React可以在每个操作上去重新渲染应用; 最终结果都是一样的。
在当前的实现中，你可以看到一个事实是一个子树已经成功移动到它的兄弟元素当中，但你不能告诉它已经移动到别的地方。 该算法将重新渲染这个完整的子元素树。
因为React很依赖这个直观推断的算法来判断DOM是否需要重新处理，如果不能满足这个算法的那两个假设条件前提，应用的性能将会受到很大影响。
