React中的diff算法

diff作为Virtual DOM的加速器，其算法上的改进优化是React整个界面渲染的基础和性能保障。传统的diff算法，计算一棵树形结构转换成另一颗树形结构的最少操作是通过循环递归对节点进行依次对比，这种方式效率低下，算法复杂度达到O(n^3)，其中n是树中节点的总数。而React diff将O(n^3)复杂度的问题转换成O(n)复杂度的问题。

1. diff策略

• 策略一： Web UI中DOM节点跨层级的移动操作特别少，可以忽略不计。
• 策略二：拥有相同类的两个组件将会生成相似的树形结构，拥有不同类的两个组件将会生成不同的树形结构。
• 策略三：对于同一层级的一组子节点，它们可以通过唯一id进行区分。

基于以上策略，React分别对tree diff、component diff以及element diff进行算法优化。

1.1 tree diff

基于策略一，React的做法是把dom tree分层级，对于两个dom tree只比较同一层次的节点，忽略Dom中节点跨层级移动操作，只对同一个父节点下的所有的子节点进行比较。如果对比发现该父节点不存在则直接删除该节点下所有子节点，不会做进一步比较，这样只需要对dom tree进行一次遍历就完成了两个tree的比较。

1.2 component diff

React应用是基于组件构建的，对于组件的比较优化侧重于以下几点：

• 同一类型组件遵从tree diff比较v-dom树
• 不通类型组件，先将该组件归类为dirty component，替换下整个组件下的所有子节点

• 同一类型组件Virtual Dom没有变化，React允许开发者使用shouldComponentUpdate（）来判断该组件是否进行diff，运用得当可以节省diff计算时间，提升性能

  
  component diff
  

  如上图，当组件D → 组件G时，diff判断为不同类型的组件，虽然它们的结构相似甚至一样，diff仍然不会比较二者结构，会直接销毁D及其子节点，然后新建一个G相关的子tree，这显然会影响性能，官方虽然认定这种情况极少出现，但是开发中的这种现象造成的影响是非常大的。
  对于同一类型组件合理使用shouldComponentUpdate（），应该避免结构相同类型不同的组件

1.3 element diff

对于同一层级的element节点，diff提供了以下3种节点操作：

• INSERT_MARKUP 插入节点：对全新节点执行节点插入操作
• MOVE_EXISING 移动节点：组件新集合中有组件旧集合中的类型，且element可更新，即组件调用了receiveComponent，这时可以复用之前的dom，执行dom移动操作
• REMOVE_NODE 移除节点：此时有两种情况：组件新集合中有组件旧集合中的类型，但对应的element不可更新、旧组建不在新集合里面，这两种情况需要执行节点删除操作
  element diff
  一般diff在比较集合[A,B,C,D]和[B，A，D，C]的时候会进行全部对比，即按对应位置逐个比较，发现每个位置对应的元素都有所更新，则把旧集合全部移除，替换成新的集合，如上图，但是这样的操作在React中显然是复杂、低效、影响性能的操作，因为新集合中所有的元素都可以进行复用，无需删除重新创建，耗费性能和内存，只需要移动元素位置即可。
  React对这一现象做出了一个高效的策略：允许开发者对同一层级的同组子节点添加唯一key值进行区分。意义就是代码上的一小步，性能上的一大步，甚至是翻天覆地的变化！
  React通过key是如何进行element管理的呢？为何如此高效？
  React会先进行新集合遍历，for(name in nextChildren)，通过key值判断两个对比集合中是否存在相同的节点，即if(prevChild === nextChild)，如何为true则进行移动操作，在此之前，需要执行被移动节点在新旧（child._mountIndex）集合中的位置比较，if(child._mountIndex < lastIndex)为true时进行移动，否则不执行该操作，这实际上是一种顺序优化，lastIndex是不断更新的，表示访问过的节点在集合中的最右的位置。若当前访问节点在旧集合中的位置比lastIndex大，即靠右，说明它不会影响其他元素的位置，因此不用添加到差异队列中，不执行移动操作，反之则进行移动操作。
  image.png
  nextIndex = 0，lastIndex = 0，从新集合中获取B，在旧集合中发现相同节点B，旧集合中：B._mountIndex = 1，child._mountIndex < lastIndex ==> false，不执行移动操作，更新lastIndex = Math.max(prevChild._mountIndex, lastIndex), prevChild._mountIndex === B._mountIndex ==> true，更新B在新集合中的位置：prevChild._mountIndex = nextIndex，在新集合中：B._mountIndex = 0，nextIndex++，进行下一个节点判断。

