讲 react diff 策略的文章很多，很多只说了基础内容，看了 《深入 React 技术栈》 之后，了解更深入了。

一、React diff 策略

React 对于传统的 diff 算法做了一些约定（or 假想或者策略），使得原本 O(n3) 复杂度大部分情况下维持了 O(n) 的复杂度。

React diff 算法的三个策略:

  • Web UI 中 DOM 节点跨层级的移动操作非常少，可以忽略不计
  • 想同类的两个组件将会组成相似的树形结构，拥有不同类的两个组件将会生成不同的树形结构
  • 对于同一层级的一组子节点，他们可以通过唯一 ID 进行区分

二、 React Tree Diff

对于树的 diff 算法， 基于策略一，这种优化是对树进行分层比较，两棵树只会对同一层次的节点进行比较。

这个策略基于：DOM 节点跨层的移动操作少到可以忽略不计。

针对这一现象，React 通过 updatDepth 对 Virtual DOM树进行层级控制，只会对相同层级的 DOM 节点进行比较。即同一个父节点下的所有子节点。

当发现节点已经不存在的时候，该节点及其子节点会被完全删除，不会进一步比较。因此只需要对数树进行一次遍历，便能完成整个 DOM 树的比较。

如果出现跨层级的变动：

如果 DOM 节点出现了跨层级的移动，则基于 React 的策略，不会出现 移动 操作，而是会出现 重建-销毁 操作。

因此，如果出现了下图所示的 DOM 操作。 A 节点所在的子树不会直接移动到 D 节点下面，真正的操作是：遍历 A 节点及其子树，在 D 节点下重建 A 节点及其子树，然后将 A 节点及其子树完全删除。

官方建议不要进行 DOM 节点跨层级的操作

在开发组件时，保持稳定的 DOM 结构会有助于性能的提升。例如，可以通过 CSS 隐藏
或显示节点，而不是真正地移除或添加 DOM 节点。

1.jpg

上图来自 《深入 React 技术栈》 图 3-19

三、React Component Diff

React 对于组件间的 diff 策略如下：

  • 如果是同一类型组件，按照元策略继续比较 Virtual DOM 树即可。
  • 如果不是同一类型组件，将该组件判断为 dirty component，从而替换整个组件下的所有子节点。
  • 对于同一类型组件，有可能其 virtual DOM 没有任何变化，如果能确切的知道这个前提，则可以节省大量的 diff 运算时间。因此 React 允许用户通过 shouldComponentUpdate() 来判断组件是否需要进行 diff 算法分析。

下图所示，如果 D 节点及其子树发生了变化，即使 D 子树和 G 子树结构相似，但是 React 会直接删除 D ，然后重建 G。

（React 认为不同类型的组件，DOM 树相同的情况非常少，这种极端的因素可以忽略不计或者难以造成极大的影响）

2.jpg

上图来自 《深入 React 技术栈》 图 3-20

四、React Element Diff

统一层级的节点进行 diff 的时候，有三种节点操作：

  • INSERT_MARKUP （插入）：新的组件类型不在旧集合中，即全新的节点，需要对新节点执行插入操作
  • MOVE_EXISTING （移动）：旧集合中有新组建类型，而且 element 是可更新的类型，generateComponentChildren 已带哦用 receiveComponent ，这种情况下 prevChild=nextChild，就需要做移动操作，可以复用以前的 DOM 节点。
  • REMOVE_NODE （删除）：旧组件类型，在新集合里也有，但对应的 element 不同则不能直接复用和更新，需要执行删除操作，或者旧组件不在新集合中的，也需要执行删除操作。

React 允许开发者对同一层级的同组子节点添加唯一 key 进行区分，极大的提高了性能

这种情况下，diff 算法的工作原理：

  1. 对集合中的节点进行循环遍历 for (name in nextChildren)，通过唯一 key 进行判断新旧集合中是否存在相同的节点，if(prevChild === nextChild) ，如果存在相同的节点， 则进行移动操作。
  2. 但是在移动前需要将当前节点在旧集合中的位置与 lastIndex 进行比较 if(child._mountIndex < lastIndex)，否则不执行操作。
  • 这是一种顺序优化方式， lastIndex 一直在更新，表示访问过的节点在旧集合中最右的位置（最大的位置）。
  1. 如果新集合中当前当前访问的节点比 lastIndex 大，说明当前访问节点在旧集合中就比上一个节点位置靠后，则该节点不会影响其他节点的位置，因此不同添加到差异队列中，也就不执行移动操作。
  2. 只有当访问的节点比 lastIndex 小的时候，才需要继续移动

3.jpg

上图来自 《深入 React 技术栈》 图 3-22

上面节点变化时，首先从新结合中取得 B ，然后判断旧集合中是否存在相同的节点 B，此时发现存在节点 B（注意 key），接着通过对比节点位置判断是否进行移动操作。

B 在旧集合中的位置 B.moundIndex = 1 此时 lastIndex = 0，不满足 child._moundIndex < lastIndex，因此不会 B 进行移动。

更新 lastIndex = Math.max(prevChild._mountIndex,lastIndex)，其中 prevChild._mountIndex 表示 B 在旧集合中的位置，则 lastIndex = 1,并将 的 位置更新为新集合中的位置 prevChild._mountIndex，此时新集合中 B.mountIndex = 0 , nextIndex++ 进入下一个节点判断。

从新集合中取得 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 操作到此完成。