Vue原理解析（八）：一起搞明白令人頭疼的diff算法

Vue原理解析（七）：全面深入理解響應(yīng)式原理(下)-數(shù)組進階篇

之前章節(jié)介紹了VNode如何生成真實Dom黎做，這只是patch內(nèi)首次渲染做的事鹰晨，完成了一小部分功能而已，而它做的最重要的事情是當(dāng)響應(yīng)式觸發(fā)時鸡典，讓頁面的重新渲染這一過程能高效完成芳悲。其實頁面的重新渲染完全可以使用新生成的Dom去整個替換掉舊的Dom，然而這么做比較低效馏臭，所以就借助接下來將介紹的diff比較算法來完成野蝇。

diff算法做的事情是比較VNode和oldVNode，再以VNode為標(biāo)準(zhǔn)的情況下在oldVNode上做小的改動括儒，完成VNode對應(yīng)的Dom渲染绕沈。

回到之前_update方法的實現(xiàn)，這個時候就會走到else的邏輯了：

Vue.prototype._update = function(vnode) {
  const vm = this
  const prevVnode = vm._vnode
  
  vm._vnode = vnode  // 緩存為之前vnode
  
  if(!prevVnode) {  // 首次渲染
    vm.$el = vm.__patch__(vm.$el, vnode)
  } else {  // 重新渲染
    vm.$el = vm.__patch__(prevVnode, vnode)
  }
}

既然是在現(xiàn)有的VNode上修修補補來達到重新渲染的目的帮寻，所以無非是做三件事情：

創(chuàng)建新增節(jié)點

刪除廢棄節(jié)點

更新已有節(jié)點

接下來我們將介紹以上三種情況分別什么情況下會遇到乍狐。

創(chuàng)建新增節(jié)點

新增節(jié)點兩種情況下會遇到：

VNode中有的節(jié)點而oldVNode沒有

VNode中有的節(jié)點而oldVNode中沒有，最明顯的場景就是首次渲染了固逗，這個時候是沒有oldVNode的浅蚪，所以將整個VNode渲染為真實Dom插入到根節(jié)點之內(nèi)即可藕帜，這一詳細過程之前章節(jié)有詳細說明。

VNode和oldVNode完全不同

當(dāng)VNode和oldVNode不是同一個節(jié)點時惜傲，直接會將VNode創(chuàng)建為真實Dom洽故，插入到舊節(jié)點的后面，這個時候舊節(jié)點就變成了廢棄節(jié)點盗誊，移除以完成替換過程时甚。

判斷兩個節(jié)點是否為同一個節(jié)點，內(nèi)部是這樣定義的：

function sameVnode (a, b) {  // 是否是相同的VNode節(jié)點
  return (
    a.key === b.key && (  // 如平時v-for內(nèi)寫的key
      (
        a.tag === b.tag &&   // tag相同
        a.isComment === b.isComment &&  // 注釋節(jié)點
        isDef(a.data) === isDef(b.data) &&  // 都有data屬性
        sameInputType(a, b)  // 相同的input類型
      ) || (
        isTrue(a.isAsyncPlaceholder) &&  // 是異步占位符節(jié)點
        a.asyncFactory === b.asyncFactory &&  // 異步工廠方法
        isUndef(b.asyncFactory.error)
      )
    )
  )
}

刪除廢棄節(jié)點

上面創(chuàng)建新增節(jié)點的第二種情況以略有提及哈踱，比較vnode和oldVnode撞秋，如果根節(jié)點不相同就將Vnode整顆渲染為真實Dom，插入到舊節(jié)點的后面嚣鄙，最后刪除掉已經(jīng)廢棄的舊節(jié)點即可：

image

在patch方法內(nèi)將創(chuàng)建好的Dom插入到廢棄節(jié)點后面之后：

if (isDef(parentElm)) {  // 在它們的父節(jié)點內(nèi)刪除舊節(jié)點
  removeVnodes(parentElm, [oldVnode], 0, 0)
}

-------------------------------------------------------------

