写作不易，未经作者容许禁止以任何模式转载！
如果感觉文章不错，欢送关注、点赞和分享！
博客原文链接：Vue进阶 Diff算法详解
一、虚构DOM
什么是虚构DOM？
虚构DOM就是把实在DOM树的构造和信息形象进去，以对象的模式模仿树形构造，如下：
实在DOM:
<div> <p>Hello World</p></div>对应的虚构DOM就是：
let vnode = { tag: 'div', children:[ {tag:'p', text:'Hello World'}]}为什么须要虚构DOM？
渲染实在DOM会有肯定的开销，如果每次批改数据都进行实在DOM渲染，都会引起DOM树的重绘和重排，性能开销很大。那么有没有可能只批改一小部分数据而不渲染整个DOM呢？虚构DOM和Diff算法能够实现。
怎么实现？
- 先依据实在DOM生成一颗虚构DOM树
- 当某个DOM节点数据产生扭转时，生成一个新的Vnode
- 新的Vnode和旧的oldVnode进行比照
- 通过patch函数一边比对一边给实在DOM打补丁或者创立Vnode、移除oldVnode等
有什么不一样？
- 实在DOM操作为一个属性一个属性去批改，开销较大。
- 虚构DOM间接批改整个DOM节点再替换实在DOM
还有什么益处？
Vue的虚构DOM数据更新机制是异步更新队列，并不是数据变更马上更新DOM，而是被推动一个数据更新异步队列对立更新。想要马上拿到DOM更新后DOM信息？有个API叫 Vue.nextTick
二、 Diff算法
传统Diff算法
遍历两棵树中的每一个节点，每两个节点之间都要做一次比拟。
比方 a->e 、a->d 、a->b、a->c、a->a
- 遍历实现的工夫复杂度达到了O(n^2)
- 比照完差别后还要计算最小转换形式，实现后复杂度来到了O(n^3)
Vue优化的Diff算法
Vue的diff算法只会比拟同层级的元素，不进行跨层级比拟
三、 Vue中的Diff算法实现
Vnode分类
- EmptyVNode: 没有内容的正文节点
- TextVNode: 文本节点
- ElementVNode: 一般元素节点
- ComponentVNode: 组件节点
- CloneVNode: 克隆节点，能够是以上任意类型的节点，惟一的区别在于isCloned属性为true
Patch函数
patch函数接管以下参数：
- oldVnode：旧的虚构节点
- Vnode：新的虚构节点
- hydrating：是否要和实在DOM混合
- removeOnly：非凡的flag，用于 transition-group
解决流程大抵分为以下步骤：
- vnode不存在，oldVnode存在时，移除oldVnode
- vnode存在，oldVnode不存在时，创立vnode
vnode和oldVnode都存在时
- 如果vnode和oldVnode是同一个节点（通过sameVnode函数比照 后续详解），通过patchVnode进行后续比对工作
- 如果vnode和oldVnode不是同一个节点，那么依据vnode创立新的元素并挂载至oldVnode父元素下。如果组件根节点被替换，遍历更新父节点element。而后移除旧节点。如果oldVnode是服务端渲染元素节点，须要用hydrate函数将虚构dom和真是dom进行映射
源码如下，已写好正文便于浏览
return function patch(oldVnode, vnode, hydrating, removeOnly) { // 如果vnode不存在，然而oldVnode存在，移除oldVnode if (isUndef(vnode)) { if (isDef(oldVnode)) invokeDestroyHook(oldVnode) return } let isInitialPatch = false const insertedVnodeQueue = [] // 如果oldVnode不存在，然而vnode存在时，创立vnode if (isUndef(oldVnode)) { isInitialPatch = true createElm(vnode, insertedVnodeQueue) } else { // 残余状况为vnode和oldVnode都存在 // 判断是否为实在DOM元素 const isRealElement = isDef(oldVnode.nodeType) if (!isRealElement && sameVnode(oldVnode, vnode)) { // 如果vnode和oldVnode是同一个（通过sameVnode函数进行比对 后续详解） // 受用patchVnode函数进行后续比对工作 （函数后续详解） patchVnode(oldVnode, vnode, insertedVnodeQueue, removeOnly) } else { // vnode和oldVnode不是同一个的状况 if (isRealElement) { // 如果存在实在的节点，存在data-server-render属性 if (oldVnode.nodeType === 1 && oldVnode.hasAttribute(SSR_ATTR)) { // 当旧的Vnode是服务端渲染元素，hydrating记为true oldVnode.removeAttribute(SSR_ATTR) hydrating = true } // 须要用hydrate函数将虚构DOM和实在DOM进行映射 if (isTrue(hydrating)) { // 须要合并到实在DOM上 if (hydrate(oldVnode, vnode, insertedVnodeQueue)) { // 调用insert钩子 invokeInsertHook(vnode, insertedVnodeQueue, true) return oldVnode } else if (process.env.NODE_ENV !== 'production') { warn( 'The client-side rendered virtual DOM tree is not matching ' + 'server-rendered content. This is likely caused by incorrect ' + 'HTML markup, for example nesting block-level elements inside ' + '<p>, or missing <tbody>. Bailing hydration and performing ' + 'full client-side render.' ) } } // 如果不是服务端渲染元素或者合并到实在DOM失败，则创立一个空的Vnode节点去替换它 oldVnode = emptyNodeAt(oldVnode) } // 获取oldVnode父节点 const oldElm = oldVnode.elm const parentElm = nodeOps.parentNode(oldElm) // 依据vnode创立一个实在DOM节点并挂载至oldVnode的父节点下 createElm( vnode, insertedVnodeQueue, oldElm._leaveCb ? null : parentElm, nodeOps.nextSibling(oldElm) ) // 如果组件根节点被替换，遍历更新父节点Element if (isDef(vnode.parent)) { let ancestor = vnode.parent const patchable = isPatchable(vnode) while (ancestor) { for (let i = 0; i < cbs.destroy.length; ++i) { cbs.destroy[i](ancestor) } ancestor.elm = vnode.elm if (patchable) { for (let i = 0; i < cbs.create.length; ++i) { cbs.create[i](emptyNode, ancestor) } // #6513 // invoke insert hooks that may have been merged by create hooks. // e.g. for directives that uses the "inserted" hook. const insert = ancestor.data.hook.insert if (insert.merged) { // start at index 1 to avoid re-invoking component mounted hook for (let i = 1; i < insert.fns.length; i++) { insert.fns[i]() } } } else { registerRef(ancestor) } ancestor = ancestor.parent } } // 销毁旧节点 if (isDef(parentElm)) { // 移除老节点 removeVnodes(parentElm, [oldVnode], 0, 0) } else if (isDef(oldVnode.tag)) { // 调用destroy钩子 invokeDestroyHook(oldVnode) } } } // 调用insert钩子并返回节点 invokeInsertHook(vnode, insertedVnodeQueue, isInitialPatch) return vnode.elm }sameVnode函数
Vue怎么判断是不是同一个节点？流程如下：
- 判断Key值是否一样
- tag的值是否一样
- isComment，这个不必太关注。
- 数据一样
- sameInputType()，专门对表单输出项进行判断的：input一样然而外面的type不一样算不同的inputType
从这里能够看出key对diff算法的辅助作用，能够疾速定位是否为同一个元素，必须保障唯一性。
如果你用的是index作为key，每次打乱程序key都会扭转，导致这种判断生效，升高了Diff的效率。
因而，用好key也是Vue性能优化的一种形式。
- 源码如下：
function sameVnode(a, b) { return ( a.key === b.key && ( ( a.tag === b.tag && a.isComment === b.isComment && isDef(a.data) === isDef(b.data) && sameInputType(a, b) ) || ( isTrue(a.isAsyncPlaceholder) && a.asyncFactory === b.asyncFactory && isUndef(b.asyncFactory.error) ) ) )}patchVnode函数
前置条件vnode和oldVnode是同一个节点
执行流程：
- 如果oldVnode和vnode援用统一，能够认为没有变动，return
- 如果oldVnode的isAsyncPlaceholder属性为true，跳过查看异步组件，return
- 如果oldVnode跟vnode都是动态节点，且具备雷同的key，同时vnode是克隆节点或者v-once指令管制的节点时，只须要把oldVnode.elm和oldVnode.child都复制到vnode上，也不必再有其余操作，return
如果vnode不是文本节或正文节点
- 如果vnode和oldVnode都有子节点并且两者子节点不统一时，就调用updateChildren更新子节点
- 如果只有vnode有自子节点，则调用addVnodes创立子节点
- 如果只有oldVnode有子节点，则调用removeVnodes把这些子节点都删除
- 如果vnode文本为undefined，则清空vnode.elm文本
- 如果vnode是文本节点然而和oldVnode文本内容不同，只需更新文本。
源代码如下，已写好正文便于浏览
function patchVnode(oldVnode, vnode, insertedVnodeQueue, removeOnly) { // 如果新老节点援用统一，间接返回。 if (oldVnode === vnode) { return } const elm = vnode.elm = oldVnode.elm // 如果oldVnode的isAsyncPlaceholder属性为true，跳过查看异步组件 if (isTrue(oldVnode.isAsyncPlaceholder)) { if (isDef(vnode.asyncFactory.resolved)) { hydrate(oldVnode.elm, vnode, insertedVnodeQueue) } else { vnode.isAsyncPlaceholder = true } return } // 如果新旧都是动态节点，vnode的key也雷同 // 新vnode是克隆所得或新vnode有 v-once属性 // 则进行赋值，而后返回。vnode的componentInstance 放弃不变 if (isTrue(vnode.isStatic) && isTrue(oldVnode.isStatic) && vnode.key === oldVnode.key && (isTrue(vnode.isCloned) || isTrue(vnode.isOnce)) ) { vnode.componentInstance = oldVnode.componentInstance return } let i const data = vnode.data // 执行data.hook.prepatch 钩子 if (isDef(data) && isDef(i = data.hook) && isDef(i = i.prepatch)) { i(oldVnode, vnode) } // 获取子元素列表 const oldCh = oldVnode.children const ch = vnode.children if (isDef(data) && isPatchable(vnode)) { // 遍历调用 cbs.update 钩子函数，更新oldVnode所有属性 // 包含attrs、class、domProps、events、style、ref、directives for (i = 0; i < cbs.update.length; ++i) cbs.update[i](oldVnode, vnode) // 执行data.hook.update 钩子 if (isDef(i = data.hook) && isDef(i = i.update)) i(oldVnode, vnode) } // Vnode 的 text选项为undefined if (isUndef(vnode.text)) { if (isDef(oldCh) && isDef(ch)) { //新老节点的children不同，执行updateChildren办法 if (oldCh !== ch) updateChildren(elm, oldCh, ch, insertedVnodeQueue, removeOnly) } else if (isDef(ch)) { // oldVnode children不存在 执行 addVnodes办法 if (isDef(oldVnode.text)) nodeOps.setTextContent(elm, '') addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue) } else if (isDef(oldCh)) { // vnode不存在执行removeVnodes办法 removeVnodes(elm, oldCh, 0, oldCh.length - 1) } else if (isDef(oldVnode.text)) { // 新旧节点都是undefined，且老节点存在text，清空文本。 nodeOps.setTextContent(elm, '') } } else if (oldVnode.text !== vnode.text) { // 新老节点文本内容不同，更新文本 nodeOps.setTextContent(elm, vnode.text) } if (isDef(data)) { // 执行data.hook.postpatch钩子，至此 patch实现 if (isDef(i = data.hook) && isDef(i = i.postpatch)) i(oldVnode, vnode) } }updateChildren函数
重点！！！
前置条件：vnode和oldVnode的children不相等
整体的执行思路如下：
- vnode头比照oldVnode头
- vnode尾比照oldVnode尾
- vnode头比照oldVnode尾
vnode尾比照oldVnode头
- 只有合乎一种状况就进行patch，挪动节点，挪动下标等操作
都不对再在oldChild中找一个key和newStart雷同的节点
- 找不到，新建一个。
找到，获取这个节点，判断它和newStartVnode是不是同一个节点
- 如果是雷同节点，进行patch 而后将这个节点插入到oldStart之前，newStart下标继续移动
- 如果不是雷同节点，须要执行createElm创立新元素
为什么会有头对尾、尾对头的操作？
- 能够疾速检测出reverse操作，放慢diff效率。
源码如下 已写好正文便于浏览：
function updateChildren(parentElm, oldCh, newCh, insertedVnodeQueue, removeOnly) { // 定义变量 let oldStartIdx = 0 // 老节点Child头下标 let newStartIdx = 0 // 新节点Child头下标 let oldEndIdx = oldCh.length - 1 // 老节点Child尾下标 let oldStartVnode = oldCh[0] // 老节点Child头结点 let oldEndVnode = oldCh[oldEndIdx] // 老节点Child尾结点 let newEndIdx = newCh.length - 1 // 新节点Child尾下标 let newStartVnode = newCh[0] // 新节点Child头结点 let newEndVnode = newCh[newEndIdx] // 新节点Child尾结点 let oldKeyToIdx, idxInOld, vnodeToMove, refElm // removeOnly is a special flag used only by <transition-group> // to ensure removed elements stay in correct relative positions // during leaving transitions const canMove = !removeOnly if (process.env.NODE_ENV !== 'production') { checkDuplicateKeys(newCh) } // 定义循环 while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) { // 存在检测 if (isUndef(oldStartVnode)) { oldStartVnode = oldCh[++oldStartIdx] // Vnode has been moved left } else if (isUndef(oldEndVnode)) { oldEndVnode = oldCh[--oldEndIdx] // 如果老结点Child头和新节点Child头是同一个节点 } else if (sameVnode(oldStartVnode, newStartVnode)) { // patch差别 patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue) // patch实现 挪动节点地位 持续比对下一个节点 oldStartVnode = oldCh[++oldStartIdx] newStartVnode = newCh[++newStartIdx] // 如果老结点Child尾和新节点Child尾是同一个节点 } else if (sameVnode(oldEndVnode, newEndVnode)) { // patch差别 patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue) // patch实现 挪动节点地位 持续比对下一个节点 oldEndVnode = oldCh[--oldEndIdx] newEndVnode = newCh[--newEndIdx] // 如果老结点Child头和新节点Child尾是同一个节点 } else if (sameVnode(oldStartVnode, newEndVnode)) { // Vnode moved right // patch差别 patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue) // 把oldStart节点放到oldEnd节点前面 canMove && nodeOps.insertBefore(parentElm, oldStartVnode.elm, nodeOps.nextSibling(oldEndVnode.elm)) // patch实现 挪动节点地位 持续比对下一个节点 oldStartVnode = oldCh[++oldStartIdx] newEndVnode = newCh[--newEndIdx] // 如果老结点Child尾和新节点Child头是同一个节点 } else if (sameVnode(oldEndVnode, newStartVnode)) { // Vnode moved left // patch差别 patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue) // 把oldEnd节点放到oldStart节点后面 canMove && nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm) // patch实现 挪动节点地位 持续比对下一个节点 oldEndVnode = oldCh[--oldEndIdx] newStartVnode = newCh[++newStartIdx] } else { // 如果没有雷同的Key，执行createElm办法创立元素 if (isUndef(oldKeyToIdx)) oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx) idxInOld = isDef(newStartVnode.key) ? oldKeyToIdx[newStartVnode.key] : findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx) if (isUndef(idxInOld)) { // New element createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx) } else { // 有雷同的Key，判断这两个节点是否为sameNode vnodeToMove = oldCh[idxInOld] if (sameVnode(vnodeToMove, newStartVnode)) { // 如果是雷同节点，进行patch 而后举将oldStart插入到oldStart之前，newStart下标继续移动 patchVnode(vnodeToMove, newStartVnode, insertedVnodeQueue) oldCh[idxInOld] = undefined canMove && nodeOps.insertBefore(parentElm, vnodeToMove.elm, oldStartVnode.elm) } else { // 如果不是雷同节点，须要执行createElm创立新元素 createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx) } } newStartVnode = newCh[++newStartIdx] } } // oldStartIdx > oldEndIdx阐明oldChild先遍历完，应用addVnode办法增加newStartIdx指向的节点到newEndIdx的节点 if (oldStartIdx > oldEndIdx) { refElm = isUndef(newCh[newEndIdx + 1]) ? null : newCh[newEndIdx + 1].elm addVnodes(parentElm, refElm, newCh, newStartIdx, newEndIdx, insertedVnodeQueue) } else if (newStartIdx > newEndIdx) { // 如果newStartIdx > newEndIdx阐明newChild先遍历完，remove掉oldChild未遍历完的节点 removeVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx) } }四、总结
- 正确应用key，能够疾速执行sameVnode比对，减速Diff效率，能够作为性能优化的一个点。
- DIff只做同级比拟，应用sameVnode函数比对，文本节点间接替换文本内容。
子元素列表的Diff，进行头对头、尾对尾、头对尾等系列比拟，直到遍历完两个元素的子元素列表。
- 或一个列表先遍历完了，间接addVnode / removeVnode。
原文链接：Vue进阶 Diff算法详解 | 学习笔记
掘金：前端LeBron
知乎：前端LeBron
继续分享技术博文，关注微信公众号