聊聊|聊聊 Vue2 是如何更新节点的 | diff 算法详解聊聊Vue2是如何更新节点的|di

前言今天我们来聊聊 Vue2 的双端 diff 算法。
为什么要聊呢，最直白的原因就是面试会考，当面试官问你 key 的作用，十有八九都会引到 diff 算法。
没办法，面试问咱们就只能学，好在也不怎么难，跟着我一起看看吧。
篇幅原因，本文并不会介绍虚拟 DOM 树是如何生成的，仅讲解在数据更新时，是如何比较两颗虚拟 DOM 树并更新真实 DOM 的，主要实现 Vue2 源码中的 patchVnode、updateChildren 函数
预备知识 diff 算法作用
聊 diff 算法前得认识一下它是干嘛的。
我们知道在网页运行中，我们改变一些数据，它们可能会影响到 DOM 树。如何在页面中展示最新的数据呢，最简单的方式就是整棵树推到重建，当然这样会导致大量的浪费，所以 Vue 使用虚拟 DOM 保存页面中 DOM 树的状态，在数据变化后，构建一棵新的虚拟 DOM 树，找到前后两颗树的不同之处，针对性地更新真实 DOM。
而如何找到两颗树的不同之处，减少 DOM 元素的销毁与重建，就是 diff 算法的作用
虚拟 DOM
虚拟 DOM，又称虚拟节点(vnode)，简单来说就是包含 DOM 元素信息的对象，一般由 h 函数创建，下面这个对象就可以看成是一个虚拟节点