function removeVnodes (parentElm, vnodes, startIdx, endIdx) {
  for (; startIdx <= endIdx; ++startIdx) {
    const ch = vnodes[startIdx]
    if (isDef(ch)) {
      removeNode(ch.elm)
    }
  }
}  // 移除從startIdx到endIdx之間的內(nèi)容

------------------------------------------------------------

function removeNode(el) {  // 單個節(jié)點移除
  const parent = nodeOps.parentNode(el)
  if(isDef(parent)) {
    nodeOps.removeChild(parent, el)
  }
}

更新已有節(jié)點 (重點)

這個才是diff算法的重點吻贿，當(dāng)兩個節(jié)點是相同的節(jié)點時，這個時候就需要找出它們的不同之處哑子，比較它們主要是使用patchVnode方法舅列，這個方法里面主要也是處理幾種分支情況：

都是靜態(tài)節(jié)點

function patchVnode(oldVnode, vnode) {
  
  if (oldVnode === vnode) {  // 完全一樣
    return
  }

  const elm = vnode.elm = oldVnode.elm
  if(isTrue(vnode.isStatic) && isTrue(oldVnode.isStatic)) {  
    vnode.componentInstance = oldVnode.componentInstance
    return  // 都是靜態(tài)節(jié)點，跳過
  }
  ...
}

什么是靜態(tài)節(jié)點了卧蜓？這是編譯階段做的事情帐要，它會找出模板中的靜態(tài)節(jié)點并做上標(biāo)記(isStatic為true)，例如：

<template>
  <div>
    <h2>{{title}}</h2>
    <p>新鮮食材</p>
  </div>
</template>

這里的h2標(biāo)簽就不是靜態(tài)節(jié)點弥奸，因為是根據(jù)插值變化的榨惠，而p標(biāo)簽就是靜態(tài)節(jié)點，因為不會改變盛霎。如果都是靜態(tài)節(jié)點就跳過這次比較赠橙，這也是編譯階段為diff比對做的優(yōu)化。

vnode節(jié)點沒有文本屬性

