关于前端:Vue关于响应式三Diff-Patch原理分析

上一节咱们学习了 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 公布！