vue 虛擬dom和diff演算法詳解

虛擬dom是當前前端最流行的兩個框架（vue和react）都用到的一種技術，都說他能幫助vue和react提升渲染性能，提升用戶體驗，那么今天我們來詳細看看虛擬dom到底是個什么鬼

虛擬dom的定義與作用

• 什么是虛擬dom

大家一定要記住的一點就是，虛擬dom就是一個普通的js物件，是一個用來描述真實dom結構的js物件，因為他不是真實dom，所以才叫虛擬dom，

• 虛擬dom的結構
  從下圖中，我們來看一看虛擬dom結構到底是怎樣的
  
  如上圖，這就是虛擬dom的結構，他是一個物件，下面有6個屬性，sel表示當前節點標簽名，data內是節點的屬性，elm表示當前虛擬節點對應的真實節點（這里暫時沒有），text表示當前節點下的文本，children表示當前節點下的其他標簽
  
• 虛擬dom的作用

1、我們都知道，傳統dom資料發送變化的時候，我們都需要不斷的去操作dom，才能更新dom的資料，雖然后面出現了模板引擎這種東西，可以讓我們一次性去更新多個dom，但模板引擎依舊沒有一種可以追蹤狀態的機制，當引擎內某個資料發生變化時，他依然要操作dom去重新渲染整個引擎，
而虛擬dom可以很好的跟蹤當前dom狀態，因為他會根據當前資料生成一個描述當前dom結構的虛擬dom，然后資料發送變化時，又會生成一個新的虛擬dom，而這兩個虛擬dom恰恰保存了變化前后的狀態，然后通過diff演算法，計算出兩個前后兩個虛擬dom之間的差異，得出一個更新的最優方法（哪些發生改變，就更新哪些），可以很明顯的提升渲染效率以及用戶體驗
2、因為虛擬dom是一個普通的javascript物件，故他不單單只能允許在瀏覽器端，渲染出來的虛擬dom可同時在node環境下或者weex的app環境下允許，有很好的跨端性

什么是diff演算法

diff演算法就是用于比較新舊兩個虛擬dom之間差異的一種演算法，具體詳情，后面我們會說

vue中的虛擬dom

目前虛擬dom的類別庫有多種，常見的有snabbdom和virtual-dom， vue以前用的是virtual-dom，從2.x版本后都是使用的snabbdom，(snabbdom原始碼下載) 今天，我們就通過snabbdom原始碼來決議vue的虛擬dom
首先我們看下snabbdom原始碼結構，

要搞清楚vue虛擬dom，我們就需要搞清楚幾個核心的方法

• h函式
• patch函式
• patchVnode函式
• updateChildren函式

這幾個核心函式的原始碼，看著可能會比較累，我就不一一對原始碼做詳細的介紹，我主要會介紹每個函式主要做了什么事情，然后后面再附上原始碼，會加點注釋，看的懂得可以詳細看看

h函式

h函式，看著是不是很眼熟？ 他是在vue的什么階段去呼叫的？

眼熟吧，是不是在這地方看過啊，沒錯，h函式就是在render函式內運行的，我們在前面vue生命周期的文章中就提過，vue在created–>beforeMount之間的時候會將模板編譯成render函式，其實就是將模板編譯成某種格式放在render函式內，然后當render函式運行得時候，就會生成虛擬dom，那么編譯成什么格式呢，就是編譯成h函式所認可的格式，那么我們來看看h函式需要什么格式

有的人可能會說，唉，這個h函式怎么定義了多個啊，沒錯，h函式是使用函式多載的方式定義的，那么什么是函式多載

函式多載

函式多載就是定義多個重名函式，利用函式的引數個數以及引數型別來區分，當引數個數不同，引數型別不同時，函式內執行的代碼也會相應不同，
下面，我們就來看下最典型得一種，也就是圖中得第四種，

• 第一個引數sel 表示dom 名稱，如： div
• 第二個引數表示dom屬性，是個物件如：{ class: ‘ipt’, value: ‘今天天氣很好’ }
• 第三個引數表示子節點，子節點也可以是一個子虛擬節點，也可以是文本節點