function patchVnode(oldVnode, vnode) {

  const elm = vnode.elm = oldVnode.elm
  const oldCh = oldVnode.children
  const ch = vnode.children

  if (isUndef(vnode.text)) {  // vnode沒有text屬性
    
    if (isDef(oldCh) && isDef(ch)) {  // // 都有children
      if (oldCh !== ch) {  // 且children不同
        updateChildren(elm, oldCh, ch)  // 更新子節(jié)點
      }
    } 
    
    else if (isDef(ch)) {  // 只有vnode有children
      if (isDef(oldVnode.text)) {  // oldVnode有文本節(jié)點
        nodeOps.setTextContent(elm, '')  // 設(shè)置oldVnode文本為空
      }
      addVnodes(elm, null, ch, 0, ch.length - 1)
      // 往oldVnode空的標(biāo)簽內(nèi)插入vnode的children的真實dom
    } 
    
    else if (isDef(oldCh)) {  // 只有oldVnode有children
      removeVnodes(elm, oldCh, 0, oldCh.length - 1)  // 全部移除
    } 
    
    else if (isDef(oldVnode.text)) {  // oldVnode有文本節(jié)點
      nodeOps.setTextContent(elm, '')  // 設(shè)置為空
    }
  } 
  
  else {  vnode有text屬性
    ...
  }
  
  ...

如果vnode沒有文本節(jié)點愤炸，又會有接下來的四個分支：

1. 都有children且不相同

使用updateChildren方法更詳細的比對它們的children期揪，如果說更新已有節(jié)點是patch的核心，那這里的更新children就是核心中的核心规个，這個之后使用流程圖的方式仔仔細細說明凤薛。

2. 只有vnode有children

那這里的oldVnode要么是一個空標(biāo)簽或者是文本節(jié)點，如果是文本節(jié)點就清空文本節(jié)點诞仓，然后將vnode的children創(chuàng)建為真實Dom后插入到空標(biāo)簽內(nèi)缤苫。

3. 只有oldVnode有children

因為是以vnode為標(biāo)準(zhǔn)的，所以vnode沒有的東西墅拭，oldVnode內(nèi)就是廢棄節(jié)點活玲，需要刪除掉。

4. 只有oldVnode有文本

只要是oldVnode有而vnode沒有的，清空或移除即可翼虫。

vnode節(jié)點有文本屬性

function patchVnode(oldVnode, vnode, insertedVnodeQueue) {

  const elm = vnode.elm = oldVnode.elm
  const oldCh = oldVnode.children
  const ch = vnode.children

  if (isUndef(vnode.text)) {  // vnode沒有text屬性
    ...
  } else if(oldVnode.text !== vnode.text) {  // vnode有text屬性且不同
    nodeOps.setTextContent(elm, vnode.text)  // 設(shè)置文本
  }
  
  ...

還是那句話屑柔，以vnode為標(biāo)準(zhǔn)，所以vnode有文本節(jié)點的話珍剑，無論oldVnode是什么類型節(jié)點掸宛，直接設(shè)置為vnode內(nèi)的文本即可。至此招拙，整個diff比對的大致過程就算是說明完畢了唧瘾，我們還是以一張流程圖來理清思路：

image

更新已有節(jié)點之更新子節(jié)點 (重點中的重點)

更新子節(jié)點示例：
<template>
  <ul>
    <li v-for='item in list' :key='item.id'>{{item.name}}</li>
  </ul>
</template>

export default {
  data() {
    return {
      list: [{
        id: 'a1',name: 'A'}, {
        id: 'b2',name: 'B'}, {
        id: 'c3',name: 'C'}, {
        id: 'd4',name: 'D'}
      ]
    }
  },
  mounted() {
    setTimeout(() => {
      this.list.sort(() => Math.random() - .5)
        .unshift({id: 'e5', name: 'E'})
    }, 1000)
  }
}

上述代碼中首先渲染一個列表，然后將其隨機打亂順序后并添加一項到列表最前面别凤，這個時候就會觸發(fā)該組件更新子節(jié)點的邏輯饰序，之前也會有一些其他的邏輯，這里只用關(guān)注更新子節(jié)點相關(guān)规哪，來看下它怎么更新Dom的：

function updateChildren(parentElm, oldCh, newCh) {
  let oldStartIdx = 0  // 舊第一個下標(biāo)
  let oldStartVnode = oldCh[0]  // 舊第一個節(jié)點
  let oldEndIdx = oldCh.length - 1  // 舊最后下標(biāo)
  let oldEndVnode = oldCh[oldEndIdx]  // 舊最后節(jié)點
  
  let newStartIdx = 0  // 新第一個下標(biāo)
  let newStartVnode = newCh[0]  // 新第一個節(jié)點
  let newEndIdx = newCh.length - 1  // 新最后下標(biāo)
  let newEndVnode = newCh[newEndIdx]  // 新最后節(jié)點
  
  let oldKeyToIdx  // 舊節(jié)點key和下標(biāo)的對象集合
  let idxInOld  // 新節(jié)點key在舊節(jié)點key集合里的下標(biāo)
  let vnodeToMove  // idxInOld對應(yīng)的舊節(jié)點
  let refElm  // 參考節(jié)點
  
  checkDuplicateKeys(newCh) // 檢測newVnode的key是否有重復(fù)
  
  while(oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {  // 開始遍歷children
  
    if (isUndef(oldStartVnode)) {  // 跳過因位移留下的undefined
      oldStartVnode = oldCh[++oldStartIdx]
    } else if (isUndef(oldEndVnode)) {  // 跳過因位移留下的undefine
      oldEndVnode = oldCh[--oldEndIdx]  
    } 
    
    else if(sameVnode(oldStartVnode, newStartVnode)) {  // 比對新第一和舊第一節(jié)點
      patchVnode(oldStartVnode, newStartVnode)  // 遞歸調(diào)用                        
      oldStartVnode = oldCh[++oldStartIdx]  // 舊第一節(jié)點和下表重新標(biāo)記后移        
      newStartVnode = newCh[++newStartIdx]  // 新第一節(jié)點和下表重新標(biāo)記后移        
    }
    
    else if (sameVnode(oldEndVnode, newEndVnode)) {  // 比對舊最后和新最后節(jié)點     
      patchVnode(oldEndVnode, newEndVnode)  // 遞歸調(diào)用                            
      oldEndVnode = oldCh[--oldEndIdx]  // 舊最后節(jié)點和下表重新標(biāo)記前移            
      newEndVnode = newCh[--newEndIdx]  // 新最后節(jié)點和下表重新標(biāo)記前移            
    }
    
    else if (sameVnode(oldStartVnode, newEndVnode)) { // 比對舊第一和新最后節(jié)點
      patchVnode(oldStartVnode, newEndVnode)  // 遞歸調(diào)用
      nodeOps.insertBefore(parentElm, oldStartVnode.elm, nodeOps.nextSibling(oldEndVnode.elm))  
      // 將舊第一節(jié)點右移到最后求豫，視圖立刻呈現(xiàn)
      oldStartVnode = oldCh[++oldStartIdx]  // 舊開始節(jié)點被處理，舊開始節(jié)點為第二個
      newEndVnode = newCh[--newEndIdx]  // 新最后節(jié)點被處理诉稍，新最后節(jié)點為倒數(shù)第二個
    }
    
    else if (sameVnode(oldEndVnode, newStartVnode)) { // 比對舊最后和新第一節(jié)點
      patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue)  // 遞歸調(diào)用
      nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm)
      // 將舊最后節(jié)點左移到最前面蝠嘉，視圖立刻呈現(xiàn)
      oldEndVnode = oldCh[--oldEndIdx]  // 舊最后節(jié)點被處理，舊最后節(jié)點為倒數(shù)第二個
      newStartVnode = newCh[++newStartIdx]  // 新第一節(jié)點被處理杯巨，新第一節(jié)點為第二個
    }
    
    else {  // 不包括以上四種快捷比對方式
      if (isUndef(oldKeyToIdx)) {
        oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx) 
        // 獲取舊開始到結(jié)束節(jié)點的key和下表集合
      }
      
      idxInOld = isDef(newStartVnode.key)  // 獲取新節(jié)點key在舊節(jié)點key集合里的下標(biāo)
          ? oldKeyToIdx[newStartVnode.key]
          : findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx)
      
      if (isUndef(idxInOld)) { // 找不到對應(yīng)的下標(biāo)蚤告，表示新節(jié)點是新增的，需要創(chuàng)建新dom
        createElm(
          newStartVnode, 
          insertedVnodeQueue, 
          parentElm, 
          oldStartVnode.elm, 
          false, 
          newCh, 
          newStartIdx
        )
      }
      
      else {  // 能找到對應(yīng)的下標(biāo)服爷，表示是已有的節(jié)點杜恰，移動位置即可
        vnodeToMove = oldCh[idxInOld]  // 獲取對應(yīng)已有的舊節(jié)點
        patchVnode(vnodeToMove, newStartVnode, insertedVnodeQueue)
        oldCh[idxInOld] = undefined
        nodeOps.insertBefore(parentElm, vnodeToMove.elm, oldStartVnode.elm)
      }
      
      newStartVnode = newCh[++newStartIdx]  // 新開始下標(biāo)和節(jié)點更新為第二個節(jié)點
      
    }
  }
  
  ...
  
}

