#### 什么是diff算法
React中最值得称道的部分莫过于Virtual DOM与diff的完美结合,特别是起高效的diff算法,可以让用户无需顾忌性能问题而“任性自由”地刷新页面, 让开发者也无需了解Virtual DOM 背后的运作原理.因为diff会帮助我们计算出Virtual DOM真正变化的部分,并只针对该部分进行原生DOM操作,而非重新渲染整个页面,从而保证了每次操作更新后页面高效的渲染.
#### 传统diff算法
计算一棵树形结构转换成另一棵树形结构的最少操作,是一个复杂且值得研究的问题.diff算法通过循环递归对节点进行依次对比,效率低下,算法复杂度达到O(n3)
#### 详解diff算法
React将Virtual DOM树转换成actual DOM树的最少操作的过程称为调和, diff算法便是调和的具体表现.
##### diff策略
* 策略一: Web UI中DOM节点跨层级的移动操作特别少,可以忽略不计
* 策略二: 拥有相同类的两个组件将会生成相似的树形结构,拥有不同类的 两个组件将会生成不同的树形结构
* 策略三:对于同一层级的一组子节点,它们可以通过唯一id进行区分
##### tree diff
基于策略一, React对树的算法进行了简洁明了的优化,即对树进行分层比较,两棵树只会对同一层次的节点进行比较.DOM节点跨级操作可以忽略不计,针对这一现象,React通过updateDepth对Virtual DOM树进行层级控制,只会对相同层级的DOM节点进行比较,即同一个父节点下的所有子节点.当发现节点已经不存在时,则该节点以及子节点会被完全删除掉,不会用于进一步比较,这样只需要对树进行一次遍历,便能完成整个DOM树的比较
##### component diff
* 如果是同一类型的组件,按照原策略继续比较Virtual DOM树即可
* 如果不是,则将该组件判断为dirty component,从而替换整个组件下的所有子节点
* 对于同一类型的组件,又可能其Virtual DOM没有任何变化,如果能准确知道这点,那么就可以节省大量的diff运算时间.因此,React允许用户通过shouldComponentUpdate()来判断该组件是否需要进行diff算法
如图所示, 当组件D变成组件G时,即使这两个组件结构相似,一旦React判断D和G为不同类型的组件,就不会比较二者的结构,而是直接删除组件D,重新创建组件G以及其子节点.虽然当两个组件是不同类型但结构相似时,diff会影响性能,但正如React官方博客所言: 不同类型组件很少存在相似的DOM树情况,因此这种极端因素很难在实际开发过程中造成重大影响
##### element diff
**_mountIndex < lastIndex 原节点元素下标小于现在节点元素下标,否则则进行移动**
**lastIndex: 表示访问过的节点在旧集合中最右的位置(即最大位置)**
1.新旧集合中存在相同节点但位置不同
如图所示
1. 从新集合中取得B, 然后判断旧集合中是否存在相同节点B,此时发现节点B,接着通过对比节点位置判断是否进行移动操作.B在旧集合中的位置B._mountIndex=1, 此时lastIndex=0, **不满足B._mountIndex=1 < lastIndex**,因此**不进行移动**操作,更新lastIndex = Math.max(prevChild._mountIndex, lastIndex),其中prevChild._mountIndex表示B在旧集合中的位置,则lastIndex=1,并将B的位置更新为新集合中的位置prevChild._mountIndex= nextIndex, 此时新集合中B._mountIndex=0,nextIndex++进入下一个节点的判断
2. 从新集合中取得A, 然后判断旧集合中是否存在相同节点A,此时发现节点A,接着通过对比节点位置判断是否进行移动操作.A在旧集合中的位置A._mountIndex=0, 此时lastIndex=1, **满足A._mountIndex=0 < lastIndex**,因此**进行移动**操作enqueueMove(this,child_mountIndex,toIndex),其中todoIndex其实就是nextIndex,表示A需要移动到的位置,更新lastIndex = Math.max(prevChild._mountIndex, lastIndex),则lastIndex=1,并将A的位置更新为新集合中的位置prevChild._mountIndex= nextIndex, 此时新集合中A._mountIndex=1,nextIndex++进入下一个节点的判断
3. 从新集合中取得D, 然后判断旧集合中是否存在相同节点D,此时发现存在节点D, D在旧集合中的位置D._mountIndex=3,此时lasteIndex=2, **不满足D._mountIndex < lastIndex**,因此**不进行移动**,更新lastIndex = Math.max(prevChild._mountIndex, lastIndex), 则lastIndex = 3, 并将D的位置更新为新集合中的位置prevChild._mountIndex= nextIndex, 此时新集合中D._mountIndex=2,nextIndex++进入下一个节点的判断
4. 从新集合中取得C, 然后判断旧集合中是否存在相同节点C,此时发现存在节点C, C在旧集合中的位置D._mountIndex=2,此时lasteIndex=3, **满足C._mountIndex < lastIndex**, 因此**进行移动**, enqueueMove(this,child_mountIndex,toIndex), 更新lastIndex=Math.max(prevChild._mountIndex, lastIndex), 则lastIndex=3, 并将C位置更新为新集合中的位置prevChild._mountIndex= nextIndex, 此时新集合中C._mountIndex=3, 由于C已经是最后一个节点, diff操作到此完成
2.新旧集合中有新加入的节点且旧集合存在需要删除的节点
3.diff算法存在些许不足与待优化的地方
#### React Patch方法
* React在Virtual DOM中进行构建虚拟标签,执行组件生命周期,更新state,计算tree diff等, 然而浏览器中并未能显示出更新的数据,那么React又是如何让浏览器展示出最新的数据呢?
* React Patch实现了关键的最后一步.所谓Patch, 简而言之就是将tree diff计算出来的DOM差异队列更新到真实的DOM节点上,最终让浏览器能够渲染出最新的数据.Patch方法如此重要,但是它的实现却非常简单明了, 主要通过遍历差异队列实现的,遍历差异队列时,通过更新类型进行相应的操作,包括: 新节点的插入,已有节点的移动和移除等
