你瞭解vue diff演演算法嗎？原理解析

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

一、是什麼

diff 演演算法是一種通過同層的樹節點進行比較的高效演演算法。（學習視訊分享：）

其有兩個特點：

比較只會在同層級進行, 不會跨層級比較
在diff比較的過程中，迴圈從兩邊向中間比較

diff 演演算法在很多場景下都有應用，在 vue 中，作用於虛擬 dom 渲染成真實 dom 的新舊 VNode 節點比較

二、比較方式

diff整體策略為：深度優先，同層比較

比較只會在同層級進行, 不會跨層級比較

比較的過程中，迴圈從兩邊向中間收攏

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

新舊VNode節點如下圖所示：

第一次迴圈後，發現舊節點D與新節點D相同，直接複用舊節點D作為diff後的第一個真實節點，同時舊節點endIndex移動到C，新節點的 startIndex 移動到了 C

第二次迴圈後，同樣是舊節點的末尾和新節點的開頭(都是 C)相同，同理，diff 後建立了 C 的真實節點插入到第一次建立的 D 節點後面。同時舊節點的 endIndex 移動到了 B，新節點的 startIndex 移動到了 E

第三次迴圈中，發現E沒有找到，這時候只能直接建立新的真實節點 E，插入到第二次建立的 C 節點之後。同時新節點的 startIndex 移動到了 A。舊節點的 startIndex 和 endIndex 都保持不動

第四次迴圈中，發現了新舊節點的開頭(都是 A)相同，於是 diff 後建立了 A 的真實節點，插入到前一次建立的 E 節點後面。同時舊節點的 startIndex 移動到了 B，新節點的startIndex 移動到了 B

第五次迴圈中，情形同第四次迴圈一樣，因此 diff 後建立了 B 真實節點插入到前一次建立的 A 節點後面。同時舊節點的 startIndex移動到了 C，新節點的 startIndex 移動到了 F

新節點的 startIndex 已經大於 endIndex 了，需要建立 newStartIdx 和 newEndIdx 之間的所有節點，也就是節點F，直接建立 F 節點對應的真實節點放到 B 節點後面

三、原理分析

當資料發生改變時，set方法會呼叫Dep.notify通知所有訂閱者Watcher，訂閱者就會呼叫patch給真實的DOM打修補程式，更新相應的檢視

原始碼位置：src/core/vdom/patch.js

function patch(oldVnode, vnode, hydrating, removeOnly) {
    if (isUndef(vnode)) { // 沒有新節點，直接執行destory勾點函數
        if (isDef(oldVnode)) invokeDestroyHook(oldVnode)
        return
    }

    let isInitialPatch = false
    const insertedVnodeQueue = []

    if (isUndef(oldVnode)) {
        isInitialPatch = true
        createElm(vnode, insertedVnodeQueue) // 沒有舊節點，直接用新節點生成dom元素
    } else {
        const isRealElement = isDef(oldVnode.nodeType)
        if (!isRealElement && sameVnode(oldVnode, vnode)) {
            // 判斷舊節點和新節點自身一樣，一致執行patchVnode
            patchVnode(oldVnode, vnode, insertedVnodeQueue, null, null, removeOnly)
        } else {
            // 否則直接銷燬及舊節點，根據新節點生成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函數前兩個引數位為oldVnode 和 Vnode ，分別代表新的節點和之前的舊節點，主要做了四個判斷：

沒有新節點，直接觸發舊節點的destory勾點
沒有舊節點，說明是頁面剛開始初始化的時候，此時，根本不需要比較了，直接全是新建，所以只呼叫 createElm
舊節點和新節點自身一樣，通過 sameVnode 判斷節點是否一樣，一樣時，直接呼叫 patchVnode去處理這兩個節點
舊節點和新節點自身不一樣，當兩個節點不一樣的時候，直接建立新節點，刪除舊節點

下面主要講的是patchVnode部分

function patchVnode (oldVnode, vnode, insertedVnodeQueue, removeOnly) {
    // 如果新舊節點一致，什麼都不做
    if (oldVnode === vnode) {
      return
    }
    // 讓vnode.el參照到現在的真實dom，當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
    }
    // 如果新舊都是靜態節點，並且具有相同的key
    // 當vnode是克隆節點或是v-once指令控制的節點時，只需要把oldVnode.elm和oldVnode.child都複製到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不是文位元組點或者註釋節點
    if (isUndef(vnode.text)) {
      // 並且都有子節點
      if (isDef(oldCh) && isDef(ch)) {
        // 並且子節點不完全一致，則呼叫updateChildren
        if (oldCh !== ch) updateChildren(elm, oldCh, ch, insertedVnodeQueue, removeOnly)
        // 如果只有新的vnode有子節點
      } else if (isDef(ch)) {
        if (isDef(oldVnode.text)) nodeOps.setTextContent(elm, '')
        // elm已經參照了老的dom節點，在老的dom節點上新增子節點
        addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue)
        // 如果新vnode沒有子節點，而vnode有子節點，直接刪除老的oldCh
      } else if (isDef(oldCh)) {
        removeVnodes(elm, oldCh, 0, oldCh.length - 1)
        // 如果老節點是文位元組點
      } else if (isDef(oldVnode.text)) {
        nodeOps.setTextContent(elm, '')
      }
      // 如果新vnode和老vnode是文位元組點或註釋節點
      // 但是vnode.text != oldVnode.text時，只需要更新vnode.elm的文字內容就可以
    } 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主要做了幾個判斷：

新節點是否是文位元組點，如果是，則直接更新dom的文字內容為新節點的文字內容
新節點和舊節點如果都有子節點，則處理比較更新子節點
只有新節點有子節點，舊節點沒有，那麼不用比較了，所有節點都是全新的，所以直接全部新建就好了，新建是指建立出所有新DOM，並且新增進父節點
只有舊節點有子節點而新節點沒有，說明更新後的頁面，舊節點全部都不見了，那麼要做的，就是把所有的舊節點刪除，也就是直接把DOM 刪除

子節點不完全一致，則呼叫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完了，迴圈結束
    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是同一個節點
      } else if (sameVnode(oldStartVnode, newStartVnode)) {
        // patch oldStartVnode和newStartVnode， 索引左移，繼續迴圈
        patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue)
        oldStartVnode = oldCh[++oldStartIdx]
        newStartVnode = newCh[++newStartIdx]
      // oldEndVnode和newEndVnode是同一個節點
      } else if (sameVnode(oldEndVnode, newEndVnode)) {
        // patch oldEndVnode和newEndVnode，索引右移，繼續迴圈
        patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue)
        oldEndVnode = oldCh[--oldEndIdx]
        newEndVnode = newCh[--newEndIdx]
      // oldStartVnode和newEndVnode是同一個節點
      } 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是同一個節點
      } 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是一個新的節點
        if (isUndef(idxInOld)) { // New element
          // 建立一個新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的新節點是否是同一個節點
          //不設key，newCh和oldCh只會進行頭尾兩端的相互比較，設key後，除了頭尾兩端的比較外，還會從用key生成的物件oldKeyToIdx中查詢匹配的節點，所以為節點設定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相同，但是節點不相同，則建立一個新的節點
          } else {
            // same key but different element. treat as new element
            createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm)
          }
        }
        // 右移
        newStartVnode = newCh[++newStartIdx]
      }
    }

