本篇文章帶大家了解一下Vue2中的雙端diff算法，并聊聊Vue2 是如何更新節(jié)點的，希望對大家有所幫助！

今天我們來聊聊 Vue2 的雙端 diff 算法。（學習視頻分享：vue視頻教程）

為什么要聊呢，最直白的原因就是面試會考，當面試官問你 key 的作用，十有八九都會引到 diff 算法。

沒辦法，面試問咱們就只能學，好在也不怎么難，跟著我一起看看吧。

篇幅原因，本文并不會介紹虛擬 DOM 樹是如何生成的，僅講解在數(shù)據(jù)更新時，是如何比較兩顆虛擬 DOM 樹并更新真實 DOM 的，主要實現(xiàn) Vue2 源碼中的 patchVnode、updateChildren 函數(shù)

預備知識

diff 算法作用

聊 diff 算法前得認識一下它是干嘛的。

我們知道在網(wǎng)頁運行中，我們改變一些數(shù)據(jù)，它們可能會影響到 DOM 樹。如何在頁面中展示最新的數(shù)據(jù)呢，最簡單的方式就是整棵樹推到重建，當然這樣會導致大量的浪費，所以 Vue 使用虛擬 DOM 保存頁面中 DOM 樹的狀態(tài)，在數(shù)據(jù)變化后，構建一棵新的虛擬 DOM 樹，找到前后兩顆樹的不同之處，針對性地更新真實 DOM。

而如何找到兩顆樹的不同之處，減少 DOM 元素的銷毀與重建，就是 diff 算法的作用

虛擬 DOM

虛擬 DOM，又稱虛擬節(jié)點(vnode)，簡單來說就是包含 DOM 元素信息的對象，一般由 h 函數(shù)創(chuàng)建，下面這個對象就可以看成是一個虛擬節(jié)點