const vdom = h('div', { class: 'vdom'}, [
  h('p', { class: 'text'}, ['hello word']),
  h('input', { class: 'ipt', value: '今天星期二' })
]) // 模板就是會編譯成這種格式
console.log(vdom)

而h函式內最主要得就是執行了 vnode函式，vnode函式得主要作用就是將h函式傳進來得引數轉行為了js物件（即虛擬dom）

而vnode函式，我就不多說了，沒幾句代碼，也很簡單，反正就是執行了生成js物件（虛擬dom）的代碼，直接上圖

看到現在，我們心里應該要清楚虛擬dom是怎么生成的，什么時候生成的，如果不清楚，那么請往上滑，再看一遍，哈哈，下面我們總結下虛擬dom生成的程序，

• 首先，代碼初次運行，會走生命周期，當生命周期走到created到beforeMount之間的時候，會編譯template模板成render函式，然后當render函式運行時，h函式被呼叫，而h函式內呼叫了vnode函式生成虛擬dom，并回傳生成結果，故虛擬dom首次生成，
• 之后，當資料發生變化時會重新編譯生成一個新vdom，再后面就等待新 舊兩個vdom進行對比吧，我們后面就繼續說對比的事情，

diff 比較規則

1、diff 比較兩個虛擬dom只會在同層級之間進行比較，不會跨層級進行比較，而用來判斷是否是同層級的標準就是

1. 是否在同一層
2. 是否有相同的父級
   下面，我們來一張圖，就很好理解了（盜用網上一張很經典的圖）
   
   2、diff是采用先序深度優先遍歷得方式進行節點比較的，即，當比較某個節點時，如果該節點存在子節點，那么會優先比較他的子節點，直到所有子節點全部比較完成，才會開始去比較改節點的下一個同層級節點，不好理解嗎？沒關系，我們畫個圖看一下，就很清晰了
   
   當比較新舊兩個dom時，會按照圖中1-9的順序去進行比較，

不過，既然話都說到他的比較順序了，我就想干脆，先整體將他每一步是如何比較的，讓大家心里有一個總體的比較思路后，我們再去一步一步看patch函式，patchVnode函式和updateChildren函式

diff比較整體思路

首先開始比較兩個vdom時，這兩個vdom肯定是都有各自的根節點的，且根節點必定是一個元素，不可能存在多個，我們首先要比較的肯定是根節點，那我們都知道根節點只有一個，就可以直接比較了，而一個節點的比較，通常分為3個部分

宣告，下面所說的sel選擇器相同，指的是標簽名，id，class都相同，
例如
<div class=“abc” id=“app”>’這樣一個dom，他的sel是"div#app.abc"

• 比較兩個節點是否是相同節點，判斷是否是相同節點的條件是，key和sel（選擇器）必須都相同（那有的人可能會說了，那我標簽沒有key怎么辦啊，沒有key那就是undefined，undefined === undefined 始終為true，所以沒有key只需要保證sel相同就行），如果不相同，那么執行替換操作（即新增新vnode上的元素，洗掉舊vnode上的元素 例如，原來是div，新vnode變成了p，那么就是新增p元素，再洗掉div元素，相當于就是p替換了div），這一步，只有比較根節點時，是在patch函式中進行的，非根節點都是在updateChildren函式中執行的，因為根節點只會有一個，可以直接比較，而其他節點會存在多個，需要通過一些演算法來判斷，具體詳情后面會說
• 如果節點相同，那么進去第二部分，即比較兩個節點的屬性是否相同，節點是否存在文本，文本是否相同，是否存在子節點，子節點是否相同，這部分主要在patchVnode中執行
  那么，在第二部分，會做哪些事情呢，
  1、如果存在文本時，更新文本
  2、如果存在屬性時，更新屬性
  3、如果存在子節點時，更新子節點
  那么，如何更新呢，邏輯也很簡單，遵循以下規則：
  1、如果舊vnode上存在，而新vnode上不存在，那么執行洗掉操作
  2、如果舊vnode上不存在，而新vnode上存在，那么執行新增操作
  3、如果新舊vnode上都存在，那么執行替換操作（即，新增新的，洗掉舊的），文本，和屬性的替換是在這部分完成，而對于子節點，如果新vnode和舊vnode上都存在子節點時，那么會進入第三部分比較，比較子節點的差異，
