請闡述 vue 的 diff 算法

diff是什麼？diff就是比較兩棵樹，render 會生成兩顆樹，一棵新樹 newVnode，一棵舊樹 oldVnode，然後兩棵樹進行對比更新找差異就是diff，全稱difference，在 vue 裏面 diff 算法是通過 patch 函數來完成的，所以有的時候也叫patch算法

⏳ diff 發生的時機

diff發生在什麼時候呢？當然我們可以說在數據更新的時候發生 diff，因爲數據更新會運行 render 函數得到虛擬 dom 樹，最後頁面重新渲染。

當組件創建的時候，組件所依賴的屬性或者數據變化時，會運行一個函數 (下面代碼中的updateComponent)，該函數會做兩件事：

運行_render生成一顆新的虛擬 dom 樹（vnode tree）
運行_updata，傳入_render 生成的虛擬 dom 樹的根節點，對新舊兩棵樹進行對比，最終完成對真實 dom 的更新

核心代碼如下，跟原代碼有所差異，但都差不多，是這麼個意思：

// vue構造函數
function Vue(){
  // ... 其他代碼
  var updateComponent = () => {
    this._update(this._render());
  }
  new Watcher(updateComponent);
  // ... 其他代碼
}

diff就發生在_update函數的運行過程中

代碼中先調用_render函數得到虛擬 dom 根節點，然後傳入_update函數中，在將updateComponent傳入Watcher中，watcher 可以監聽函數執行的過程，監測函數執行期間用到了哪些響應式數據並且進行依賴收集，關於 watcher 可以瞅瞅我上一篇文章：一文帶你瞭解 vue2 之響應式原理

🔨 _update 函數在幹什麼？

_update函數會接收到一個vonde參數，這就是新生成的虛擬 dom 樹，同時，_update 函數通過當前組件的_vnode屬性，拿到舊的虛擬 dom 樹。_update 函數首先會給組件的_vnode 屬性重新賦值，讓它指向新樹

簡單用代碼表示：

function update(vnode){
    //vnode新樹
    //this._vnode舊樹
    this._vnode = vnode
}

如果只考慮更新虛擬 dom 樹，這一步已經完成了，但是最終目的是要更新頁面，所以就要用到 diff 進行樹的節點對比，所以可以保存下舊樹 oldVnode 用於對比

簡單用代碼表示：

 <body>
    <div id="app"></div>
    <script src="./vue.js"></script>
    <script>
      const vm = new Vue({
        el: "#app",
      });


      function update(vnode) {
        //vnode新樹
        //this._vnode舊樹
        
        let oldVnode = vm._vnode; //保存舊樹
        
        this._vnode = vnode; //更新新樹
      }
    </script>
  </body>

對比oldVnode和vnode就行了，對比的目的就是更新真實 dom

接下來，會判斷舊樹 oldVnode 是否存在：

不存在：說明這是第一次加載組件，於是通過內部的 patch 函數，直接遍歷新樹，爲每個節點生成真實 DOM，然後掛載到每個節點的elm屬性上

簡單用代碼表示：

<body>
    <div id="app"></div>
    <script src="./vue.js"></script>
    <script>
      const vm = new Vue({
        el: "#app",
      });
      console.log(vm);

      function update(vnode) {
        //vnode新樹
        //this._vnode舊樹
        let oldVnode = vm._vnode; //保存舊樹
        this._vnode = vnode; //更新新樹

        //如果舊樹oldVnode不存在
        if(!oldVnode){
            this.__patch__(vm.$el,vnode);
        }
      }
    </script>
  </body>

存在：說明之前已經渲染過該組件，於是通過內部的 patch 函數，對新舊兩棵樹進行對比，從而達到下面兩個目標：

完成對所有真實 dom 的最小化處理
讓新樹的節點對應合適的真實 dom

🙌 patch 函數的對比流程

術語解釋：一會看到以下字眼，均代表以下意思

1.「相同」：是指兩個虛擬節點的標籤類型和 key 值均相同，但 input 元素還要看 type 屬性。這個術語在 vue 源碼中叫sameVnode，它是一個函數，用來判斷兩個虛擬節點是不是同一個節點

