React - 虚拟DOM 和 Diff 算法

一、虚拟DOM

虚拟DOM是一个对象，一个用来表示真实DOM的对象。

概念

Virtual DOM 是一种编程概念。在这个概念里，UI以一种理想化的，或者说“虚拟的”表现形式被保存于内存中。

在React中，render执行的结果得到的并不是真正的DOM节点，结果仅仅是轻量级的JavaScript对象。比如

<div class="box">
    <span>hello world!</span>
</div>
1
2
3

上面这段代码会转换为这样的虚拟DOM结构

{
    tag: "div",
    props: {
        class: "box"
    },
    children: [{
        tag: "span",
        props: {},
        children: ["hello world!"]
    }]
}
1
2
3
4
5
6
7
8
9
10
11

二、Diff 算法

传统的 diff 算法

传统的 diff 算法的通过循环递归来比对节点的，这里时间复杂度是 O(n^2) ，于此同时还需要对 diff 的节点做修改的操作这里的话是 O(n)的时间复杂度,结合到一起就变成了 O(n^3)的时间复杂度。

这样的时间复杂度是不能容忍的，因为在你浏览页面的时候如果 1s 内呈现不了内容人就会觉得这个页面卡顿。而 React 中的 diff 算法却能做到只有 O(n)的时间复杂度。

React 的 Diff 算法

新旧虚拟DOM对比的时候，Diff算法比较只会在同层级进行, 不会跨层级比较。

所以Diff 算法是：深度优先算法、时间复杂度:O(n)。
  
Diff算法是一种对比旧虚拟DOM和新虚拟DOM的算法。

使用虚拟DOM算法的损耗计算： 总损耗 = 虚拟DOM增删改+（与Diff算法效率有关）真实DOM差异增删改+（较少的节点）排版与重绘

直接操作真实DOM的损耗计算： 总损耗 = 真实DOM完全增删改+（可能较多的节点）排版与重绘

实际上，Diff 算法探讨的就是虚拟 DOM 树发生变化后，生成 DOM 树更新补丁的方式。

它通过对比新旧两株虚拟 DOM 树的变更差异，将更新补丁作用于真实 DOM，以最小成本完成视图更新。

具体的流程如下：

• 真实的 DOM 首先会映射为虚拟 DOM；
• 当虚拟 DOM 发生变化后，就会根据差距计算生成 patch；
• 这个 patch 是一个结构化的数据，内容包含了增加、更新、移除等；
• 根据 patch 去更新真实的 DOM，反馈到用户的界面上。

React 的 Diff 策略

基于三个策略

• Web UI 中 DOM 节点跨层级的移动操作特别少，所以基本是比较同级两颗节点树的差异（tree diff）
• 拥有相同类的两个组件将会生成相似的树形结构，拥有不同类的两个组件将会生成不同的树形结（component diff）
• 对于同一层级的一组子节点，它们可以通过唯一 id 进行区分，通过Key 用于追踪哪些列表中元素被修改、被添加或者被移除的辅助标识（element diff）

1. Tree diff

DOM 节点跨层级的移动操作特别少，React 会将这种行为忽略，只对 Dom 树同一层级的节点进行比较，也就同一个父节点下的所有子节点。

当发现节点已经不存在时，则该节点及其子节点会被完全删除掉，不会用于进一步的比较。这个策略就保证了只需要对树进行一次遍历。
  
如下所示新旧Dom树，React这个策略导致的行为是：在遍历第一层的时候不进行操作，第二层的时候 删除A节点，第三层的时候 创建 A节点及其子节点. (Delete A => Create A -> create B -> create C)。
  

2. Component diff

拥有相同类的两个组件将会生成相似的 Dom 结构，拥有不同类的两个组件将会生成不同的 Dom 结构，所以如果是不同类型的两个组件 React 会直接重建新的组件。
  
对于同类型的组件我们可以使用 shouldComponentUpdate() 来手动判断是否需要进行 diff 运算，如果不进行 diff 运行这显然是可以改善性能的。

如下图所示的新旧Dom树，在基于Tree diff 后React这个策略导致的行为是：发现新旧Dom 树的 D G节点不是同类型的组件，那么就直接删除D节点然后新建G节点及其子节点(Delete D => Create G -> create E -> create F)。
  

3. Element diff

Element diff 提供了3种节点操作：插入、移动、删除。

对比新老元素集合，如果新集合存在老集合中没有的元素，那么就插入，如果有并且是可以复用的，那么就移动(这期间会有一个if (child._mountIndex < lastIndex)的策略决定是否移动元素位置)，剩下的在老集合中存在而新集合没用的元素就删除。

如图，老集合中包含节点： A、B、C、D，更新后的新集合中包含节点： B、A、D、C。

此时新老集合进行 diff 差异化对比，发现 B != A，则创建并插入 B 至新集合，删除老集合 A。以此类推，创建并插入 A、D 和 C，删除 B、C 和 D。

这类操作烦琐冗余，因为这些都是相同的节点，但由于位置发生变化，导致需要进行繁杂低效的删除、创建操作，其实只要对这些节点进行位置移动即可。
  

所以针对如图这个情况，React key的作用就体现出来了。

加入key 这个策略后，React首先对新集合的节点进行循环遍历，for (name in nextChildren)，通过唯一 key 可以判断新老集合中是否存在相同的节点，if (prevChild === nextChild)。

如果存在相同节点，则进行移动操作，但在移动前需要将当前节点在老集合中的位置与 lastIndex 进行比较，if (child._mountIndex < lastIndex),则进行节点移动操作，否则不执行该操作。

这是一种顺序优化手段，lastIndex 一直在更新，表示访问过的节点在老集合中最右的位置（即最大的位置），如果新集合中当前访问的节点比 lastIndex 大，说明当前访问节点在老集合中就比上一个节点位置靠后，则该节点不会影响其他节点的位置，因此不用添加到差异队列中，即不执行移动操作，只有当访问的节点比 lastIndex 小时，才需要进行移动操作。

4. Patch 操作

Diff 操作都还是在 Virtual DOM 中进行的。

然而浏览器中并未能显示出更新的数据，所以就需要Pathch 操作来把 tree diff 计算出来的 DOM差异队列更新到真实的 DOM 节点上，最终让浏览器能够渲染出更新后的数据。

这主要是通过遍历差异队列实现的。遍历差异队列时，通过更新类型(插入,删除,移动) 进行相应的操作。

React之所以可以直接依次插入节点，就是因为在就是在 diff 阶段添加差异节点到差异队列时，本身就是有序添加。

也就是说，移动节点和新增节点在队列里的顺序就是最终真实DOM的顺序，因此可以直接依次根据 index 去插入节点。

而且，React 并不是计算出一个差异就去执行一次 Patch，而是计算出全部差异并放入差异队列后，再一次性地去执行 Patch 方法完成真实DOM 的更新。

---

参考链接：
15张图，20分钟吃透Diff算法核心原理
React diff算法分析和理解