• nextIndex = 1，lastIndex = 1，从新集合中获取A，在旧集合中发现相同节点A，旧集合中：A._mountIndex = 0，child._mountIndex < lastIndex ==> true，对A进行移动操作enqueueMove(this, child._mountIndex, toIndex)，toIndex是A要被移动到的位置，更新lastIndex = Math.max(prevChild._mountIndex, lastIndex)，更新A在新集合中的位置prevChild._mountIndex = nextIndex，在新集合中：A._mountIndex = 1，nextIndex++，进行下一个节点判断。
• nextIndex = 2，lastIndex = 1，从新集合中获取D，在旧集合中发现相同节点D，旧集合中：D._mountIndex = 3，child._mountIndex < lastIndex ==> false，不执行移动操作，更新lastIndex = Math.max(prevChild._mountIndex, lastIndex), prevChild._mountIndex === D._mountIndex ==> true，更新D在新集合中的位置：prevChild._mountIndex = nextIndex，在新集合中：D._mountIndex = 2，nextIndex++，进行下一个节点判断。
• nextIndex = 3，lastIndex = 3，从新集合中获取C，在旧集合中发现相同节点C，旧集合中：C._mountIndex = 2，child._mountIndex < lastIndex ==> true，对C进行移动操作enqueueMove(this, child._mountIndex, toIndex)，toIndex是C要被移动到的位置，更新lastIndex = Math.max(prevChild._mountIndex, lastIndex)，更新C在新集合中的位置prevChild._mountIndex = nextIndex，在新集合中：A._mountIndex = 3，nextIndex++，进行下一个节点判断。
• 由于是最后一个节点，diff操作完成
  那么，除了有可复用节点，新集合当有新插入节点，旧集合有需要删除的节点呢？
  image.png
  对于这种情况，React则是执行以下步骤：
• nextIndex = 0，lastIndex = 0，从新集合中获取B，在旧集合中发现相同节点B，旧集合中：B._mountIndex = 1，child._mountIndex < lastIndex ==> false，不执行移动操作，更新lastIndex = 1，更新B在新集合中的位置，nextIndex++，进行下一个节点判断。
• nextIndex = 1，lastIndex = 1，从新集合中获取E，在旧集合中没有发现相同节点E，nextIndex++进入下一个节点判断。
• nextIndex = 2，lastIndex = 1，从新集合中获取C，在旧集合中发现相同节点C，旧集合中：C._mountIndex = 2，child._mountIndex < lastIndex ==> false，不对C进行移动操作，更新lastIndex = 2，更新C在新集合的位置，nextIndex++，进行下一个节点判断。
• nextIndex = 3，lastIndex = 2，从新集合中获取A，在旧集合中发现相同节点A，旧集合中：A._mountIndex = 0，child._mountIndex < lastIndex ==> true，对A进行移动操作，更新lastIndex = 2，更新A在新集合中的位置，nextIndex++进入下一个节点判断。
• 当完成新集合所有节点中的差异对比后，对旧集合进行遍历，判读旧集合中是否存在新集合中不存在的节点，此时发现D节点符合判断，执行删除D节点的操作，diff操作完成。

优化后diff的不足

按照上述顺序优化，则旧集合中D的位置是最大的，最少的操作只是将D移动到第一位就可以了，实际上diff操作会移动D之前的三个节点到对应的位置，这种情况会影响渲染的性能。

优化建议

在开发过程中，同层级的节点添加唯一key值可以极大提升性能，尽量减少将最后一个节点移动到列表首部的操作，当节点达到一定的数量以后或者操作过于频繁，在一定程度上会影响React的渲染性能。比如大量节点拖拽排序的问题。