• 第三部分，主要在updateChildren函式中執行，主要用于比較某個節點下的子節點差異，而在這里，就要用到diff的一個演算法了，具體怎么算，我們后面詳細說updateChildren時再說，

可能大家看的有點懵，沒關系，看完心里有個大概的步驟就好，下面我們再來詳細講每一步對應的函式

patch 函式

上面我們說了，patch是比較的開始，相當于是diff的入口，diff就是從這一步開始的，那么既然是開始，說明patch函式比較的肯定就是兩個新舊vdom的根節點了，所以，兩個vdom直接的比較，patch是只會觸發一次的，
作用：比較兩個虛擬dom根節點是否相同，下面我們看下主要的核心代碼

patchVnode

patchVnode 是用于比較兩個相同節點的子級（文本，或子節點）的一個函式，故它的呼叫總是在sameVnode判斷之后，只有判斷當前比較的兩個vnode相同時（這里我最后再解釋一次，兩個vnode相同僅僅代表key相同且sel選擇器相同），才會被執行，
但，在比對之前，會先判斷下oldVnode === vNode ，因為如果全等，代表子級肯定也完全相等，那么就沒必要對比了，直接return;

作用：對比新舊兩個節點，更新dom的子級（子級包含文本或者是子節點）
對比程序：

1、如果新vnode有text屬性

• 舊vnode是否有子節點，如果有，代表原來是子節點，現在變成文本了，那么洗掉子節點，并且設定vnode物件的真實dom的text值（使用setTextContent函式）
• 其他情況不用管，直接設定vnode物件的真實dom的text值
  

2、如果新vnode沒有text屬性

• 如果新vnode和舊vnode都存在子節點時，是不是要深度對比兩個vnode的子節點啊，這個時候會進入第三步，比較子節點（執行updateChildren）
  

• 如果只有新vnode有子節點，老vnode沒有，那么很簡單，執行添加節點的操作
  

• 如果只有舊vnode有子節點，新vnode沒有子節點，很明顯，要執行洗掉舊vnode子節點的操作
  

• 如果兩個vnode上都沒有子節點，但舊節點有text，那么很簡單，說明原來有文本，現在沒有了，清空vnode對應dom的text
  下面，我們看下整體代碼
  

updateChildren

終于到這最復雜的一步了，首先，我先說一下這一步的作用以及具體做了些什么
作用：用于比較新舊兩個vnode的子節點
那具體做了什么，怎么比較的，
比較規則

宣告：下文中所指的匹配上，指的就是判斷是否是sameVnode，即上文中所說的，key相同，sel選擇器相同

• 首先，會將新舊vnode的子節點（oldCh, Ch）提取出來，并分別加上兩個指標oldStart, oldEnd, newStart, newEnd，分別指向odlCh的第一個節點，oldCh的最后一個節點，Ch的第一個節點，Ch的最后一個節點
• 比較時，會優先拿oldStart<—>newStart，oldStart<—>newEnd，oldEnd<—>newStart，oldEnd<—>newEnd 兩兩進行對比，如果匹配上，那么會將舊節點對應的真實dom移到新節點的位置上，并將匹配上了的指標往中間移動，同時匹配上了的兩個節點會繼續指向patchVnode函式去進一步比對（指標的移動相當于永遠保持指標中間的節點還是尚未匹配狀態，已經匹配到的移到指標外面去）
• 如果上面4種比較都沒有匹配上，那么這個時候，有key和沒key處理方式就不一樣了，具體怎么處理，后面會細說，
• 當oldStart > oldEnd 或者 newStart > newEnd時，結束對比，此時
  1、如果是oldStart > oldEnd，代表oldCh都已匹配完成，而此時，如果newStart <= newEnd，那么代表 newStart 和 newEnd直接的節點為新增節點，那么真實dom會在當前newStart 和newEnd之間新增newStart 和 newEnd中間還未匹配的節點，
  2、如果是newStart > newEnd，代表Ch全都已經匹配完成，而此時，如果oldStart 和 newEnd之間還有節點，則說明，這些節點是原來存在的，但現在沒有了，此時真實dom洗掉這些節點，
  此時，比較結束，

