深入淺析Vue2中的Diff演演算法

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

因為之前看面試直播也經常問到 Diff 演演算法，然後作者本人用 Vue2 比較多，所以打算研究一下 Vue2 的 Diff 演演算法，其實很早就想學的，但是可能因為感覺 Diff 演演算法比較深奧，就一直拖著沒學，但是最近在準備面試，就想著遲早都要學的，趁這個機會把 Diff 演演算法搞懂吧 ?，作者就花了一天的時間研究了一下，可能沒有完全理解 Diff 演演算法的精髓，請各位見諒。

? 這個其實算作者的學習筆記，而且作者水平有限，改文章僅代表作者個人觀點，如果有錯誤可以評論區指出來，會不斷完善；同時本文很長，所以請讀者們有耐心的看完，看完後作者相信你們會對 Diff 演演算法有更深的瞭解。本人覺得本文比目前網上講解 Diff 演演算法的大部分文章要更好，因為本文從問題出發，教會大家如何思考，而不是直接從答案出發，就像讀答案一樣，這樣感覺沒什麼意思，本文一步一步的引導大家去感受 Diff 演演算法的精妙，同時最後也做了一下小實驗，讓大家對 Diff 演演算法有更加直觀的感受 ?。

為什麼要用 Diff 演演算法

虛擬 DOM

因為 Vue2 底層是用虛擬 DOM 來表示頁面結構的，虛擬 DOM其實就是一個物件，如果想知道怎麼生成的，其實大概流程就是：

首先解析模板字串，也就是 .vue 檔案
然後轉換成 AST 語法樹
接著生成 render 函數
最後呼叫 render 函數，就能生成虛擬 DOM 【相關推薦：、】

最小量更新

其實框架為了效能才使用的虛擬 DOM，因為 js 生成 DOM 然後展示頁面是很消耗效能的，如果每一次的更新都把整個頁面重新生成一遍那體驗肯定不好，所以需要找到兩個頁面中變化的地方，然後只要把變化的地方用 js 更新 (可能是增加、刪除或者更新) 一下就行了，也就是最小量更新。那麼怎麼實現最小量更新呢？那麼就要用 Diff 演演算法了，那麼 Diff 演演算法對比的到底是什麼呢？可能這是剛學 Diff 演演算法比較容易誤解的地方，其實比對的是新舊虛擬 DOM，所以 Diff 演演算法就是找不同，找到兩次虛擬 DOM 的不同之處，然後將不同反應到頁面上，這就實現了最小量更新，如果只更新變化的地方那效能肯定更好。

頁面更新流程

其實這個比較難解釋，作者也就大致說一下，學了 Vue 的都知道這個框架的特點之一就有資料響應式，什麼是響應式，也就是資料更新頁面也更新，那麼頁面是怎麼知道自己要更新了呢？其實這就是這個框架比較高明的地方了，大致流程如下：

之前也說了會執行 render 函數，那麼執行 render 函數的時候會被資料劫持，也就是進入 Object.defineProperty 的 get，那麼在這裡收集依賴，那麼是誰收集依賴呢？是每個元件，每個元件就是一個 Watcher，會記錄這個元件內的所有變數 (也就是依賴)，當然每個依賴 (Dep) 也會收集自己所在元件的 Watcher；
然後當頁面中的資料發生變化，那麼就會出發 Object.defineProperty 的 set，在這個函數裡面資料就會通知每個 Watcher 更新頁面，然後每個頁面就會呼叫更新方法，這個方法就是 patch；
接著，就要找到兩個頁面之間的變化量，那麼就要用到 Diff 演演算法了
最後找到變化量後就可以進行更新頁面了

其實是邊找邊更新的，為了讓大家理解容易就將這兩個部分分開了

Diff 演演算法簡單介紹

面試問到 Diff 演演算法是什麼，大家肯定會說兩句，比如 頭頭、尾尾、尾頭、頭尾、深度優先遍歷(dfs)、同層比較 類似這些話語，雖然能說一兩句其實也是淺嘗輒止。其實作者看了 CSDN 上發的關於 Diff 演演算法的文章，就是閱讀量很高的文章，作者覺得他也沒講明白，可能他自己沒明白，或者自己明白了但是沒講清楚，那麼作者會用自己的感悟和大家分享一下。

