这一节，仍然是深刻分析Vue源码系列，上几节内容介绍了Virtual DOM是Vue在渲染机制上做的优化，而渲染的外围在于数据变动时，如何高效的更新节点，这就是diff算法。因为源码中对于diff算法局部流程简单，间接分析每个流程不易于了解，所以这一节咱们换一个思路，参考源码来手动实现一个简易版的diff算法。
之前讲到Vue在渲染机制的优化上，引入了Virtual DOM的概念，利用Virtual DOM形容一个实在的DOM,实质上是在JS和实在DOM之间架起了一层缓冲层。当咱们通过大量的JS运算,并将最终后果反馈到浏览器进行渲染时，Virtual DOM能够将多个改变合并成一个批量的操作，从而缩小 dom 重排的次数，进而缩短了生成渲染树和绘制节点所花的工夫，达到渲染优化的目标。之前的章节，咱们简略的介绍了Vue中Vnode的概念，以及创立Vnode到渲染Vnode再到实在DOM的过程。如果有遗记流程的，能够参考后面的章节剖析。
从render函数到创立虚构DOM,再到渲染实在节点，这一过程是残缺的，也是容易了解的。然而引入虚构DOM的外围不在这里，而在于当数据发生变化时，如何最优化数据变动到视图更新的过程。这一个过程才是Vnode更新视图的外围，也就是常说的diff算法。上面跟着我来实现一个简易版的diff算法
8.1 创立根底类
代码编写过程会遇到很多根本类型的判断，第一步须要先将这些办法封装。
class Util { constructor() {} // 检测根底类型 _isPrimitive(value) { return (typeof value === 'string' || typeof value === 'number' || typeof value === 'symbol' || typeof value === 'boolean') } // 判断值不为空 _isDef(v) { return v !== undefined && v !== null }}// 工具类的应用const util = new Util()8.2 创立Vnode
Vnode这个类在之前章节曾经剖析过源码，实质上是用一个对象去形容一个实在的DOM元素，简易版关注点在于元素的tag标签，元素的属性汇合data,元素的子节点children,text为元素的文本节点,简略的形容类如下：
class VNode { constructor(tag, data, children) { this.tag = tag; this.data = data; this.children = children; this.elm = '' // text属性用于标记Vnode节点没有其余子节点，只有纯文本 this.text = util._isPrimitive(this.children) ? this.children : '' }}8.3 模仿渲染过程
接下来须要创立另一个类模仿将render函数转换为Vnode,并将Vnode渲染为实在DOM的过程，咱们将这个类定义为Vn,Vn具备两个根本的办法createVnode, createElement, 别离实现创立虚构Vnode,和创立实在DOM的过程。
8.3.1 createVnode
createVnode模仿Vue中render函数的实现思路，目标是将数据转换为虚构的Vnode,先看具体的应用和定义。
// index.html<script src="diff.js"><script>// 创立Vnodelet createVnode = function() { let _c = vn.createVnode; return _c('div', { attrs: { id: 'test' } }, arr.map(a => _c(a.tag, {}, a.text)))}// 元素内容构造let arr = [{ tag: 'i', text: 2 }, { tag: 'span', text: 3 }, { tag: 'strong', text: 4 }]</script>// diff.js(function(global) { class Vn { constructor() {} // 创立虚构Vnode createVnode(tag, data, children) { return new VNode(tag, data, children) } } global.vn = new Vn()}(this))这是一个残缺的Vnode对象，咱们曾经能够用这个对象来简略的形容一个DOM节点，而createElement就是将这个对象对应到实在节点的过程。最终咱们心愿的后果是这样的。
Vnode对象
渲染后果
8.3.2 createElement
渲染实在DOM的过程就是遍历Vnode对象，递归创立实在节点的过程，这个不是本文的重点，所以咱们能够毛糙的实现。
class Vn { createElement(vnode, options) { let el = options.el; if(!el || !document.querySelector(el)) return console.error('无奈找到根节点') let _createElement = vnode => { const { tag, data, children } = vnode; const ele = document.createElement(tag); // 增加属性 this.setAttr(ele, data); // 简略的文本节点，只有创立文本节点即可 if (util._isPrimitive(children)) { const testEle = document.createTextNode(children); ele.appendChild(testEle) } else { // 简单的子节点须要遍历子节点递归创立节点。 children.map(c => ele.appendChild(_createElement(c))) } return ele } document.querySelector(el).appendChild(_createElement(vnode)) }}8.3.3 setAttr
setAttr是为节点设置属性的办法，利用DOM原生的setAttribute为每个节点设置属性值。
class Vn { setAttr(el, data) { if (!el) return const attrs = data.attrs; if (!attrs) return; Object.keys(attrs).forEach(a => { el.setAttribute(a, attrs[a]); }) }}至此一个简略的 数据 -> Virtual DOM => 实在DOM的模型搭建胜利,这也是数据变动、比拟、更新的根底。
8.4 diff算法实现
更新组件的过程首先是响应式数据产生了变动,数据频繁的批改如果间接渲染到实在DOM上会引起整个DOM树的重绘和重排，频繁的重绘和重排是极其耗费性能的。如何优化这一渲染过程，Vue源码中给出了两个具体的思路，其中一个是在介绍响应式零碎时提到的将屡次批改推到一个队列中，在下一个tick去执行视图更新，另一个就是接下来要着重介绍的diff算法，将须要批改的数据进行比拟，并只渲染必要的DOM。
数据的扭转最终会导致节点的扭转，所以diff算法的外围在于在尽可能小变动的前提下找到须要更新的节点，间接调用原生相干DOM办法批改视图。不论是实在DOM还是后面创立的Virtual DOM,都能够了解为一颗DOM树，算法比拟节点不同时，只会进行同层节点的比拟，不会跨层进行比拟，这也大大减少了算法复杂度。
参考Vue3源码视频解说：进入学习
8.4.1 diffVnode
在之前的根底上，咱们实现一个思路，1秒之后数据产生扭转。
// index.htmlsetTimeout(function() { arr = [{ tag: 'span', text: 1 },{ tag: 'strong', text: 2 },{ tag: 'i', text: 3 },{ tag: 'i', text: 4 }] // newVnode 示意扭转后新的Vnode树 const newVnode = createVnode(); // diffVnode会比拟新旧Vnode树，并实现视图更新 vn.diffVnode(newVnode, preVnode);})diffVnode的逻辑，会比照新旧节点的不同，并实现视图渲染更新
class Vn { ··· diffVnode(nVnode, oVnode) { if (!this._sameVnode(nVnode, oVnode)) { // 间接更新根节点及所有子节点 return *** } this.generateElm(vonde); this.patchVnode(nVnode, oVnode); }}8.4.2 _sameVnode
新旧节点的比照是算法的第一步，如果新旧节点的根节点不是同一个节点，则间接替换节点。这听从下面提到的准则，只进行同层节点的比拟，节点不统一，间接用新节点及其子节点替换旧节点。为了了解不便，咱们假设节点雷同的判断是tag标签是否统一(理论源码要简单)。
class Vn { _sameVnode(n, o) { return n.tag === o.tag; }}8.4.3 generateElm
generateElm的作用是跟踪每个节点理论的实在节点，不便在比照虚构节点后实时更新实在DOM节点。尽管Vue源码中做法不同，然而这不是剖析diff的重点。
class Vn { generateElm(vnode) { const traverseTree = (v, parentEl) => { let children = v.children; if(Array.isArray(children)) { children.forEach((c, i) => { c.elm = parentEl.childNodes[i]; traverseTree(c, c.elm) }) } } traverseTree(vnode, this.el); }}执行generateElm办法后，咱们能够在旧节点的Vnode中跟踪到每个Virtual DOM的实在节点信息。
8.4.4 patchVnode
patchVnode是新旧Vnode比照的外围办法，比照的逻辑如下。
- 节点雷同，且节点除了领有文本节点外没有其余子节点。这种状况下间接替换文本内容。
- 新节点没有子节点，旧节点有子节点，则删除旧节点所有子节点。
- 旧节点没有子节点，新节点有子节点，则用新的所有子节点去更新旧节点。
- 新旧都存在子节点。则比照子节点内容做操作。
代码逻辑如下：
class Vn { patchVnode(nVnode, oVnode) { if(nVnode.text && nVnode.text !== oVnode) { // 以后实在dom元素 let ele = oVnode.elm // 子节点为文本节点 ele.textContent = nVnode.text; } else { const oldCh = oVnode.children; const newCh = nVnode.children; // 新旧节点都存在。比照子节点 if (util._isDef(oldCh) && util._isDef(newCh)) { this.updateChildren(ele, newCh, oldCh) } else if (util._isDef(oldCh)) { // 新节点没有子节点 } else { // 老节点没有子节点 } } }}上述例子在patchVnode过程中，新旧子节点都存在，所以会走updateChildren分支。
8.4.5 updateChildren
子节点的比照，咱们通过文字和画图的模式剖析，通过图解的模式能够很清晰看到diff算法的奇妙之处。
大抵逻辑是：
- 旧节点的起始地位为
oldStartIndex,截至地位为oldEndIndex,新节点的起始地位为newStartIndex,截至地位为newEndIndex。 - 新旧
children的起始地位的元素两两比照，程序是newStartVnode, oldStartVnode;newEndVnode, oldEndVnode;newEndVnode, oldStartVnode;newStartIndex, oldEndIndex newStartVnode, oldStartVnode节点雷同，执行一次patchVnode过程，也就是递归比照相应子节点，并替换节点的过程。oldStartIndex，newStartIndex都像右挪动一位。newEndVnode, oldEndVnode节点雷同，执行一次patchVnode过程，递归比照相应子节点，并替换节点。oldEndIndex， newEndIndex都像左挪动一位。newEndVnode, oldStartVnode节点雷同，执行一次patchVnode过程，并将旧的oldStartVnode挪动到尾部,oldStartIndex右移一味，newEndIndex左移一位。newStartIndex, oldEndIndex节点雷同，执行一次patchVnode过程，并将旧的oldEndVnode挪动到头部,oldEndIndex左移一味，newStartIndex右移一位。- 四种组合都不雷同，则会搜寻旧节点所有子节点，找到将这个旧节点和
newStartVnode执行patchVnode过程。 - 一直比照的过程使得
oldStartIndex一直迫近oldEndIndex，newStartIndex一直迫近newEndIndex。当oldEndIndex <= oldStartIndex阐明旧节点曾经遍历完了，此时只有批量减少新节点即可。当newEndIndex <= newStartIndex阐明旧节点还有剩下，此时只有批量删除旧节点即可。
联合后面的例子：
第一步：
第二步：
第三步：
第三步：
第四步：
依据这些步骤，代码实现如下：
class Vn { updateChildren(el, newCh, oldCh) { // 新children开始标记 let newStartIndex = 0; // 旧children开始标记 let oldStartIndex = 0; // 新children完结标记 let newEndIndex = newCh.length - 1; // 旧children完结标记 let oldEndIndex = oldCh.length - 1; let oldKeyToId; let idxInOld; let newStartVnode = newCh[newStartIndex]; let oldStartVnode = oldCh[oldStartIndex]; let newEndVnode = newCh[newEndIndex]; let oldEndVnode = oldCh[oldEndIndex]; // 遍历完结条件 while (newStartIndex <= newEndIndex && oldStartIndex <= oldEndIndex) { // 新children开始节点和旧开始节点雷同 if (this._sameVnode(newStartVnode, oldStartVnode)) { this.patchVnode(newCh[newStartIndex], oldCh[oldStartIndex]); newStartVnode = newCh[++newStartIndex]; oldStartVnode = oldCh[++oldStartIndex] } else if (this._sameVnode(newEndVnode, oldEndVnode)) { // 新childre完结节点和旧完结节点雷同 this.patchVnode(newCh[newEndIndex], oldCh[oldEndIndex]) oldEndVnode = oldCh[--oldEndIndex]; newEndVnode = newCh[--newEndIndex] } else if (this._sameVnode(newEndVnode, oldStartVnode)) { // 新childre完结节点和旧开始节点雷同 this.patchVnode(newCh[newEndIndex], oldCh[oldStartIndex]) // 旧的oldStartVnode挪动到尾部 el.insertBefore(oldCh[oldStartIndex].elm, null); oldStartVnode = oldCh[++oldStartIndex]; newEndVnode = newCh[--newEndIndex]; } else if (this._sameVnode(newStartVnode, oldEndVnode)) { // 新children开始节点和旧完结节点雷同 this.patchVnode(newCh[newStartIndex], oldCh[oldEndIndex]); el.insertBefore(oldCh[oldEndIndex].elm, oldCh[oldStartIndex].elm); oldEndVnode = oldCh[--oldEndIndex]; newStartVnode = newCh[++newStartIndex]; } else { // 都不合乎的解决，查找新节点中与比照旧节点雷同的vnode this.findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx); } } // 新节点比旧节点多，批量减少节点 if(oldEndIndex <= oldStartIndex) { for (let i = newStartIndex; i <= newEndIndex; i++) { // 批量减少节点 this.createElm(oldCh[oldEndIndex].elm, newCh[i]) } } } createElm(el, vnode) { let tag = vnode.tag; const ele = document.createElement(tag); this._setAttrs(ele, vnode.data); const testEle = document.createTextNode(vnode.children); ele.appendChild(testEle) el.parentNode.insertBefore(ele, el.nextSibling) } // 查找匹配值 findIdxInOld(newStartVnode, oldCh, start, end) { for (var i = start; i < end; i++) { var c = oldCh[i]; if (util.isDef(c) && this.sameVnode(newStartVnode, c)) { return i } } }}8.5 diff算法优化
后面有个分支，当四种比拟节点都找不到匹配时，会调用findIdxInOld找到旧节点中和新的比拟节点统一的节点。节点搜寻在数量级较大时是迟缓的。查看Vue的源码，发现它在这一个环节做了优化，也就是咱们常常在编写列表时被要求退出的惟一属性key，有了这个惟一的标记位，咱们能够对旧节点建设简略的字典查问，只有有key值便能够不便的搜寻到符合要求的旧节点。批改代码：
class Vn { updateChildren() { ··· } else { // 都不合乎的解决，查找新节点中与比照旧节点雷同的vnode if (!oldKeyToId) oldKeyToId = this.createKeyMap(oldCh, oldStartIndex, oldEndIndex); idxInOld = util._isDef(newStartVnode.key) ? oldKeyToId[newStartVnode.key] : this.findIdxInOld(newStartVnode, oldCh, oldStartIndex, oldEndIndex); // 后续操作 } } // 建设字典 createKeyMap(oldCh, start, old) { const map = {}; for(let i = start; i < old; i++) { if(oldCh.key) map[key] = i; } return map; }}8.6 问题思考
最初咱们思考一个问题，Virtual DOM 的重绘性能真的比单纯的innerHTML要好吗，其实并不是这样的，作者的解释
innerHTML: render html string O(template size) +从新创立所有DOM元素O(DOM size)Virtual DOM: render Virtual DOM + diff O(template size) +必要的DOM更新O(DOM change)Virtual DOM render + diff显然比渲染 html 字符串要慢，然而！它仍然是纯 js 层面的计算，比起前面的DOM操作来说，仍然便宜了太多。能够看到，innerHTML的总计算量不论是js计算还是DOM操作都是和整个界面的大小相干，但Virtual DOM的计算量外面，只有js计算和界面大小相干，DOM 操作是和数据的变动量相干的。