const vnode = { tag: 'div', // 标签类型 text: '', // 文本内容 children: undefined, // 子节点 }

对于这段 HTML

a b c

转换成 vnode 是这样的

const vnode = { tag: 'div', // 标签类型 text: undefined, // 文本内容 children: [ // 子节点 { tag: 'p', text: 'a', children: undefined, }, { tag: 'p', text: 'b', children: undefined, }, { tag: 'p', text: 'c', children: undefined, }, ], }

因为我们需要通过虚拟节点去操作真实 DOM，所以 vnode 身上有个 elm 属性指向真实的 DOM 元素。而且在之后的 diff 算法中，还会用到一个 key 来对节点进行唯一标识，所以下文中的 vnode 是这样的对象

const vnode = { tag: 'div', // 标签类型 text: '', // 文本内容 children: undefined, // 子节点 elm: undefined, // 对应的真实DOM key: '', // 唯一标识 }

Vue 的虚拟节点还有很多属性，不过与 diff 算法无关，就不列举了

说明一点，虚拟节点的 text 和 children 不会同时有值。在有 children 属性的情况下，text 中的内容会转化为一个文本节点置入 children 数组中

预备函数
为了使等会的代码实现更简单，我们准备几个函数，功能不难，直接贴代码了
我们首先需要就是一个将虚拟节点转换为真实 DOM 的函数

// 根据虚拟节点创建真实节点 function createElement(vnode) { const dom = document.createElement(vnode.tag) if (vnode.children) { // 包含子节点，递归创建 for (let i = 0; i < vnode.children.length; i++) { const childDom = createElement(vnode.children[i]) dom.appendChild(childDom) } } else { // 内部是文字 dom.innerHTML = vnode.text } // 补充elm属性 vnode.elm = dom return dom }

以及三个工具函数

// 判断是否未定义 function isUndef(v) { return v === undefined || v === null } // 判断是否已定义 function isDef(v) { return v !== undefined && v !== null } // 检查是否可复用 function checkSameVnode(a, b) { return a.tag === b.tag && a.key === b.key }

patchVnode 当数据更新后，Vue 创建出一棵新 vnode，然后执行 patchVnode 函数比较新老两个虚拟节点的不同之处，然后根据情况进行处理

function patchVnode(newVnode, oldVnode) {}

首先判断新旧两个虚拟节点是同一对象，如果是的话就不用处理

if (oldVnode === newVnode) return

然后将旧节点的 DOM 元素赋给新节点，并获取新旧节点的 children 属性

let elm = (newVnode.elm = oldVnode.elm) let oldCh = oldVnode.children let newCh = newVnode.children

这里可以直接赋值是因为调用 patchVnode 的新旧节点它们的 tag 与 key 是一定相同的，在下文会有讲解
然后根据两个节点内容，决定如何更新 DOM

新旧两个节点内容都是文本。修改文本即可

if (isUndef(oldCh) && isUndef(newCh)) { if (newVnode.text !== oldVnode.text) { elm.innerText = newVnode.text } }
旧节点有子节点，新节点内容是文本。清空旧节点内容，改为文本

if (isDef(oldCh) && isUndef(newCh)) { elm.innerHTML = newVnode.text }
旧节点内容是文本，新节点有子节点。清空旧节点内容，遍历新节点生成子 DOM 元素插入节点中

if (isUndef(oldCh) && isDef(newCh)) { elm.innerHTML = '' for (let i = 0, n = newCh.length; i < n; i++){ elm.appendChild(createElement(newCh[i])) } }
新旧节点都有子节点。调用 updateChildren 来处理，该函数在下一章讲解

if (isDef(oldCh) && isDef(newCh)) { updateChildren(elm, oldCh, newCh) }

情况 4 可以与情况 3 的处理一样，清空旧节点，然后遍历生成新 DOM。但是我们要知道，创建 DOM 元素是一件非常耗时的工作，而且新旧子节点在大多时候都是相同的，如果可以复用，将极大优化我们的性能。
那我们要如何判定一个节点是否可以复用呢？
这就需要 Vue 的使用者来帮忙了，使用者在节点上定义 key 属性，告诉 Vue 哪些节点可以复用
【聊聊|聊聊 Vue2 是如何更新节点的 | diff 算法详解】只要标签类型与 key 值都相等，就说明当前元素可以被复用
然而在我们的项目中，一般只有在 v-for 中才设置 key，其他节点都没设置 key
其实没有设置 key 的节点，它们的 key 值默认相等
事实也是如此，我们项目中大部分元素都可以复用，只有 v-for 生成的子元素，它依赖的数组可能发生一些较复杂的变化，所以才需要明确标注 key 值，以帮助 Vue 尽可能地复用节点。

patchVnode 的内容当然不止这些，还有样式、类名、props等数据的对比更换，篇幅原因本文将其省略了。

updateChildren 为什么采用双端 diff
好了，Vue 的使用者为每个节点的设置了 key，我们要如何从老节点中找到 key 相等的节点复用元素呢？
简单的方式就是穷举遍历，对于每个新节点的 key 遍历所有老节点，找到了就移动到首位，没找到就创建添加。
然而这明显有优化的空间，Vue 实现这部分功能时借鉴了 snabbdom 的双端 diff 算法，因为此算法将我们平时操作数组常见的 4 种情况抽离了出来，涵盖了我们业务中的大多数场景，将 O(n2) 的时间复杂度降到了 O(n)
接下来我们来学习这是如何实现的
函数实现
函数实现较为复杂，我直接把完整的代码放上来，再带领大家一段段解读

// 三个参数为：父DOM元素，旧的子节点数组，新的子节点数组 function updateChildren(parentElm, oldCh, newCh) { // 旧前索引 let oldStartIdx = 0 // 新前索引 let newStartIdx = 0 // 旧后索引 let oldEndIdx = oldCh.length - 1 // 新后索引 let newEndIdx = newCh.length - 1 // 四个索引对应节点 let oldStartVnode = oldCh[0] let newStartVnode = newCh[0] let oldEndVnode = oldCh[oldEndIdx] let newEndVnode = newCh[newEndIdx]let keyMap// 开始循环 while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) { // 跳过空节点 (和最后一种情况有关) if (isUndef(oldStartVnode)) { oldStartVnode = oldCh[++oldStartIdx] } else if (isUndef(oldEndVnode)) { oldEndVnode = oldCh[--oldEndIdx] } else if (checkSameVnode(oldStartVnode, newStartVnode)) { // 情况1 // 旧前和新前相等，不需要移动 patchVnode(newStartVnode, oldStartVnode) oldStartVnode = oldCh[++oldStartIdx] newStartVnode = newCh[++newStartIdx] } else if (checkSameVnode(oldEndVnode, newEndVnode)) { // 情况2 // 旧后和新后相等，也不需要移动 patchVnode(newEndVnode, oldEndVnode) oldEndVnode = oldCh[--oldEndIdx] newEndVnode = newCh[--newEndIdx] } else if (checkSameVnode(oldStartVnode, newEndVnode)) { // 情况3 // 旧前和新后相等 // 旧序列的第一个节点，变成了新序列的最后一个节点 // 需要将这个节点移动到旧序列最后一个节点的后面 // 也就是最后一个节点的下一个节点的前面 parentElm.insertBefore(oldStartVnode.elm, oldEndVnode.elm.nextSibling) patchVnode(newEndVnode, oldStartVnode) oldStartVnode = oldCh[++oldStartIdx] newEndVnode = newCh[--newEndIdx] } else if (checkSameVnode(oldEndVnode, newStartVnode)) { // 情况4 // 旧后和新前相等 // 旧序列的最后一个节点，变成了新序列的第一个节点 // 需要将这个节点移动到旧序列第一个节点的前面 parentElm.insertBefore(oldEndVnode.elm, oldStartVnode.elm) patchVnode(newStartVnode, oldEndVnode) oldEndVnode = oldCh[--oldEndIdx] newStartVnode = newCh[++newStartIdx] } else { // 以上四种情况都不符合 // 制作旧节点key的映射对象 // 键为 key，值为索引 if (!keyMap) { keyMap = {} for (let i = oldStartIdx; i <= oldEndIdx; i++) { keyMap[oldCh[i].key] = i } } // 寻找当前新节点在keyMap中映射的位置序号 const idxInOld = keyMap[newStartVnode.key] if (isUndef(idxInOld)) { // 没有找到，表示他是全新的项 // 转化为DOM节点，加入旧序列第一个节点的前面 parentElm.insertBefore(createElement(newStartVnode), oldStartVnode.elm) } else { // 不是全新的项，需要移动 const oldVnode = oldCh[idxInOld] // 移动到旧序列第一个节点之前 parentElm.insertBefore(oldVnode.elm, oldStartVnode.elm) patchVnode(oldVnode, newStartVnode) // 把这项设置成空，循环时遇到时跳过 oldCh[idxInOld] = undefined } // 当前新节点处理完毕，下一轮循环处理下一个新节点 newStartVnode = newCh[++newStartIdx] } }// 循环结束了，start还是比end小，说明有节点没有处理到 if (newStartIdx <= newEndIdx) { // 新节点没有处理到，则创建按DOM添加到新序列最后一个节点的前面 for (let i = newStartIdx; i <= newEndIdx; i++) { // insertBefore方法传入null则添加到队尾 const before = newCh[newEndIdx + 1]?.elm || null parentElm.insertBefore(createElement(newCh[i]), before) } } else if (oldStartIdx <= oldEndIdx) { // 旧节点没有处理到，删除 for (let i = oldStartIdx; i <= oldEndIdx; i++) { parentElm.removeChild(oldCh[i].elm) } } }

代码注释中及下文的新/旧序列，仅包含从新/旧开始索引到结束索引间的节点，也就是还未处理的节点序列，而不是整个子节点数组。

根据例子讲解
我们以下图的例子，来讲解这个函数的运行流程（方框中的内容为子节点的 key，所有节点标签相同）
首先定义了 8 个变量，表示新旧序列的开始和结束位置的索引与节点

文章图片

然后开始循环，初始时节点都不为空
第一次循环命中情况 1，旧前与新前(key)相等
这表示旧序列的第一个节点到新序列仍是第一个节点，也就不需要移动，但还需要比较一下节点的内容有没有改变(patchVnode)，并且让新旧开始索引都前进一步

// 比较节点的数据及子节点，并且将旧节点的DOM赋给新节点 patchVnode(newStartVnode, oldStartVnode) oldStartVnode = oldCh[++oldStartIdx] newStartVnode = newCh[++newStartIdx]

文章图片

情况 1 是业务中最常见的，表示从前至后两两比较。一般把商品添加到购物车末尾，或是没有设置 key 值的子节点，都是依靠情况 1 把可复用的节点筛选完毕。
第二次循环命中情况 2，旧后和新后相等
这表示序列的末尾节点到新序列仍是末尾节点，也不需要移动，然后让新旧结束索引都后退一步

patchVnode(newEndVnode, oldEndVnode) oldEndVnode = oldCh[--oldEndIdx] newEndVnode = newCh[--newEndIdx]

文章图片

情况 2 是情况 1 的补充，表示从后向前两两比较。有时会把新发布的评论插到开头，或者从购物车删除了一些商品，这时仅依靠情况 1 就无法迅速的筛选可复用节点，所以需要从后向前比较来配合。
第三次循环命中情况 3，旧前和新后相等
这表示旧序列的第一个节点，变成了新序列的最后一个节点。需要将这个节点移动到序列的末尾，也就是旧序列末尾节点的下一个节点(节点 e)的前面

parentElm.insertBefore(oldStartVnode.elm, oldEndVnode.elm.nextSibling)

文章图片

然后比较新旧节点，修改索引

patchVnode(newEndVnode, oldStartVnode) oldStartVnode = oldCh[++oldStartIdx] newEndVnode = newCh[--newEndIdx]

文章图片

情况 3 主要处理数组反转的情况，比如升序改降序，每个起始节点被移动到了末尾的位置，使用此情况将它们重新排序。
第四次循环命中情况 4，旧后与新前相等
这表示旧序列的最后一个节点，变成了新序列的第一个节点。需要将这个节点移动到序列的开头，也就是旧序列开始节点（节点 c）的前面

parentElm.insertBefore(oldStartVnode.elm, oldEndVnode.elm.nextSibling)

文章图片

到这里说一下，图上标注的是节点 a 的后面，是因为节点 b 被移动到了末尾
节点的移动都是根据旧节点来定位的，如果想把一个节点放到序列的开头，就放到旧序列开始节点的前面；如果想把一个节点放到序列的末尾，就要放到旧序列结束节点的下一个节点的前面
然后也是比较新旧节点，修改索引，之后是下图情况

patchVnode(newStartVnode, oldEndVnode) oldEndVnode = oldCh[--oldEndIdx] newStartVnode = newCh[++newStartIdx]

文章图片

情况 4 是情况 3 的补充，避免反转数组后又插入/删除了节点导致情况 3 无法匹配，本例就是这个情况。
第五次循环，4 种情况均为未命中
很遗憾，无法迅速锁定节点的位置，只能用传统的方式进行遍历
我们这里选择了以空间换时间的方式，定义了 keyMap，将旧序列节点的 key 与索引存起来，然后使用新开始节点的 key 去查找。
如果没找到，说明这是一个新节点，创建节点并放到开头，也就是插入到旧序列开始节点的前面
但如果找到了，则同样移动节点到序列开头，然后将对应的旧节点索引置空，在以后循环遇到空的旧节点就跳过了
本例中是未找到的情况，此节点处理完毕，新开始索引加一，超过了新结束索引，不满足循环条件，退出循环

文章图片

然而，节点 c 并没有被处理，此时的 DOM 序列为：a,d,f,c,b,e
所以在循环之后，要检测是否有未处理的节点，如果是旧节点未处理，删除即可；
如果是新节点未处理，则创建新节点插入到旧序列的末尾或者旧序列的开头，二者其实是一个位置
我们假设旧节点中没有 c，则在第四次循环后就会出现以下情况（第四次循环命中的是情况 1）

文章图片

如果把 f 放到序列的开头，就是旧开始节点（节点 e）的前面
而如果把 f 放到序列的末尾，也就是旧结束节点的下一个节点（节点 e）的前面
此时旧序列就是一个点，不分开头和结尾，只要保证新增节点序列按序添加就好了
至此，双端 diff 算法就讲完了
Vue 中的 key 学完 diff 算法，再聊聊 key 的作用
v-for 中的 key
上面讲的都是有 key 情况下，diff 算法能够迅速找到新旧序列中的同一节点，以较小的代价完成更新。
而如果在 v-for 中不设置 key 呢？
假设我们在数组头部插入了一个新节点，然后开始循环，每次循环都命中情况 1，尝试“复用”此节点。
但是，在对比新旧节点的内容时，都会发现内容不同，需要用新节点的内容替换旧节点。这只是复用了 DOM 的外壳，节点的内容、数据以及该节点的子节点全都要更改。
相比有 key 时的只添加一个新节点，无 key 则将所有节点都修改一遍。
v-if 自带 key
v-for 以外的元素我们一般是不设置 key 的，但是如果子元素中有 v-if 的话，就像下面这个场景（abcd是内容，并不是 key），更新子元素又会复现上一节的情况。

文章图片

然而 Vue 官方也考虑到了这点，会为 v-if 的元素加上利用 hash 函数生成的唯一 key

// 以下出自 v2 源码 var needsKey = !!el.if …… needsKey ? ',null,false,' + hash(generatedSlots) : ''

key 的另一个用法
顺便再提一嘴，key 可以绑到任意元素上，当 key 发生变化时，会导致 DOM 的销毁与重建，一般用来重复触发动画或生命周期钩子。
详情可看官方链接
结语不记得这是第几次梳理双端 diff 的逻辑了，很早之前就已经拥抱 v3 了，把 v2 的响应式原理和 diff 算法总结一遍也算是给 v2 画上句号了。
没想到这篇文章写了 4000 多字，为此还特意去翻看了 v2 的源码。本文的代码和 v2 差别还是蛮大的，主要参考的是 snabbdom 和以前的教程，加了点自己的风格将 patchVnode 和 updateChildren 实现了一遍。
接下来就能心无旁骛地看 v3 的源码了……
整理不易，如果有所帮助的话，希望能点赞关注，鼓励一下作者。
如果文章有不正确或存疑的地方，欢迎评论指出。