日常抄书之React中Diff算法思路
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 进行算法优化；