上一节咱们学习了Vue中异步渲染队列的原理，本节咱们沿着响应式图谱学习下一个局部——渲染页面。

如上图所示，Vue会依据之前失去的变更告诉生成一颗新的Virtual DOM树，而后再将新的Virtual DOM树和旧的Virtual DOM树进行diff patch操作。

本节的指标是学习Virtual DOM以及Vue是如何对新旧两颗Virtual DOM树进行diff patch算法。

后面大节的链接在这里：

Vue—对于响应式（一、依赖收集原理剖析）

Vue—对于响应式（二、异步更新队列原理剖析）

一、Virtual DOM

1.1. 什么是Virtual DOM

一听到"虚构DOM"这个词汇，天然的会升起一种它很高级的感觉。没错，它的确很高级，然而稳住不要慌，你能够把它当成咱们吃饭用的筷子，对于外国人而言，中国的筷子也是一种高级（共同点：都是外国人创造的【手动滑稽】）。你天天用筷子当然就不会感觉筷子很高级，这个情理是：你越相熟它，它对你而言就越不神秘。

在js中，简略了解Virtual DOM就是通过 JS的对象构造 来形容 DOM树结构的一种工具。

1.2. 为什么要应用Virtual DOM

这个问题很多文章是这么答复的：操作DOM是很消耗性能的一件事件，咱们能够思考通过JS对象来模仿DOM对象，毕竟操作JS对象比操作DOM省时的多。

事实上这种说法是不对的，操作JS对象的确比操作DOM省时，然而在Virtual DOM中并不能缩小DOM操作，这一步DOM操作是由Virtual DOM在diff patch的过程中实现的，通过这一步事实上它缩小的是咱们前端人员间接通过DOM API去增删改查DOM节点的操作，从而进步了咱们的开发效率而并非产品性能。

在计算机界始终流传着这么一句话：

翻译过去就是说：软件开发中遇到的所有问题都能够通过减少一层形象而得以解决。

Virtual DOM也是相似，它也是分层思维的一种体现，为什么这么说？当咱们在开发的时候是基于肯定的DSL的，比方说咱们前端会应用HTML、JS、CSS来写代码，那么框架帮咱们形象出一层Virtual DOM，通过这层Virtual DOM，框架能够将不同的Virtual DOM节点适配到不同的view显示端，其中包含像H5、小程序以及App native，从而使咱们的代码具备一次编写多端执行的可能性。

看完形象的概念，咱们再来看一下Virtual DOM在代码中具体是怎么体现的。

1.3. Virtual DOM的具体表现形式

以上面这段html代码为例：

<ul id='list'>  <li class='item'>Item 1</li>  <li class='item'>Item 2</li>  <li class='item'>Item 3</li></ul>

Virtual DOM形象进去的js对象为：

