聊聊Vue2中的雙端diff演演算法，看看如何更新節點的！

今天我們來聊聊 Vue2 的雙端 diff 演演算法。（學習視訊分享：）

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

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

篇幅原因，本文並不會介紹虛擬 DOM 樹是如何生成的，僅講解在資料更新時，是如何比較兩顆虛擬 DOM 樹並更新真實 DOM 的，主要實現 Vue2 原始碼中的 patchVnode、updateChildren 函數

預備知識

diff 演演算法作用

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

我們知道在網頁執行中，我們改變一些資料，它們可能會影響到 DOM 樹。如何在頁面中展示最新的資料呢，最簡單的方式就是整棵樹推到重建，當然這樣會導致大量的浪費，所以 Vue 使用虛擬 DOM 儲存頁面中 DOM 樹的狀態，在資料變化後，構建一棵新的虛擬 DOM 樹，找到前後兩顆樹的不同之處，針對性地更新真實 DOM。

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

虛擬 DOM

虛擬 DOM，又稱虛擬節點(vnode)，簡單來說就是包含 DOM 元素資訊的物件，一般由 h 函數建立，下面這個物件就可以看成是一個虛擬節點

const vnode = {
    tag: 'div', // 標籤型別
    text: '', // 文字內容
    children: undefined, // 子節點
}

對於這段 HTML

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

轉換成 vnode 是這樣的

const vnode = {
    tag: 'div', // 標籤型別
    text: undefined, // 文字內容
    children: [ // 子節點
        {
            tag: 'p',
            text: 'a',
            children: undefined,
        },
        {
            tag: 'p',
            text: 'b',
            children: undefined,
        },
        {
            tag: 'p',
            text: 'c',
            children: undefined,
        },
    ],
}

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

const vnode = {
    tag: 'div', // 標籤型別
    text: '', // 文字內容
    children: undefined, // 子節點
    elm: undefined, // 對應的真實DOM
    key: '', // 唯一標識
}

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

說明一點，虛擬節點的 text 和 children 不會同時有值。在有 children 屬性的情況下，text 中的內容會轉化為一個文位元組點置入 children 陣列中

預備函數

為了使等會的程式碼實現更簡單，我們準備幾個函數，功能不難，直接貼程式碼了

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

