一文搞定Diff算法

關注公衆号“執鸢者”，回複“資料”擷取500G資料（各“兵種”均有），還有專業交流群等你一起來潇灑。（哈哈）

不管是Vue還是React，其為了比較虛拟DOM節點的變化，實作最小量更新，均利用了diff算法，本文就與老鐵們一起來看看diff算法。

一、基礎

Diff算法實作的是最小量更新虛拟DOM。這句話雖然簡短，但是涉及到了兩個核心要素：虛拟DOM、最小量更新。

虛拟DOM

虛拟DOM指的就是将真實的DOM樹構造為js對象的形式，進而解決浏覽器操作真實DOM的性能問題。

例如：如下DOM與虛拟DOM之間的映射關系

一文搞定Diff算法

最小量更新

Diff的用途就是在新老虛拟DOM之間找到最小更新的部分，進而将該部分對應的DOM進行更新。

二、整個流程

Diff算法真的很美，整個流程如下圖所示：

一文搞定Diff算法

一、首先比較一下新舊節點是不是同一個節點（可通過比較sel（選擇器）和key（唯一辨別）值是不是相同），不是同一個節點則進行暴力删除（注：先以舊節點為基準插入新節點，然後再删除舊節點）。

二、若是同一個節點則需要進一步比較

完全相同，不做處理
新節點内容為文本，直接替換完事
新節點有子節點，這個時候就要仔細考慮一下了:若老節點沒有子元素，則直接清空老節點，将新節點的子元素插入即可；若老節點有子元素則就需要按照上述的更新政策老搞定了（記住更新政策，又可以吹好幾年了，666666）。

三、實戰

光說不練假把式，下面直接輸出diff算法的核心内容。

3.1 patch函數

Diff算法的入口函數，主要判斷新舊節點是不是同一個節點，然後交由不同的邏輯進行處理。

export default function patch(oldVnode, newVnode) {
    // 判斷傳入的第一個參數，是DOM節點還是虛拟節點
    if (oldVnode.sel === '' || oldVnode.sel === undefined) {
        // 傳入的第一個參數是DOM節點，此時要包裝成虛拟節點
        oldVnode = vnode(oldVnode.tagName.toLowerCase(), {}, [], undefined, oldVnode);
    }

    // 判斷oldVnode和newVnode是不是同一個節點
    if (oldVnode.key === newVnode.key && oldVnode.sel === newVnode.sel) {
        //是同一個節點，則進行精細化比較
        patchVnode(oldVnode, newVnode);
    }
    else {
        // 不是同一個節點，暴力插入新的，删除舊的
        let newVnodeElm = createElement(newVnode);

        // 将新節點插入到老節點之前
        if (oldVnode.elm.parentNode && newVnodeElm) {
            oldVnode.elm.parentNode.insertBefore(newVnodeElm, oldVnode.elm);
        }
        // 删除老節點
        oldVnode.elm.parentNode.removeChild(oldVnode.elm);
    }
}

3.2 patchVnode函數

該函數主要負責精細化比較，通過按照上述流程圖中的邏輯依次判斷屬于哪一個分支，進而采取不同的處理邏輯。（思路清晰，算法太牛了）

export default function patchVnode(oldVnode, newVnode) {
    // 判斷新舊vnode是否是同一個對象
    if (oldVnode === newVnode) {
        return;
    }
    // 判斷vnode有沒有text屬性
    if (newVnode.text !== undefined && (newVnode.children === undefined || newVnode.children.length === 0)) {
        console.log('新vnode有text屬性');
        if (newVnode.text !== oldVnode.text) {
            oldVnode.elm.innerText = newVnode.text;
        }
    }
    else {
        // 新vnode沒有text屬性，有children
        console.log('新vnode沒有text屬性');
        // 判斷老的有沒有children
        if (oldVnode.children !== undefined && oldVnode.children.length > 0) {
            // 老的有children，新的也有children
            updateChildren(oldVnode.elm, oldVnode.children, newVnode.children);
        }
        else {
            // 老的沒有children，新的有children
            // 清空老的節點的内容
            oldVnode.elm.innerHTML = '';
            // 周遊新的vnode的子節點，建立DOM，上樹
            for (let i = 0; i < newVnode.children.length; i++) {
                let dom = createElement(newVnode.children[i]);
                oldVnode.elm.appendChild(dom);
            }
        }
    }
}