函數(shù)內(nèi)首先會定義一堆let定義的變量，這些變量是隨著while循環(huán)體而改變當(dāng)前值的仍源，循環(huán)的退出條件為只要新舊節(jié)點列表有一個處理完就退出心褐，看著循環(huán)體代碼挺復(fù)雜，其實它只是做了三件事镜会，明白了哪三件事再看循環(huán)體檬寂，會發(fā)現(xiàn)其實并不復(fù)雜：

1. 跳過undefined

為什么會有undefined终抽，之后的流程圖會說明清楚戳表。這里只要記住，如果舊開始節(jié)點為undefined昼伴，就后移一位匾旭；如果舊結(jié)束節(jié)點為undefined，就前移一位圃郊。

2. 快捷查找

首先會嘗試四種快速查找的方式价涝，如果不匹配，再做進一步處理：

2.1 新開始和舊開始節(jié)點比對

如果匹配持舆，表示它們位置都是對的色瘩，Dom不用改伪窖，就將新舊節(jié)點開始的下標(biāo)往后移一位即可。

2.2 舊結(jié)束和新結(jié)束節(jié)點比對

如果匹配居兆，也表示它們位置是對的覆山，Dom不用改，就將新舊節(jié)點結(jié)束的下標(biāo)前移一位即可泥栖。