var VNode = {  tagName: 'ul', // 标签名  props: { // 属性用对象存储键值对    id: 'list'  },  children: [ // 子节点    {tagName: 'li', props: {class: 'item'}, children: ["Item 1"]},    {tagName: 'li', props: {class: 'item'}, children: ["Item 2"]},    {tagName: 'li', props: {class: 'item'}, children: ["Item 3"]},  ]}

比照下面的代码，很容易看进去它们之间的映射关系。既然DOM节点能够转换成JS对象，反之亦然，Virtual DOM须要做的就是：

  1. 将你编写好的DOM树结构（如.vue文件中的template）转换成JS对象树结构，而后再将JS对象树构建成真正的DOM树即可。
  2. 当检测到状态变更时，生成新的JS对象树并与旧的对象树进行比对，通过diff算法最终确认要进行多少更新。

小结

  • Virtual DOM是分层思维的一种体现，通过减少形象层来帮忙咱们实现一次编写多端通用的性能。
  • Virtual DOM是通过JS对象构造来形容DOM树结构的工具。
  • Virtual DOM检测到状态变更时会生成新的对象树，通过diff算法比对新旧对象树来最终确认DOM更新策略。

二、Diff Patch

2.1. 什么是diff算法

作为面向百度工程师，第一步当然是你们懂的了【手动滑稽】

百度百科给出的答案是：

  • Virtual DOM中采纳的算法
  • 将树结构按层级划分，只比拟同级元素，不同层级的节点只有创立和删除操作
  • 为列表构造的每个单元增加惟一的key

有了这个概念咱们持续往下学习。

那到底什么是diff算法？

打个比方，把老虎变成大象最短须要几步？换种说法，把Tiger这个字符串变成Elephant字符串最短须要几步？从Tom到Michael到Sunny呢？

为理解出这个题，你须要设计一种最优的字符串变更和匹对的算法，而Virtual DOM为了确定最优的DOM变更策略，它的解题算法就是diff。

2.2. Virtual DOM为什么要抉择diff算法

咱们都晓得DOM操作的开销十分低廉，轻微的操作都有可能引起页面重排损耗性能，所以要尽量减少DOM操作，diff算法的作用就是通过比对新旧Virtual DOM树的差别，最小化的执行DOM操作，从而进步开发人员的效率。

最小化操作dom的过程，咱们就不必再思考那么多间接操作DOM带来的问题了，次要目标是为了提效，开发者的程度参差不齐，不必手动操作DOM了，从侧面来讲也是对性能的优化。

2.3. diff策略

咱们的利用通过Vue框架其实会转换成一颗虚构DOM树，当咱们进行了一些页面上的操作时，或者说咱们失去了一些异步数据更新响应之后，其实是将右边的DOM树转化成左边的DOM树，这个转化过程中就要利用到diff的策略。

当初支流的MVVM框架根本都会依照以下策略：

  1. 按tree层级diff
  2. 按类型进行diff（组件类型或者是元素类型）
  3. 列表diff

2.3.1. 按tree层级diff

如下图所示，对每一层进行diff。这次要是因为在web UI当中很少会呈现DOM节点跨层级挪动，这种状况少的能够忽略不计，因而Virtual DOM的diff策略是在新旧节点树之间按层级进行diff从而失去差别。

2.3.2. 按类型进行diff

无论Virtual DOM中的节点数据对应的是一个原生DOM节点还是Vue的一个组件，不同类型的节点所具备的子树节点之间构造往往差别显著，因而对不同类型的节点子树进行递归diff的投入老本与产出比将会比拟昂扬，为了晋升diff效率，Virtual DOM只对雷同类型的节点进行diff，当新旧节点产生了类型的扭转时则并不进行子树的比拟，而是间接创立新类型的Virtual DOM替换旧节点。

如下图所示，假如咱们diff到了这一层

当初要将父节点的五角星转换成下图的三角形节点

依照规定，首先是同层级进行diff，能够看到在这一层中五角星和三角形不是一个类型，如下图所示：

那么这个组件以及它的子组件都会被齐全的销毁，哪怕这个组件上面的两个五角星子组件跟原来的组件是同一个组件，它们依然须要再一次被创立，如下图所示：

2.3.3. 列表diff

在列表diff的过程中，能够给每一项都设置一个key，通过key能够晋升diff的效率。如下图所示，左图没有key，所以老的节点全副删除，新的节点再全副创立；右图增加key值，所以只须要将A挪动到B，将C挪动到D即可。

咱们来看一下源码中是怎么进行列表diff的，以vue 2.6.11版本为例，源码在src/vdom/patch.js中

对于updateChildren函数的源码解析参考文章：

https://zhuanlan.zhihu.com/p/...

具体细节很多，咱们通过图解来看一下它具体的思维是什么样的。

如下图所示，假如咱们旧的Virtual DOM层级下面的节点数是这么一个排列，当初要变成新的排列，浅灰色圆圈代表Virtual Node，也就是咱们的虚构节点，外面的深灰色小圆圈代表的是DOM的实体

当初咱们页面上的DOM实体是以123456来排列的，咱们来看图解过程，在算法开始之前，vue外面首先会定义四个指针，这四个指针别离是oldStartIdx/oldEndIdx、newStartIdx/newEndIdx，它们的名字其实也就代表了它们的意思，就是老的Virtual DOM节点开始的地位和完结的地位、新的Virtual DOM开始的地位以及完结的地位

代码的判断逻辑是，首先vue会判断oldStartIdx以及newStartIdx这两个指针所对应的节点的Virtual DOM是否为同一个，如下图所示

图示中咱们发现它们就是同一个（旧树是1，新树是1），这时候第一轮循环就实现了，此时oldStartIdx指针往后挪动了一位，newStartIdx也会往后挪动了一位，如下图所示

而后进入到第二个循环，比照下一个Virtual Node，依照上一步的逻辑，还是先比对oldStartIdx和newStartIdx的值是否相等，这个时候咱们发现2和5并不是同一个Virtual Node

接下来就换一种形式比拟，去比拟oldEndIdx和newEndIdx，凑近开端的两个节点是否为同一个节点？这个时候咱们发现它们又是同一个节点（旧树是6，新树是6）

与后面类似，第二轮循环实现，此时oldEndIdx减一，newEndIdx也进行减一，两个完结下标向前挪动一位，如下图所示：

接下来比拟第三个循环，还是先比拟两个开始下标oldStartIdx/newStartIdx所指向的Virtual Node是否统一，咱们能够看到不统一（旧树是2，新树是5），如下图所示：

而后再比拟两个完结下标oldEndIdx/newEndIdx指向的Virtual Node是否统一，能够看到也不统一（旧树是5，新树是2），如下图所示：

之前的两种比对形式节点都不同，这个时候就会比拟oldStartIdx和newEndIdx，进行捺向比拟，这个时候发现这两个节点是统一的（旧树是2，新树是2），然而它的地位产生了扭转，所以这个时候就须要把oldStartIdx所指向的Virtual DOM节点外面的实在DOM节点（深灰色2）挪到oldEndIdx所指向的Virtual DOM节点的实在DOM节点之后，同时oldStartIdx也会向后挪动一位（加一），newEndIdx也会向前挪动一位（减一），如下图所示：

（捺向比照）

（移动实在dom节点2地位）

（oldStartIdx后移一位，newEndIdx前移一位）

接下来进入第四个循环，同样的先判断两个开始下标oldStartIdx/newStartIdx，能够看到节点不统一（旧树是3，新树是5），如下图所示：

而后再比拟两个完结下标oldEndIdx/newEndIdx指向的Virtual Node是否统一，能够看到也不统一（旧树是5，新树是7），如下图所示：

接着进行捺向比拟，比拟oldStartIdx跟newEndIdx指向的Virtual Node是否统一，能够看到不统一（旧树是3，新树是7），如下图所示：

这个时候就会再进行另外一种穿插方向比对，就是oldEndIdx和newStartIdx的比照，这是一个撇方向的比照，这时候发现对应的节点是统一的（旧树是5，新树是5），而后就会把oldEndIdx所指向的理论的DOM节点（深灰色5）挪到oldStartIdx所指向的理论节点的后面，同时，咱们的oldEndIdx向前挪动一位（减一），newStartIdx往后挪动一位（加一），如下图所示：

（撇向比照）

（移动实在dom节点5地位）

（oldStartIdx前移一位，newEndIdx后移一位）

而后进入第五个循环，同样的先判断两个开始下标oldStartIdx/newStartIdx，能够看到节点不统一（旧树是3，新树是7），如下图所示：

而后再比拟两个完结下标oldEndIdx/newEndIdx指向的Virtual Node是否统一，能够看到也不统一（旧树是4，新树是7），如下图所示：

接着进行捺向比拟，oldStartIdx和newEndIdx比拟，发现3和7也不统一

而后就会进行撇向比拟，也就是oldEndIdx和newStartIdx所指向的节点，4和7也不统一

这个时候vue就会对oldStartIdx和oldEndIdx这两个指针所指向的节点之间的所有节点进行一次遍历，而后寻找newStartIdx所指向的节点是否存在于这些老的Virtual DOM当中，如果找到的话就会把它挪到oldStartIdx所指向的节点之前。

这里咱们会发现其实是找不到的，7不在oldStartIdx和oldEndIdx这两个指针之间，这时候就须要新创建一个节点7，在实现了这一步之后咱们的newEndIdx也会向前挪动一位（减一）

这个时候咱们就会发现，newEndIdx曾经小于newStartIdx了，这也标记着咱们的New Vnode列表曾经生成结束了，接下来一步就是把咱们的Old Vnode列表当中多余的局部给删除掉。

多余的局部其实就是oldStartIdx和oldEndIdx这两个指针之间的那局部，也就是咱们的3、4节点，删除掉这部分，如下图所示：

这个时候咱们就发现了新的Virtual DOM的列表其实就是下方的这个New Vnode列表，而理论页面上的DOM节点1、5、7、2、6也是依照这个New Vnode列表程序来维持的，那么Old Vnode上的Virtual DOM的生命周期也就到此为止了，也就是能够被销毁了，如下图所示：

2.3.3.1. key的作用

在vue的官网文档下面着重的说了一句：

为了给Vue一个提醒，以便它能跟踪每个节点的身份，从而重用和从新排序现有元素，你须要为每一项提供一个惟一 key 属性

文档地址：https://cn.vuejs.org/v2/guide...

key属性在这个算法当中又有什么作用呢？

咱们假如后面的Old Vnode当中多了一个节点7

当咱们没有设置key的时候，咱们的匹对程序第一步还是依照两个StartIdx所指向的节点进行比拟

第二步是两个EndIdx进行比拟

第三步是捺向的方向进行比拟，也就是oldStartIdx跟newEndIdx所指向的节点进行比拟

第四步是撇向的方向进行比拟，也就是oldEndIdx跟newStartIdx所指向的节点进行比拟

这个时候发现都不统一的时候，依照咱们后面说的，如果没有设置key的状况下就会去遍历oldStartIdx和oldEndIdx之间去寻找是否存在这么一个节点，如果存在的话就会把它挪到后面去。

如果有设置了key属性，首先会去寻找在这个key map当中是否存在着对应的一个序号如下图，这里咱们能够发现7这个节点也就是key-7对应的就是咱们下面的列表当中的第四项

这个时候咱们就不须要再对oldStartIdx和oldEndIdx之间的节点进行遍历了，就缩小了这次循环操作，能够间接把7这个节点挪到5这个节点前面去，最初删除多余的节点就失去了新的节点树1、5、7、2、6，如下图所示：

从这里咱们就可以看进去，如果设置了一个key，算法复杂度为O(n)

当咱们不设置key的时候，算法复杂度的最好状况才是一个O(n)，这种状况就是咱们基本就没有进行遍历，刚好齐全就是匹对的状况，最坏的状况就会回升到O(n²)，其实就是说咱们对每一个oldStartIdx跟oldEndIdx之间的区间都进行一次遍历。

对于key，官网文档形容如下：

文档地址：https://cn.vuejs.org/v2/api/#key

Vue的整个diff过程就是整个patch办法的流程，整个流程也会通过递归地调用patchVnode来实现对整棵Virtual DOM Tree的更新，正是因为它的节点操作是在diff过程中同时进行的，也正是因为这种模式晋升了Vue在增删改查DOM节点时的效率。

2.4. 小结

  • diff算法用来比对新旧Virtual DOM的差别，使咱们尽可能少的操作实在DOM以进步开发效率。
  • diff算法分为两个粒度，一个是组件级别(Component diff)，另一个是元素级别(Element Diff)。组件级别的diff算法比较简单，节点不雷同就进行创立和替换，节点雷同的话就会对其子节点进行更新；对子节点进行更新也就是元素级别的diff，通过插入、挪动、删除等形式使旧列表与新列表统一。

  • Vue中的diff算法大抵分为5个步骤：

    1. 先从两棵树的开始下标进行比对
    2. 再从两棵树的完结下标进行比对
    3. 而后从捺向进行比对
    4. 接着从撇向进行比对
    5. 最初从Old Vnode开始下标地位和完结下标地位之间进行遍历查找（如果有设置key，则间接找到key对应的节点进行复用，无需再进行遍历）
  • 列表渲染时，应用key能够很好的进步性能。

前面要学习的内容在这里：

Vue—对于响应式（四、深刻学习Vue响应式源码）

三、参考

合格前端系列第五弹- Virtual Dom && Diff

深度了解 Virtual DOM

DIFF算法浅析（一）概念

源码解读 —— vue diff 算法

精读《DOM diff 原理详解》

详解vue中的diff算法

本文由博客一文多发平台 OpenWrite 公布！