共计 5273 个字符，预计需要花费 14 分钟才能阅读完成。
1. 前言
diff 并非 React 首创，只是 React 针对 diff 算法进行了优化。在 React 中 diff 算法和 Virtual Dom 的完美结合可以让我们不需要关心页面的变化导致的性能问题。因为 diff 会帮助我们计算出 Virtual Dom 变化的部分，然后只对该部分进行原生 DOM 操作，而非重新渲染整个页面，从而保证每次操作更新后页面的高效渲染。
2. 详解 diff
React 将 Virtual Dom 转为真实 DOM 树的最少操作的过程叫做调和 (reconciliation)。diff 便是调和的具体实现。
3. diff 策略
策略一：Web UI 中 DOM 节点跨层级的移动操作特别少，可以忽略不计。
策略二：拥有相同类的两个组件将会生成相似的树形结构，拥有不同类的两个组件将会生成不同的树形结构。
策略三：对于同一层级的一组节点，它们可以通过唯一 id 进行区分。
基于以上策略，React 分别对 tree diff、component diff、element diff 进行算法优化。
4. tree diff 对于树的比较
基于策略一 (Web UI 中 DOM 节点跨层级的移动操作特别少，可以忽略不计)。React 对树的算法进行简洁明了的优化，既对树进行分层比较，两棵树只会对同一层次的节点进行比较。
既然 DOM 节点跨层级的移动操作可以忽略不计，针对这一现象，React 通过 updateDepth 对 Virtual DOM 树进行层级控制，只会对相同层级的 DOM 进行比较，即同一个父节点下的所有子节点，当发现节点已经不存在时，则删除该节点以及其子节点，不会用于进一步比较，这样只需对树进行一次遍历，便能够完成整个 DOM 树比较。
updateChildren: function(nextNestedChildrenElements, transaction, context) {
updateDepth ++
var errorThrown = true
try {
this._updateChildren(nextNestedChildrenElements, transaction, context)
} finally {
updateDepth —
if(!updateDepth) {
if(errorThrown) {
clearQueue()
}else {
processQueue()
}
}
}
}
如下出现 DOM 节点跨层级移动操作，A 节点整个被移动到了 D 节点下，由于 React 只会简单的考虑同层级节点的位置变化，对于不同层级的节点只有创建和删除。当根节点发现子节点中 A 消失，就会直接销毁 A；当 D 发现多了一个子节点 A，则会创建新的 A 和其子节点，此时 diff 执行情况：createA—>createB—>crateC—>createA:
可以发现跨层级移动时，会出现重新创建整个树的操作，这种比较影响性能，所以不推荐进行 DOM 节点跨节点操作。
5. component diff 对于组件的比较
React 是基于组件构建应用的，对于组件间的比较所采取的策略也是非常简洁的、高效的。
如果是同一类型的组件，按照原策略继续比较 Virtual DOM 树即可。
如果不是同一类型组件，则将该组件判断为 dirtycomponent，从而替换整个组件下的所有子组件。
对于同一类型的组件，有可能其 Virtual DOM 没有任何变化，如果能够确切知道这点，那么就可以节省大量的 diff 运算时间。因此 React 允许用户通过 shouldComponentUpdate 来判断该组件是否需要进行 diff 算法分析。
6. element diff
当节点处于同一层级时，diff 提供了 3 种节点操作，分别为 INSERT_MARKUP(插入)、MOVE_EXISTING(移动)、REMOVE_NODE(删除)：
INSERT_MARKUP: 新的组件类型不在旧集合里，即全新的节点，需要对新节点执行插入操作。
MOVE_EXISTING: 旧集合中有新组件类型，且 element 是可更新的类型，generateComponentChildren 已调用 receiveComponent，这种情况下 prevChild=nextChild，就需要做移动操作，可以复用以前的 DOM 节点。
REMOVE_NODE: 旧组件类型，在新集合里也有，但对应的 element 不同则不能直接复用和更新，需要执行删除操作，或者旧组件不在新集合里，也需要执行删除操作。
相关代码如下：
function makeInsertMarkup(markup, afterNode) {
return {
type: ReactMultiChildUpdateTypes.INSERT_MARKUP,
content: markup,
fromIndex: null,
fromNode: null,
toIndexL toIndex,
afterNode: afterNode
}
}
function makeMove(child, afterNode, toIndex) {
return {
type: ReactMultiChildUpdateTypes.MOVE)EXISTING,
content: null,
fromIndex: child._mountIndex,
fromNode: ReactReconciler.getNativeNode(child),
toIndex: toIndex,
afterNode: afterNode
}
}
function makeRemove(child, node) {
return {
type: ReactMultiChildUpdateTypes.REMOVE_NODE,
content: null,
fromIndex: child._mountIndex,
fromNode: node,
toIndex: null,
afterNode: null
}
}
如下图：旧集合中包含节点 A,B,C,D。更新后集合中包含节点 B,A,D,C。此时新旧集合进行 diff 差异化对比，发现 B!=A，则创建并插入 B 至新集合，删除就集合 A。以此类推，创建并插入 A,D,C。删除 B,C,D。
React 发现这类操作繁琐冗余，因为这些都是相同的节点，只是由于位置发生变化，导致需要进行烦杂低效的删除，创建操作，其实只要对这些节点进行位置移动即可。
针对这一现象，React 提出优化策略：允许开发者对同一层级的同组子节点，添加唯一的 key 进行区别。
新旧集合所包含的节点如下图所示，进行 diff 差异化对比后，通过 key 发现新旧集合中的节点都是相同的节点，因此无需进行节点的删除和创建，只需要将旧集合中节点的位置进行移动，更为新集合中节点的位置，此时 React 给出的 diff 结果为：B,D 不做任何操作，A,C 进行移动即可。
源码分析一波：首先，对新集合中的节点进行循环遍历，通过唯一的 key 判断新旧集合中是否存在相同的节点, 如果存在相同的节点，则进行移动操作，但在移动前需要将当前节点在旧集合中的位置与 lastIndex 进行比较。否则不执行该操作。这是一种顺序优化手段，lastIndex 一直更新，表示访问过的节点在旧集合中最右边的位置 (即最大的位置)。如果新集合中当前访问的节点比 lastIndex 大，说明当前访问节点在旧集合中就比上一个节点位置靠后，则该节点不会影响其他节点的位置，因此不用添加到差异队列中，即不执行移动操作
以上面的那个图为例子：
从新集合中取得 B，判断旧集合中是否存在相同节点 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 = nextIdex，此时新集合中 B._mountIndex = 0, nextIndex ++ 进入下一个节点判断。
从新集合中取得 A，然后判断旧集合中是否存在 A 相同节点 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++ 进入下一个节点的判断。
从新集合中取得 D，然后判断旧集合中是否存在相同节点 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++ 进入下一个节点的判断。
从新集合中取得 C，然后判断旧集合中是否存在相同节点 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 操作到此完成。
如果有新增的节点和删除的节点 diff 如何处理呢？(以下都是复制的，码不动字了 ….)
从新集合中取得 B，然后判断旧集合中存在是否相同节点 B，可以发现存在节点 B。由于
B 在旧集合中的位置 B._mountIndex = 1，此时 lastIndex = 0，因此不对 B 进行移动操作。更新 lastIndex = 1，并将 B 的位置更新为新集合中的位置 B._mountIndex = 0，nextIndex++ 进入下一个节点的判断。
从新集合中取得 E，然后判断旧集合中是否存在相同节点 E，可以发现不存在，此时可以
创建新节点 E。更新 lastIndex = 1，并将 E 的位置更新为新集合中的位置，nextIndex++ 进入下一个节点的判断。
从新集合中取得 C，然后判断旧集合中是否存在相同节点 C，此时可以发现存在节点 C。
由于 C 在旧集合中的位置 C._mountIndex = 2，lastIndex = 1，此时 C._mountIndex >lastIndex，因此不对 C 进行移动操作。更新 lastIndex = 2，并将 C 的位置更新为新集合中的位置，nextIndex++ 进入下一个节点的判断。
从新集合中取得 A，然后判断旧集合中是否存在相同节点 A，此时发现存在节点 A。由于
A 在旧集合中的位置 A._mountIndex = 0，lastIndex = 2，此时 A._mountIndex < lastIndex，因此对 A 进行移动操作。更新 lastIndex = 2，并将 A 的位置更新为新集合中的位置，nextIndex++ 进入下一个节点的判断。
当完成新集合中所有节点的差异化对比后，还需要对旧集合进行循环遍历，判断是否存
在新集合中没有但旧集合中仍存在的节点，此时发现存在这样的节点 D，因此删除节点 D，到此 diff 操作全部完成。
这一篇读的有点乱 … 稍微总结一下下：
React 通过 diff 策略，将 O(n3) 复杂度的问题转换成 O(n) 复杂度的问题；
React 通过分层求异的策略，对 tree diff 进行算法优化；
React 通过相同类生成相似树形结构，不同类生成不同树形结构的策略，对 component diff 进行算法优化；
React 通过设置唯一 key 的策略，对 element diff 进行算法优化；
