DIff 算法 -帶圖-,請收藏-

前言

面試官:" 你瞭解虛擬DOM(Virtual DOM)Diff算法嗎, 請描述一下它們 ";

我:"額,... 鵝, 那個", 完了😰, 突然智商不在線, 沒組織好語言沒答好或者壓根就答不出來;

所以這次我總結一下相關的知識點, 讓你可以有一個清晰的認知之餘也會讓你在今後遇到這種情況可以坦然自若, 應付自如, 遊刃有餘:

相關知識點:

虛擬 DOM(Virtual DOM)

什麼是虛擬 DOM

一句話總結虛擬 DOM 就是一個用來描述真實 DOM 的 javaScript 對象, 這樣說可能不夠形象, 那我們來舉個🌰: 分別用代碼來描述真實 DOM 以及虛擬 DOM

真實 DOM:

對應的虛擬 DOM:

控制檯打印出來的 Vnode:

h 函數生成的虛擬 DOM 這個 JS 對象 (Vnode) 的源碼:

補充:

上面的 h 函數大家可能有點熟悉的感覺但是一時間也沒想起來, 沒關係我來幫大夥回憶;

開發中常見的現實場景, render 函數渲染:

爲什麼要使用虛擬 DOM

靈魂發問: 使用了虛擬 DOM 就一定會比直接渲染真實 DOM 快嗎? 答案當然是否定的, 且聽我說:

舉例: 當一個節點變更時 DOMA->DOMB

上述情況:示例1是創建一個DOMB然後替換掉DOMA;示例2創建虛擬DOM+DIFF算法比對發現DOMBDOMA不是相同的節點, 最後還是創建一個DOMB然後替換掉DOMA; 可以明顯看出 1 是更快的, 同樣的結果, 2 還要去創建虛擬 DOM+DIFF 算啊對比 所以說使用虛擬 DOM 比直接操作真實 DOM 就一定要快這個說法是錯誤的,不嚴謹的

舉例: 當 DOM 樹裏面的某個子節點的內容變更時:

當一些複雜的節點, 比如說一個父節點裏面有多個子節點, 當只是一個子節點的內容發生了改變, 那麼我們沒有必要像示例1重新去渲染這個DOM樹, 這個時候虛擬DOM+DIFF算法就能夠得到很好的體現, 我們通過示例2使用虛擬DOM+Diff算法去找出改變了的子節點更新它的內容就可以了

總結: 複雜視圖情況下提升渲染性能, 因爲虛擬DOM+Diff算法可以精準找到 DOM 樹變更的地方, 減少 DOM 的操作 (重排重繪)

虛擬 dom 庫

Diff 算法

在看完上述的文章之後相信大家已經對 Diff 算法有一個初步的概念, 沒錯, Diff 算法其實就是找出兩者之間的差異;

diff 算法首先要明確一個概念就是 Diff 的對象是虛擬 DOM(virtual dom),更新真實 DOM 是 Diff 算法的結果。

下面我將會手撕snabbdom源碼核心部分爲大家打開Diff的心, 給點耐心, 別關網頁, 我知道你們都是這樣:

snabbdom 的核心

init 函數

init 函數時設置模塊, 然後創建 patch() 函數, 我們先通過場景案例來有一個直觀的體現:

當 init 使用了導入的模塊就能夠在 h 函數中用這些模塊提供的 api 去創建虛擬DOM(Vnode)對象; 在上文中就使用了樣式模塊以及事件模塊讓創建的這個虛擬 DOM 具備樣式屬性以及事件屬性, 最終通過patch函數對比兩個虛擬dom(會先把 app 轉換成虛擬 dom), 更新視圖;

我們再簡單看看 init 的源碼部分:

h 函數

些地方也會用createElement來命名, 它們是一樣的東西, 都是創建虛擬DOM的, 在上述文章中相信大夥已經對 h 函數有一個初步的瞭解並且已經聯想了使用場景, 就不作場景案例介紹了, 直接上源碼部分:

總結:h函數先生成一個vnode函數, 然後vnode函數再生成一個Vnode對象 (虛擬 DOM 對象)

