1. 关于diff算法
????????1.1 什么是diff算法
? ? ? ? ? ? diff算法即差异查找算法。
????????1.2 diff算法的作用
? ? ? ? ? ? 计算出虚拟DOM中真正变化的部分，并只针对该部分进行原生DOM操作，而非重新渲染整个页面。
????????1.3 传统diff算法
? ? ? ? ? ?通过循环递归对节点进行依次对比，算法复杂度达到O(n^3)，n是树的节点数，效率极其低下。如果要展示1000个节点，要进行上亿次比较。现在的CPU每秒能执行大概30亿条指令，很难在一秒内计算出差异。
????????1.4 React diff算法
?????????????1.4.1 什么是调和
? ? ? ? ? ? ? ? ? 将虚拟DOM树转换成真实DOM树的最少操作过程称为调和。
? ? ? ? ? ? ? ? 1.4.2 什么是React diff算法
? ? ? ? ? ? ? ? ? 调和过程的具体实现就是React diff算法。
? ? ? ? ? ? ? ? 1.4.3 diff策略
? ? ? ? ? ? ? ? ? React通过三大策略将时间复杂度从O(n^3)转化为O(n)。
? ? ? ? ? ? ? ? ? 策略一（tree diff）：
????????????????????????Web UI中DOM节点跨层级的移动操作非常少，可以忽略不计。
? ? ? ? ? ? ? ? ? 策略二（component diff）：
????????????????????????拥有相同类的两个组件，生成相同的树形结构。
? ? ? ? ? ? ? ? ? ? ? ? 拥有不同类的两个组件，生成不同的树形结构。
? ? ? ? ? ? ? ? ? 策略三（element diff）：
? ? ? ? ? ? ? ? ? ? ? ? 对于同一层级的字节点，通过唯一Id区分。
2. React diff 三大策略详解
? ? ? ? 2.1 tree diff? ?
? ? ? ? ? ? ? ? 1.? React通过updateDepth对虚拟DOM进行层级控制。
? ? ? ? ? ? ? ? 2. 对树分层比较，两棵树只对同一层级的节点进行比较。如果该节点不存在时，该节点及其子节点会被完全删除，不会再进一步比较。
? ? ? ? ? ? ? ? 3. 只需遍历一次，就可以完成整颗DOM树的比较。
? ? ? ? ? ? ? ? diff只考虑同层级的节点位置变换，如果DOM节点中出现了跨层级的操作，那么只会删除元素和创建元素。
如上图：左边是上一次的虚拟DOM，右边是新的虚拟DOM。A节点整个被移动到了D节点下，由于React只会简单的考虑同层级节点的位置变换，对于不同层级的节点，只有创建和删除操作。diff算法在比较时，发现A节点消失了，就会直接删除A节点。当发现D多了一个子节点A?，就会创建A节点（包括其子节点）。React diff的执行情况是：create A -> create B -> create C -> delete?A。当进行跨层级操作时，以A为根节点的树会被重新创建，这样比较影响React性能。React官方建议不要进行DOM节点跨层级操作。
? ? ? ? 2.2 component diff
? ? ? ? ? ? ? ? React对不同的组件间的比较有三种策略。
? ? ? ? ? ? ? ? 1. 同一类型的组件，按原策略继续比较虚拟DOM树即可。
? ? ? ? ? ? ? ? 2. 不同类型的组件，将该组件（将被替换的）判断为dirty component，从而替换该组件下所有的子节点。
? ? ? ? ? ? ? ? 3. 同一类型的组件，有可能其虚拟DOM并没有任何变化，如果可以知道这点那可以节省大量的diff计算时间。因此React允许用户通过shouldComponentUpdate() 来判断该组件是否需要进行diff。
如上图，当component D改变为component G时，即使这两个component结构类似，一旦React判断D 和 G是不同类型的组件，就不会比较二者的结构，而是直接删除D，重新创建G及其子节点。虽然当两个组件结构类似但类型不同时，React diff会影响性能，但正如React官方所言：不同类型的component是很少存在相似DOM tree的机会的，因此这种极端情况基本不会在开发过程中造成重大影响。
? ? ? ? 2.3 element diff
? ? ? ? 当节点处于同一层级时，React提供了三种操作：插入、移动、删除。
? ? ? ? 插入：新的component类型不在老的集合里，既是全新的节点，需要对新节点执行插入操作。
? ? ? ? 移动：在老集合有新component类型，且element是可更新的类型，generateComponentChildren已调用receiveComponent，这种情况下preChild=nextChild，就需要做移动操作，可以复用以前的DOM节点。
? ? ? ? 删除：老component类型，在新集合里也有，但对应的element不同，不能直接复用和更新，需要执行删除操作。或者老component不在新的集合里，也需要执行删除操作。
? ? ? ? 如下图：老集合中包含节点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进行移动操作。
如此高效的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)，其中prevChild._mountIndex是D在老集合中的位置，则lastIndx = 3，并将D的位置更新为新集合中的位置，prevChild._mountIndex = nextIndex，此时新集合中D._mountIndex = 0，nextIndex++进行下一个节点的判断。
? ? ? ? 4. 从新集合中取得C，判断老集合中存在相同节点C，通过对比节点位置判断是否进行移动操作。C在老集合中的位置C._mountIndex = 2，此时lastIndex = 3，满足child._mountIndex <lastIndex的条件，因此对C进行移动操作，enqueueMove(this, child._mountIndex, toIndex)，其中toIndex其实就是nextIndex，表示C需要移动到的位置，更新lastIndex = Math.max(prevChild._mountIndex, lastIndex)，则lastIndex = 1，并将C的位置更新为新集合中的位置prevChild._mountIndex = nextIndex，此时新集合中C._mountIndex = 3，nextIndex++进入下一个节点的判断。
? ? ? ? 以上主要分析新老集合节点相同但位置不同时，对节点进行位置移动的情况。如果新集合中存在需要添加的节点且老集合中存在需要删除的节点，那么React diff又是如何运作对比的呢？
????????以下图为例：
? ? ? ? 1. 从新集合中取得节点B，判断老集合中存在相同节点B，由于B在老集合中的位置B._mountIndex = 1，此时lastIndex = 0，不对B进行移动操作。更新lastIndex = 1，并将B的位置更新为新集合中的位置B._mountIndex = 0，nextIndex++进入下一个节点的判断。
? ? ? ? 2. 从新集合中取得节点E，判断老集合中不存在相同节点E，则创建新节点E。更新lastIndex = 1，并将E的位置更新为新集合中的位置E._mountIndex = 1，nextIndex++进入下一个节点的判断。
? ? ? ? 3. 从新集合中取得节点C，判断老集合中存在相同节点C，由于C在老集合中的位置C._mountIndex = 2，此时lastIndex = 1，不对C进行移动操作。更新lastIndex = 2，并将C的位置更新为新集合中的位置C._mountIndex = 2，nextIndex++进入下一个节点的判断。
? ? ? ? 4. 从新集合中取得节点A，判断老集合中存在相同节点A，由于A在老集合中的位置A._mountIndex = 0，此时lastIndex = 2，满足prevChild._mountIndex < lastIndex的条件，对A节点进行移动操作，enqueueMove(this, child._mountIndex, toIndex)， toIndex既是nextIndex。更新lastIndex = Math.max(prevChild._mountIndex, lastIndex)，则lastIndex = 2。更新A的位置为新集合中的位置prevChild._mountIndex = nextIndex。nextIndex++进入下一个节点的判断。
? ? ? ? 5. 当完成新集合中所有节点diff时，最后还需要对老集合进行循环遍历，判断是否存在新集合中没有但在老集合中仍然存在的节点，发现存在这样的节点D，删除节点D，至此diff完成。
? ? ? ? 当然React还是存在些许不足和待优化的地方。如下图所示，若新集合的节点更新为：D，A，B，C，与老集合对比只有D节点移动，而A，B，C，仍保持原有的顺序，理论上diff算法只需要对D执行移动操作，然而由于D在老集合里的位置是最大的，导致其他节点的_mountIndex小于lastIndex，造成D没有执行移动操作，而是A，B，C，全部移到D后面的现象。
? ? ? ? 在此我们可以思考如何优化上述问题。
? ? ? ? 建议：在开发过程中，尽量减少类似将最后一个节点移动到首部的操作，当节点数量过大或更新操作过于频繁时，?会影响React的性能。
3. 总结
? ? ? ? 1. React通过制定大胆的diff策略，将O(n^3)复杂度的问题转化为O(n)复杂度的问题。
? ? ? ? 2. React通过分层求异的策略，对tree diff进行算法优化。
? ? ? ? 3. React通过相同类生成相似树形结构、不同类生成不同树形结构的策略，对component diff进行优化。
? ? ? ? 4. React通过设置唯一key的策略，对element进行算法优化。
? ? ? ? 5. 建议在开发组件时，保持稳定的DOM结构有助于性能的提升。
? ? ? ? 6. 建议尽量减少类似将最后一个节点移动到首部的操作，当节点数量过大或更新操作过于频繁时，会影响React的性能。
? ? ? ? 参考资料：
????????https://grfia.dlsi.ua.es/ml/algorithms/references/editsurvey_bille.pdf