const vnode = {     tag: 'div', // 標簽類型     text: '', // 文本內容     children: undefined, // 子節(jié)點 }

對于這段 HTML

<div>     <p>a</p>     <p>b</p>     <p>c</p> </div>

轉換成 vnode 是這樣的

const vnode = {     tag: 'div', // 標簽類型     text: undefined, // 文本內容     children: [ // 子節(jié)點         {             tag: 'p',             text: 'a',             children: undefined,         },         {             tag: 'p',             text: 'b',             children: undefined,         },         {             tag: 'p',             text: 'c',             children: undefined,         },     ], }

因為我們需要通過虛擬節(jié)點去操作真實 DOM，所以 vnode 身上有個 elm 屬性指向真實的 DOM 元素。而且在之后的 diff 算法中，還會用到一個 key 來對節(jié)點進行唯一標識，所以下文中的 vnode 是這樣的對象

const vnode = {     tag: 'div', // 標簽類型     text: '', // 文本內容     children: undefined, // 子節(jié)點     elm: undefined, // 對應的真實DOM     key: '', // 唯一標識 }

Vue 的虛擬節(jié)點還有很多屬性，不過與 diff 算法無關，就不列舉了

說明一點，虛擬節(jié)點的 text 和 children 不會同時有值。在有 children 屬性的情況下，text 中的內容會轉化為一個文本節(jié)點置入 children 數(shù)組中

預備函數(shù)

為了使等會的代碼實現(xiàn)更簡單，我們準備幾個函數(shù)，功能不難，直接貼代碼了

我們首先需要就是一個將虛擬節(jié)點轉換為真實 DOM 的函數(shù)

// 根據(jù)虛擬節(jié)點創(chuàng)建真實節(jié)點 function createElement(vnode) {     const dom = document.createElement(vnode.tag)     if (vnode.children) {         // 包含子節(jié)點，遞歸創(chuàng)建         for (let i = 0; i < vnode.children.length; i++) {             const childDom = createElement(vnode.children[i])             dom.appendChild(childDom)         }     } else {         // 內部是文字         dom.innerHTML = vnode.text     }     // 補充elm屬性     vnode.elm = dom     return dom }

以及三個工具函數(shù)

// 判斷是否未定義 function isUndef(v) {     return v === undefined || v === null } // 判斷是否已定義 function isDef(v) {     return v !== undefined && v !== null } // 檢查是否可復用 function checkSameVnode(a, b) {     return a.tag === b.tag && a.key === b.key }

patchVnode

當數(shù)據(jù)更新后，Vue 創(chuàng)建出一棵新 vnode，然后執(zhí)行 patchVnode 函數(shù)比較新老兩個虛擬節(jié)點的不同之處，然后根據(jù)情況進行處理

function patchVnode(newVnode, oldVnode) {}

首先判斷新舊兩個虛擬節(jié)點是同一對象，如果是的話就不用處理

if (oldVnode === newVnode) return

然后將舊節(jié)點的 DOM 元素賦給新節(jié)點，并獲取新舊節(jié)點的 children 屬性

let elm = (newVnode.elm = oldVnode.elm) let oldCh = oldVnode.children let newCh = newVnode.children

這里可以直接賦值是因為調用 patchVnode 的新舊節(jié)點它們的 tag 與 key 是一定相同的，在下文會有講解

然后根據(jù)兩個節(jié)點內容，決定如何更新 DOM

1、新舊兩個節(jié)點內容都是文本。修改文本即可

if (isUndef(oldCh) && isUndef(newCh)) {     if (newVnode.text !== oldVnode.text) {         elm.innerText = newVnode.text     } }

2、舊節(jié)點有子節(jié)點，新節(jié)點內容是文本。清空舊節(jié)點內容，改為文本

if (isDef(oldCh) && isUndef(newCh)) {     elm.innerHTML = newVnode.text }

3、舊節(jié)點內容是文本，新節(jié)點有子節(jié)點。清空舊節(jié)點內容，遍歷新節(jié)點生成子 DOM 元素插入節(jié)點中

if (isUndef(oldCh) && isDef(newCh)) {     elm.innerHTML = ''     for (let i = 0, n = newCh.length; i < n; i++){         elm.appendChild(createElement(newCh[i]))     } }

4、新舊節(jié)點都有子節(jié)點。調用 updateChildren 來處理，該函數(shù)在下一章講解

if (isDef(oldCh) && isDef(newCh)) {     updateChildren(elm, oldCh, newCh) }

情況 4 可以與情況 3 的處理一樣，清空舊節(jié)點，然后遍歷生成新 DOM。但是我們要知道，創(chuàng)建 DOM 元素是一件非常耗時的工作，而且新舊子節(jié)點在大多時候都是相同的，如果可以復用，將極大優(yōu)化我們的性能。

那我們要如何判定一個節(jié)點是否可以復用呢？

這就需要 Vue 的使用者來幫忙了，使用者在節(jié)點上定義 key 屬性，告訴 Vue 哪些節(jié)點可以復用

只要標簽類型與 key 值都相等，就說明當前元素可以被復用

然而在我們的項目中，一般只有在 v-for 中才設置 key，其他節(jié)點都沒設置 key

其實沒有設置 key 的節(jié)點，它們的 key 值默認相等

事實也是如此，我們項目中大部分元素都可以復用，只有 v-for 生成的子元素，它依賴的數(shù)組可能發(fā)生一些較復雜的變化，所以才需要明確標注 key 值，以幫助 Vue 盡可能地復用節(jié)點。

patchVnode 的內容當然不止這些，還有樣式、類名、props等數(shù)據(jù)的對比更換，篇幅原因本文將其省略了。

updateChildren

為什么采用雙端 diff

好了，Vue 的使用者為每個節(jié)點的設置了 key，我們要如何從老節(jié)點中找到 key 相等的節(jié)點復用元素呢？

簡單的方式就是窮舉遍歷，對于每個新節(jié)點的 key 遍歷所有老節(jié)點，找到了就移動到首位，沒找到就創(chuàng)建添加。

然而這明顯有優(yōu)化的空間，Vue 實現(xiàn)這部分功能時借鑒了 snabbdom 的雙端 diff 算法，因為此算法將我們平時操作數(shù)組常見的 4 種情況抽離了出來，涵蓋了我們業(yè)務中的大多數(shù)場景，將 O(n²) 的時間復雜度降到了 O(n)

接下來我們來學習這是如何實現(xiàn)的

函數(shù)實現(xiàn)

函數(shù)實現(xiàn)較為復雜，我直接把完整的代碼放上來，再帶領大家一段段解讀

// 三個參數(shù)為：父DOM元素，舊的子節(jié)點數(shù)組，新的子節(jié)點數(shù)組 function updateChildren(parentElm, oldCh, newCh) {     // 舊前索引     let oldStartIdx = 0     // 新前索引     let newStartIdx = 0     // 舊后索引     let oldEndIdx = oldCh.length - 1     // 新后索引     let newEndIdx = newCh.length - 1     // 四個索引對應節(jié)點     let oldStartVnode = oldCh[0]     let newStartVnode = newCh[0]     let oldEndVnode = oldCh[oldEndIdx]     let newEndVnode = newCh[newEndIdx]      let keyMap      // 開始循環(huán)     while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {         // 跳過空節(jié)點 (和最后一種情況有關)         if (isUndef(oldStartVnode)) {             oldStartVnode = oldCh[++oldStartIdx]         } else if (isUndef(oldEndVnode)) {             oldEndVnode = oldCh[--oldEndIdx]         } else if (checkSameVnode(oldStartVnode, newStartVnode)) {             // 情況1             // 舊前和新前相等，不需要移動             patchVnode(newStartVnode, oldStartVnode)             oldStartVnode = oldCh[++oldStartIdx]             newStartVnode = newCh[++newStartIdx]         } else if (checkSameVnode(oldEndVnode, newEndVnode)) {             // 情況2             // 舊后和新后相等，也不需要移動             patchVnode(newEndVnode, oldEndVnode)             oldEndVnode = oldCh[--oldEndIdx]             newEndVnode = newCh[--newEndIdx]         } else if (checkSameVnode(oldStartVnode, newEndVnode)) {             // 情況3             // 舊前和新后相等             // 舊序列的第一個節(jié)點，變成了新序列的最后一個節(jié)點             // 需要將這個節(jié)點移動到舊序列最后一個節(jié)點的后面             // 也就是最后一個節(jié)點的下一個節(jié)點的前面             parentElm.insertBefore(oldStartVnode.elm, oldEndVnode.elm.nextSibling)             patchVnode(newEndVnode, oldStartVnode)             oldStartVnode = oldCh[++oldStartIdx]             newEndVnode = newCh[--newEndIdx]         } else if (checkSameVnode(oldEndVnode, newStartVnode)) {             // 情況4             // 舊后和新前相等             // 舊序列的最后一個節(jié)點，變成了新序列的第一個節(jié)點             // 需要將這個節(jié)點移動到舊序列第一個節(jié)點的前面             parentElm.insertBefore(oldEndVnode.elm, oldStartVnode.elm)             patchVnode(newStartVnode, oldEndVnode)             oldEndVnode = oldCh[--oldEndIdx]             newStartVnode = newCh[++newStartIdx]         } else {             // 以上四種情況都不符合             // 制作舊節(jié)點key的映射對象             // 鍵為 key，值為 索引             if (!keyMap) {                 keyMap = {}                 for (let i = oldStartIdx; i <= oldEndIdx; i++) {                     keyMap[oldCh[i].key] = i                 }             }             // 尋找當前新節(jié)點在keyMap中映射的位置序號             const idxInOld = keyMap[newStartVnode.key]             if (isUndef(idxInOld)) {                 // 沒有找到，表示他是全新的項                 // 轉化為DOM節(jié)點，加入舊序列第一個節(jié)點的前面                 parentElm.insertBefore(createElement(newStartVnode), oldStartVnode.elm)             } else {                 // 不是全新的項，需要移動                 const oldVnode = oldCh[idxInOld]                 // 移動到舊序列第一個節(jié)點之前                 parentElm.insertBefore(oldVnode.elm, oldStartVnode.elm)                 patchVnode(oldVnode, newStartVnode)                 // 把這項設置成空，循環(huán)時遇到時跳過                 oldCh[idxInOld] = undefined             }             // 當前新節(jié)點處理完畢，下一輪循環(huán)處理下一個新節(jié)點             newStartVnode = newCh[++newStartIdx]         }     }      // 循環(huán)結束了，start還是比end小，說明有節(jié)點沒有處理到     if (newStartIdx <= newEndIdx) {         // 新節(jié)點沒有處理到，則創(chuàng)建按DOM添加到新序列最后一個節(jié)點的前面         for (let i = newStartIdx; i <= newEndIdx; i++) {             // insertBefore方法傳入null則添加到隊尾             const before = newCh[newEndIdx + 1]?.elm || null             parentElm.insertBefore(createElement(newCh[i]), before)         }     } else if (oldStartIdx <= oldEndIdx) {         // 舊節(jié)點沒有處理到，刪除         for (let i = oldStartIdx; i <= oldEndIdx; i++) {             parentElm.removeChild(oldCh[i].elm)         }     } }

代碼注釋中及下文的新/舊序列，僅包含從新/舊開始索引到結束索引間的節(jié)點，也就是還未處理的節(jié)點序列，而不是整個子節(jié)點數(shù)組。

根據(jù)例子講解

我們以下圖的例子，來講解這個函數(shù)的運行流程（方框中的內容為子節(jié)點的 key，所有節(jié)點標簽相同）

首先定義了 8 個變量，表示新舊序列的開始和結束位置的索引與節(jié)點

然后開始循環(huán)，初始時節(jié)點都不為空

第一次循環(huán)命中情況 1，舊前與新前(key)相等

這表示舊序列的第一個節(jié)點到新序列仍是第一個節(jié)點，也就不需要移動，但還需要比較一下節(jié)點的內容有沒有改變(patchVnode)，并且讓新舊開始索引都前進一步

// 比較節(jié)點的數(shù)據(jù)及子節(jié)點，并且將舊節(jié)點的DOM賦給新節(jié)點 patchVnode(newStartVnode, oldStartVnode) oldStartVnode = oldCh[++oldStartIdx] newStartVnode = newCh[++newStartIdx]

情況 1 是業(yè)務中最常見的，表示從前至后兩兩比較。一般把商品添加到購物車末尾，或是沒有設置 key 值的子節(jié)點，都是依靠情況 1 把可復用的節(jié)點篩選完畢。

第二次循環(huán)命中情況 2，舊后和新后相等

這表示序列的末尾節(jié)點到新序列仍是末尾節(jié)點，也不需要移動，然后讓新舊結束索引都后退一步

patchVnode(newEndVnode, oldEndVnode) oldEndVnode = oldCh[--oldEndIdx] newEndVnode = newCh[--newEndIdx]

情況 2 是情況 1 的補充，表示從后向前兩兩比較。有時會把新發(fā)布的評論插到開頭，或者從購物車刪除了一些商品，這時僅依靠情況 1 就無法迅速的篩選可復用節(jié)點，所以需要從后向前比較來配合。

第三次循環(huán)命中情況 3，舊前和新后相等

這表示舊序列的第一個節(jié)點，變成了新序列的最后一個節(jié)點。需要將這個節(jié)點移動到序列的末尾，也就是舊序列末尾節(jié)點的下一個節(jié)點(節(jié)點 e)的前面

parentElm.insertBefore(oldStartVnode.elm, oldEndVnode.elm.nextSibling)

然后比較新舊節(jié)點，修改索引

patchVnode(newEndVnode, oldStartVnode) oldStartVnode = oldCh[++oldStartIdx] newEndVnode = newCh[--newEndIdx]

情況 3 主要處理數(shù)組反轉的情況，比如升序改降序，每個起始節(jié)點被移動到了末尾的位置，使用此情況將它們重新排序。

第四次循環(huán)命中情況 4，舊后與新前相等

這表示舊序列的最后一個節(jié)點，變成了新序列的第一個節(jié)點。需要將這個節(jié)點移動到序列的開頭，也就是舊序列開始節(jié)點（節(jié)點 c）的前面

parentElm.insertBefore(oldStartVnode.elm, oldEndVnode.elm.nextSibling)

到這里說一下，圖上標注的是節(jié)點 a 的后面，是因為節(jié)點 b 被移動到了末尾

節(jié)點的移動都是根據(jù)舊節(jié)點來定位的，如果想把一個節(jié)點放到序列的開頭，就放到舊序列開始節(jié)點的前面；如果想把一個節(jié)點放到序列的末尾，就要放到舊序列結束節(jié)點的下一個節(jié)點的前面

然后也是比較新舊節(jié)點，修改索引，之后是下圖情況

patchVnode(newStartVnode, oldEndVnode) oldEndVnode = oldCh[--oldEndIdx] newStartVnode = newCh[++newStartIdx]

情況 4 是情況 3 的補充，避免反轉數(shù)組后又插入/刪除了節(jié)點導致情況 3 無法匹配，本例就是這個情況。

第五次循環(huán)，4 種情況均為未命中

很遺憾，無法迅速鎖定節(jié)點的位置，只能用傳統(tǒng)的方式進行遍歷

我們這里選擇了以空間換時間的方式，定義了 keyMap，將舊序列節(jié)點的 key 與索引存起來，然后使用新開始節(jié)點的 key 去查找。

如果沒找到，說明這是一個新節(jié)點，創(chuàng)建節(jié)點并放到開頭，也就是插入到舊序列開始節(jié)點的前面

但如果找到了，則同樣移動節(jié)點到序列開頭，然后將對應的舊節(jié)點索引置空，在以后循環(huán)遇到空的舊節(jié)點就跳過了

本例中是未找到的情況，此節(jié)點處理完畢，新開始索引加一，超過了新結束索引，不滿足循環(huán)條件，退出循環(huán)

然而，節(jié)點 c 并沒有被處理，此時的 DOM 序列為：a,d,f,c,b,e

所以在循環(huán)之后，要檢測是否有未處理的節(jié)點，如果是舊節(jié)點未處理，刪除即可；

如果是新節(jié)點未處理，則創(chuàng)建新節(jié)點插入到舊序列的末尾或者舊序列的開頭，二者其實是一個位置

我們假設舊節(jié)點中沒有 c，則在第四次循環(huán)后就會出現(xiàn)以下情況（第四次循環(huán)命中的是情況 1）

如果把 f 放到序列的開頭，就是舊開始節(jié)點（節(jié)點 e）的前面

而如果把 f 放到序列的末尾，也就是舊結束節(jié)點的下一個節(jié)點（節(jié)點 e）的前面

此時舊序列就是一個點，不分開頭和結尾，只要保證新增節(jié)點序列按序添加就好了

至此，雙端 diff 算法就講完了

Vue 中的 key

學完 diff 算法，再聊聊 key 的作用

v-for 中的 key

上面講的都是有 key 情況下，diff 算法能夠迅速找到新舊序列中的同一節(jié)點，以較小的代價完成更新。

而如果在 v-for 中不設置 key 呢？

假設我們在數(shù)組頭部插入了一個新節(jié)點，然后開始循環(huán)，每次循環(huán)都命中情況 1，嘗試“復用”此節(jié)點。

但是，在對比新舊節(jié)點的內容時，都會發(fā)現(xiàn)內容不同，需要用新節(jié)點的內容替換舊節(jié)點。這只是復用了 DOM 的外殼，節(jié)點的內容、數(shù)據(jù)以及該節(jié)點的子節(jié)點全都要更改。

相比有 key 時的只添加一個新節(jié)點，無 key 則將所有節(jié)點都修改一遍。

v-if 自帶 key

v-for 以外的元素我們一般是不設置 key 的，但是如果子元素中有 v-if 的話，就像下面這個場景（abcd是內容，并不是 key），更新子元素又會復現(xiàn)上一節(jié)的情況。

然而 Vue 官方也考慮到了這點，會為 v-if 的元素加上利用 hash 函數(shù)生成的唯一 key

// 以下出自 v2 源碼 var needsKey = !!el.if  …… needsKey ? ',null,false,' + hash(generatedSlots) : ''

key 的另一個用法

順便再提一嘴，key 可以綁到任意元素上，當 key 發(fā)生變化時，會導致 DOM 的銷毀與重建，一般用來重復觸發(fā)動畫或生命周期鉤子。

詳情可看官方鏈接

https://cn.vuejs.org/v2/api/#key

結語

不記得這是第幾次梳理雙端 diff 的邏輯了，很早之前就已經擁抱 v3 了，把 v2 的響應式原理和 diff 算法總結一遍也算是給 v2 畫上句號了。

沒想到這篇文章寫了 4000 多字，為此還特意去翻看了 v2 的源碼。本文的代碼和 v2 差別還是蠻大的，主要參考的是 snabbdom 和以前的教程，加了點自己的風格將 patchVnode 和 updateChildren 實現(xiàn)了一遍。

接下來就能心無旁騖地看 v3 的源碼了……

整理不易，如果有所幫助的話，希望能點贊關注，鼓勵一下作者。

原文地址：https://juejin.cn/post/7120919895713251335

作者：清隆

【相關視頻教程推薦：vuejs入門教程、web前端入門】