虚拟DOM和DIFF算法

发表于 分类于 / / Changyan：

虚拟DOM

🌈为什么需要虚拟DOM

目的：为了解决频繁操作 DOM 导致性能开销大的问题

方案：JS运算效率 远高于 操作DOM效率，所以把真实DOM树抽象成JS对象树，运用 patch 算法 来用JS计算出真正需要更新的节点，最大限度地减少 DOM 操作，从而显著提高性能

  1. Vue/React 等框架都是数据驱动页面更新，让用户无需自己操作 DOM
  2. 由于操作 DOM 这个行为本身开销成本大，而数据的频繁更新会导致 DOM 也得频繁操作
  3. 所以框架本身就得想出一个解决方案，能够尽可能减少 DOM 操作
  4. 而执行 JS 的效率远高于操作真实 DOM，所以想到用 JavaScript对象树 来模拟 真实DOM树，这样一来，不直接操作 DOM ，而是操作 JS 数据。性能就能提高许多
  5. 再通过 diff 算法，把最终更新时需要操作的部分计算好，最后一次性操作 DOM
  6. 从而达到减少 DOM 操作，提升性能的目的

🌈什么是虚拟DOM

Virtual DOM 其实就是一棵以 JavaScript 对象（vNode节点）作为基础的树，用对象属性来描述节点，实际

是一层对真实 DOM 的抽象。

基本成员：

  • tag （标签名）
  • props （属性）
  • children （子元素对象集合）

例如：

1
2
3
4
5
6
7
8
<div id="app" class="container">
  <h1>虚拟DOM</h1>
  <ul style="color: orange">
    <li>第一项</li>
    <li>第二项</li>
    <li>第三项</li>
  </ul>
</div>

虚拟DOM表示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
{
	tag: 'div',
  props: {
  	id: 'app',
    class: 'container'
  },
  children: [
    {
    	tag: 'h1',
      children: '虚拟DOM' 
    },
    {
    	tag: 'ul',
      props: { // 节点属性及绑定事件...
      	style: 'color: orange'
      },
      children: [
        {
        	tag: 'li',
          children: '第一项'
        },
        {
        	tag: 'li',
          children: '第二项'
        },
        {
        	tag: 'li',
          children: '第二项'
        }
      ]
    }
  ]
}

模板转化为视图的过程

🌈构建虚拟DOM

获取 template →

template 转 AST 语法树 →

AST 语法数 转 render 函数 → 

1
render 函数 返回 VNode(虚拟DOM节点）

🌈更新视图

  1. 数据变化
  2. 触发对应 Dep（订阅者） 中的 Watcher 对象们
  3. Watchers 会调用各自的 update 函数更新视图
    1. 利用 diff 算法将新旧虚拟节点进行差异对比
    2. 根据对比结果进行 DOM 操作

总结

转化过程：

1
模板`→  `AST树`→`渲染函数`→ `虚拟DOM`→ `真实DOM

其中：

  • 渲染函数：渲染函数是用来生成 Virtual DOM 的

  • VNode 虚拟节点：代表一个真实的 DOM 节点。通过 createElement 方法能将 VNode 渲染成 DOM节点

  • Patch 算法：通过对比新旧虚拟节点（diff 算法），找出需要更新的节点，将 VNode 渲染成真实的 DOM

🌈虚拟 DOM 的优势

  • 运行效率高
    • 因为 DOM 操作的执行速度远不如 Javascript的运算速度快。因此，把大量的 DOM 操作放在到 Javascript 中，运用 patch 算法来计算出真正需要更新的节点，最大限度地减少 DOM 操作，从而显著提高性能
  • 提高渲染的性能
    • Virtual DOM的优势在于在大量、频繁的数据更新下，能够对视图进行合理、高效的更新
  • 具备跨平台的优势
    • 由于 Virtual DOM 是以 Javascript 对象为基础而不依赖真实平台环境，所以使它具有了跨平台的能力

AST 抽象语法树（Abstract Syntax Tree）

源代码的抽象语法的树状描述

目的

把代码形成树状结构，然后对这个结构做分析、优化、处理，最终再把它转化为真正所需内容

🌈 应用

  • webpack 利用AST：import 转 require()
  • ts 利用AST：ts 转 js
  • eslint 代码规范解析

说白了就是字符串解析、拼接、再解析、再拼接…

template 转 AST

对源代码的数据结构化

目的

模板中有 v-show 、v-if 、v-model 这些指令等其他内容，而这些内容是不能存在于虚拟 DOM 中的，因为真实 html 不需要它们，它们是框架所需的，类似这种东西全部都得转为 AST 后做处理，把这些多余的（相对真实html）属性都解析成对应功能并最终删除它们。例如

  • vue的各种指令 => 处理
  • 用户少写了结束标签 </div> => 帮用户补上 or 给警告

示例

1
2
3
4
5
6
7
8
<div id="app" style="color: red;font-size: 20px;">
  hello
  <h1>{{ name }}</h1>
  <ul>
    <li style="color: green">{{ age }}</li>
    <li>{{ info.job }}</li>
  </ul>
</div>

转为 👇🏻

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
{
	tag: "div",
  type: 1, // 1代表标签
  attrs: [
    {
    	name: 'id',
      value 'app'
    },
    {
    	name: 'style',
      value: {
      	'color': 'red',
        'font-size': '20px'
      }
    }
  ],
  children: [
    {
    	type: 3, // 3代表文本
      text: 'hello'
    },
    {
    	type: 1,
      tag: 'h1',
      attr: null,
      children: [
        {
        	type: 3,
          text: '{{name}}'
        }
      ]
    }
  ]
}

这不是虚拟 DOM ，只是类似。虚拟 DOM 是描述 DOM 对象（节点）的，最终是要变成真实 DOM 的

🌈diff 算法

虚拟 DOM 的最终目的就是将虚拟节点渲染到视图上。

  • 直接替换（不推荐）：
    • 如果是用新的虚拟节点直接覆盖原来旧的虚拟节点的话，就会有很多不必要的DOM操作。
  • 新旧节点比较（推荐）：
    • 为了避免这些不必要的 DOM 操作，就需要将新的虚拟节点与上一次渲染视图所使用的旧的虚拟节点做对比，找出真正需要更新的节点来进行DOM操作。最后在更新视图。

上面的过程就是所谓的虚拟 DOM 的算法，也就是 diff 算法，它主要包括两个步骤：

  • 初次渲染
    • 把 JavaScript 对象结构表示的 DOM 树转化为虚拟节点，再渲染成真正的 DOM ，最终插入到容器里面
  • 再次渲染
    • 将新的 VNode 和旧的 VNode 进行对比，然后将两者之间的差异更新到真正的 DOM 树上，完成视图的更新

算法

特点

同层比较、不跨级

标签名不同，直接替换，不深度比较

标签名和key都相同，当做相同节点，属性改变则更新属性

🌈 步骤

  1. 如果新老节点不是同一个节点名称，那么就暴力删除旧的节点，创建插入新的节点。
  2. 只能同级比较，不能跨层比较。如果跨层那么就暴力删除旧的节点，创建插入新的节点。
  3. 如果是相同节点，又分为很多情况
    1. 新节点有没有children
      1. 如果新的节点没有children，那就证明新节点是文本，那直接把旧日的替换成新的文本
    2. 新节点有children
      1. 新的有children，旧的也有 children ====> 就是diff算法的核心了
1
2
3
4
5
6
7
diff 算法核心（最复杂的情况）
1. 旧前 vs 新前
2. 旧后 vs 新后
3. 旧前 vs 新后
4. 旧后 vs 新前
5. 以上都不满足，遍历查找
6. 创建 or 删除
  1. 新的有children，旧的没有 children  ====> 创建元素添加（把旧的内容删除清空掉，增加新的)

