深入Vue2.x的虚拟DOM diff原理

Vue的核心是双向绑定和虚拟DOM（下文我们简称为vdom），关于双向绑定可以参阅木琴的文章《剖析Vue原理&实现双向绑定MVVM》，vdom是树状结构，其节点为vnode，vnode和浏览器DOM中的Node一一对应，通过vnode的elm属性可以访问到对应的Node。

vdom因为是纯粹的JS对象，所以操作它会很高效，但是vdom的变更最终会转换成DOM操作，为了实现高效的DOM操作，一套高效的虚拟DOM diff算法显得很有必要。

Vue的diff算法是基于snabbdom改造过来的，感兴趣的朋友可以选择查阅。

这是一张很经典的图，出自《React’s diff algorithm》，Vue 的 diff 算法也同样，即仅在同级的 vnode 间做 diff，递归地进行同级 vnode 的 diff，最终实现整个 DOM 树的更新。那同级 vnode diff 的细节又是怎样的呢？正是本文所要讲的。

一、例子

我们在下文中将使用这个简化的例子来讲述 diff 的过程

如上图的例子，更新前是 1 到 10 排列的 Node 列表，更新后是乱序排列的 Node 列表。罗列一下图中有以下几种类型的节点变化情况：

（1）头部相同、尾部相同的节点：如 1、10

（2）头尾相同的节点：如 2、9（处理完头部相同、尾部相同节点之后）

（3）新增的节点：11

（4）删除的节点：8

（5）其他节点：3、4、5、6、7

二、简单的 diff

简单的 diff 算法可以这样设计：

逐个遍历 newVdom 的节点，找到它在 oldVdom 中的位置，如果找到了就移动对应的 DOM 元素，如果没找到说明是新增节点，则新建一个节点插入。遍历完成之后如果 oldVdom 中还有没处理过的节点，则说明这些节点在 newVdom 中被删除了，删除它们即可。

仔细思考一下，几乎每一步都要做移动 DOM 的操作，这在 DOM 整体结构变化不大时的开销是很大的，实际上 DOM 变化不大的情况现实中经常发生，很多时候我们只需要变更某个节点的文本而已。

接下来我们看一下 Vue 的 diff 实现

三、Vue 的 diff 实现

上图例子中我画上了 oldStart+oldEnd，newStart+newEnd 这样 2 对指针，分别对应 oldVdom 和 newVdom 的起点和终点。起止点之前的节点是待处理的节点，Vue 不断对 vnode 进行处理同时移动指针直到其中任意一对起点和终点相遇。处理过的节点 Vue 会在 oldVdom 和 newVdom 中同时将它标记为已处理（标记方法后文中有介绍）。Vue 通过以下措施来提升 diff 的性能。

（一）优先处理特殊场景

（1）头部的同类型节点、尾部的同类型节点

这类节点更新前后位置没有发生变化，所以不用移动它们对应的 DOM

（2）头尾/尾头的同类型节点

这类节点位置很明确，不需要再花心思查找，直接移动 DOM 就好

处理了这些场景之后，一方面一些不需要做移动的 DOM 得到快速处理，另一方面待处理节点变少，缩小了后续操作的处理范围，性能也得到提升

（二）“原地复用”

“原地复用”是指 Vue 会尽可能复用 DOM，尽可能不发生 DOM 的移动。Vue 在判断更新前后指针是否指向同一个节点，其实不要求它们真实引用同一个 DOM 节点，实际上它仅判断指向的是否是同类节点（比如 2 个不同的 div，在 DOM 上它们是不一样的，但是它们属于同类节点），如果是同类节点，那么 Vue 会直接复用 DOM，这样的好处是不需要移动 DOM。再看上面的实例，假如 10 个节点都是 div，那么整个 diff 过程中就没有移动 DOM 的操作了。

“原地复用”在 Vue 的官方文档中有提到，虽然带来了好处，但是也会产生一些问题，朋友们可以复习一下

https://cn.vuejs.org/v2/guide/list.html#key

https://cn.vuejs.org/v2/guide/conditional.html#用-key-管理可复用的元素

四、按步解剖实例

（一）整体视图

先看一张整体视图，整个 diff 分两部分：

（1）第一部分是一个循环，循环内部是一个分支逻辑，每次循环只会进入其中的一个分支，每次循环会处理一个节点，处理之后将节点标记为已处理（oldVdom 和 newVdom 都要进行标记，如果节点只出现在其中某一个 vdom 中，则另一个 vdom 中不需要进行标记），标记的方法有 2 种，当节点正好在 vdom 的指针处，移动指针将它排除到未处理列表之外即可，否则就要采用其他方法，Vue 的做法是将节点设置为 undefined。

（2）循环结束之后，可能 newVdom 或者 oldVdom 中还有未处理的节点，如果是 newVdom 中有未处理节点，则这些节点是新增节点，做新增处理。如果是 oldVdom 中有这类节点，则这些是需要删除的节点，相应在 DOM 树中删除之

