diff算法是一種通過同層的樹節(jié)點進(jìn)行比較的高效算法，避免了對樹進(jìn)行逐層搜索遍歷。那么大家對diff算法嗎有多少了解？下面本篇文章就來帶大家深入解析下vue的diff算法，希望對大家有所幫助！

一、是什么

diff 算法是一種通過同層的樹節(jié)點進(jìn)行比較的高效算法。（學(xué)習(xí)視頻分享：vue視頻教程）

其有兩個特點：

• 比較只會在同層級進(jìn)行, 不會跨層級比較
• 在diff比較的過程中，循環(huán)從兩邊向中間比較

diff 算法在很多場景下都有應(yīng)用，在 vue 中，作用于虛擬 dom 渲染成真實 dom 的新舊 VNode 節(jié)點比較

二、比較方式

diff整體策略為：深度優(yōu)先，同層比較

• 比較只會在同層級進(jìn)行, 不會跨層級比較

• 比較的過程中，循環(huán)從兩邊向中間收攏

下面舉個vue通過diff算法更新的例子：

新舊VNode節(jié)點如下圖所示：

第一次循環(huán)后，發(fā)現(xiàn)舊節(jié)點D與新節(jié)點D相同，直接復(fù)用舊節(jié)點D作為diff后的第一個真實節(jié)點，同時舊節(jié)點endIndex移動到C，新節(jié)點的 startIndex 移動到了 C

第二次循環(huán)后，同樣是舊節(jié)點的末尾和新節(jié)點的開頭(都是 C)相同，同理，diff 后創(chuàng)建了 C 的真實節(jié)點插入到第一次創(chuàng)建的 D 節(jié)點后面。同時舊節(jié)點的 endIndex 移動到了 B，新節(jié)點的 startIndex 移動到了 E

第三次循環(huán)中，發(fā)現(xiàn)E沒有找到，這時候只能直接創(chuàng)建新的真實節(jié)點 E，插入到第二次創(chuàng)建的 C 節(jié)點之后。同時新節(jié)點的 startIndex 移動到了 A。舊節(jié)點的 startIndex 和 endIndex 都保持不動

第四次循環(huán)中，發(fā)現(xiàn)了新舊節(jié)點的開頭(都是 A)相同，于是 diff 后創(chuàng)建了 A 的真實節(jié)點，插入到前一次創(chuàng)建的 E 節(jié)點后面。同時舊節(jié)點的 startIndex 移動到了 B，新節(jié)點的startIndex 移動到了 B

第五次循環(huán)中，情形同第四次循環(huán)一樣，因此 diff 后創(chuàng)建了 B 真實節(jié)點 插入到前一次創(chuàng)建的 A 節(jié)點后面。同時舊節(jié)點的 startIndex移動到了 C，新節(jié)點的 startIndex 移動到了 F

新節(jié)點的 startIndex 已經(jīng)大于 endIndex 了，需要創(chuàng)建 newStartIdx 和 newEndIdx 之間的所有節(jié)點，也就是節(jié)點F，直接創(chuàng)建 F 節(jié)點對應(yīng)的真實節(jié)點放到 B 節(jié)點后面

三、原理分析

當(dāng)數(shù)據(jù)發(fā)生改變時，set方法會調(diào)用Dep.notify通知所有訂閱者Watcher，訂閱者就會調(diào)用patch給真實的DOM打補(bǔ)丁，更新相應(yīng)的視圖

源碼位置：src/core/vdom/patch.js

