深入剖析vue2.x中diff演算法的原理

diff演算法是一種透過同層的樹節點進行比較的高效演算法，避免了對樹進行逐層搜尋遍歷。這篇文章帶大家深入剖析vue2.x中diff演算法的原理，希望對大家有幫助！

原始碼分析文章看了很多,也閱讀了至少兩次原始碼。終歸還是想自己寫寫,作為自己的一種記錄和學習。 重點看註釋部分和總結,其餘不用太關心,透過總結對照源碼回看過程和註釋收穫更大

更新方法的定義

在產生render 函數後,就會呼叫掛載方法,在掛載時就會經過diff 計算,在初始化的時候,由於沒有舊的虛擬節點,所以初次會將真實的dom 節點與虛擬節點作對比,由於虛擬節點不是原生節點,所以第一次會做一個替換操作。 （學習影片分享：vue影片教學）

// /src/core/instance/lifecycle.js
Vue.prototype._update = function (vnode: VNode, hydrating?: boolean) {
    const vm: Component = this
    const prevEl = vm.$el
    const prevVnode = vm._vnode
    const restoreActiveInstance = setActiveInstance(vm)
    vm._vnode = vnode // 当前render函数产生的虚拟节点,保存后以便下次做对比
    if (!prevVnode) {
      vm.$el = vm.__patch__(vm.$el, vnode, hydrating, false) //初次渲染
    } else {
      vm.$el = vm.__patch__(prevVnode, vnode)
    }
   ...
  }

diff 演算法兩大主要分支

主體會有為兩大分支: 前後虛擬節點一致、前後虛擬節點不一致

// /src/core/vdom/patch.js
export function createPatchFunction (backend) {
  ...
  return function patch (oldVnode, vnode, hydrating, removeOnly) {
    ...
      if (!isRealElement && sameVnode(oldVnode, vnode)) {
        ...// 前后虚拟节点一致的方法
      } else {
        ...// 前后虚拟节点不一致的方法
      }
  }
}

前後虛擬節點不一致

分為三個步驟: 1.建立新的節點、2.更新父佔位符節點、3.刪除舊節點
初次進行掛載元件時兩者不相同,之後會判斷如果是真實dom,就會將其轉為虛擬節點並替換掉

if (isRealElement) {
  ...
  //需要diff 所以将第一次的真实节点转换成虚拟节点
  oldVnode = emptyNodeAt(oldVnode) //<div id="app"></div>
}
// 拿到父类的dom节点
const oldElm = oldVnode.elm //app
const parentElm = nodeOps.parentNode(oldElm) // body
//创建新dom节点 内部包含组件逻辑
createElm(
  vnode,
  insertedVnodeQueue,
  oldElm._leaveCb ? null : parentElm,
  nodeOps.nextSibling(oldElm)
)
//更新父的占位符节点 (组件更新相关)
if (isDef(vnode.parent)) {
  // 在生成render函数时会生成占位符节点<Dialog>提示</Dialog> => <div>提示</div> <Dialog></Dialog>就是占位符节点
  let ancestor = vnode.parent
  // 判断是否可挂载
  const patchable = isPatchable(vnode)
  while (ancestor) {
    for (let i = 0; i < cbs.destroy.length; ++i) {
      cbs.destroy[i](ancestor)
    }
    //更新父占位符的element
    ancestor.elm = vnode.elm
    if (patchable) {
      ...
    } else {
      registerRef(ancestor)
    }
    ancestor = ancestor.parent
  }
}
// 删除旧节点
if (isDef(parentElm)) {
  removeVnodes([oldVnode], 0, 0)
} else if (isDef(oldVnode.tag)) {
  invokeDestroyHook(oldVnode)
}

#前後虛擬節點一致

• 首先判斷新節點是否為文字,是則直接設定文字,不是則繼續判斷
• #新、舊節點都有children,深度對比(重點)
• 新節點有children,舊節點沒有,循環新增節點
• 新節點沒有,舊節點有children,直接刪除舊節點