Diff 演演算法的前提

為了讓大家能夠了解清楚，這裡先說明一下函數呼叫流程：

patch
patchVnode
updateChildren

Diff 演演算法的 前提 這個是很重要的，可能大家會問什麼是前提？不就是之前說的那些比較嘛？說的沒錯但也不對，因為 Diff 演演算法到達之前說的 頭頭、尾尾、尾頭、頭尾 這一步的前提就是兩次對比的節點是 相同的，這裡的相同不是大家想的完全相同，只是符合某些條件就是相同了，為了簡化說明，文章就只考慮一個標籤只包含 key 和 標籤名(tag)，那麼之前說的相同就是 key 相同以及 tag 相同，為了證明作者的說法是有點正確的，那麼這裡也貼上原始碼：

// https://github.com/vuejs/vue/blob/main/src/core/vdom/patch.ts
// 36行
function sameVnode(a, b) {
  return (
    a.key === b.key &&
    a.asyncFactory === b.asyncFactory &&
    ((a.tag === b.tag &&
      a.isComment === b.isComment &&
      isDef(a.data) === isDef(b.data) &&
      sameInputType(a, b)) ||
      (isTrue(a.isAsyncPlaceholder) && isUndef(b.asyncFactory.error)))
  )
}
登入後複製

如果怕亂了，下面的可以省略不看也沒事不影響整體瞭解，下面只是為了考慮所有情況才加的一個判斷：那麼如果兩個虛擬 DOM 不相同其實就不用繼續比較了，而且如果相同也不用比較了，這裡的相同是真的完全相同，也就是兩個虛擬 DOM 的地址是一樣的，那麼也貼上原始碼：

function patchVnode(......) {
  if (oldVnode === vnode) {
    return
  }
  ......
}
登入後複製

到目前為止大家可能會比較亂，現在總結一下：

在 patch 函數裡比較的是新老虛擬 DOM 是否是 key 相同以及 tag 相同，如果不相同那麼就直接替換，如果相同用 patchVnode

說了這麼多，其實作者也就想表達一個觀點，就是隻有當兩次比較的虛擬 DOM 是 相同的 才會考慮 Diff 演演算法，如果不符合那直接把原來的刪除，替換新的 DOM 就行了。

patchVnode 函數

這個函數裡的才是真正意義上的 Diff 演演算法，那麼接下來會結合原始碼向大家介紹一下。

原始碼中核心程式碼在的 638 行至 655 行。

其實，目前介紹 patchVnode 的都是直接對著原始碼來介紹的，但是大家可能不清楚為啥要這麼分類，那麼作者在這裡就讓大家明白為什麼這麼分類，首先在這裡說一個結論：

就是 text 屬性和 children 屬性不可能同時存在，這個需要大家看模板解析原始碼部分

那麼在對比新舊節點的情況下，主要比較的就是是否存在 text 和 children 的情況，那麼會有如下九種情況

情況	老節點 text	老節點 children	新節點 text	新節點 children
1	❎	❎	❎	❎
2	❎	✅	❎	❎
3	✅	❎	❎	❎
4	❎	❎	❎	✅
5	❎	✅	❎	✅
6	✅	❎	❎	✅
7	❎	❎	✅	❎
8	❎	✅	✅	❎
9	✅	❎	✅	❎

按照上面的表格，因為如果新節點有文位元組點，其實老節點不管是什麼都會被替換掉，那麼就可以按照 新節點 text 是否存在來分類，其實 Vue 原始碼也是這麼來分類的：

if (isUndef(vnode.text)) {
  // 新虛擬 DOM 有子節點
} else if (oldVnode.text !== vnode.text) {
  // 如果新虛擬 DOM 是文位元組點，直接用 textContent 替換掉
  nodeOps.setTextContent(elm, vnode.text)
}
登入後複製