3.3 updateChildren函數

核心函數，主要負責舊虛拟節點和新虛拟節點均存在子元素的情況，按照比較政策依次進行比較，最終找出子元素中變化的部分，實作最小更新。對于該部分，涉及到一些指針，如下所示：

一文搞定Diff算法

舊前指的就是更新前虛拟DOM中的頭部指針
舊後指的就是更新前虛拟DOM中的尾部指針
新前指的就是更新後虛拟DOM中的頭部指針
新後指的就是更新後虛拟DOM中的尾部指針

按照上述的更新政策，上述舊虛拟DOM更新為新虛拟DOM的流程為：

命中“新後舊前”政策，然後将信後對應的DOM節點（也就是節點1）移動到舊後節點（節點3）後面，然後舊前節點指針下移，新後節點指針上移。
仍然命中“新後舊前”政策，做相同的操作，将節點2移動到舊後節點（節點3）後面，下移舊前節點，上移新後節點。
命中“新前舊前”政策，DOM節點不變，舊前和新前節點均下移。
跳出循環，移動結束。

export default 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 oldEndVnode = oldCh[oldEndIdx];
    // 新前節點
    let newStartVnode = newCh[0];
    // 新後節點
    let newEndVnode = newCh[newEndIdx];

    let keyMap = null;

    while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
        // 略過已經加undefined标記的内容
        if (oldStartVnode == null || oldCh[oldStartIdx] === undefined) {
            oldStartVnode = oldCh[++oldStartIdx];
        }
        else if (oldEndVnode == null || oldCh[oldEndIdx] === undefined) {
            oldEndVnode = oldCh[--oldEndIdx];
        }
        else if (newStartVnode == null || newCh[newStartIdx] === undefined) {
            newStartVnode = newCh[++newStartIdx];
        }
        else if (newEndVnode == null || newCh[newEndIdx] === undefined) {
            newEndVnode = newCh[--newEndIdx];
        }
        else if (checkSameVnode(oldStartVnode, newStartVnode)) {
            // 新前與舊前
            console.log('新前與舊前命中');
            patchVnode(oldStartVnode, newStartVnode);
            oldStartVnode = oldCh[++oldStartIdx];
            newStartVnode = newCh[++newStartIdx];
        }
        else if (checkSameVnode(oldEndVnode, newEndVnode)) {
            // 新後和舊後
            console.log('新後和舊後命中');
            patchVnode(oldEndVnode, newEndVnode);
            oldEndVnode = oldCh[--oldEndIdx];
            newEndVnode = newCh[--newEndVnode];
        }
        else if (checkSameVnode(oldStartVnode, newEndVnode)) {
            console.log('新後和舊前命中');
            patchVnode(oldStartVnode, newEndVnode);
            // 當新後與舊前命中的時候，此時要移動節點，移動新後指向的這個節點到老節點舊後的後面
            parentElm.insertBefore(oldStartVnode.elm, oldEndVnode.elm.nextSibling);
            oldStartVnode = oldCh[++oldStartIdx];
            newEndVnode = newCh[--newEndIdx];
        }
        else if (checkSameVnode(oldEndVnode, newStartVnode)) {
            // 新前和舊後
            console.log('新前和舊後命中');
            patchVnode(oldEndVnode, newStartVnode);
            // 當新前和舊後命中的時候，此時要移動節點，移動新前指向的這個節點到老節點舊前的前面
            parentElm.insertBefore(oldEndVnode.elm, oldStartVnode.elm);
            oldEndVnode = oldCh[--oldEndIdx];
            newStartVnode = newCh[++newStartIdx];
        }
        else {
            // 四種都沒有命中
            // 制作keyMap一個映射對象，這樣就不用每次都周遊老對象了
            if (!keyMap) {
                keyMap = {};
                for (let i = oldStartIdx; i <= oldEndIdx; i++) {
                    const key = oldCh[i].key;
                    if (key !== undefined) {
                        keyMap[key] = i;
                    }
                }
            }
            // 尋找目前這項（newStartIdx）在keyMap中的映射的位置序号
            const idxInOld = keyMap[newStartVnode.key];
            if (idxInOld === undefined) {
                // 如果idxInOld是undefined表示踏實全新的項，此時會将該項建立為DOM節點并插入到舊前之前
                parentElm.insertBefore(createElement(newStartVnode), oldStartVnode.elm);
            }
            else {
                // 如果不是undefined，則不是全新的項，則需要移動
                const elmToMove = oldCh[idxInOld];
                patchVnode(elmToMove, newStartVnode);
                // 把這項設定為undefined，表示已經處理完這項了
                oldCh[idxInOld] = undefined;
                // 移動
                parentElm.insertBefore(elmToMove.elm, oldStartVnode.elm);
            }
            // 指針下移，隻移動新的頭
            newStartVnode = newCh[++newStartIdx];
        }
    }

    // 循環結束後，處理未處理的項
    if (newStartIdx <= newEndIdx) {
        console.log('new還有剩餘節點沒有處理，要加項，把所有剩餘的節點插入到oldStartIdx之前');
        // 周遊新的newCh，添加到老的沒有處理的之前
        for (let i = newStartIdx; i <= newEndIdx; i++) {
            // insertBefore方法可以自動識别null，如果是null就會自動排到隊尾去
            // newCh[i]現在還沒有真正的DOM，是以要調用createElement函數變為DOM
            parentElm.insertBefore(createElement(newCh[i]), oldCh[oldStartIdx].elm);
        }
    }
    else if (oldStartIdx <= oldEndIdx) {
        console.log('old還有剩餘節點沒有處理，要删除項');
        // 批量删除oldStart和oldEnd指針之間的項
        for (let i = oldStartIdx; i <= oldEndIdx; i++) {
            if (oldCh[i]) {
                parentElm.removeChild(oldCh[i].elm);
            }
        }
    }
}

