React 中的 Diffing算法

2021-01-14 本文已影响0人弱冠而不立

官方文档链接：协调
图片示例参考文章：React 源码深度解读（十）：Diff 算法详解

设计动力

在某一时间节点调用 React 的 render() 方法，会创建一棵由 React 元素组成的树。在下一次 state 或 props 更新时，相同的 render() 方法会返回一棵不同的树。React 需要基于这两棵树之间的差别来判断如何有效率的更新 UI 以保证当前 UI 与最新的树保持同步。

这个算法问题有一些通用的解决方案，即生成将一棵树转换成另一棵树的最小操作数。然而，即使在最前沿的算法中，该算法的复杂程度为 O(n³)，其中 n 是树中元素的数量。

如果在 React 中使用了该算法，那么展示 1000 个元素所需要执行的计算量将在十亿的量级范围。这个开销实在是太过高昂。于是 React 在以下两个假设的基础之上提出了一套 O(n) 的启发式算法：

两个不同类型的元素会产生出不同的树；
开发者可以通过添加 key 来暗示哪些子元素在不同的渲染下能保持稳定；

Diffing算法

核心概念

Diff 算法性能突破的关键点在于“分层对比”；

React 的 Diff 过程直接放弃了跨层级的节点比较，它只针对相同层级的节点作对比，如下图所示。这样一来，只需要从上到下的一次遍历，就可以完成对整棵树的对比，这是降低复杂度量级方面的一个最重要的设计
类型一致的节点才有继续 Diff 的必要性；

最高效的算法应该是直接将 A 子树移动到 D 节点，但这样就涉及到跨层级比较，时间复杂度会陡然上升。React 的做法比较简单，它会先删除整个 A 子树，然后再重新创建一遍。
当 D 节点改为 G 节点时，整棵 D 子树也会被删掉，E、F 节点会重新创建
key 属性的设置，可以帮我们尽可能重用同一层级内的节点。

当没有 key 的时候，如果中间插入一个新节点，Diff 过程中从第三个节点开始的节点都是删除旧节点，创建新节点。当有 key 的时候，除了第三个节点是新创建外，第四和第五个节点都是通过移动实现的。

代码示例

节点元素类型不同时

节点元素销毁，节点元素以下的组件也会被卸载，如下：

<div>
  <Counter />
</div>

<span>
  <Counter />
</span>

React 不但会删除div节点重新创建span节点，而且还会销毁 Counter 组件并且重新装载一个新的组件。

节点元素类型相同，但属性不同时

当对比两个相同类型的 React 元素时，React 会保留 DOM 节点，仅比对及更新有改变的属性，如下：

<div className="before" title="stuff" />

<div className="after" title="stuff" />

通过对比这两个元素，React 知道只需要修改 DOM 元素上的 className 属性。

<div style={{color: 'red', fontWeight: 'bold'}} />

<div style={{color: 'green', fontWeight: 'bold'}} />

通过对比这两个元素，React 知道只需要修改 DOM 元素上的 color 样式，无需修改 fontWeight。
在处理完当前节点之后，React 继续对子节点进行递归比较。

对比同类型的组件元素

当一个组件更新时，组件实例保持不变，这样 state 在跨越不同的渲染时保持一致。React 将更新该组件实例的 props 以跟最新的元素保持一致，并且调用该实例的componentDidUpdate() 方法。如下：

<Card message="oldMessage" />

<Card message="newMessage" />

下一步，调用 render() 方法，diff 算法将在之前的结果以及新的结果中进行递归比较。

需要对子节点进行递归，或操作子元素列表时

直接在末尾新增或删除时，这种情况更新开销比较小，比如：

<ul>
  <li>first</li>
  <li>second</li>
</ul>

<ul>
  <li>first</li>
  <li>second</li>
  <li>third</li>
</ul>

React 会先匹配两个 <li>first</li> 对应的树，然后匹配第二个元素 <li>second</li> 对应的树，最后插入第三个元素的 <li>third</li> 树。

将新增元素插入/删除到表头或中间，那么更新开销会比较大（无 key 时）

<ul>
  <li>1st</li>
  <li>2nd</li>
</ul>

<ul>
  <li>3rd</li>
  <li>1st</li>
  <li>2nd</li>
</ul>

React 不会意识到应该保留 <li>1st</li> 和 <li>2nd</li>，而是会重建每一个子元素。这种情况会带来性能问题。

为了解决以上问题，React 支持 key 属性。
当子元素拥有 key 时，React 使用 key 来匹配原有树上的子元素以及最新树上的子元素。以下例子在新增 key 之后使得之前的低效转换变得高效

<ul>
  <li key="1">1st</li>
  <li key="2">2nd</li>
</ul>

<ul>
  <li key="3">3rd</li>
  <li key="1">1st</li>
  <li key="2">2nd</li>
</ul>

现在 React 知道只有带着 '3' key 的元素是新元素，带着 '1' 以及 '2' key 的元素仅仅移动了。这就意味着，后面俩个元素能够直接复用，而不被删除销毁。
所以，这就意味着 key 需要是该列表项的唯一标识，而且是不会改变的。例如：

<ul>
  {list.map((item, index) => (
      <li key={item.id}  />
  ))}
</ul> 

<ul>
  {list.map((item, index) => (
      <li key={index}  />
  ))}
</ul>

倘若，使用数组下标作为 key，则是毫无效果的。因为在操作数组时，数组下标是必定会变化的，key 值的变化，就使得 React 认为该项已经改变了。