2.3 舊開始和新結(jié)束節(jié)點比對

如果匹配簇宽，位置不對需要更新Dom視圖，將舊開始節(jié)點對應(yīng)的真實Dom插入到最后一位吧享，舊開始節(jié)點下標(biāo)后移一位魏割，新結(jié)束節(jié)點下標(biāo)前移一位。

2.4 舊結(jié)束和新開始節(jié)點比對

如果匹配钢颂，位置不對需要更新Dom視圖钞它，將舊結(jié)束節(jié)點對應(yīng)的真實Dom插入到舊開始節(jié)點對應(yīng)真實Dom的前面，舊結(jié)束節(jié)點下標(biāo)前移一位殊鞭，新開始節(jié)點下標(biāo)后移一位须揣。

3. key值查找

3.1 如果和已有key值匹配

那就說明是已有的節(jié)點，只是位置不對钱豁，那就移動節(jié)點位置即可耻卡。

3.2 如果和已有key值不匹配

再已有的key值集合內(nèi)找不到，那就說明是新的節(jié)點牲尺，那就創(chuàng)建一個對應(yīng)的真實Dom節(jié)點卵酪，插入到舊開始節(jié)點對應(yīng)的真實Dom前面即可。

這么說并不太好理解谤碳，結(jié)合之前的示例溃卡，根據(jù)以下的流程圖將會明白很多：

image

↑ 示例的初始狀態(tài)就是這樣了，之前定義的下標(biāo)以及對應(yīng)的節(jié)點就是start和end標(biāo)記蜒简。

image

↑ 首先進行之前說明兩兩四次的快捷比對瘸羡，找不到后通過舊節(jié)點的key值列表查找，并沒有找到說明E是新增的節(jié)點搓茬，創(chuàng)建對應(yīng)的真實Dom犹赖，插入到舊節(jié)點里start對應(yīng)真實Dom的前面，也就是A的前面卷仑，已經(jīng)處理完了一個峻村，新start位置后移一位。

image

↑ 接著開始處理第二個锡凝，還是首先進行快捷查找粘昨，沒有后進行key值列表查找。發(fā)現(xiàn)是已有的節(jié)點，只是位置不對张肾，那么進行插入操作芭析，參考節(jié)點還是A節(jié)點，將原來舊節(jié)點C設(shè)置為undefined吞瞪，這里之后會跳過它放刨。又處理完了一個節(jié)點，新start后移一位尸饺。

image

↑ 再處理第三個節(jié)點进统，通過快捷查找找到了，是新開始節(jié)點對應(yīng)舊開始節(jié)點浪听，Dom位置是對的螟碎，新start和舊start都后移一位。

image

↑ 接著處理的第四個節(jié)點迹栓，通過快捷查找掉分，這個時候先滿足了舊開始節(jié)點和新結(jié)束節(jié)點的匹配，Dom位置是不對的克伊，插入節(jié)點到最后位置酥郭，最后將新end前移一位，舊start后移一位愿吹。

image

↑ 處理最后一個節(jié)點不从，首先會執(zhí)行跳過undefined的邏輯，然后再開始快捷比對犁跪，匹配到的是新開始節(jié)點和舊開始節(jié)點椿息，它們各自start后移一位，這個時候就會跳出循環(huán)了坷衍。接著看下最后的收尾代碼：