function patchVnode (oldVnode,vnode,insertedVnodeQueue,ownerArray,index,removeOnly) {
    const elm = vnode.elm = oldVnode.elm

    let i
    const data = vnode.data 
    // 是组件vnode,在组件更新会调用组件的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)) { 
      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)
    }
    // 是否是text
    if (isUndef(vnode.text)) {
      // 新旧节点都有children
      if (isDef(oldCh) && isDef(ch)) {
        if (oldCh !== ch) updateChildren(elm, oldCh, ch, insertedVnodeQueue, removeOnly)
      // 新有 老没有 children 循环创建新节点
      } else if (isDef(ch)) {
        if (isDef(oldVnode.text)) nodeOps.setTextContent(elm, &#39;&#39;)
        addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue)
      // 新没有 老有 children 直接删除老节点
      } else if (isDef(oldCh)) {
        removeVnodes(oldCh, 0, oldCh.length - 1)
      // 新老都没有 children 老的是文本 就置为空
      } else if (isDef(oldVnode.text)) {
        nodeOps.setTextContent(elm, &#39;&#39;)
      }
    // 是text 直接设置文本
    } 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)
    }
  }

新舊節點都有children情況的比較

// /src/core/vdom/patch.js
 function updateChildren (parentElm, oldCh, newCh, insertedVnodeQueue, removeOnly) {
    let oldStartIdx = 0 // 老节点开始索引
    let newStartIdx = 0 // 新节点开始索引
    let oldEndIdx = oldCh.length - 1 // 老节点末尾索引
    let oldStartVnode = oldCh[0] // 老节点开始元素
    let oldEndVnode = oldCh[oldEndIdx] // 老节点末尾元素
    let newEndIdx = newCh.length - 1 // 新节点末尾索引
    let newStartVnode = newCh[0] // 新节点开始元素
    let newEndVnode = newCh[newEndIdx] // 新节点末尾元素
    let oldKeyToIdx, idxInOld, vnodeToMove, refElm
    const canMove = !removeOnly
    // 满足新节点开始索引小于新节点结束索引,旧节点开始索引小于旧节点结束索引
    while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
      if (isUndef(oldStartVnode)) { // 是否定义老节点开始元素
        oldStartVnode = oldCh[++oldStartIdx]
      } else if (isUndef(oldEndVnode)) {// 是否定义老节点结束元素
        oldEndVnode = oldCh[--oldEndIdx]
        // 头(旧节点开始元素)头(新节点开始元素)对比 例如四个li,末尾新增一个li,这种情况头头对比性能高
      } else if (sameVnode(oldStartVnode, newStartVnode)) { // sameVnode判断key和tag是否相同
        patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
        oldStartVnode = oldCh[++oldStartIdx]
        newStartVnode = newCh[++newStartIdx]
      } else if (sameVnode(oldEndVnode, newEndVnode)) { // 尾尾对比 例如四个li,头部新增一个li,这种情况尾尾对比性能高
        patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx)
        oldEndVnode = oldCh[--oldEndIdx]
        newEndVnode = newCh[--newEndIdx]
      } else if (sameVnode(oldStartVnode, newEndVnode)) {// 头尾对比 节点反转优化 reverse
        patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx)
        canMove && nodeOps.insertBefore(parentElm, oldStartVnode.elm, nodeOps.nextSibling(oldEndVnode.elm))
        oldStartVnode = oldCh[++oldStartIdx]
        newEndVnode = newCh[--newEndIdx]
      } else if (sameVnode(oldEndVnode, newStartVnode)) { // 尾头对比
        patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
        canMove && nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm)
        oldEndVnode = oldCh[--oldEndIdx]
        newStartVnode = newCh[++newStartIdx]
      } else { // 乱序对比(核心diff,其他方式为优化)
        if (isUndef(oldKeyToIdx)) oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx)
        idxInOld = isDef(newStartVnode.key)
          ? oldKeyToIdx[newStartVnode.key]
          : findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx)
        if (isUndef(idxInOld)) {
          createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx)
        } else {
          vnodeToMove = oldCh[idxInOld]
          if (sameVnode(vnodeToMove, newStartVnode)) {
            patchVnode(vnodeToMove, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
            oldCh[idxInOld] = undefined
            canMove && nodeOps.insertBefore(parentElm, vnodeToMove.elm, oldStartVnode.elm)
          } else {
            createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx)
          }
        }
        newStartVnode = newCh[++newStartIdx]
      }
    }
    // 多出来的新节点直接做插入 多出来的旧节点删除
    if (oldStartIdx > oldEndIdx) {
      refElm = isUndef(newCh[newEndIdx + 1]) ? null : newCh[newEndIdx + 1].elm
      addVnodes(parentElm, refElm, newCh, newStartIdx, newEndIdx, insertedVnodeQueue)
    } else if (newStartIdx > newEndIdx) {
      removeVnodes(oldCh, oldStartIdx, oldEndIdx)
    }
  }