下面，我們通過圖例來進一步理解

上圖表示的就是oldCh 和 Ch，那么怎么來比較，我們一一來看每一種情況

1. oldStart 和 newStart相同
   
   指標后移后，

2. oldStart 和 newEnd相同，此時會將oldStart對應的真實dom移動newEnd對應的位置
   我們就以上圖為例了，不重新畫圖了，上圖，oldStart 和 newEnd相同，此時真實dom會將b移動最末尾，同時oldStart 和 newEnd指標向中間移
   
3. oldEnd 和 newEnd相同 ，我們還是以上圖為例（就是這么巧，上圖剛好oldEnd和 newEnd相同，哈哈）c 和 c相同，oldEnd 和 newEnd往中間移動，并執行patchVnode（oldc，newc）
   
4. oldEnd和newStart相同的我們后面再畫，根據上圖，我們繼續將oldStart > oldEnd的情況，上圖中，oldStart 大于 oldEnd，說明oldCh已經全部匹配完，而此時newCh中，newStart 和 newEnd之間還有個e沒有匹配，那說明e是新增節點，此時真實dom會在newStart和newEnd之間新增還未匹配的dom（新增節點執行addVnodes函式）
   
   此時，整個oldCh和newCh的比較就已經完成了，可以看到，此時，真實dom已經變成和newCh的一樣了，
5. oldEnd 和 newStart 相同時
   
   此時，oldEnd所對應的真實dom會移動newStart所在位置，然后oldEnd 和 newStart指標往中間移動，移動后，如下圖
   
6. 當newStart > newEnd的時候，此時，如果oldStart 和 oldEnd之間還存在沒有匹配完成的節點時，那么認為，oldCh中，那么還沒匹配到的節點在新的虛擬dom樹上已經沒有了，此時，執行洗掉操作（removeVnodes函式），洗掉還oldStart和oldEnd之間的節點，
   
   好了，現在前面4種情況以及兩種匹配結束時的情況我們已經說完了，現在就剩最后一種情況，即：頭尾分別都沒匹配上，且沒有結束比較的時候，我們繼續來看第7種情況，
7. 當前面（1，2，3，5）這4種情況都匹配不到時，會拿當前newStart指標所指的那個節點去和oldCh中找，看是否能找到，這個時候，就要看是不是存在key了，因為首先，會建立一個oldCh中key和index的一個映射表，格式為{key: idx}，如果都沒有key，那么映射表為空物件{}，此時會有3種情況
   1、如果newStart指標所指的節點不存在key，那么不會去oldCh中尋找和這個一樣的節點，而是直接新增newStart所指的這個節點，新增后，newStart指標后移
   
   2、如果newStart指標所指的節點存在key，那么會去oldCh的key和Idx的映射表中尋找newStart節點的key是否存在，如果不存在，那么默認newStart節點為新增節點，真實dom會在newStart位置直接新增節點，新增完成后，指標后移
   
   3、同樣newStart指標所指的節點存在key，那么去oldCh的映射表中查找，此時如果找到了，那么會繼續判斷key相同的這兩個節點的sel選擇器是否相同，如果也相同，那么默認這是同一個節點，那么真實節點會將匹配到的節點，移到newStart對應的位置，然后執行patchVnode(oldVnode, newVnode)進行進一步對比，同時newStart指標后移，而oldCh中被匹配到的那個位置，置為undefined，
   

總體程序就是這樣，然后不停的patchVnode，updateChildren回圈遞回下去，知道oldVode和newVnode所有節點都對比完成，下面附上updateChildren函式原始碼(每一步都添加了詳細注釋)

