0 前言
React的VirtualDOM可谓是前端领域中革命性的创新，而高效的Diff算法又极大的优化了状态的对比，不同的状态对应的就是不同的UI界面。本文将简要介绍Diff算法中的精华。
1 Diff算法
1.1背景
"树"是一种常见的数据结构，对比"树"的结构在计算机相关相关领域有广泛的应用。具体到前端开发而言，Web的UI界面就是由DOM树构成，DOM作为一种有序树结构，当DOM树结构发生变化时，浏览器会重新解析渲染DOM树。造成有序树的节点变化的基本操作方式有三种：重标记(relabel)，删除(delete)和插入(insert)，如下图自上而下所示。
重标记(relabel L1 to L2)
删除节点(delete node L2)
插入节点(insert L2 to L1)
1.2 标准的Diff算法
标准的Tree-Diff算法，使用了严谨的代价函数(Cost Function)，适用于很多需要树结构对比的场景，如：计算生物学、图像分析、结构化文本数据库等。然而其算法的时间复杂度为O(n^3)，在浏览器环境中，要达到每次更新都可以整体刷新界面的目的，这样高的算法复杂度会有性能问题。
2 React Diff算法（reconciliation algorithm）
React开发团队结合Web界面的特点对标准的Diff算法做出了优化，使得其时间复杂度降低为O(n)。这一算法，即reconciliation algorithm，常见中文翻译为“协调算法”，个人更倾向于“权衡算法”这一更形象的翻译，因为该算法所实现的就是权衡利弊之后的简化。这种算法的基本假设如下：
- Web UI中DOM节点跨层级的移动操作较少，可以忽略。
- 两个相同组件产生类似的DOM结构，不同的组件产生不同的DOM结构。
- 对于同一层次的一组相同类型的子节点，它们可以通过唯一的key进行区分。
2.1 单一节点对比
为了对比两个树结构，需要先能够比较两个节点，在React中就是Virtual DOM树(以下简称“VD树”)的节点，而VD树节点的不同又分两种情况：
- 节点类型不同
- 节点类型相同但属性(props)不同
2.1.1 节点类型不同
当VD树中同一节点位置前后节点类型不同时，React直接删除旧的节点，然后创建并插入新的节点，使用的节点基本操作方法为删除和插入。
renderA: <OldNode />
renderB: <NewNode />
=> [removeNode <OldNode />], [insertNode <NewNode />]
在React组建的生命周期方法中，老节点OldNode的componentWillUnmount()方法最先触发，之后新节点NewNode的componentWillMount()和componentDidMount()方法依次触发。
2.1.2 节点类型相同但属性不同
节点类型相同但属性不同的情况下，React会对VD数节点的属性进行重设，从而实现节点的转换，使用的节点基本操作方法为重标记。因为React组件的实例保持不变，该组件的state也会保持不变，组件的componentWillReceiveProps()、componentWillUpdate()、render()方法依次触发。
renderA: <Node className="old" />
renderB: <Node className="new" />
=> [replaceAttribute className "new"]
VD树节点的style属性稍有不同，因为传入的是对象而不是字符串，React会只更新改变了的样式属性。
如果开发者能够明确节点是否有变化，则可以通过shouldComponentUpdate(nextProp, nextState)方法来决定是否进行Diff运算。
2.2 逐层进行节点对比（分层求异）
React只会对同一层级（下图中相同颜色方框内）的DOM节点进行比较，即同一个父节点下的所有子节点。如果发现已经不存在的节点，则该节点及其子节点会被完全删除掉，不再作进一步的比较。这样只需要对树进行一次遍历，便能完成整个DOM树的比较。这一方法正是基于前一假设，即不同类型的组件产生不同的VD树结构。
例如，在下图的VD树结构转换过程中，看似应该是把整个A节点从根节点插入到D节点中，最直观的操作方式应该是：
Root.remove(A).find(D).append(A)
然而，React的“权衡算法”只会简单对比同一层级的节点，不同层级的节点只有删除和插入。所以，React实际的操作方式却是直接删除节点A，至于A的子节点B和C则直接被忽略了；而当发现D节点多了一个子节点A时，则会插入一个新的节点A作为自己点。过程如下：
A.destroy();
A = new A();
A.append(new B());
A.append(new C());
D.append(A);
这样的操作看似是把简单的问题变得复杂了，在这一例子中的确如此，毕竟根据NFL定理(no free lunch theorem)，任何优化都是有代价的，Reconciliation algorithm也不例外。之所以称之为“权衡算法”，也正是因为这一方法以忽略不同类型节点的子节点的对比为代价，进而大大降低了Diff算法的时间复杂度。
鉴于这一情况，为提高性能，应尽量避免进行DOM节点跨层级的操作。此外，保持稳定的DOM结构也有助于性能提升，可以通过类名和CSS来控制节点的显示隐藏。
2.3 列表节点的对比
2.1和2.2中分别介绍了React diff算法对单一节点，和不在同一层中的节点的对比方式。与前两者不同的是，一组列表节点往往有相同的类型和属性，此外，列表节点的常见操作包含插入、删除和排序。如果每个列表节点没有唯一标识，则React无法识别每一个节点，那么只能更新所有列表节点造成效率低下。
例如，要在下图的列表节点B和C中间插入节点F，如果React无法识别每一个节点，则只能依次更新所有节点，如果节点数量很大，会有明显的性能损耗。
这时，“key”这个属性就要登场了，React通过key这个属性发现更新前后相同的列表节点，因此无需进行相同节点删除和创建，只需要将旧的节点的位置进行移动。如果有旧的节点被删除或新的节点被插入，也不会造成其他节点被重新创建。
再上图的例子中，React会通过每个节点的唯一标识(key)，准确找到插入新节点F的位置，同时保留其他节点。
如果列表节点能够获取到唯一的id属性，那么选择id作为key最好不过，如果没有id或较难获取，则退而求其次选用.map(item, index)方法中的索引index作为key。
3 总结
- React Diff 通过“权衡算法”，把复杂度O(n^3)的问题转化为复杂度O(n)的问题；
- 通过”分层求异“策略进行优化，假设不同类型的组件产生不同的DOM树结构，主动放弃了对不同父节点的子节点的对比；
- 开发组建时，保持稳定的DOM结构、避免跨层级移动DOM节点，有助于性能提升；
- 通过设置唯一key的策略，对列表节点进行了diff算法优化。
