React 虚拟Dom 和 Diff算法

虚拟Dom

在原生的JavaScript程序中，我们直接对DOM进行创建和更改，而DOM元素通过我们监听的事件和我们的应用程序进行通讯。

而React会先将你的代码转换成一个JavaScript对象，然后这个JavaScript对象再转换成真实DOM。这个JavaScript对象就是所谓的虚拟DOM。

比如下面一段html代码：

<div class="contain">
    <h3>hello</h3>
    <ul>
        <li>1</li>
        <li>2</li>
    </ul>
</div>

在React可能存储为这样的JS代码：

const VitrualDom = {
  type: 'div',
  props: { class: 'contain' },
  children: [
    {
      type: 'h3',
      children: 'hello'
    },
    {
      type: 'ul',
      children: [
        { type: 'li', children: '1' },
        { type: 'li', children: '2' }
      ]
    }
  ]
}

当我们需要创建或更新元素时，React首先会让这个VitrualDom对象进行创建和更改，然后再将VitrualDom对象渲染成真实DOM；

当我们需要对DOM进行事件监听时，首先对VitrualDom进行事件监听，VitrualDom会代理原生的DOM事件从而做出响应。

为何使用虚拟DOM

React为何采用VitrualDom这种方案呢？

提高开发效率

使用JavaScript，我们在编写应用程序时的关注点在于如何更新DOM。

使用React，你只需要告诉React你想让视图处于什么状态，React则通过VitrualDom确保DOM与该状态相匹配。你不必自己去完成属性操作、事件处理、DOM更新，React会替你完成这一切。

这让我们更关注我们的业务逻辑而非DOM操作，这一点即可大大提升我们的开发效率。

关于提升性能

很多文章说VitrualDom可以提升性能，这一说法实际上是很片面的。

直接操作DOM是非常耗费性能的，这一点毋庸置疑。但是React使用VitrualDom也是无法避免操作DOM的。

如果是首次渲染，VitrualDom不具有任何优势，甚至它要进行更多的计算，消耗更多的内存。

VitrualDom的优势在于React的Diff算法和批处理策略，React在页面更新之前，提前计算好了如何进行更新和渲染DOM。实际上，这个计算过程我们在直接操作DOM时，也是可以自己判断和实现的，但是一定会耗费非常多的精力和时间，而且往往我们自己做的是不如React好的。所以，在这个过程中React帮助我们"提升了性能"。

所以，我更倾向于说，VitrualDom帮助我们提高了开发效率，在重复渲染时它帮助我们计算如何更高效的更新，而不是它比DOM操作更快。

Diff 遍历算法

传统 diff 算法

计算一棵树形结构转换成另一棵树形结构的最少操作，是一个复杂且值得研究的问题。传统 diff 算法 通过循环递归对节点进行依次对比，效率低下，算法复杂度达到 O(n^3)，其中 n 是树中节点的总数。O(n^3) 到底有多可怕，这意味着如果要展示 1000 个节点，就要依次执行上十亿次的比较。这个开销实在是太过高昂。现今的 CPU 每秒钟能执行大约30亿条指令，即便是最高效的实现，也不可能在一秒内计算出差异情况。

如果 React 只是单纯的引入 diff 算法而没有任何的优化改进，那么其效率是远远无法满足前端渲染所要求的性能。

因此，想要将 diff 思想引入 Virtual DOM，就需要设计一种稳定高效的 diff 算法，而 React 做到了！

那么，React diff 到底是如何实现的呢？

React diff

传统 diff 算法的复杂度为 O(n^3)，显然这是无法满足性能要求的。React 通过制定大胆的策略，将 O(n^3) 复杂度的问题转换成 O(n) 复杂度的问题。React 中 Dom Diff 采用的深度优先遍历算法，深度优先遍历（DFT depth-first traversal）树的深度优先遍历是指首先遍历树的某个分支上的所有节点，在遍历另一个分支的节点，对于节点中的分支也这样处理。

diff 策略

1. Web UI 中 DOM 节点跨层级的移动操作特别少，可以忽略不计。
2. 拥有相同类的两个组件将会生成相似的树形结构，拥有不同类的两个组件将会生成不同的树形结构。
3. 对于同一层级的一组子节点，它们可以通过唯一 id 进行区分（节点移动会导致 diff 开销较大，通过 key 进行优化）。

基于以上三个前提策略，React 分别对 tree diff、component diff 以及 element diff 进行算法优化，事实也证明这三个前提策略是合理且准确的，它保证了整体界面构建的性能。

• tree diff
• component diff
• element diff

tree diff

React 对树的算法进行了简洁明了的优化，即对树进行分层比较，两棵树只会对同一层次的节点进行比较。

既然 DOM 节点跨层级的移动操作少到可以忽略不计，针对这一现象，React 通过 updateDepth 对 Virtual DOM 树进行层级控制，只会对相同颜色方框内的 DOM 节点进行比较，即同一个父节点下的所有子节点。当发现节点已经不存在，则该节点及其子节点会被完全删除掉，不会用于进一步的比较。这样只需要对树进行一次遍历，便能完成整个 DOM 树的比较。

component diff

React 是基于组件构建应用的，对于组件间的比较所采取的策略也是简洁高效。

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

element diff

当节点处于同一层级时，React diff 提供了三种节点操作，分别为：INSERTMARKUP（插入）、MOVEEXISTING（移动）、TEXTCONTENT（文本内容）、REMOVENODE（删除）。

类型	情况
MOVE_EXISTING	新的component类型在老的集合里也有，并且element是可以更新的类型，在generateComponentChildren我们已经调用了receiveComponent，这种情况下prevChild=nextChild,那我们就需要做出移动的操作，可以复用以前的dom节点。
INSERT_MARKUP	新的component类型不在老的集合里，那么就是全新的节点，我们需要插入新的节点
REMOVE_NODE	老的component类型，在新的集合里也有，但是对应的element不同了不能直接复用直接更新，那我们也得删除。
REMOVE_NODE	老的component不在新的集合里的，我们需要删除