function updateChildren(parentElm, oldCh, newCh) {
  let oldStartIdx = 0
  ...
  
  while(oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
    ...
  }
  
  if (oldStartIdx > oldEndIdx) {  // 如果舊節(jié)點列表先處理完寝优，處理剩余新節(jié)點
    refElm = isUndef(newCh[newEndIdx + 1]) ? null : newCh[newEndIdx + 1].elm
    addVnodes(parentElm, refElm, newCh, newStartIdx, newEndIdx, insertedVnodeQueue)  // 添加
  } 
  
  else if (newStartIdx > newEndIdx) {  // 如果新節(jié)點列表先處理完，處理剩余舊節(jié)點
    removeVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx)  // 刪除廢棄節(jié)點
  }
}

我們之前的示例剛好是新舊節(jié)點列表同時處理完退出的循環(huán)枫耳，這里是退出循環(huán)后為還有沒有處理完的節(jié)點乏矾，做不同的處理：

image

以新節(jié)點列表為標(biāo)準(zhǔn)，如果是新節(jié)點列表處理完迁杨，舊列表還有沒被處理的廢棄節(jié)點钻心，刪除即可；如果是舊節(jié)點先處理完仑最，新列表里還有沒被使用的節(jié)點扔役，創(chuàng)建真實Dom并插入到視圖即可。這就是整個diff算法過程了警医，大家可以對比之前的遞歸流程圖再看一遍，相信思路會清晰很多。

最后按照慣例我們還是以一道vue可能會被問到的面試題作為本章的結(jié)束~

面試官微笑而又不失禮貌的問道：

為什么v-for里建議為每一項綁定key预皇，而且最好具有唯一性侈玄，而不建議使用index？

懟回去：

在diff比對內(nèi)部做更新子節(jié)點時吟温，會根據(jù)oldVnode內(nèi)沒有處理的節(jié)點得到一個key值和下標(biāo)對應(yīng)的對象集合序仙，為的就是當(dāng)處理vnode每一個節(jié)點時，能快速查找該節(jié)點是否是已有的節(jié)點鲁豪，從而提高整個diff比對的性能潘悼。如果是一個動態(tài)列表，key值最好能保持唯一性爬橡，但像輪播圖那種不會變更的列表治唤，使用index也是沒問題的。

** 下一章** Vue原理解析（九）：監(jiān)聽屬性watch和計算屬性computed實現(xiàn)原理

順手點個贊或關(guān)注唄糙申，找起來也方便~

分享一個筆者自己寫的組件庫宾添，哪天可能會用的上了 ~ ↓

你可能會用的上的一個vue功能組件庫，持續(xù)完善中...

Vue原理解析（八）：一起搞明白令人頭疼的diff算法

Vue原理解析（八）：一起搞明白令人頭疼的diff算法

創(chuàng)建新增節(jié)點

`VNode`中有的節(jié)點而`oldVNode`沒有

`VNode`和`oldVNode`完全不同

刪除廢棄節(jié)點

更新已有節(jié)點 (重點)

都是靜態(tài)節(jié)點

`vnode`節(jié)點沒有文本屬性

`vnode`節(jié)點有文本屬性

更新已有節(jié)點之更新子節(jié)點 (重點中的重點)

1. 跳過undefined

2. 快捷查找

3. key值查找

面試官微笑而又不失禮貌的問道：

懟回去：

分享一個筆者自己寫的組件庫宾添，哪天可能會用的上了 ~ ↓

Vue原理解析（八）：一起搞明白令人頭疼的diff算法

創(chuàng)建新增節(jié)點

VNode中有的節(jié)點而oldVNode沒有

VNode和oldVNode完全不同

刪除廢棄節(jié)點

更新已有節(jié)點 (重點)

都是靜態(tài)節(jié)點

vnode節(jié)點沒有文本屬性

vnode節(jié)點有文本屬性

更新已有節(jié)點之更新子節(jié)點 (重點中的重點)

1. 跳過undefined

2. 快捷查找

3. key值查找

面試官微笑而又不失禮貌的問道：

懟回去：

分享一個筆者自己寫的組件庫宾添，哪天可能會用的上了 ~ ↓

`VNode`中有的節(jié)點而`oldVNode`沒有

`VNode`和`oldVNode`完全不同

`vnode`節(jié)點沒有文本屬性

`vnode`節(jié)點有文本屬性