參考文獻

本文是筆者看了邵山歡老師的視訊後做的一次總結，邵老師講的真心很好，爆贊。

1.如果覺得這篇文章還不錯，來個分享、點贊、在看三連吧，讓更多的人也看到～

2.關注公衆号執鸢者，領取學習資料，定期為你推送原創深度好文

3.掃描下方添加進群，裡面大佬多多，一起向他們學習

一文搞定Diff算法

1. 圖解JavaScript——代碼實作（Object.create()、flat()等十四種代碼原理實作不香嗎？）

2. 圖解JavaScript——代碼實作【2】（重點是Promise、Async、釋出/訂閱原理實作）

3. 圖解javascript——基礎篇

4. 圖解JavaScript——進階篇

5. 十五張圖帶你徹底搞懂從URL到頁面展示發生的故事

6. 圖解浏覽器安全（同源政策、XSS、CSRF、跨域、HTTPS、安全沙箱等串成糖葫蘆）

7. 六張圖帶你從HTTP/0.9進化到HTTP3.0

8. （2.6w字）網絡知識點靈魂拷問（上）——前端面試必問

9. （2.6w字）網絡知識點靈魂拷問（下）——前端面試必問

10. 理論與API相結合了解Node中的網絡通信

11. 硬核知識點——浏覽器中的三類五種請求

12. 理論與實踐相結合徹底了解CORS

13. 三步法解析Express源碼

14. 一篇搞定前端高頻手撕算法題（36道）

15. 十七張圖玩轉Node程序——榨幹它

16. 理論與API相結合了解Node中的網絡通信

17. 一文徹底搞懂前端監控

18. 前端的葵花寶典——架構

19. canvas從入門到豬頭

20. 前端工程師的一大神器——puppeteer

21. 2021 年前端寶典【超三百篇】

22. 前端也要懂機器學習（上）

23. 前端也要懂機器學習（下）

24. 學架構助力前端起飛

一文搞定Diff算法

一、基礎

二、整個流程

三、實戰

3.1 patch函數

3.2 patchVnode函數

3.3 updateChildren函數

參考文獻

繼續閱讀

neo4j之cypher使用文檔

Dijkstra--簡易版（最短路徑）

适用于JavaScript的ECMAScript 2020規範向前發展

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

spark/scala關于【資源檔案】加載方法概述外部檔案加載方案測試資源檔案打包入jar包中小結

mybatis_入門程式Mybatis入門

JS生成uuid的四種方法

AOP程式設計_Android優雅權限架構(1)概念基礎，2021金三銀四前言正文大綱正文

Effective Java 8:通用程式設計

OOM三種類型

工廠模式-三種類型

【遞歸】高效率求2的n次幂

layui多任務上傳添加進度條

win10本地scala和spark安裝安裝scala安裝spark

scala (3) Function 和 Method

hdu7108哈希