Virtual DOM能够体现高质量的渲染性能，不得不得意与强大的diff算法。计算一棵树形结构转换成另一棵树形结构的最少操作，是一个复杂且值得研究的问题。传统 diff 算法通过循环递归对节点进行依次对比，效率低下，算法复杂度达到 O(n^3)，其中 n 是树中节点的总数。O(n^3) 到底有多可怕，这意味着如果要展示1000个节点，就要依次执行上十亿次的比较。这种指数型的性能消耗对于前端渲染场景来说显然代价太高了，鉴于此，React diff诞生了，下面让我们探秘一下这个强大的React diff。
一、diff策略
1.web UI中DOM节点跨层级的移动操作特别少，可以忽略不计。
2.拥有相同类型的两个组件将会生成相似的树形结构，拥有不同类型的两个组件将会生成不同树形结构。
3.对于同一层级的一组自节点，他们可以通过唯一id进行区分。
基于以上策略，react分别对tree diff、component diff 以及 element diff 进行算法优化。
二、tree diff
React 对树的算法进行了简洁明了的优化，即对树进行分层比较，两棵树只会对同一层次的节点进行比较。React 通过 updateDepth 对 Virtual DOM 树进行层级控制，只会对相同颜色方框内的 DOM 节点进行比较，即同一个父节点下的所有子节点。当发现节点已经不存在，则该节点及其子节点会被完全删除掉，不会用于进一步的比较。这样只需要对树进行一次遍历，便能完成整个 DOM 树的比较。如下图，就是同样颜色的框内的元素进行比较：
updateChildren方法对应源码如下：
如果是跨层级的移动操作，如下图：
当根节点发现子节点中 A 消失了，就会直接销毁 A；当 D 发现多了一个子节点 A，则会创建新的 A（包括子节点）作为其子节点。此时，React diff 的执行情况：create A -> create B -> create C -> delete A。
因此，当进行跨层级的移动操作，React并不是简单的进行移动，而是进行了删除和创建的操作，会影响到React性能。应该避免DOM节点的跨层级操作（ps：在开发组件时，保持稳定的 DOM 结构会有助于性能的提升。例如，可以通过控制CSS来达到显示和隐藏，而不是真的添加或移除DOM节点）。
三、component diff
React 是基于组件构建应用的，对于组件间的比较所采取的策略也是简洁高效的，具体有以下策略：
1、如果是同一类型的组件，按照原策略继续比较 virtual DOM tree。
2、如果不是，则将该组件判断为 dirty component，从而替换整个组件下的所有子节点。
3、对于同一类型的组件，有可能其 Virtual DOM 没有任何变化，如果能够确切的知道这点那可以节省大量的 diff 运算时间，因此 React 允许用户通过 shouldComponentUpdate() 来判断该组件是否需要进行 diff。
如图：
如果组件D和组件G，如果类型不同，但是结构类似。这种情况下，因为类型不同，所以react会删除D，创建G。所以我们可以使用shouldComponentUpdate()返回false来中断diff运算，虽然当两个 component 是不同类型但结构相似时，React diff 会影响性能，但正如 React 官方博客所言：不同类型的 component 是很少存在相似 DOM tree 的机会，因此这种极端因素很难在实现开发过程中造成重大影响的。
因此，在component diff阶段的主要优化策略就是使用shouldComponentUpdate() 方法。
四、element diff
当节点处于同一层级时，React diff 提供了三种节点操作，分别为：INSERT_MARKUP（插入）、MOVE_EXISTING（移动）和 REMOVE_NODE（删除）。
1、INSERT_MARKUP，新的 component 类型不在老集合里， 即是全新的节点，需要对新节点执行插入操作。
2、 MOVE_EXISTING，在老集合有新 component 类型，且 element 是可更新的类型，generateComponentChildren 已调用 receiveComponent，这种情况下 prevChild=nextChild，就需要做移动操作，可以复用以前的 DOM 节点。
3、 REMOVE_NODE，老 component 类型，在新集合里也有，但对应的 element 不同则不能直接复用和更新，需要执行删除操作，或者老 component 不在新集合里的，也需要执行删除操作。
源码如下：
element diff针对这三个方法进行运算，但是单纯的去比较新旧集合的差异化，会导致只是进行繁杂的添加、删除操作，于是React 提出优化策略：允许开发者对同一层级的同组子节点，添加唯一 key 进行区分，这样的策略便使性能有了质的飞跃：
不使用key时，当发现心机和中的B != A，便会创建并插入B至新集合，删除旧集合A；以此类推，插入A、D、C，删除B、C、D，这样对于相同的节点，只是位置的变化便进行了如此繁杂的创建、插入和删除操作，显然效率很低。使用key的时候则是另一种情况：
此时新老集合进行 diff 差异化对比，通过 key 发现新老集合中的节点都是相同的节点，因此无需进行节点删除和创建，只需要将老集合中节点的位置进行移动，更新为新集合中节点的位置，此时 React 给出的 diff 结果为：B、D 不做任何操作，A、C 进行移动操作即可，这显然会使性能优化很多。那么如此高效的diff到底是怎么工作的呢，我们来分析一波：
首先对新集合的节点进行循环遍历，for (name in nextChildren)，通过唯一 key 可以判断新老集合中是否存在相同的节点，if (prevChild === nextChild)，如果存在相同节点，则进行移动操作，但在移动前需要将当前节点在老集合中的位置与 lastIndex 进行比较，if (child._mountIndex < lastIndex)，则进行节点移动操作，否则不执行该操作。
这是一种顺序优化手段，lastIndex 一直在更新，表示访问过的节点在老集合中最右的位置（即最大的位置），如果新集合中当前访问的节点比 lastIndex 大，说明当前访问节点在老集合中就比上一个节点位置靠后，则该节点不会影响其他节点的位置，因此不用添加到差异队列中，即不执行移动操作，只有当访问的节点比 lastIndex 小时，才需要进行移动操作。
以上图为例，可以更为清晰直观的描述 diff 的差异对比过程：
1、从新集合中取得 B，判断老集合中存在相同节点 B，通过对比节点位置判断是否进行移动操作，B 在老集合中的位置 B._mountIndex = 1，此时 lastIndex = 0，不满足 child._mountIndex < lastIndex 的条件，因此不对 B 进行移动操作；更新 lastIndex = Math.max(prevChild._mountIndex, lastIndex)，其prevChild._mountIndex 表示 B 在老集合中的位置，则 lastIndex ＝ 1，并将 B 的位置更新为新集合中的位置prevChild._mountIndex = nextIndex，此时新集合中 B._mountIndex = 0，nextIndex++ 进入下一个节点的判断。
2、从新集合中取得 A，判断老集合中存在相同节点 A，通过对比节点位置判断是否进行移动操作，A 在老集合中的位置 A._mountIndex = 0，此时 lastIndex = 1，满足 child._mountIndex < lastIndex的条件，因此对 A 进行移动操作enqueueMove(this, child._mountIndex, toIndex)，其中 toIndex 其实就是 nextIndex，表示 A 需要移动到的位置；更新 lastIndex = Math.max(prevChild._mountIndex, lastIndex)，则 lastIndex ＝ 1，并将 A 的位置更新为新集合中的位置 prevChild._mountIndex = nextIndex，此时新集合中A._mountIndex = 1，nextIndex++ 进入下一个节点的判断。
3、从新集合中取得 D，判断老集合中存在相同节点 D，通过对比节点位置判断是否进行移动操作，D 在老集合中的位置 D._mountIndex = 3，此时 lastIndex = 1，不满足 child._mountIndex < lastIndex的条件，因此不对 D 进行移动操作；更新 lastIndex = Math.max(prevChild._mountIndex, lastIndex)，则 lastIndex ＝ 3，并将 D 的位置更新为新集合中的位置 prevChild._mountIndex = nextIndex，此时新集合中D._mountIndex = 2，nextIndex++ 进入下一个节点的判断。
4、从新集合中取得 C，判断老集合中存在相同节点 C，通过对比节点位置判断是否进行移动操作，C 在老集合中的位置 C._mountIndex = 2，此时 lastIndex = 3，满足 child._mountIndex < lastIndex 的条件，因此对 C 进行移动操作 enqueueMove(this, child._mountIndex, toIndex)；更新 lastIndex = Math.max(prevChild._mountIndex, lastIndex)，则 lastIndex ＝ 3，并将 C 的位置更新为新集合中的位置 prevChild._mountIndex = nextIndex，此时新集合中 A._mountIndex = 3，nextIndex++ 进入下一个节点的判断，由于 C 已经是最后一个节点，因此 diff 到此完成。
以上主要分析新老集合中存在相同节点但位置不同时，对节点进行位置移动的情况，如果新集合中有新加入的节点且老集合存在需要删除的节点，那么 React diff 又是如何对比运作的呢？请看下图：
位置的调整同以上一样，lastIndex，比较是否有该节点，有的话判断是否移动，没有的话则在新集合里进行创建、插入操作（注意此时的lastIndex是不变的），然后依次进行到A，位置更新完毕。此时注意在进行完差异化对比后，虽然完成了新集合中所有节点 diff ，但还要对老集合进行循环遍历，判断是否存在新集合中没有但老集合中仍存在的节点，发现存在这样的节点 D，因此删除节点 D，到此 diff 全部完成。（源码过多，此处就不贴了，感兴趣的可自己研究，源码地址： /v15.0.0/src/renderers/shared/reconciler/ReactMultiChild.js）。
让然，React diff 还是存在些许不足与待优化的地方，如下图所示，若新集合的节点更新为：D、A、B、C，与老集合对比只有 D 节点移动，而 A、B、C 仍然保持原有的顺序，理论上 diff 应该只需对 D 执行移动操作，然而由于 D 在老集合的位置是最大的，导致其他节点的 _mountIndex < lastIndex，造成 D 没有执行移动操作，而是 A、B、C 全部移动到 D 节点后面的现象。
因此，在开发过程中，尽量减少类似将最后一个节点移动到列表首部的操作，当节点数量过大或更新操作过于频繁时，在一定程度上会影响 React 的渲染性能。
到此，我们介绍完了神秘而又强大的React diff算法介绍完毕了，让我们总结一下：
1、React 通过制定大胆的 diff 策略，将 O(n3) 复杂度的问题转换成 O(n) 复杂度的问题；
2、React 通过分层求异的策略，对 tree diff 进行算法优化；
3、React 通过相同类生成相似树形结构，不同类生成不同树形结构的策略，对 component diff 进行算法优化；
4、React 通过设置唯一 key的策略，对 element diff 进行算法优化；
5、建议，在开发组件时，保持稳定的 DOM 结构会有助于性能的提升；
6、建议，在开发过程中，尽量减少类似将最后一个节点移动到列表首部的操作，当节点数量过大或更新操作过于频繁时，在一定程度上会影响 React 的渲染性能。
至此，这个伟大的框架的核心概念已经基本介绍完毕，可爱的React的出现在前端史上有着极其重大的意义，他引发了前端界的变革，但是，Vue的出现可能在一定程度上撼动了我们的React的地位，但是React不会停下前进的脚步，下一节，为大家带来React的又一次创新和突破，它让React又一次如虎添翼，那就是在React 16中推出的新引擎——React Fiber ，请期待～(￣▽￣～)(～￣▽￣)～