while迴圈主要處理了以下五種情景：

當新老 VNode 節點的 start 相同時，直接 patchVnode ，同時新老 VNode 節點的開始索引都加 1
當新老 VNode 節點的 end相同時，同樣直接 patchVnode ，同時新老 VNode 節點的結束索引都減 1
當老 VNode 節點的 start 和新 VNode 節點的 end 相同時，這時候在 patchVnode 後，還需要將當前真實 dom 節點移動到 oldEndVnode 的後面，同時老 VNode 節點開始索引加 1，新 VNode 節點的結束索引減 1
當老 VNode 節點的 end 和新 VNode 節點的 start 相同時，這時候在 patchVnode 後，還需要將當前真實 dom 節點移動到 oldStartVnode 的前面，同時老 VNode 節點結束索引減 1，新 VNode 節點的開始索引加 1
如果都不滿足以上四種情形，那說明沒有相同的節點可以複用，則會分為以下兩種情況：
- 從舊的 VNode 為 key 值，對應 index 序列為 value 值的雜湊表中找到與 newStartVnode 一致 key 的舊的 VNode 節點，再進行patchVnode，同時將這個真實 dom移動到 oldStartVnode 對應的真實 dom 的前面
- 呼叫 createElm 建立一個新的 dom 節點放到當前 newStartIdx 的位置

小結

當資料發生改變時，訂閱者watcher就會呼叫patch給真實的DOM打修補程式
通過isSameVnode進行判斷，相同則呼叫patchVnode方法
patchVnode做了以下操作：
- 找到對應的真實dom，稱為el
- 如果都有都有文位元組點且不相等，將el文位元組點設定為Vnode的文位元組點
- 如果oldVnode有子節點而VNode沒有，則刪除el子節點
- 如果oldVnode沒有子節點而VNode有，則將VNode的子節點真實化後新增到el
- 如果兩者都有子節點，則執行updateChildren函數比較子節點
updateChildren主要做了以下操作：
- 設定新舊VNode的頭尾指標
- 新舊頭尾指標進行比較，迴圈向中間靠攏，根據情況呼叫patchVnode進行patch重複流程、呼叫createElem建立一個新節點，從雜湊表尋找 key一致的VNode 節點再分情況操作

（學習視訊分享：、）

以上就是你瞭解vue diff演演算法嗎？原理解析的詳細內容，更多請關注TW511.COM其它相關文章！