function updateChildren (parentElm: Node,oldCh: VNode[],newCh: VNode[],insertedVnodeQueue: VNodeQueue) {
    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: KeyToIndexMap | undefined
    let idxInOld: number
    let elmToMove: VNode
    let before: any

    // 通過while不斷回圈進行對比，直到oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx
    while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
      if (oldStartVnode == null) { // 這一步的操作是始終保證oldStartVnode為oldStartIdx指標所指向的那個節點
        oldStartVnode = oldCh[++oldStartIdx]
      } else if (oldEndVnode == null) { // 這一步的操作是始終保證oldEndVnode為oldEndIdx指標所指向的那個節點
        oldEndVnode = oldCh[--oldEndIdx]
      } else if (newStartVnode == null) { // 這一步的操作是始終保證newStartVnode為newStartIdx指標所指向的那個節點
        newStartVnode = newCh[++newStartIdx]
      } else if (newEndVnode == null) { // 這一步的操作是始終保證newEndVnode為newEndIdx指標所指向的那個節點
        newEndVnode = newCh[--newEndIdx]
      } else if (sameVnode(oldStartVnode, newStartVnode)) { // oldStart和newStart相同時，執行patchVnode進一步比較
        patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue)
        oldStartVnode = oldCh[++oldStartIdx] // 并將指標往中間移動
        newStartVnode = newCh[++newStartIdx] // 并將指標往中間移動
      } else if (sameVnode(oldEndVnode, newEndVnode)) { // oldEnd和newEnd相同時，執行patchVnode進一步比較
        patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue)
        oldEndVnode = oldCh[--oldEndIdx] // 并將指標往中間移動
        newEndVnode = newCh[--newEndIdx] // 并將指標往中間移動
      } else if (sameVnode(oldStartVnode, newEndVnode)) { // oldStart和newEnd相同時，執行patchVnode進一步比較
        patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue)
        api.insertBefore(parentElm, oldStartVnode.elm!, api.nextSibling(oldEndVnode.elm!))
        oldStartVnode = oldCh[++oldStartIdx] // 并將指標往中間移動
        newEndVnode = newCh[--newEndIdx] // 并將指標往中間移動
      } else if (sameVnode(oldEndVnode, newStartVnode)) { // oldEnd和newStart相同時，執行patchVnode進一步比較
        patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue)
        api.insertBefore(parentElm, oldEndVnode.elm!, oldStartVnode.elm!)
        oldEndVnode = oldCh[--oldEndIdx] // 并將指標往中間移動
        newStartVnode = newCh[++newStartIdx] // 并將指標往中間移動
      } else { // 這里面就是當前面4種情況都不匹配時的處理結果
        if (oldKeyToIdx === undefined) {
          // 存在key的情況下 得到oldCh中 key和idx的一個映射關系，格式為{key: idx}, 
          oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx)
        }
        idxInOld = oldKeyToIdx[newStartVnode.key as string] // 通過key,找到當前key的節點在oldCh中的位置，如果找不到會回傳undefined
        if (isUndef(idxInOld)) { // 如果是undefind，說明newStartVnode的節點的key在oldCh中不存在，或者newStartVnode沒有key
          // 此時會直接創建新的節點，所以key的設定，會優化比較步驟
          api.insertBefore(parentElm, createElm(newStartVnode, insertedVnodeQueue), oldStartVnode.elm!)
        } else { // 如果找到了newStartVnode的可以在oldCh中的位置，說明可能只是移動了位置，
          elmToMove = oldCh[idxInOld] // 獲取需要移動的舊節點
          if (elmToMove.sel !== newStartVnode.sel) { // 如果舊節點和新節點的sel不同，代表變了（比如原來是div，現在變成了p）
            // 新增新的節點
            api.insertBefore(parentElm, createElm(newStartVnode, insertedVnodeQueue), oldStartVnode.elm!)
          } else { // sel相等，說明是相同節點，那么patchVnode進一步進行比較
            patchVnode(elmToMove, newStartVnode, insertedVnodeQueue)
            oldCh[idxInOld] = undefined as any
            // 真實節點移動到相應的位置
            api.insertBefore(parentElm, elmToMove.elm!, oldStartVnode.elm!)
          }
        }
        // newStart指標往中間移
        newStartVnode = newCh[++newStartIdx] 
      }
    }
    if (oldStartIdx <= oldEndIdx || newStartIdx <= newEndIdx) { // 如果比對結束
      if (oldStartIdx > oldEndIdx) { // newCh的start和end之間還有節點時，新增這些節點
        before = newCh[newEndIdx + 1] == null ? null : newCh[newEndIdx + 1].elm
        addVnodes(parentElm, before, newCh, newStartIdx, newEndIdx, insertedVnodeQueue)
      } else { // 否則 oldCh的start和end之間還有節點時，移除這些節點
        removeVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx)
      }
    }
  }