例：兩個虛擬節點 div 是否相同

<div>法醫</div>
<div>前端獵手</div>

標籤類型都爲div，key 值不僅僅在 v-for 遍歷中，也可以用在任何標籤中，上面兩個 div 中沒有 key 值，所以都爲undefined，所以標籤類型和 key 值都相同，不用看內容是否相同，它是另一個節點：文本節點

<div key="fayi">法醫</div>
<div key="qdls">前端獵手</div>

上面兩個虛擬節點是不同的，因爲 key 值不同

 <input type="text">
 <input type="radio">

上面兩個虛擬節點是不同的，因爲 input 不僅僅要看 key 值和標籤類型，還要看 type 是否相同

2.「新建元素」：是指根據一個虛擬節點提供的信息，創建一個真實 dom 元素，同時掛載到虛擬節點的 elm 屬性上

3.「銷燬元素」：是指：vnode.elm.remove()

4.「更新」：是指對兩個虛擬節點進行對比更新，它僅發生在兩個虛擬節點「相同」的情況下。具體過程稍後描述。

5.「對比子節點」：是指對兩個虛擬節點的子節點進行對比，具體過程稍後描述

詳細流程

根節點比較

patch 函數首先對根節點進行對比

如果兩個節點：

「相同」，進入 「更新」 流程

將舊節點的真實 dom 賦值到新節點：newVnode.elm = oldVnode.elem，舊節點會被垃圾回收機制回收
對比新節點和舊節點的屬性，有變化的更新到真實 dom 中
當前新舊兩個節點處理完成，開始 「對比子節點」

不 「相同」

新節點遞歸， 「新建元素」
舊節點 「銷燬元素」

對比子節點

虛擬 dom 樹已經完成，就剩修改真實 dom 了，但是修改真實 dom 的效率是比較耗時的，vue 的原則是能不改就不改，儘量啥也別做，在「對比子節點」時，vue 一切的出發點，都是爲了：

儘量啥也別做
不行的話，儘量僅改動元素屬性
還不行的話，儘量移動元素，而不是刪除和創建元素
實在不行的話，刪除和創建元素

對比流程：

圖片說明：

黃色圓圈：表示舊子節點和新子節點所對應的相同節點類型
數字：表示 key 值，用來區分是不是同一個節點
藍色方塊：表示對比之前舊子節點所對應的真實 dom
箭頭：分別表示頭指針和尾指針

接下來，我們要做的就是對比舊子節點和新子節點之間的差異，目標是改變真實dom，並且將新虛擬子節點對應到真實 dom 裏面去，vue 使用兩個指針分別指向新舊子節點樹的頭和尾

步驟：

首先對比新樹和舊樹的頭指針，瞅瞅兩個節點是否一樣，從圖中可以看到是一樣的，如果一樣則進入 「更新」 流程：先將舊節點的真實 dom 賦值到新節點（真實 dom 連線到新子節點），然後循環對比新舊節點的屬性，看看有沒有不一樣的地方，將有變化的更新到真實 dom 中，最後還要採用深度優先（一顆樹的節點走到盡頭，再走另一個節點）的方式遞歸循環這兩個新舊子節點是否還有子節點，如果存在，則同理，這裏我們就假設它不存子節點。灰色表示已經處理完成，然後兩個頭指針往後移動

接下來，繼續比較兩個頭指針，看看兩個節點是否一樣，很明顯，兩個節點是不一樣的，因爲 key 值不同，不一樣的時候它不會銷燬刪除從建立，喫個🍗壓壓驚，淡定！前面有提到儘量別操作 dom，它一定會找到一樣的節點，一條道走到黑，然後會對比尾指針，可以看到尾指針是一樣的，跟第一步是一樣的：一頓操作猛如虎，先將舊節點的真實 dom 賦值到新節點（真實 dom 連線到新子節點），然後循環對比新舊節點的屬性，將有變化的更新到真實 dom 中，接着還要遞歸循環這兩個新舊子節點是否還有子節點，最後兩個尾指針往前移動