補充:

在 h 函數源碼部分涉及一個函數重載的概念, 簡單說明一下:

重載這個概念個參數相關, 和返回值無關

patch 函數 (核心)

要是看完前面的鋪墊, 看到這裏你可能走神了,醒醒啊,這是核心啊,上高地了兄弟;

源碼:

補充 1: sameVnode 函數

patchVnode

源碼:

看得可能有點矇蔽, 下面再上一副思維導圖:

題外話: diff 算法簡介

傳統 diff 算法

snabbdom 的 diff 算法優化

下面我們就會介紹updateChildren函數怎麼去對比子節點的異同, 也是Diff算法裏面的一個核心以及難點;

updateChildren(核中核: 判斷子節點的差異)

  1. oldStartVnode/newStartVnode(舊開始節點 / 新開始節點) 相同

  2. oldEndVnode/newEndVnode(舊結束節點 / 新結束節點) 相同

  3. oldStartVnode/newEndVnode(舊開始節點 / 新結束節點) 相同

  4. oldEndVnode/newStartVnode(舊結束節點 / 新開始節點) 相同

  5. 特殊情況當1,2,3,4的情況都不符合的時候就會執行, 在oldVnodes裏面尋找跟newStartVnode一樣的節點然後位移到oldStartVnode, 若沒有找到在就oldStartVnode創建一個

爲了更加直觀的瞭解, 我們再來看看同級別節點比較五種情況的實現細節:

新開始節點和舊開始節點 (情況 1)

新結束節點和舊結束節點 (情況 2)

舊開始節點 / 新結束節點 (情況 3)

舊結束節點 / 新開始節點 (情況 4)

新開始節點 / 舊節點數組中尋找節點 (情況 5)

下面我們再介紹一下結束循環的收尾工作(oldStartIdx>oldEndIdx || newStartIdx>newEndIdx):

最後附上源碼:

function updateChildren(parentElm, oldCh, newCh, insertedVnodeQueue) {    let oldStartIdx = 0;                // 舊節點開始節點索引
    let newStartIdx = 0;                // 新節點開始節點索引
    let oldEndIdx = oldCh.length - 1;   // 舊節點結束節點索引
    let oldStartVnode = oldCh[0];       // 舊節點開始節點
    let oldEndVnode = oldCh[oldEndIdx]; // 舊節點結束節點
    let newEndIdx = newCh.length - 1;   // 新節點結束節點索引
    let newStartVnode = newCh[0];       // 新節點開始節點
    let newEndVnode = newCh[newEndIdx]; // 新節點結束節點
    let oldKeyToIdx;                    // 節點移動相關
    let idxInOld;                       // 節點移動相關
    let elmToMove;                      // 節點移動相關
    let before;
    // 同級別節點比較
    while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
        if (oldStartVnode == null) {
            oldStartVnode = oldCh[++oldStartIdx]; 
            // Vnode might have been moved left
        }
        else if (oldEndVnode == null) {
            oldEndVnode = oldCh[--oldEndIdx];
        }
        else if (newStartVnode == null) {
            newStartVnode = newCh[++newStartIdx];
        }
        else if (newEndVnode == null) {
            newEndVnode = newCh[--newEndIdx];
        }
        else if (sameVnode(oldStartVnode, newStartVnode))
         { // 判斷情況1
            patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue);
            oldStartVnode = oldCh[++oldStartIdx];
            newStartVnode = newCh[++newStartIdx];
        }
        else if (sameVnode(oldEndVnode, newEndVnode))
         {   // 情況2
            patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue);
            oldEndVnode = oldCh[--oldEndIdx];
            newEndVnode = newCh[--newEndIdx];
        }
        else if (sameVnode(oldStartVnode, newEndVnode)) 
        { // Vnode moved right情況3
            patchVnode(oldStartVnode, newEndVnode, 
            insertedVnodeQueue);
            api.insertBefore(parentElm, oldStartVnode.elm, api.
            nextSibling(oldEndVnode.elm));
            oldStartVnode = oldCh[++oldStartIdx];
            newEndVnode = newCh[--newEndIdx];
        }
        else if (sameVnode(oldEndVnode, newStartVnode)) { // Vnode moved left情況4
            patchVnode(oldEndVnode, newStartVnode, 
            insertedVnodeQueue);
            api.insertBefore(parentElm, oldEndVnode.elm, 
            oldStartVnode.elm);
            oldEndVnode = oldCh[--oldEndIdx];
            newStartVnode = newCh[++newStartIdx];
        }
        else {                                            // 情況5
            if (oldKeyToIdx === undefined) {
                oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, 
                oldEndIdx);
            }
            idxInOld = oldKeyToIdx[newStartVnode.key];
            if (isUndef(idxInOld))
             { // New element  // 創建新的節點在舊節點的新節點前
                api.insertBefore(parentElm, createElm
                (newStartVnode,
                 insertedVnodeQueue), oldStartVnode.elm);
            }
            else {
                elmToMove = oldCh[idxInOld];
                if (elmToMove.sel !== newStartVnode.sel) 
                { // 創建新的節點在舊節點的新節點前
                    api.insertBefore(parentElm, createElm
                    (newStartVnode, insertedVnodeQueue), 
                    oldStartVnode.elm);
                }
                else 
  {// 在舊節點數組中找到相同的節點就對比差異更新視圖,然後移動位置
                    patchVnode(elmToMove, newStartVnode, 
                    insertedVnodeQueue);
                    oldCh[idxInOld] = undefined;
                    api.insertBefore(parentElm, elmToMove.elm, 
                    oldStartVnode.elm);
                }
            }
            newStartVnode = newCh[++newStartIdx];
        }
    }
    // 循環結束的收尾工作
    if (oldStartIdx <= oldEndIdx || newStartIdx <= newEndIdx) {
        if (oldStartIdx > oldEndIdx) {
// newCh[newEndIdx + 1].elm就是舊節點數組中的結束節點對應的dom元素
// newEndIdx+1是因爲在之前成功匹配了newEndIdx需要-1
 // newCh[newEndIdx + 1].elm,因爲已經匹配過有相同的節點了,
 它就是等於舊節點數組中的結束節點對應的dom元素(oldCh[oldEndIdx + 1]
 .elm)
before = newCh[newEndIdx + 1] == null ? 
null : newCh[newEndIdx + 1].
elm;
 // 把新節點數組中多出來的節點插入到before前
addVnodes(parentElm, before, newCh, newStartIdx, newEndIdx, 
insertedVnodeQueue);
}
        else {
            // 這裏就是把沒有匹配到相同節點的節點刪除掉
 removeVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx);
        }
    }
}

key 的作用

以下我們看看這些作用的實例:

Diff 操作可以更加準確;****(避免渲染錯誤):

實例: a,b,c 三個 dom 元素中的 b,c 間插入一個 z 元素

沒有設置 key 當設置了 key:

Diff 操作可以更加準確;(避免渲染錯誤)

實例: a,b,c 三個 dom 元素, 修改了 a 元素的某個屬性再去在 a 元素前新增一個 z 元素

沒有設置 key:

因爲沒有設置 key, 默認都是 undefined, 所以節點都是相同的, 更新了 text 的內容但還是沿用了之前的 dom, 所以實際上a->z(a原本打勾的狀態保留了,只改變了text),b->a,c->b,d->c, 遍歷完畢發現還要增加一個 dom, 在最後新增一個 text 爲 d 的 dom 元素

設置了 key:

當設置了 key,a,b,c,d 都有對應的 key,a->a,b->b,c->c,d->d, 內容相同無需更新, 遍歷結束, 新增一個 text 爲 z 的 dom 元素

不推薦使用索引作爲 key:

設置索引爲 key:

這明顯效率不高, 我們只希望找出不同的節點更新, 而使用索引作爲 key 會增加運算時間, 我們可以把 key 設置爲與節點 text 爲一致就可以解決這個問題:

來源:

https://juejin.cn/post/7000266544181674014

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