function patch(oldVnode, vnode, hydrating, removeOnly) {     if (isUndef(vnode)) { // 沒有新節(jié)點，直接執(zhí)行destory鉤子函數(shù)         if (isDef(oldVnode)) invokeDestroyHook(oldVnode)         return     }      let isInitialPatch = false     const insertedVnodeQueue = []      if (isUndef(oldVnode)) {         isInitialPatch = true         createElm(vnode, insertedVnodeQueue) // 沒有舊節(jié)點，直接用新節(jié)點生成dom元素     } else {         const isRealElement = isDef(oldVnode.nodeType)         if (!isRealElement && sameVnode(oldVnode, vnode)) {             // 判斷舊節(jié)點和新節(jié)點自身一樣，一致執(zhí)行patchVnode             patchVnode(oldVnode, vnode, insertedVnodeQueue, null, null, removeOnly)         } else {             // 否則直接銷毀及舊節(jié)點，根據(jù)新節(jié)點生成dom元素             if (isRealElement) {                  if (oldVnode.nodeType === 1 && oldVnode.hasAttribute(SSR_ATTR)) {                     oldVnode.removeAttribute(SSR_ATTR)                     hydrating = true                 }                 if (isTrue(hydrating)) {                     if (hydrate(oldVnode, vnode, insertedVnodeQueue)) {                         invokeInsertHook(vnode, insertedVnodeQueue, true)                         return oldVnode                     }                 }                 oldVnode = emptyNodeAt(oldVnode)             }             return vnode.elm         }     } }

patch函數(shù)前兩個參數(shù)位為oldVnode 和 Vnode ，分別代表新的節(jié)點和之前的舊節(jié)點，主要做了四個判斷：

• 沒有新節(jié)點，直接觸發(fā)舊節(jié)點的destory鉤子
• 沒有舊節(jié)點，說明是頁面剛開始初始化的時候，此時，根本不需要比較了，直接全是新建，所以只調(diào)用 createElm
• 舊節(jié)點和新節(jié)點自身一樣，通過 sameVnode 判斷節(jié)點是否一樣，一樣時，直接調(diào)用 patchVnode去處理這兩個節(jié)點
• 舊節(jié)點和新節(jié)點自身不一樣，當(dāng)兩個節(jié)點不一樣的時候，直接創(chuàng)建新節(jié)點，刪除舊節(jié)點

下面主要講的是patchVnode部分

function patchVnode (oldVnode, vnode, insertedVnodeQueue, removeOnly) {     // 如果新舊節(jié)點一致，什么都不做     if (oldVnode === vnode) {       return     }     // 讓vnode.el引用到現(xiàn)在的真實dom，當(dāng)el修改時，vnode.el會同步變化     const elm = vnode.elm = oldVnode.elm     // 異步占位符     if (isTrue(oldVnode.isAsyncPlaceholder)) {       if (isDef(vnode.asyncFactory.resolved)) {         hydrate(oldVnode.elm, vnode, insertedVnodeQueue)       } else {         vnode.isAsyncPlaceholder = true       }       return     }     // 如果新舊都是靜態(tài)節(jié)點，并且具有相同的key     // 當(dāng)vnode是克隆節(jié)點或是v-once指令控制的節(jié)點時，只需要把oldVnode.elm和oldVnode.child都復(fù)制到vnode上     // 也不用再有其他操作     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     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)) {       for (i = 0; i < cbs.update.length; ++i) cbs.update[i](oldVnode, vnode)       if (isDef(i = data.hook) && isDef(i = i.update)) i(oldVnode, vnode)     }     // 如果vnode不是文本節(jié)點或者注釋節(jié)點     if (isUndef(vnode.text)) {       // 并且都有子節(jié)點       if (isDef(oldCh) && isDef(ch)) {         // 并且子節(jié)點不完全一致，則調(diào)用updateChildren         if (oldCh !== ch) updateChildren(elm, oldCh, ch, insertedVnodeQueue, removeOnly)         // 如果只有新的vnode有子節(jié)點       } else if (isDef(ch)) {         if (isDef(oldVnode.text)) nodeOps.setTextContent(elm, '')         // elm已經(jīng)引用了老的dom節(jié)點，在老的dom節(jié)點上添加子節(jié)點         addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue)         // 如果新vnode沒有子節(jié)點，而vnode有子節(jié)點，直接刪除老的oldCh       } else if (isDef(oldCh)) {         removeVnodes(elm, oldCh, 0, oldCh.length - 1)         // 如果老節(jié)點是文本節(jié)點       } else if (isDef(oldVnode.text)) {         nodeOps.setTextContent(elm, '')       }       // 如果新vnode和老vnode是文本節(jié)點或注釋節(jié)點       // 但是vnode.text != oldVnode.text時，只需要更新vnode.elm的文本內(nèi)容就可以     } else if (oldVnode.text !== vnode.text) {       nodeOps.setTextContent(elm, vnode.text)     }     if (isDef(data)) {       if (isDef(i = data.hook) && isDef(i = i.postpatch)) i(oldVnode, vnode)     }   }

patchVnode主要做了幾個判斷：

• 新節(jié)點是否是文本節(jié)點，如果是，則直接更新dom的文本內(nèi)容為新節(jié)點的文本內(nèi)容
• 新節(jié)點和舊節(jié)點如果都有子節(jié)點，則處理比較更新子節(jié)點
• 只有新節(jié)點有子節(jié)點，舊節(jié)點沒有，那么不用比較了，所有節(jié)點都是全新的，所以直接全部新建就好了，新建是指創(chuàng)建出所有新DOM，并且添加進(jìn)父節(jié)點
• 只有舊節(jié)點有子節(jié)點而新節(jié)點沒有，說明更新后的頁面，舊節(jié)點全部都不見了，那么要做的，就是把所有的舊節(jié)點刪除，也就是直接把DOM 刪除

子節(jié)點不完全一致，則調(diào)用updateChildren

function updateChildren (parentElm, oldCh, newCh, insertedVnodeQueue, removeOnly) {     let oldStartIdx = 0 // 舊頭索引     let newStartIdx = 0 // 新頭索引     let oldEndIdx = oldCh.length - 1 // 舊尾索引     let newEndIdx = newCh.length - 1 // 新尾索引     let oldStartVnode = oldCh[0] // oldVnode的第一個child     let oldEndVnode = oldCh[oldEndIdx] // oldVnode的最后一個child     let newStartVnode = newCh[0] // newVnode的第一個child     let newEndVnode = newCh[newEndIdx] // newVnode的最后一個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     // 如果oldStartVnode和oldEndVnode重合，并且新的也都重合了，證明diff完了，循環(huán)結(jié)束     while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {       // 如果oldVnode的第一個child不存在       if (isUndef(oldStartVnode)) {         // oldStart索引右移         oldStartVnode = oldCh[++oldStartIdx] // Vnode has been moved left       // 如果oldVnode的最后一個child不存在       } else if (isUndef(oldEndVnode)) {         // oldEnd索引左移         oldEndVnode = oldCh[--oldEndIdx]       // oldStartVnode和newStartVnode是同一個節(jié)點       } else if (sameVnode(oldStartVnode, newStartVnode)) {         // patch oldStartVnode和newStartVnode， 索引左移，繼續(xù)循環(huán)         patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue)         oldStartVnode = oldCh[++oldStartIdx]         newStartVnode = newCh[++newStartIdx]       // oldEndVnode和newEndVnode是同一個節(jié)點       } else if (sameVnode(oldEndVnode, newEndVnode)) {         // patch oldEndVnode和newEndVnode，索引右移，繼續(xù)循環(huán)         patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue)         oldEndVnode = oldCh[--oldEndIdx]         newEndVnode = newCh[--newEndIdx]       // oldStartVnode和newEndVnode是同一個節(jié)點       } else if (sameVnode(oldStartVnode, newEndVnode)) { // Vnode moved right         // patch oldStartVnode和newEndVnode         patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue)         // 如果removeOnly是false，則將oldStartVnode.eml移動到oldEndVnode.elm之后         canMove && nodeOps.insertBefore(parentElm, oldStartVnode.elm, nodeOps.nextSibling(oldEndVnode.elm))         // oldStart索引右移，newEnd索引左移         oldStartVnode = oldCh[++oldStartIdx]         newEndVnode = newCh[--newEndIdx]       // 如果oldEndVnode和newStartVnode是同一個節(jié)點       } else if (sameVnode(oldEndVnode, newStartVnode)) { // Vnode moved left         // patch oldEndVnode和newStartVnode         patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue)         // 如果removeOnly是false，則將oldEndVnode.elm移動到oldStartVnode.elm之前         canMove && nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm)         // oldEnd索引左移，newStart索引右移         oldEndVnode = oldCh[--oldEndIdx]         newStartVnode = newCh[++newStartIdx]       // 如果都不匹配       } else {         if (isUndef(oldKeyToIdx)) oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx)         // 嘗試在oldChildren中尋找和newStartVnode的具有相同的key的Vnode         idxInOld = isDef(newStartVnode.key)           ? oldKeyToIdx[newStartVnode.key]           : findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx)         // 如果未找到，說明newStartVnode是一個新的節(jié)點         if (isUndef(idxInOld)) { // New element           // 創(chuàng)建一個新Vnode           createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm)         // 如果找到了和newStartVnodej具有相同的key的Vnode，叫vnodeToMove         } else {           vnodeToMove = oldCh[idxInOld]           /* istanbul ignore if */           if (process.env.NODE_ENV !== 'production' && !vnodeToMove) {             warn(               'It seems there are duplicate keys that is causing an update error. ' +               'Make sure each v-for item has a unique key.'             )           }           // 比較兩個具有相同的key的新節(jié)點是否是同一個節(jié)點           //不設(shè)key，newCh和oldCh只會進(jìn)行頭尾兩端的相互比較，設(shè)key后，除了頭尾兩端的比較外，還會從用key生成的對象oldKeyToIdx中查找匹配的節(jié)點，所以為節(jié)點設(shè)置key可以更高效的利用dom。           if (sameVnode(vnodeToMove, newStartVnode)) {             // patch vnodeToMove和newStartVnode             patchVnode(vnodeToMove, newStartVnode, insertedVnodeQueue)             // 清除             oldCh[idxInOld] = undefined             // 如果removeOnly是false，則將找到的和newStartVnodej具有相同的key的Vnode，叫vnodeToMove.elm             // 移動到oldStartVnode.elm之前             canMove && nodeOps.insertBefore(parentElm, vnodeToMove.elm, oldStartVnode.elm)           // 如果key相同，但是節(jié)點不相同，則創(chuàng)建一個新的節(jié)點           } else {             // same key but different element. treat as new element             createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm)           }         }         // 右移         newStartVnode = newCh[++newStartIdx]       }     }

while循環(huán)主要處理了以下五種情景：

• 當(dāng)新老 VNode 節(jié)點的 start 相同時，直接 patchVnode ，同時新老 VNode 節(jié)點的開始索引都加 1
• 當(dāng)新老 VNode 節(jié)點的 end相同時，同樣直接 patchVnode ，同時新老 VNode 節(jié)點的結(jié)束索引都減 1
• 當(dāng)老 VNode 節(jié)點的 start 和新 VNode 節(jié)點的 end 相同時，這時候在 patchVnode 后，還需要將當(dāng)前真實 dom 節(jié)點移動到 oldEndVnode 的后面，同時老 VNode 節(jié)點開始索引加 1，新 VNode 節(jié)點的結(jié)束索引減 1
• 當(dāng)老 VNode 節(jié)點的 end 和新 VNode 節(jié)點的 start 相同時，這時候在 patchVnode 后，還需要將當(dāng)前真實 dom 節(jié)點移動到 oldStartVnode 的前面，同時老 VNode 節(jié)點結(jié)束索引減 1，新 VNode 節(jié)點的開始索引加 1
• 如果都不滿足以上四種情形，那說明沒有相同的節(jié)點可以復(fù)用，則會分為以下兩種情況：
  • 從舊的 VNode 為 key 值，對應(yīng) index 序列為 value 值的哈希表中找到與 newStartVnode 一致 key 的舊的 VNode 節(jié)點，再進(jìn)行patchVnode，同時將這個真實 dom移動到 oldStartVnode 對應(yīng)的真實 dom 的前面
  • 調(diào)用 createElm 創(chuàng)建一個新的 dom 節(jié)點放到當(dāng)前 newStartIdx 的位置

小結(jié)

• 當(dāng)數(shù)據(jù)發(fā)生改變時，訂閱者watcher就會調(diào)用patch給真實的DOM打補(bǔ)丁
• 通過isSameVnode進(jìn)行判斷，相同則調(diào)用patchVnode方法
• patchVnode做了以下操作：
  • 找到對應(yīng)的真實dom，稱為el
  • 如果都有都有文本節(jié)點且不相等，將el文本節(jié)點設(shè)置為Vnode的文本節(jié)點
  • 如果oldVnode有子節(jié)點而VNode沒有，則刪除el子節(jié)點
  • 如果oldVnode沒有子節(jié)點而VNode有，則將VNode的子節(jié)點真實化后添加到el
  • 如果兩者都有子節(jié)點，則執(zhí)行updateChildren函數(shù)比較子節(jié)點
• updateChildren主要做了以下操作：
  • 設(shè)置新舊VNode的頭尾指針
  • 新舊頭尾指針進(jìn)行比較，循環(huán)向中間靠攏，根據(jù)情況調(diào)用patchVnode進(jìn)行patch重復(fù)流程、調(diào)用createElem創(chuàng)建一個新節(jié)點，從哈希表尋找 key一致的VNode 節(jié)點再分情況操作

（學(xué)習(xí)視頻分享：web前端開發(fā)、編程基礎(chǔ)視頻）