整个过程是逐步找到更新前后 vdom 的差异，然后将差异反应到 DOM 树上（也就是 patch），特别要提一下 Vue 的 patch 是即时的，并不是打包所有修改最后一起操作 DOM（React 则是将更新放入队列后集中处理），朋友们会问这样做性能很差吧？实际上现代浏览器对这样的 DOM 操作做了优化，并无差别。

（二）逐步解析

（1）处理头部的同类型节点，即 oldStart 和 newStart 指向同类节点的情况，如下图中的节点 1

这种情况下，将节点 1 的变更更新到 DOM，然后对其进行标记，标记方法是 oldStart 和 newStart 后移 1 位即可，过程中不需要移动 DOM（更新 DOM 或许是要的，比如属性变更了，文本内容变更了等等）

（2）处理尾部的同类型节点，即 oldEnd 和 newEnd 指向同类节点的情况，如下图中的节点 10

与情况（1）类似，这种情况下，将节点 10 的变更更新到 DOM，然后 oldEnd 和 newEnd 前移 1 位进行标记，同样也不需要移动 DOM

（3）处理头尾/尾头的同类型节点，即 oldStart 和 newEnd，以及 oldEnd 和 newStart 指向同类节点的情况，如下图中的节点 2 和节点 9

先看节点 2，其实是往后移了，移到哪里？移到 oldEnd 指向的节点（即节点 9）后面，移动之后标记该节点，将 oldStart 后移 1 位，newEnd 前移一位

操作结束之后情况如下图

同样地，节点 9 也是类似的处理，处理完之后成了下面这样

（4）处理新增的节点

newStart 来到了节点 11 的位置，在 oldVdom 中找不到节点 11，说明它是新增的

那么就创建一个新的节点，插入 DOM 树，插到什么位置？插到 oldStart 指向的节点（即节点 3）前面，然后将 newStart 后移 1 位标记为已处理（注意 oldVdom 中没有节点 11，所以标记过程中它的指针不需要移动），处理之后如下图

（5）处理更新的节点

经过第（4）步之后，newStart 来到了节点 7 的位置，在 oldVdom 中能找到它而且不在指针位置（查找 oldVdom 中 oldStart 到 oldEnd 区间内的节点），说明它的位置移动了

那么需要在 DOM 树中移动它，移到哪里？移到 oldStart 指向的节点（即节点 3）前面，与此同时将节点标记为已处理，跟前面几种情况有点不同，newVdom 中该节点在指针下，可以移动 newStart 进行标记，而在 oldVdom 中该节点不在指针处，所以采用设置为 undefined 的方式来标记（一定要标记吗？后面会提到）

处理之后就成了下面这样

（6）处理 3、4、5、6 节点

经过第（5）步处理之后，我们看到了令人欣慰的一幕，newStart 和 oldStart 又指向了同一个节点（即都指向节点 3），很简单，按照（1）中的做法只需移动指针即可，非常高效，3、4、5、6 都如此处理，处理完之后如下图

（7）处理需删除的节点

经过前 6 步处理之后（实际上前 6 步是循环进行的），朋友们看 newStart 跨过了 newEnd，它们相遇啦！而这个时候，oldStart 和 oldEnd 还没有相遇，说明这 2 个指针之间的节点（包括它们指向的节点，即上图中的节点 7、节点 8）是此次更新中被删掉的节点。

OK，那我们在 DOM 树中将它们删除，再回到前面我们对节点 7 做了标记，为什么标记是必需的？标记的目的是告诉 Vue 它已经处理过了，是需要出现在新 DOM 中的节点，不要删除它，所以在这里只需删除节点 8。

在应用中也可能会遇到 oldVdom 的起止点相遇了，但是 newVdom 的起止点没有相遇的情况，这个时候需要对 newVdom 中的未处理节点进行处理，这类节点属于更新中被加入的节点，需要将他们插入到 DOM 树中。

至此，整个 diff 过程结束了

Vue 的 diff 算法与动态规划算法中的经典案例“计算 a 到 b 的最小编辑距离”看上去有些相似，实际完全不同，Vue 的 diff 相对来说轻量很多，感兴趣的朋友可以查阅相关资料进行了解。

好啦，感谢你的阅读，希望能帮助你理解 Vue 的 diff 算法，在阅读过程中遇到的问题也欢迎一起交流！

作者介绍：

汪玉林，高级工程师，增值产品部前端 Leader，目前团队负责手 Q 游戏中心、手 Q 游戏运营、手 Q 阅读等项目，有丰富的 Web 前端架构经验。

本文转载自公众号小时光茶舍（ID：gh_7322a0f167b5）。

原文链接：

https://mp.weixin.qq.com/s/pd0Mshl-f0aJ8C-1Vc95Zw