那麼如果有子節點的話，那應該怎麼分類呢？我們可以按照每種情況需要做什麼來進行分類，比如說：

第一種情況，我們啥都不用做，因此也可以不用考慮
第二種情況，我們應該把原來 DOM 的 textContent 設定為 ''
第三種情況，我們也應該把原來 DOM 的 textContent 設定為 ''
第四種情況，我們應該加入新的子節點
第五種情況，這個情況比較複雜，需要對比新老子節點的不同
第六種情況，我們應該把原來的 textContent 設定為 '' 後再加入新的子節點

那麼通過以上六種情況 (新虛擬 DOM 不含有 text，也就是不是文位元組點的情況)，我們可以很容易地進行歸類：

分類 1️⃣： 第二種情況 和 第三種情況。進行的是操作是：把原來 DOM 的 textContent 設定為 ''
分類 2️⃣： 第四種情況 和 第六種情況。進行的是操作是：如果老虛擬 DOM 有 text，就置空，然後加入新的子節點
分類 3️⃣：第五種情況。進行的是操作是：需要進行精細比較，即對比新老子節點的不同

其實原始碼也是這麼來進行分類的，而且之前說的 同層比較 也就得出來了，因為每次比較都是比較的同一個父節點每一個子元素 (這裡的子元素包括文位元組點和子節點) 是否相同，而 深度優先遍歷(dfs) 是因為每次比較中，如果該節點有子節點 (這裡的子節點指的是有 children 屬性，而不包括文位元組點) 的話需要進行遞迴遍歷，知道最後到文位元組點結束。

⭕️ 這裡需要搞清楚子節點和子元素的區別和聯絡

然後我們來看看原始碼是怎麼寫吧，只看新虛擬 DOM 不含有 text，也就是不是文位元組點的情況：

if (isUndef(vnode.text)) {
  if (isDef(oldCh) && isDef(ch)) {
    if (oldCh !== ch)
      // 遞迴處理，精細比較
      // 對應分類 3️⃣
      updateChildren(elm, oldCh, ch, insertedVnodeQueue, removeOnly)
  } else if (isDef(ch)) {
    if (__DEV__) {
      checkDuplicateKeys(ch) // 可以忽略不看
    }
    // 對應分類 2️⃣
    if (isDef(oldVnode.text)) nodeOps.setTextContent(elm, '')
    addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue)
  } else if (isDef(oldCh)) {
  	// 對應分類 1️⃣
    removeVnodes(oldCh, 0, oldCh.length - 1)
  } else if (isDef(oldVnode.text)) {
  	// 對應分類 1️⃣
    nodeOps.setTextContent(elm, '')
  }
}
登入後複製

❓我們可以看到原始碼把分類 1️⃣ 拆開來了，這是因為如果老虛擬 DOM 有子節，那麼可能繫結了一些函數，需要進行解綁等一系列操作，作者也沒自信看，大致瞄了一眼，但是如果我們要求不高，如果只是想自己手動實現 Diff 演演算法，那麼沒有拆開的必要。

作者覺得這麼講可能比網上其他介紹 Diff 演演算法的要好，其他的可能直接給你說原始碼是怎麼寫的，可能沒有說明白為啥這麼寫，但是通過之前這麼分析講解後可能你對為什麼這麼寫會有更深的理解和幫助吧。

updateChildren 函數

同層比較

因為當都含有子節點，即都包含 children 屬性後，需要精細比較不同，不能像之前那些情況一樣進行簡單處理就可以了那麼這個函數中就會介紹大家經常說的 頭頭、尾尾、尾頭、頭尾 比較了，其實這不是 Vue 提出來的，是很早就提出來的演演算法，就一直沿用至今，大家可以參考

? 在這之前我們要定義四個指標 newStartIdx、newEndIdx、oldStartIdx 和 oldEndIdx，分別指向 新頭節點、新尾節點、舊頭節點 與 舊尾節點

迴圈條件如下：

while(oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
  ......
}
登入後複製