總結

我們在最后整理一下步驟，
1、比較兩個虛擬dom樹，對根節點root進行執行patch(oldVnode，newVnode)函式，比較兩個根節點是否是相同節點，如果不同，直接替換（新增新的，洗掉舊的）

2、如果相同，對兩個節點執行patchVnode（oldVnode, newVnode），比較屬性，文本，已經子節點，此時，要么新增，要么洗掉，要么直接修改文本內容，只有當都存在子節點時，并且oldVnode === newVnode 為false時，會執行updateChildren函式，去進一步比較他們的子節點，

3、比較分3大類，
第一類：oldStart === newStart， oldStart === newEnd，oldEnd === newStart，oldEnd === newEnd 這4種情況的比較，如果這4種情況中任何一種匹配，那么會執行patchVnode進一步比較，同時指標往中間移

第二類：oldStart > oldEnd 或者 newStart > newEnd時，表示匹配結束，此時，多余的元素洗掉，新增的元素新增，

第三類：上面幾種情況都不匹配，那么這個時候key是否存在，就起到關鍵性作用了，存在key時，可以直接通過key去找到節點的原來的位置，如果沒有找到，就新增節點，找到了，就移動節點位置，查找效率非常高
而如果沒有key呢，那么壓根就不會去原來的節點中查找了，而是直接新增這個節點，這就導致這個節點下的所有子節點都會被重新新增，會出現明顯的性能損耗，所以，合理的應用key，也是一種性能上的優化，

總之一句話，diff的程序，就是一個 patch —> patchVnode —> updateChildren —> patchVnode —> updateChildren —> patchVnode… 這樣的一個回圈遞回的程序

題外話 diff和資料劫持的共同作業原理

另外，我這里再插一句，可能有的人會疑惑了，那我通過這個虛擬dom的diff演算法，就能精準的知道被更新的地方在哪，然后去更新變動的部分，那我vue靠這個就夠了呀，我為什么還需要資料劫持呢，還需要getter，setter呢，沒錯，其實單單靠虛擬dom的diff確實是可以實作的，比如react就是這么做的，react精確查找資料的更新就是純用虛擬dom的diff的，
但是這會產生一個什么問題呢，當專案非常大的時候，dom樹是非常復雜的，如果每次一個小小的改動，就要通過diff演算法去精確找到改動的地方，那么這個計算量是非常大的，產生的性能損耗也會巨大，這顯然是不合理的，那么vue和react分別是怎么解決這個問題的

vue: 了解vueMVVM原理的人應該都清楚，vue通過Object.defineproperty的資料劫持，會劫持到每一個狀態資料，給他們加上getter，setter，并且創建一個發布者Dep,同時，會給依賴這個狀態資料的每個依賴者添加一個訂閱者watcher，這樣，當資料發生變化時，會觸發對應的setter，從而Dep會發布通知，通知每一個訂閱者watcher，然后watcher更新對應的資料，但是，如果任何一個資料的依賴我都增加一個watcher，那么專案中的watcher數量是會非常龐大的，細粒度太高，會帶來記憶體和依賴關系維護的巨大消耗，這樣一種情況下，vue采用回應式+diff的方式，通過回應式的getter,setter快速知道資料的變化發生在哪個組件中，然后組件內部再通過diff的方式去獲取更詳細的更新情況，并更新資料，

react: 而react卻是通過他的一個生命周期函式shouldComponentUpdate實作的，通過手動在這個生命周期函式中判斷當前組件的資料是否有發生變化，來決定當前組件是否需要更新，這樣，沒有發生狀態資料變化的組件就不需要進行diff，從而縮小diff的范圍，

好了，今天的文章就寫到這了，如果有問題，歡迎評論！！