React Diff 算法核心

Diff 算法,即差异比较算法,是 React 实现原理的核心之一,React 通过此算法比较每次更新之后子虚拟 DOM 树种最小的差异点,并进行计算。

首先观察 React 是如何工作的。

假设有一个组件MyComponent,长这样

class MyComponent extends React.Component {
  render() {
    const { isFirst } = this.props;
    if (isFirst) {
      return (
        <div className="first">
          <span>A Span</span>
        </div>
      );
    }
    return (
      <div className="second">
        <p>A Paragraph</p>
      </div>
    );
  }
}

我们希望执行以下的行为:

  1. 首先挂载<MyComponent isFirst={true} />

  2. 然后用<MyComponent isFirst={flase} />替换<MyComponent isFirst={true} />

  3. 卸载这个组件

将这样的一个过程转换成 DOM 指令:

从没有到第一步:

创建一个节点

<div className="first">
  <span>A Span</span>
</div>
;

从第一步到第二步:

替换属性className="first"className="seconde". 替换节点<span>A Span</span><p>A paragraph</p>

从第二步到卸载组件:

删除节点

<div className="second">
  <p>A Paragraph</p>
</div>

Diff 算法核心

区分两棵树时,React 首先比较两个根元素。行为因根元素的类型而异。

找到两棵任意的树之间的最小的差异是一个复杂度为 O(n3)O(n^3)的问题,React Diff 算法根据 Web 应用的特点 (Web 应用很少有 component 移动到树的另一个层级,它们大部分只是在相邻的子节点之间移动) 作出以下两个假设,最终达到了接近 O(n)O(n) 的复杂度:

  1. 不同类型的两个元素将产生不同的树。

  2. 开发人员可以使用 props key 提示哪些子元素在不同渲染中可以保持稳定。

How React Compare two tree

不同类型的 React Element

每当根元素具有不同类型时,React 都会拆开旧树并从头开始构建新树。从 <a><img>,或从 <Article><Comment>,或从 <Button><div> -任何这些都将导致完全重建。

拆除树时,旧的 DOM 节点将被破坏。 组件实例接收 componentWillUnmount()。 建立新树时,会将新的 DOM 节点插入到 DOM 中。 组件实例接收 componentWillMount(),然后接收 componentDidMount()。 与旧树关联的任何状态都将丢失。 根目录下的所有组件也将被卸载并破坏其状态。

<div>
  <Counter />
</div>

<span>
  <Counter />
</span>

这将销毁旧的 Counter,然后重新安装新的 Counter

同类型的 DOM Element

比较两个相同类型的 React DOM 元素时,React 会查看两者的属性,保留相同的基础 DOM 节点,并仅更新更改的属性。

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

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

通过比较这两个元素,React 知道只修改底层 DOM 节点上的 className。

在更新样式时,React 还知道仅更新已更改的属性。

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

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

在这两个元素之间进行转换时,React 知道仅修改颜色样式,而不修改 fontWeight。

处理完 DOM 节点后,React 然后在子节点上递归。

同类型的 React Element

组件更新时,实例保持不变,因此在渲染之间保持状态。 React 更新基础组件实例的属性以匹配新元素,并在基础实例上调用 componentWillReceiveProps()componentWillUpdate()

接下来,调用 render()方法,并且 diff 算法根据先前的结果和新的结果进行递归。

递归子节点

默认情况下,在 DOM 节点的子节点上递归时,React 只会同时遍历两个子节点列表,并在存在差异时生成一个更新操作。

例如,在子元素的末尾添加元素时,在这两个树之间进行转换会很好:

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

React 会匹配两个 <li>first</li> 树,两个 <li>second</li> 树,然后插入一个 <li>third</li> 树。(这看起来很不错)

但是,对于下列例子则会导致糟糕的性能。

<ul>
  <li>Duke</li>
  <li>Villanova</li>
</ul>
// to
<ul>
  <li>Connecticut</li>
  <li>Duke</li>
  <li>Villanova</li>
</ul>

React 会操作每个子节点,而不是使<li>Duke</li><li>Villanova</li>保持不变,并在前面插入 <li>Connecticut</li>

React 中渲染多个组件如果不包含 key 属性,你将会在控制面板看到这个警告 "Warning: Each child in an array or iterator should have a unique 'key' prop.

React Key

React 支持 key 属性。当子项具有 key 时,React 使用该键将原始树中的子项与后续树中的子项进行匹配。

React Render with Key in React v15

在对子项进行 diff 时,存在三种类型的操作:

  • MOVE_EXISTING -- 存在相同的节点则复用以前的 DOM 节点,做移动操作。

  • INSERT_MARKUP -- 新的节点不在旧集合里则插入新的节点。

  • REMOVE_NODE -- 新集合里在旧集合中对应的 node 不同,不能直接复用和更新,需要执行删除操作,或者旧集合中的节点不在新集合里的。

  1. 遍历 newChildrens,基于 key 判断 newChild 是否在 oldChildrens 存在相同的节点.

    1. 如果存在相同节点(prevChild === nextChild)

      1. 判断原先节点的变化顺序(不考虑头部新插入的节点)

        1. 节点的挂载顺序变大(从前往后),移动节点

        2. 节点的挂载顺序变小(从后往前或不变),不做操作

      2. 节点的 _mountIndex 变为新集合中的 index

    2. 如果不存在相同节点,

      1. 之前存在相同

      2. 在上一个新集合中的节点后插入新节点

  2. 遍历 oldChildrens,移除在新集合中不存在的节点 (???)

// befor
<ul>
  <li key="2015">Duke</li>
  <li key="2016">Villanova</li>
  <li key="2017">Alex</li>
  <li key="2018">Frank</li>
</ul>

// after
<ul>
  <li key="2014">Connecticut</li>
  <li key="2018">Frank</li>
  <li key="2015">Duke</li>
  <li key="2016">Villanova</li>
</ul>

对与上述例子 DOM 节点的变化顺序为

// step 1
// 插入新的节点 `<li key="2014">Connecticut</li>`
<ul>
  <li key="2014">Connecticut</li>
  <li key="2015">Duke</li>
  <li key="2016">Villanova</li>
  <li key="2017">Alex</li>
  <li key="2018">Frank</li>
</ul>

// step 2
// key 2018 向前移动,实际上不做操作
<ul>
  <li key="2014">Connecticut</li>
  <li key="2015">Duke</li>
  <li key="2016">Villanova</li>
  <li key="2017">Alex</li>
  <li key="2018">Frank</li>
</ul>

// step 3
// `<li key="2015">Duke</li>` 移动至 `<li key="2018">Frank</li>` 后
<ul>
  <li key="2014">Connecticut</li>
  <li key="2016">Villanova</li>
  <li key="2017">Alex</li>
  <li key="2018">Frank</li>
  <li key="2015">Duke</li>
</ul>

// step 4
// `<li key="2016">Villanova</li>` 移动至 `<li key="2015">Duke</li>` 后
<ul>
  <li key="2014">Connecticut</li>
  <li key="2017">Alex</li>
  <li key="2018">Frank</li>
  <li key="2015">Duke</li>
  <li key="2016">Villanova</li>
</ul>

// step 5
// 移除新集合中不存在的节点 `<li key="2017">Frank</li>`
<ul>
  <li key="2014">Connecticut</li>
  <li key="2018">Frank</li>
  <li key="2015">Duke</li>
  <li key="2016">Villanova</li>
</ul>

所以不得已时,您可以将数组中项目的索引作为键传递。但是使用索引作为 key 式,重新排序会很慢。

参考

最后更新于