其實這個比較也就是按人類的習慣來進行比較的，比較順序如下：

1️⃣ 新頭節點與舊頭節點：++newStartIdx 和 ++oldStartIdx
2️⃣ 新尾節點與舊尾節點：--newEndIdx 和 --oldEndIdx
3️⃣ 新尾節點與舊頭節點：需要將 舊頭節點 移動到 舊尾節點之前，為什麼要這麼做，講起來比較複雜，記住就好，然後 --newEndIdx 和 ++oldStartIdx
4️⃣ 新頭節點與舊尾節點：需要將 舊尾節點 移動到 舊頭節點之前，為什麼要這麼做，講起來比較複雜，記住就好，然後 ++newStartIdx 和 --oldEndIdx
5️⃣ 如果都沒有匹配的話，就把 新頭節點 在舊節點列表 (也就是 children 屬性的值) 中進行查詢，查詢方式按照如下：
- 如果有 key 就把 key 在 oldKeyToIdx 進行匹配，oldKeyToIdx 根據舊節點列表中元素的 key 生成對應的下標
- 如果沒有，就按順序遍歷舊節點列表找到該節點所在的下標
- 如果在舊節點列表是否找到也分為兩種情況：
  - 找到了，那麼只要將 新頭節點 新增到 舊頭節點 之前即可
  - 沒找到，那麼需要建立新的元素然後新增到 舊頭節點 之前
  - 然後把這個節點設定為 undefined

根據迴圈條件我們可以得到兩種剩餘情況，如下：

6️⃣ 如果 oldStartIdx > oldEndIdx 說明老節點先遍歷完成，那麼新節點比老節點多，就要把 newStartIdx 與 newEndIdx 之間的元素新增
7️⃣ 如果 newStartIdx > newEndIdx 說明新節點先遍歷完成，那麼老節點比新節點多，就要把 oldStartIdx 與 oldEndIdx 之間的元素刪除

其實我們上面還沒有考慮如果節點為 undefined 的情況，因為在上面也提到過，如果四種都不匹配後會將該節點置為 undefined，也只有舊節點列表中才有，因此要在開頭考慮這兩種情況：

8️⃣ 當 oldStartVnode 為 undefined：++oldStartIdx
9️⃣ 當 oldEndVnode 為 undefined：--oldEndIdx

那麼我們來看原始碼怎麼寫的吧，其中用到的函數可以檢視原始碼附錄：

// https://github.com/vuejs/vue/blob/main/src/core/vdom/patch.ts
// 439 行至 556 行
while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
  if (isUndef(oldStartVnode)) {
  	// 情況 8️⃣
    oldStartVnode = oldCh[++oldStartIdx] // Vnode has been moved left
  } else if (isUndef(oldEndVnode)) {
  	// 情況 9️⃣
    oldEndVnode = oldCh[--oldEndIdx]
  } else if (sameVnode(oldStartVnode, newStartVnode)) {
  	// 情況 1️⃣
    patchVnode(...)
    oldStartVnode = oldCh[++oldStartIdx]
    newStartVnode = newCh[++newStartIdx]
  } else if (sameVnode(oldEndVnode, newEndVnode)) {
  	// 情況 2️⃣
    patchVnode(...)
    oldEndVnode = oldCh[--oldEndIdx]
    newEndVnode = newCh[--newEndIdx]
  } else if (sameVnode(oldStartVnode, newEndVnode)) {
    // Vnode moved right
    // 情況 3️⃣
    patchVnode(...)
    canMove &&
      nodeOps.insertBefore(
        parentElm,
        oldStartVnode.elm,
        nodeOps.nextSibling(oldEndVnode.elm)
      )
    oldStartVnode = oldCh[++oldStartIdx]
    newEndVnode = newCh[--newEndIdx]
  } else if (sameVnode(oldEndVnode, newStartVnode)) {
    // Vnode moved left
    // 情況 4️⃣
    patchVnode(...)
    canMove &&
      nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm)
    oldEndVnode = oldCh[--oldEndIdx]
    newStartVnode = newCh[++newStartIdx]
  } else {
  	// 情況 5️⃣
    if (isUndef(oldKeyToIdx)) // 建立 key -> index 的 Map
      oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx) 
    // 找到 新頭節點 的下標
    idxInOld = isDef(newStartVnode.key)
      ? oldKeyToIdx[newStartVnode.key]
      : findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx)
    if (isUndef(idxInOld)) {
      // New element
      // 如果沒找到
      createElm(...)
    } else {
      // 如果找到了
      vnodeToMove = oldCh[idxInOld]
      if (sameVnode(vnodeToMove, newStartVnode)) {
        patchVnode(...)
        oldCh[idxInOld] = undefined
        canMove &&
          nodeOps.insertBefore(
            parentElm,
            vnodeToMove.elm,
            oldStartVnode.elm
          )
      } else {
        // same key but different element. treat as new element
        createElm(...)
      }
    }
    newStartVnode = newCh[++newStartIdx]
  }
}
if (oldStartIdx > oldEndIdx) {
  // 情況 6️⃣
  refElm = isUndef(newCh[newEndIdx + 1]) ? null : newCh[newEndIdx + 1].elm
  addVnodes(...)
} else if (newStartIdx > newEndIdx) {
  // 情況 7️⃣
  removeVnodes(...)
}
登入後複製

