谈谈React虚拟DOM和diff算法

开篇我们先举个简单并且常见的例子：

<ul id='list'>
  <li class='item'>1</li>
  <li class='item'>2</li>
  <li class='item'>3</li>
</ul>
复制代码

页面上有个list，数据依次是1、2、3，现在需要替换成4、5、6、7，如果不使用React，应该怎么操作？

方法1： removeChild() 清空列表， appendChild() 添加4个元素

方法2：针对前3个元素做 nodeValue / textContent 修改，然后 appendChild() 添加1个元素

方法3：使用 innerHtml 直接对整个列表做覆盖式操作

以上3种方式都是使用原生DOM API，都可以实现效果，但是性能上会存在差异。造成差异的原因多种多样，可能取决于元素类型，列表长度，甚至浏览器版本（万恶的IE）。因此应当根据当前环境灵活选用不同的DOM操作方式，但这无疑增加了开发难度，不利于工程师专注实现当前业务。

使用React的话就简单多了，我们无需关心如何进行DOM操作，只需要把数据存在 state 中，然后在 render 函数中 map 生成JSX代码。至于如何操作DOM，由React决定，这些都得益于虚拟DOM和diff算法。

二、什么是虚拟DOM？

虚拟DOM就是使用javascript对象来表示真实DOM，是一个树形结构。

在真实DOM中，一个普通的div打印出来也是很复杂的：

可以想象浏览器处理DOM结构有多慢！和操作DOM相比，操作javascript对象更方便快速，开篇的例子中的DOM结构就可以用javascript来表示：

const tree = {
  tagName: 'ul', // 节点标签名
  props: {       // DOM的属性，用一个对象存储键值对
    id: 'list'
  },
  children: [    // 该节点的子节点
    {tagName: 'li', props: {class: 'item'}, children: ['1']},
    {tagName: 'li', props: {class: 'item'}, children: ['2']},
    {tagName: 'li', props: {class: 'item'}, children: ['3']},
  ]
}
复制代码

虚拟DOM只保留了真实DOM节点的一些基本属性，和节点之间的层次关系，它相当于建立在javascript和DOM之间的一层“缓存”，可以类比CPU和硬盘：硬盘的读写速度是很慢的，相比较于廉价的内存来说。

三、什么是Diff算法？

React需要同时维护两棵虚拟DOM树：一棵表示当前的DOM结构，另一棵在React状态变更将要重新渲染时生成。React通过比较这两棵树的差异，决定是否需要修改DOM结构，以及如何修改。这种算法称作Diff算法。

key prop

有人说虚拟DOM快，这也是相比较来说的。由于维护虚拟DOM树和Diff算法的计算，简化了DOM操作，和MVVM变更整个DOM树的模式相比，确实节省了不少时间。但是和原生JS的开发模式相比，还是直接操作DOM比较快一些，因为开发者明确地知道应该变更哪部分的DOM结构（前提是开发者了解最基本的DOM优化方法）。

四、Diff算法的具体过程

Diff算法会对新旧两棵树做 深度优先遍历 ，避免对两棵树做完全比较，因此算法复杂度可以达到 O(n) 。然后给每个节点生成一个 唯一的标志 ：

在遍历的过程中，每遍历到一个节点，就将新旧两棵树作比较，并且 只对同一级别的元素进行比较 ：

也就是只比较图中用虚线连接起来的部分，把前后差异记录下来。

可能存在的差异类型如下：

1. 不同类型的元素

举个例子，当一个元素从 <a> 变成 <img> ，从 <Article> 变成 <Comment> ，或从 <Button> 变成 <div> ，都会触发一个完整的重建流程： 该节点以及该节点的子节点，都会被销毁，之后创建新的节点 。即 removeChild() -> appendChild() 或者 setInnerHTML() 。

2. 同类型的元素

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

<div className="after" title="stuff" />
复制代码

当比对两个相同类型的元素时，React 会保留当前 DOM 节点和子节点，仅比对及更新有改变的属性。 通过比对这两个元素，React 知道只需要修改 DOM 元素上的 className 属性。即 removeAttribute() -> setAttribute() 或者 setAttribute() 。

另外，React会针对style的改变做特殊处理：

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

<div style={{color: 'green', fontWeight: 'bold'}} />
复制代码

通过比对这两个元素，React 知道只需要修改 DOM 元素上的 color 样式，无需修改 fontWeight 。

如果是React组件，当一个组件更新时，组件实例保持不变，并且更新组件状态，调用该实例的 componentWillReceiveProps() 和 componentWillUpdate() 方法。下一步，调用 render() 方法，diff 算法将在之前的结果以及新的结果中进行递归。

3. 文本节点

<div>text 1</div>
<div>text 2</div>
复制代码

文本节点改动时，React会修改 nodeValue / textContent ，这点无需赘述。

4. 移动、删除、新增子节点

在默认条件下，当递归 DOM 节点的子元素时，React 会同时遍历两个子元素的列表；当产生差异时，生成一个 mutation。

在子元素列表末尾新增元素时，更变开销比较小。比如：

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

<ul>
  <li>first</li>
  <li>second</li>
  <li>third</li>
</ul>
复制代码

通过比较，前两个元素不存在差异，只需要在末尾插入一个 <li>third</li> 。

如果简单实现的话，在列表头部插入会很影响性能，比如：

<ul>
  <li>Duke</li>
  <li>Villanova</li>
</ul>

<ul>
  <li>Connecticut</li>
  <li>Duke</li>
  <li>Villanova</li>
</ul>
复制代码

根据之前提到的算法规则， <li>Duke</li> 和 <li>Villanova</li> 是不能被保留的，都会被看做差异部分，这样的变更开销会比较大。

五、Keys

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

<ul>
  <li key="2015">Duke</li>
  <li key="2016">Villanova</li>
</ul>

<ul>
  <li key="2014">Connecticut</li>
  <li key="2015">Duke</li>
  <li key="2016">Villanova</li>
</ul>
复制代码

Diff算法通过比较得知， key 为'2014'的元素是新增的， key 为'2015'和'2016'的元素仅仅是移动了位置，所以可以调用 insertBefore() 来插入节点。

生成key的注意点：

• key 在列表中应当具有唯一性，但不需要全局唯一。
• key 应当具有稳定性，一个节点在确定 key 之后就不应当变更 key （除非你希望它重新渲染）。不稳定的 key （比如在 render() 中通过 Math.random() 生成的 ）会导致许多组件实例和 DOM 节点被不必要地重新创建，这可能导致性能下降和子组件中的状态丢失。
• 可以使用元素在数组中的下标作为 key 。这个策略在元素不进行重新 排序 时比较合适，但一旦有顺序修改，diff 就会变得慢。

当基于下标的组件进行重新排序时，组件 state 可能会遇到一些问题。由于组件实例是基于它们的 key 来决定是否更新以及复用，如果 key 是一个下标，那么修改顺序时会修改当前的 key ，导致非受控组件的 state （比如输入框）可能相互篡改导致无法预期的变动。