浅谈React的diff算法和key属性

React快速的致胜法宝是虚拟DOM及其高效的diff算法。

可以无需担心性能问题而“随时”刷新整个页面，虚拟DOM可以确保只对界面上真正变化的部分进行实际的DOM操作。虽然在实际开发中，基本无需关心虚拟DOM是如何运作的，但理解其运行机制不仅能帮助更好地理解React组件的生命周期，还会对进一步优化React程序也会有很大帮助。

1、Diff算法

Web界面由DOM树构成，页面某部分发生变化，其实是某个DOM节点发生了变化。变化前后对应两套界面，需要React比较两个界面的区别，这就需要通过diff算法对DOM树进行分析，即针对变化前后的两棵DOM树，找到最少的转换步骤。

标准的diff算法的复杂度为O(n^3)，Facebook工程师结合Web界面的特点做出了以下两个简单的假设，使得Diff算法的复杂度直接降低到O(n)：

①　相同的组件产生类似的DOM结构，不同的组件产生不同的DOM结构；

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

逐层进行节点比较：

在React中，两棵DOM树只会对同一层的节点进行比较。若发现节点已不存在，则该节点及其子节点会被完全删除，不会用于进一步的比较。这样，只需要对树进行一次遍历，就能完成整个DOM树的比较。

对于同层节点，若节点本身完全相同（类型相同，属性相同），只是位置不同，则React只需要考虑同层节点的位置变换，不需要进行节点的销毁和重新创建，这就需要用到下面介绍的key属性，但对于不同层的节点，只能销毁和重新创建。

比较两个虚拟DOM节点，可以分为以下三种情况：

1) 节点类型不同； 

当在树中的同一位置前后的节点类型不同，React会直接删除原节点，然后创建并插入新的节点。

注意：删除节点即彻底销毁该节点，也就是说，后续不会查找是否有另外一个节点等同于删除的该节点。如果删除的该节点有子节点，那么子节点也会被删除。这也是diff算法复杂度能降到O(n)的原因。

同理，当树的同一个位置遇到前后不同的组件时，也是销毁原组件，把新的组件加上去。这应用了第一个假设，不同的组件一般会产生不同的DOM结构，与其浪费时间去比较不同的DOM结构，还不如完全创建一个新的组件加上去。

2) 节点类型相同，但是属性不同。

React会对属性进行重设从而实现节点的转换。

3) 节点类型相同且属性相同。

对于同层节点，若节点本身完全相同（类型相同且属性相同），只是位置不同，则React只需要考虑同层节点的位置变换，不需要进行节点的销毁和重新创建，这就需要用到下面介绍的key属性。

对于不同层的节点，即使节点本身完全相同（类型相同且属性相同），也只能销毁和重新创建。

2、key属性

为列表节点提供唯一的key属性，可以帮助React定位到正确的节点进行比较，从而大幅减少DOM操作的次数，提高性能。

React在处理列表时如果未给每个元素设置key，会提示如下找不到key的警告：

Warning: Each child in an array or iterator should have a unique "key" prop.

虽然无视该警告大部分界面也能正确工作，但会带来潜在的性能问题——React可能无法高效地更新该列表。

eg1：

某列表为a-b-c-d，若需要往b和c直接插入节点e，在jQuery中使用$(b).after(e)即可实现，而在React中只会告诉React新的列表应该是a-b-e-c-d，更新界面交由diff算法完成。如果每个节点都没有唯一的标识key，那么React将无法识别每一个节点，导致更新过程很低效，即将c更新成e，d更新成c，最后再插入一个d节点；而如果给每个节点唯一的标识key，React将能够找到正确的位置去插入新的节点。

eg2：

某虚拟DOM树的某一层原有两个节点a和b，页面更新后得到的新DOM树的该层还是只有a和b，只是a和b的位置与原来不同了。如果未提供唯一的标识key，React将认为a和b对应的位置前后的组件类型不同，而选择完全销毁后重新创建；而如果提供了唯一的标识key，React将能够判断出a和b只是位置不同，更新位置即可。