Vue2中的雙端diff算法怎么更新節點

這篇文章主要介紹了Vue2中的雙端diff算法怎么更新節點的相關知識，內容詳細易懂，操作簡單快捷，具有一定借鑒價值，相信大家閱讀完這篇Vue2中的雙端diff算法怎么更新節點文章都會有所收獲，下面我們一起來看看吧。

預備知識

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 的銷毀與重建，一般用來重復觸發動畫或生命周期鉤子。

關于“Vue2中的雙端diff算法怎么更新節點”這篇文章的內容就介紹到這里，感謝各位的閱讀！相信大家對“Vue2中的雙端diff算法怎么更新節點”知識都有一定的了解，大家如果還想學習更多知識，歡迎關注億速云行業資訊頻道。