注意點

• key某些情況下不能使用索引,因為改變前後的索引都是一樣的,當在頭部添加元素時,如果用索引做key就會出現更新錯誤問題,vue會理解為在末尾添加一個元素(因為前後的key都是0)
• 在各種對比情況下,只要找到兩者相同就會去遞歸對比children
• 在亂序對比中,key的作用是極大的。無key會出現更新出錯問題,同時達不到復用效果
• diff對比是深度優先,同層比較

總結

在掛載時會經過diff演算法後進行模板更新,初次會將真實dom節點和生成的虛擬節點進行對比,並將生成的虛擬節點儲存起來,以便之後更新做對比。 diff演算法只要分兩發分支,前後虛擬節點一致和前後虛擬節點不一致。當前後虛擬節點不一致時,會建立新節點、更新父佔位符、刪除舊節點。如果舊節點是真實節點,就將其轉為虛擬節點,拿到舊節點的父節點後替換舊節點。當前後虛擬節點一致時,會先判斷新節點是否為文本,如果值則直接添加,如果不是先比較屬性,再判斷如果新節點有children,舊節點沒children,就直接添加新節點children,如果新節點沒有,舊節點有,就會將舊節點的children移除,如果新舊節點都有children,利用雙指針同層對比,通過頭頭對比、尾尾對比、頭尾對比、尾頭對比、亂序對比不斷迭代對其進行判斷更新,最大程度的利用舊節點,之後如果有多餘的新節點就會將其添加,多餘的舊節點將其刪除,最後將對比後的虛擬節點返回儲存起來,作為下次對比的舊節點。

• 頭對比
  如果新舊開始元素是相同vnode,遞歸調用patchVnode方法進行深層對比,之後移動索引至下一個元素
• 尾尾對比
  如果新舊結束元素是相同vnode,遞歸呼叫patchVnode方法進行深層對比,之後移動索引至上一個元素
• 頭尾對比
  將舊節點開始元素和舊節點尾元素進行比較,相同就遞歸呼叫patchVnode方法進行深層對比,之後將舊節點元素移動至最後,舊節點頭指針移動到下一個,新節點的尾指針移動至上一個。例如舊:A,B,C,新:C,B,A,第一次對比將舊A移動到C後邊
• 尾頭對比
  將舊節點尾元素和舊節點開始元素進行比較,相同就遞歸呼叫patchVnode方法進行深層對比,之後將舊節點元素移動至最前,舊節點尾指標移動到上一個,新節點的頭指標移動至下一個。例如舊:A,B,C,新:C,B,A,D第一次對比將舊C移到A前邊
• 亂序對比
  在做比較前會根據key和對應的索引將舊節點產生映射表。在亂序對比時會用當前的key去找舊節點的key,如果能復用,就將節點移動到舊的節點開頭處並遞歸對比children,如果不能復用就創建新的差入到舊的節點開頭處。之後將新的索引移至下一個元素

（學習影片分享：web前端開發、程式設計基礎影片）

以上是深入剖析vue2.x中diff演算法的原理的詳細內容。更多資訊請關注PHP中文網其他相關文章！