然後繼續比較頭指針，很明顯不一樣，尾指針呢？也不一樣，因爲 key 值還是不一樣。隨後它會比較頭指針和尾指針，看看是否一樣，可以看到舊節點的圓 2 頭指針和新節點圓 2 尾指針是一樣的，所以操作跟前兩步是一樣的，又是一頓操作猛如虎，結果如下圖：

這裏我們要注意的是真實 dom 必須和新虛擬子節點要一一對應上的，所以除了更新變化的地方之外還要進行位置移動，移動到舊樹尾指針的後面，最後舊樹頭指針往後移動，新樹尾指針往前移動，如下圖：

繼續比對，新舊頭指針不同，尾指針不同，兩個頭尾也不同，然後它會以新樹頭指針爲基準，循環舊虛擬子節點，看看新樹圓 3 是否存在於舊虛擬子節點，存在的話在哪個位置，找到之後進行復用，連線，有變化的地方更新到真實 dom，操作跟前面幾步一樣，真實 dom 也要進行位置移動，移動到舊樹頭指針之前。隨後新樹頭指針繼續往後移動到圓 9 位置，如下圖:

繼續比對，新舊頭指針不同，尾指針不同，但新樹頭指針和舊樹尾指針相同，操作跟前面幾步相同，但依然需要進行位置移動，移動到舊樹頭指針之前。隨後新樹頭指針往後移動，與新樹尾指針重合，舊樹尾指針向前移動到圓 1 位置，如下圖：

繼續比對，新舊兩樹頭指針不同，尾指針不同，兩個頭尾也不同，然後它以新樹頭指針爲基準，循環舊虛擬子節點，找圓 8 在舊樹中存不存在，從圖中可以看出，並不存在，這個時候確實沒辦法了，只能 「新建元素」。隨後新樹頭指針繼續向後移動到圓 2 位置，如圖：

當頭指針移動到圓 2 位置時，頭指針已經不再是有效的了，當頭指針超過尾指針的時候，循環結束，從過程我們可以看到新樹先循環完成，但是舊樹還有剩餘的節點，這說明舊樹中剩餘的節點都是應該被刪除的節點，所對應的真實 dom 也會被移除

最終真實 dom 生成完畢，整個過程我們只新建了一個元素，如下圖：

在面試的時候也會被問到關於 diff 算法的問題，以下是參考回答：

當組件創建和更新時，vue 會執行內部的 update 函數，該函數使用 render 函數生成的虛擬 dom 樹，將新舊兩樹進行對比，找到差異點，最終更新到真實 dom

對比差異的過程叫 diff，vue 在內部通過一個叫 patch 的函數完成該過程

在對比時，vue 採用深度優先、同級比較的方式進行比對。同級比較就是說它不會跨越結構進行比較

在判斷兩個節點是否相同時，vue 是通過虛擬節點的 key 和 tag 來進行判斷的

具體來說，首先對根節點進行對比，如果相同則將舊節點關聯的真實 dom 的引用掛到新節點上，然後根據需要更新屬性到真實 dom，然後再對比其子節點數組；如果不相同，則按照新節點的信息遞歸創建所有真實 dom，同時掛到對應虛擬節點上，然後移除掉舊的 dom。

在對比其子節點數組時，vue 對每個子節點數組使用了兩個指針，分別指向頭尾，然後不斷向中間靠攏來進行對比，這樣做的目的是儘量複用真實 dom，儘量少的銷燬和創建真實 dom。如果發現相同，則進入和根節點一樣的對比流程，如果發現不同，則移動真實 dom 到合適的位置。

這樣一直遞歸的遍歷下去，直到整棵樹完成對比。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/fbI_su3_unxvwsAgCKMOpA

⏳ diff 發生的時機

🔨 _update 函數在幹什麼？

🙌 patch 函數的對比流程

術語解釋： 一會看到以下字眼，均代表以下意思

詳細流程

猜你喜歡

術語解釋：一會看到以下字眼，均代表以下意思