前言
明天咱们来聊聊 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
<div>
<p>a</p>
<p>b</p>
<p>c</p>
</div>转换成 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 哪些节点能够复用
只有标签类型与 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 的源码了……
整顿不易，如果有所帮忙的话，心愿能点赞关注，激励一下作者。
如果文章有不正确或存疑的中央，欢送评论指出。