// 根據虛擬節點建立真實節點
function createElement(vnode) {
    const dom = document.createElement(vnode.tag)
    if (vnode.children) {
        // 包含子節點，遞迴建立
        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
}

以及三個工具函數

// 判斷是否未定義
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

當資料更新後，Vue 建立出一棵新 vnode，然後執行 patchVnode 函數比較新老兩個虛擬節點的不同之處，然後根據情況進行處理

function patchVnode(newVnode, oldVnode) {}

首先判斷新舊兩個虛擬節點是同一物件，如果是的話就不用處理

if (oldVnode === newVnode) return

然後將舊節點的 DOM 元素賦給新節點，並獲取新舊節點的 children 屬性

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

這裡可以直接賦值是因為呼叫 patchVnode 的新舊節點它們的 tag 與 key 是一定相同的，在下文會有講解

然後根據兩個節點內容，決定如何更新 DOM

1、新舊兩個節點內容都是文字。修改文字即可

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

2、舊節點有子節點，新節點內容是文字。清空舊節點內容，改為文字

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

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

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

4、新舊節點都有子節點。呼叫 updateChildren 來處理，該函數在下一章講解

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

情況 4 可以與情況 3 的處理一樣，清空舊節點，然後遍歷生成新 DOM。但是我們要知道，建立 DOM 元素是一件非常耗時的工作，而且新舊子節點在大多時候都是相同的，如果可以複用，將極大優化我們的效能。

那我們要如何判定一個節點是否可以複用呢？

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

只要標籤型別與 key 值都相等，就說明當前元素可以被複用

然而在我們的專案中，一般只有在 v-for 中才設定 key，其他節點都沒設定 key

其實沒有設定 key 的節點，它們的 key 值預設相等

事實也是如此，我們專案中大部分元素都可以複用，只有 v-for 生成的子元素，它依賴的陣列可能發生一些較複雜的變化，所以才需要明確標註 key 值，以幫助 Vue 儘可能地複用節點。

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

updateChildren

為什麼採用雙端 diff

好了，Vue 的使用者為每個節點的設定了 key，我們要如何從老節點中找到 key 相等的節點複用元素呢？

簡單的方式就是窮舉遍歷，對於每個新節點的 key 遍歷所有老節點，找到了就移動到首位，沒找到就建立新增。

然而這明顯有優化的空間，Vue 實現這部分功能時借鑑了 snabbdom 的雙端 diff 演演算法，因為此演演算法將我們平時運算元組常見的 4 種情況抽離了出來，涵蓋了我們業務中的大多數場景，將 O(n²) 的時間複雜度降到了 O(n)

接下來我們來學習這是如何實現的

函數實現

函數實現較為複雜，我直接把完整的程式碼放上來，再帶領大家一段段解讀

// 三個引數為：父DOM元素，舊的子節點陣列，新的子節點陣列
function updateChildren(parentElm, oldCh, newCh) {
    // 舊前索引
    let oldStartIdx = 0
    // 新前索引
    let newStartIdx = 0
    // 舊後索引
    let oldEndIdx = oldCh.length - 1
    // 新後索引
    let newEndIdx = newCh.length - 1
    // 四個索引對應節點
    let oldStartVnode = oldCh[0]
    let newStartVnode = newCh[0]
    let oldEndVnode = oldCh[oldEndIdx]
    let newEndVnode = newCh[newEndIdx]

    let keyMap

    // 開始迴圈
    while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
        // 跳過空節點 (和最後一種情況有關)
        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
            // 舊前和新後相等
            // 舊序列的第一個節點，變成了新序列的最後一個節點
            // 需要將這個節點移動到舊序列最後一個節點的後面
            // 也就是最後一個節點的下一個節點的前面
            parentElm.insertBefore(oldStartVnode.elm, oldEndVnode.elm.nextSibling)
            patchVnode(newEndVnode, oldStartVnode)
            oldStartVnode = oldCh[++oldStartIdx]
            newEndVnode = newCh[--newEndIdx]
        } else if (checkSameVnode(oldEndVnode, newStartVnode)) {
            // 情況4
            // 舊後和新前相等
            // 舊序列的最後一個節點，變成了新序列的第一個節點
            // 需要將這個節點移動到舊序列第一個節點的前面
            parentElm.insertBefore(oldEndVnode.elm, oldStartVnode.elm)
            patchVnode(newStartVnode, oldEndVnode)
            oldEndVnode = oldCh[--oldEndIdx]
            newStartVnode = newCh[++newStartIdx]
        } else {
            // 以上四種情況都不符合
            // 製作舊節點key的對映物件
            // 鍵為 key，值為 索引
            if (!keyMap) {
                keyMap = {}
                for (let i = oldStartIdx; i <= oldEndIdx; i++) {
                    keyMap[oldCh[i].key] = i
                }
            }
            // 尋找當前新節點在keyMap中對映的位置序號
            const idxInOld = keyMap[newStartVnode.key]
            if (isUndef(idxInOld)) {
                // 沒有找到，表示他是全新的項
                // 轉化為DOM節點，加入舊序列第一個節點的前面
                parentElm.insertBefore(createElement(newStartVnode), oldStartVnode.elm)
            } else {
                // 不是全新的項，需要移動
                const oldVnode = oldCh[idxInOld]
                // 移動到舊序列第一個節點之前
                parentElm.insertBefore(oldVnode.elm, oldStartVnode.elm)
                patchVnode(oldVnode, newStartVnode)
                // 把這項設定成空，迴圈時遇到時跳過
                oldCh[idxInOld] = undefined
            }
            // 當前新節點處理完畢，下一輪迴圈處理下一個新節點
            newStartVnode = newCh[++newStartIdx]
        }
    }

    // 迴圈結束了，start還是比end小，說明有節點沒有處理到
    if (newStartIdx <= newEndIdx) {
        // 新節點沒有處理到，則建立按DOM新增到新序列最後一個節點的前面
        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) {
        // 舊節點沒有處理到，刪除
        for (let i = oldStartIdx; i <= oldEndIdx; i++) {
            parentElm.removeChild(oldCh[i].elm)
        }
    }
}