注意：如果要提升性能，一定要加入key， key是唯一标示，在更改前后，确认是不是同一个节点

diff算法核心示例

  • 旧前 vs 新前
    • 匹配：旧前的指针++、新前的指针++

每次都从第一个元素（从前往后）开始新旧两两比较，都从指针（索引index）0开始，如果两两相同，就原地复用，把a更新页面上，然后index++，直到比较完毕，最终全部复用

  • 旧后 vs 新后
    • 匹配：旧后的指针–、新后的指针–

还是先从前往后比较，如果新旧节点从第一个开始比较，发现节点不一样，那么指针就从后边往前面比较

  • 旧前 vs 新后

    • 匹配：旧前的指针++，新后的指针–
  1. 先走第一种策略，比较【旧a vs 新a】一样，新旧指针index都++，然后比较【旧b 和 新b】一样，又 index都++；
  2. 比较到第三对 【旧c 和 新d】时，发现不一样了，就走第二种策略（旧后 vs 新后），发现 【旧d vs 旧c】不一样；
  3. 改为第三种策略（旧前 vs 新后），此时【旧c vs 新c】一样了，那么此时旧index++，新index–；
  4. 最后还是从第一种策略开始（不要以为此刻是下图的旧d和新d交叉在比较），此刻的比较对象就是【旧d vs 新d】了

  • 旧后 vs 新前

    • 匹配：旧后的指针–、新前的指针++

  • 以上都不满足条件，遍历查找

  1. 先走第一种策略【旧a vs 新b】不一样
  2. 然后走第二种策略【旧d vs 新m】不一样
  3. 接着走第三种策略【旧a vs 新m】不一样
  4. 再走第四种策略【旧d vs 新b】不一样
  5. 上边都不满足
  6. 遍历新节点找【旧a】，然后在新节点中找到了，此时先把【新b】放到页面中，然后新前指针 index++（此时指针情况：【旧前index=0；新前index=1】）
    1. 接着又会去旧节点中找【新b】，找到了，就把【旧b】设置为 undefined
  7. 接着还是从第一策略走一遍，1，2，3，4中策略都不满足，又从新节点中找【旧a】，找到了，此时又把【新c】放到页面中，新前指针又index++（此时指针情况：【旧前index=0；新前index=2】）
    1. 接着又会去旧节点中找【新c】，找到了，就把【旧c】设置为 undefined
  8. 接着继续从第一策略开始匹配，发现此时【旧a vs 新a】匹配上了，那么原地复用，旧前index++，新前index++（此时指针情况：【旧前index=1；新前index=3】）
  9. 接着还是从第一策略开始匹配，发现此时【旧b】已经是 undefined 了，那么就会直接把旧前index++（此时指针情况：【旧前index=2；新前index=3】）
  10. 仍然从第一策略开始匹配，发现此时【旧c】也是 undefined 了，重复上边步骤，旧前index++（此时指针情况：【旧前index=3；新前index=3】）
  11. 继续从第一策略开始，此时【旧d vs 新d】，匹配上了，原地复用
  12. 到最后m时，上边5种情况都走一遍，都不满足，就只剩最后的【创建 or 删除】了，最终创建m，添加到页面上