如果問為什麼這麼比較，回答就是經過很多人很多年的討論得出的，其實只要記住過程就行了，如果想要更深瞭解 Diff 演演算法，可以去 B 站看

v-for 中為什麼要加 key

這個問題面試很常見，但是可能大部分人也就只會背八股，沒有完全理解，那麼經過以上的介紹，我們可以得到自己的理解：

首先，如果不加 key 的話，那麼就不會去 Map 裡匹配 (O(1))，而是迴圈遍歷整個列表 (O(n))，肯定加 key 要快一點，效能更高
其次，如果不加 key 那麼在插入或刪除的時候就會出現，原本不是同一個節點的元素被認為是相同節點，上面也有說過是 sameVnode 函數判斷的，因此可能會有額外 DOM 操作

為什麼說可能有額外 DOM 操作呢？這個和插入的地方有關，之後會討論，同理刪除也一樣

證明 key 的效能

我們分為三個實驗：沒有 key、key 為 index、key 唯一，僅證明加了 key 可以進行最小化更新操作。

實驗程式碼

有小夥伴評論說可以把程式碼貼上這樣更好，那麼作者就把程式碼附上 ?：

<!DOCTYPE html>
<html>

<head>
  <meta charset="UTF-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>Document</title>
  <script src="https://cdn.jsdelivr.net/npm/vue@2/dist/vue.js"></script>
  <style>
    .box {
      display: flex;
      flex-direction: row;
    }
    .item {
      flex: 1;
    }
  </style>
</head>

<body>
  <div id="app">
    <div>
      <div>
        <h3>沒有 key</h3>
        <p v-for="(item, index) in list">{{ item }}</p>
      </div>
      <div>
        <h3>key 為 index</h3>
        <p v-for="(item, index) in list" :key="index">{{ item }}</p>
      </div>
      <div>
        <h3>key 唯一</h3>
        <p v-for="(item, index) in list" :key="item">{{ item }}</p>
      </div>
    </div>
    <button @click="click1">push(4)</button>
    <button @click="click2">splice(1, 0, 666)</button>
    <button @click="click3">unshift(999)</button>
    <br /><br />
    <button @click="click4">pop()</button>
    <button @click="click5">splice(1, 1)</button>
    <button @click="click6">shift()</button>
  </div>
  <script>
    var app = new Vue({
      el: '#app',
      data: {
        show: false,
        list: [1, 2, 3],
      },
      methods: {
        click1() {
          this.list.push(4);
        },
        click2() {
          this.list.splice(1, 0, 666);
        },
        click3() {
          this.list.unshift(999);
        },
        click4() {
          this.list.pop();
        },
        click5() {
          this.list.splice(1, 1);
        },
        click6() {
          this.list.shift();
        }
      },
    })
  </script>