程式碼註釋中及下文的新/舊序列，僅包含從新/舊開始索引到結束索引間的節點，也就是還未處理的節點序列，而不是整個子節點陣列。

根據例子講解

我們以下圖的例子，來講解這個函數的執行流程（方框中的內容為子節點的 key，所有節點標籤相同）

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

然後開始迴圈，初始時節點都不為空

第一次迴圈命中情況 1，舊前與新前(key)相等

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

// 比較節點的資料及子節點，並且將舊節點的DOM賦給新節點
patchVnode(newStartVnode, oldStartVnode)
oldStartVnode = oldCh[++oldStartIdx]
newStartVnode = newCh[++newStartIdx]

情況 1 是業務中最常見的，表示從前至後兩兩比較。一般把商品新增到購物車末尾，或是沒有設定 key 值的子節點，都是依靠情況 1 把可複用的節點篩選完畢。

第二次迴圈命中情況 2，舊後和新後相等

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

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

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

第三次迴圈命中情況 3，舊前和新後相等

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

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

然後比較新舊節點，修改索引

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

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

第四次迴圈命中情況 4，舊後與新前相等

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

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

到這裡說一下，圖上標註的是節點 a 的後面，是因為節點 b 被移動到了末尾

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

然後也是比較新舊節點，修改索引，之後是下圖情況

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

情況 4 是情況 3 的補充，避免反轉陣列後又插入/刪除了節點導致情況 3 無法匹配，本例就是這個情況。

第五次迴圈，4 種情況均為未命中

很遺憾，無法迅速鎖定節點的位置，只能用傳統的方式進行遍歷

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

如果沒找到，說明這是一個新節點，建立節點並放到開頭，也就是插入到舊序列開始節點的前面

但如果找到了，則同樣移動節點到序列開頭，然後將對應的舊節點索引置空，在以後迴圈遇到空的舊節點就跳過了

本例中是未找到的情況，此節點處理完畢，新開始索引加一，超過了新結束索引，不滿足迴圈條件，退出迴圈

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

所以在迴圈之後，要檢測是否有未處理的節點，如果是舊節點未處理，刪除即可；

如果是新節點未處理，則建立新節點插入到舊序列的末尾或者舊序列的開頭，二者其實是一個位置

我們假設舊節點中沒有 c，則在第四次迴圈後就會出現以下情況（第四次迴圈命中的是情況 1）

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

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

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

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

Vue 中的 key

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

v-for 中的 key

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

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

假設我們在陣列頭部插入了一個新節點，然後開始迴圈，每次迴圈都命中情況 1，嘗試「複用」此節點。

但是，在對比新舊節點的內容時，都會發現內容不同，需要用新節點的內容替換舊節點。這只是複用了 DOM 的外殼，節點的內容、資料以及該節點的子節點全都要更改。

相比有 key 時的只新增一個新節點，無 key 則將所有節點都修改一遍。

v-if 自帶 key

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

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

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

key 的另一個用法

順便再提一嘴，key 可以綁到任意元素上，當 key 發生變化時，會導致 DOM 的銷燬與重建，一般用來重複觸發動畫或生命週期勾點。

詳情可看官方連結

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

結語

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

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

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

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

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

作者：清隆

【相關視訊教學推薦：、】

以上就是聊聊Vue2中的雙端diff演演算法，看看如何更新節點的！的詳細內容，更多請關注TW511.COM其它相關文章！