</body>

</html>
登入後複製

增加實驗

實驗如下所示，我們首先更改原文字，然後點選按鈕**「觀察節點發生變化的個數」**：

在隊尾增加

在這裡插入圖片描述

在隊內增加

在這裡插入圖片描述

在隊首增加

在這裡插入圖片描述

刪除實驗

在隊尾刪除

在這裡插入圖片描述

在隊內刪除

在這裡插入圖片描述

在隊首刪除

在這裡插入圖片描述

實驗結論

增加實驗

表格為每次實驗中，每種情況的最小更新量，假設列表原來的長度為 n

實驗	沒有 key	key 為 index	key 唯一
在隊尾增加	1	1	1
在隊中增加	n - i + 1	n - i + 1	1
在隊首增加	n + 1	n + 1	1

刪除實驗

表格為每次實驗中，每種情況的最小更新量，假設列表原來的長度為 n

實驗	沒有 key	key 為 index	key 唯一
在隊尾刪除	1	1	1
在隊中刪除	n - i	n - i	1
在隊首刪除	n	n	1

通過以上實驗和表格可以得到加上 key 的效能和最小量更新的個數是最小的，雖然在 在隊尾增加 和 在隊尾刪除 的最小更新量相同，但是之前也說了，如果沒有 key 是要回圈整個列表查詢的，時間複雜度是 O(n)，而加了 key 的查詢時間複雜度為 O(1)，因此總體來說加了 key 的效能要更好。

寫在最後

本文從原始碼和實驗的角度介紹了 Diff 演演算法，相信大家對 Diff 演演算法有了更深的瞭解了，如果有問題可私信交流或者評論區交流，如果大家喜歡的話可以點贊 ➕ 收藏 ?

原始碼函數附錄

列舉一些原始碼中出現的簡單函數

setTextContent

function setTextContent(node: Node, text: string) {
  node.textContent = text
}
登入後複製

isUndef

function isUndef(v: any): v is undefined | null {
  return v === undefined || v === null
}
登入後複製

isDef

function isDef<T>(v: T): v is NonNullable<T> {
  return v !== undefined && v !== null
}
登入後複製

insertBefore

function insertBefore(
  parentNode: Node,
  newNode: Node,
  referenceNode: Node
) {
  parentNode.insertBefore(newNode, referenceNode)
}
登入後複製

nextSibling

function nextSibling(node: Node) {
  return node.nextSibling
}
登入後複製

createKeyToOldIdx

function createKeyToOldIdx(children, beginIdx, endIdx) {
  let i, key
  const map = {}
  for (i = beginIdx; i <= endIdx; ++i) {
    key = children[i].key
    if (isDef(key)) map[key] = i
  }
  return map
}
登入後複製

（學習視訊分享：、）

以上就是深入淺析Vue2中的Diff演演算法的詳細內容，更多請關注TW511.COM其它相關文章！

情況	老節點 text	老節點 children	新節點 text	新節點 children
1	❎	❎	❎	❎
2	❎	✅	❎	❎
3	✅	❎	❎	❎
4	❎	❎	❎	✅
5	❎	✅	❎	✅
6	✅	❎	❎	✅
7	❎	❎	✅	❎
8	❎	✅	✅	❎
9	✅	❎	✅	❎

情況	老節點 text	老節點 children	新節點 text	新節點 children
1	❎	❎	❎	❎
2	❎	✅	❎	❎
3	✅	❎	❎	❎
4	❎	❎	❎	✅
5	❎	✅	❎	✅
6	✅	❎	❎	✅
7	❎	❎	✅	❎
8	❎	✅	✅	❎
9	✅	❎	✅	❎

情況	老節點 text	老節點 children	新節點 text	新節點 children
1	❎	❎	❎	❎
2	❎	✅	❎	❎
3	✅	❎	❎	❎
4	❎	❎	❎	✅
5	❎	✅	❎	✅
6	✅	❎	❎	✅
7	❎	❎	✅	❎
8	❎	✅	✅	❎
9	✅	❎	✅	❎