當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

面试中的网红虚拟DOM，你知多少呢？深入解读diff算法

發布時間：2023/12/4 编程问答 39 豆豆

生活随笔收集整理的這篇文章主要介紹了面试中的网红虚拟DOM，你知多少呢？深入解读diff算法小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

深入淺出虛擬DOM和diff算法

一、虛擬DOM（Vitual DOM）
- 1、虛擬DOM（Vitual DOM）和diff的關系
- 2、真實DOM的渲染過程
- 3、虛擬DOM是什么？
- 4、解決方案 - vdom
- - （1）問題引出
  - （2）vdom如何解決問題：將真實DOM轉為JS對象的計算
- 5、用JS模擬一個DOM結構
- 6、通過snabbdom學習vdom
- - （1）snabbdom是什么
  - （2）snabbdom淺析
  - （2）snabbdom演示
- 7、vdom總結
二、diff算法
- 1、diff算法
- 2、diff算法概述
- 3、樹diff的時間復雜度O(n³)
- 4、優化時間復雜度到O(n)
三、深入diff算法源碼
- 1、生成vnode
- 2、patch函數
- 3、patchVnode函數
- 4、updateChildren函數
四、結束語

眾所周知，在前端的面試中，面試官非常愛考vdom和diff算法。比如，可能會出現在以下場景🤏

滴滴滴，面試官發來一個面試邀請。接受邀請📞

🧑面試官：你知道 key 的作用嗎？

🙎我：key 的作用是保證數據的唯一性。

🧑面試官：怎么保證數據的唯一性？

🙎我：就…

🧑面試官：你知道虛擬dom嗎？

🙎我：虛擬dom就是……balabala

🧑面試官：（好像有點道理）那你知道diff算法嗎？

🙎我：（心里：what……diff算法是什么？？）

🧑面試官：本次面試結束，回去等面試結果通知。

🙋🙋🙋

我們都知道， key 的作用在前端的面試是一道很普遍的題目，但是呢，很多時候我們都只浮于知識的表面，而沒有去深挖其原理所在，這個時候我們的競爭力就在這被拉下了。所以呢，深入學習原理對于提升自身的核心競爭力是一個必不可少的過程。

在接下來的這篇文章中，我們將講解面試中很愛考的虛擬DOM以及其背后的diff算法。

一、虛擬DOM（Vitual DOM）

1、虛擬DOM（Vitual DOM）和diff的關系

我們都知道 DOM 操作是非常耗費性能的，早期我們用 JQuery 來自行控制 DOM 操作的時機，也就是手動調整，這樣子其實也不是特別方便。因此就出現了虛擬 DOM ，即 Vitual DOM （下文簡稱為 vdom ），來解決 DOM 操作的問題。 vdom 是現如今的一個熱門話題，也是面試中的熱門話題，基本上在前端的面試中都會問到虛擬DOM 的問題。

而為什么會問到 vdom 的問題呢，原因在于現在流行的 vue 和 react 框架，都是數據驅動視圖，并且是基于 vdom 實現的，可以說 vdom 是實現 vue 和 react 的重要基石。

談到 vdom ，我們不明覺厲的還會想到 diff算法 。那 diff算法 和 vdom 是什么關系呢？

其實， vdom 是一個大的概念，而 diff算法是 vdom 的一部分， vdom 的核心價值在于最大程度的減少DOM的使用范圍， vdom 通過把 DOM 用JS的方式進行模擬，之后進行計算和對比，最后找出最小的更新范圍去更新。那么這個對比的過程就是 diff 算法 。也就是說他們兩者是包含關系，如下圖所示：

可以說，diff 算法是 vdom 中最核心、最關鍵的部分，整個 vdom 的核心包圍著大量的 diff算法 。

有了這幾個概念的基礎鋪墊，接下來我們來開始了解 虛擬DOM 是什么。

2、真實DOM的渲染過程

在開始講解虛擬DOM 之前，我們先來了解真實的 DOM 在瀏覽器中是怎么解析的。瀏覽器渲染引擎工作流程大致分為以下4個步驟：

創建DOM樹 → 創建CSSOM樹 → 生成render樹 → 布局render樹 → 繪制render樹 。

第一步：創建 DOM 樹。渲染引擎首先解析 HTML 代碼，并生成 DOM 樹。
第二步：創建 CSSOM 樹。瀏覽為獲得外部 css 文件的數據后，就會像構建 DOM 樹一樣開始構建 CSSOM 樹，這個過程與第一步沒什么差別。
第三步：生成 Render 樹。將 DOM 樹和 CSSOM 樹關聯起來，生成一棵 Render （渲染）樹。
第四步：布局 Render 樹。有了 Render 樹之后，瀏覽器開始對渲染樹的每個節點進行布局處理，確定其在屏幕上的顯示位置。
第五步：繪制 Render 樹。將每個節點繪制到屏幕上。

引用網上的一張圖來呈現真實DOM的渲染過程：

3、虛擬DOM是什么？

當用原生 js 或者 jq 去操作真實 DOM 的時候，瀏覽器會從構建DOM樹開始，從頭到尾執行一遍流程。那這樣的話，就很有可能導致操作次數過多。當操作次數過多時，之前計算的與 DOM 節點相關的坐標值等各種值就…不知不覺的浪費掉了其性能，因此呢，虛擬DOM由此產生。

4、解決方案 - vdom

（1）問題引出

大家都知道， DOM 樹是具有一定的復雜度的，所以，在生成 DOM 樹的過程中，會不斷的進行計算操作，但難就難在，想要減少計算次數其實還是比較難的。

那換個思路考慮，我們都知道，JS 的執行速度很快很快，那能不能嘗試著把這個計算，更多的轉為JS計算呢？答案是肯定的。

（2）vdom如何解決問題：將真實DOM轉為JS對象的計算

假設在一次操作中有1000個節點需要更新 DOM ，那么 虛擬DOM 不會立即去 操作DOM ，而是將這1000次更新的 diff 內容保存到本地的一個 JS 對象當中，之后將這個 JS對象一次性 attach 到 DOM 樹上，最后再進行后續的操作，這樣子就避免了大量沒有必要的計算。

所以，用JS對象模擬DOM節點的好處是，先將頁面的更新全部反映到虛擬 DOM 上，這樣子就先**操作內存中的JS對象**。值得注意的是，操作內存中 JS 對象的速度是相當快的。因此，等到全部 DOM節點 更新完成之后，再將 最后的JS對象 映射到 真實的DOM 上，交由 瀏覽器 去繪制。

這樣，就解決了真實 DOM 渲染速度慢，性能消耗大的問題。

5、用JS模擬一個DOM結構

根據下方的 html 代碼，用 v-node 模擬出該 html 代碼的 DOM 結構。

html代碼：

用JS模擬出以上代碼的DOM結構：

{tag: 'div',props:{className: 'container',id: 'div1'},children: [{tag: 'p',chindren: 'vdom'},{tag: 'ul',props:{ style: 'font-size: 20px' },children: [{tag: 'li',children: 'a'}// ....]}] }

通過以上代碼我們可以分析出，我們用 tag ， props 和 children 來模擬 DOM 樹結構。用 JS 模擬 DOM 樹的結構，這樣做的好處在于，可以計算出最小的變更，操作最少的DOM。

6、通過snabbdom學習vdom

vue 的 vdom 和 diff算法 是參考 github 上的一個開源庫 snabbdom 改造過來的，那么我們接下來就用這個庫為例，來學習 vdom 的思想。

（1）snabbdom是什么

snabbdom 是一個簡潔又強大的 vdom 庫，易學易用；
Vue 參考它實現的 vdom 和 diff ；
Vue3.0 重寫了 vdom 的代碼，優化了性能。

（2）snabbdom淺析

我們先來看 snabbdom 首頁上的 example ，先簡單了解其思想。下面先貼上代碼：

import {init,classModule,propsModule,styleModule,eventListenersModule,h, } from "snabbdom";const patch = init([// Init patch function with chosen modulesclassModule, // makes it easy to toggle classespropsModule, // for setting properties on DOM elementsstyleModule, // handles styling on elements with support for animationseventListenersModule, // attaches event listeners ]);const container = document.getElementById("container"); //h函數輸入一個標簽，之后再輸入一個data，最周輸入一個子元素 const vnode = h("div#container.two.classes", { on: { click: someFn } }, [h("span", { style: { fontWeight: "bold" } }, "This is bold")," and this is just normal text",h("a", { props: { href: "/foo" } }, "I'll take you places!"), ]);//第一個patch函數 // Patch into empty DOM element – this modifies the DOM as a side effect patch(container, vnode);const newVnode = h("div#container.two.classes",{ on: { click: anotherEventHandler } },[h("span",{ style: { fontWeight: "normal", fontStyle: "italic" } },"This is now italic type")," and this is still just normal text",h("a", { props: { href: "/bar" } }, "I'll take you places!"),] );//第二個patch函數 // Second `patch` invocation patch(vnode, newVnode); // Snabbdom efficiently updates the old view to the new state

通過官方的例子我們可以知道， h 函數輸入一個標簽，之后輸入一個 data ，最后輸入一個子元素。并且h函數是一個 vnode 的結構（ vnode 結構見上述第5點），層級般的一層一層遞進。最后就是 patch 函數，第一個patch 函數用來對元素進行渲染，第二個 patch 函數用來比較新舊節點。

（2）snabbdom演示

接下來我們用 cdn 的方式引入 snabbdom 的庫，來演示一遍 snabbdom 是如何操作 vdom 的。附上代碼：

<!DOCTYPE html> <html> <head><meta charset="UTF-8"><title>Document</title> </head> <body><div id="container"></div><button id="btn-change">change</button><script src="https://cdn.bootcss.com/snabbdom/0.7.3/snabbdom.js"></script><script src="https://cdn.bootcss.com/snabbdom/0.7.3/snabbdom-class.js"></script><script src="https://cdn.bootcss.com/snabbdom/0.7.3/snabbdom-props.js"></script><script src="https://cdn.bootcss.com/snabbdom/0.7.3/snabbdom-style.js"></script><script src="https://cdn.bootcss.com/snabbdom/0.7.3/snabbdom-eventlisteners.js"></script><script src="https://cdn.bootcss.com/snabbdom/0.7.3/h.js"></script><script>const snabbdom = window.snabbdom// 定義 patchconst patch = snabbdom.init([snabbdom_class,snabbdom_props,snabbdom_style,snabbdom_eventlisteners])// 定義 hconst h = snabbdom.hconst container = document.getElementById('container')// 生成 vnodeconst vnode = h('ul#list', {}, [h('li.item', {}, 'Item 1'),h('li.item', {}, 'Item 2')])patch(container, vnode)document.getElementById('btn-change').addEventListener('click', () => {// 生成 newVnodeconst newVnode = h('ul#list', {}, [h('li.item', {}, 'Item 1'),h('li.item', {}, 'Item B'),h('li.item', {}, 'Item 3')])patch(vnode, newVnode) // vnode = newVnode → patch 之后，應該用新的覆蓋現有的 vnode ，否則每次 change 都是新舊對比})</script> </body> </html>

此時我們來看瀏覽器的顯示效果：

我們可以看到，最終的效果是當我們點擊時， DOM 樹不會一整棵樹重新渲染，而是只針對改變的值進行重新比較，最終只將改變的節點進行渲染。

通過這樣的演示，相信大家對真實 DOM 和虛擬 DOM 的區別有了一定的了解。

7、vdom總結

講到這里，我們來對vdom做一個總結：

可以通過 JS 來模擬 DOM 結構（vnode）；
新舊 vnode 對比，得出最小的更新范圍，最后更新DOM；
數據驅動視圖的模式下，可以有效地控制DOM操作。

二、diff算法

我們在上述講 vdom 的時候說過， vdom 的核心價值就在于最大程度的減少DOM的使用范圍。那 vdom 是通過什么方式呢，它是通過把 DOM 用 JS 來去模擬，之后進行計算和進行對比，最后找出最小的更新范圍去更新。那么這個對比的過程對應的就是我們經常聽到的 diff 算法。

接下來就讓我們一起來了解 vdom 的另外一個內容， diff 算法。

1、diff算法

diff算法是前端的一個熱門話題，同時也是 vdom 中最核心、最關鍵的部分。
diff算法在日常使用 vue 和 react 中經常出現（如key）。

2、diff算法概述

diff 即對比，是一個廣泛的概念，如linux diff命令、git diff命令等。
兩個js對象也可以做 diff ，如 github 上的jiff庫，這個庫可以直接用來給兩個js對象做diff。
兩棵樹做 diff ，如上述所說的 vdom 和 diff 。

我們來看個例子🌰：

看到上面兩棵樹，我們可以想象下它是如何進行 diff 算法的。我們可以看到，右邊這棵樹要把左邊的 E 改為 X ，同時要新增一個節點 H 。因此如果通過 diff 來實現的話，我們可以對其進行新舊節點的比較，如果比較完一樣，則不動它；如果比較完不一樣，則對它進行修改。這樣處理的話，5個節點只需要修改2次，而不用修改5次，效率很是UpUp。

3、樹diff的時間復雜度O(n³)

對于樹來說，原始的時間復雜度有O(n³)。那么這個 O(n³) 是怎么來的呢？

首先，遍歷tree1；其次，遍歷tree2；最后，對樹進行排序。這樣 n*n*n ，就達到了O(n³)。

假設現在有1000個節點要操作，那1000的3次方就1億次了，因此，樹的這個算法不可用。那我們怎么解決呢？繼續看下面。

4、優化時間復雜度到O(n)

因為樹的時間復雜度是O(n³)，因此，我們就想辦法，優化其時間復雜度從O(n³)到O(n)，以達到操作 vdom 節點，那這個優化過程其實我們所說的 diff 算法。通過 diff 算法，我們可以將時間復雜度從O(n³)優化到O(n)。diff算法的具體思想如下：

只比較同一層級，不跨級比較；
tag 不相同，則直接刪掉重建，不再深度比較；
tag 和 key ，兩者都相同，則認為是相同節點，不再深度比較。

三、深入diff算法源碼

1、生成vnode

我們先來回顧下上面講的 snabbdom ， diff 比較先是在 h 函數里面進行，這個 h 函數輸入一個標簽，之后輸入一個 data ，最后輸入一個子元素。并且 h 函數是一個 vnode 的結構，層級般的一層一層遞進。最后就是 patch 函數，第一個patch 函數用來對元素進行渲染，第二個 patch 函數用來比較新舊節點。

接下來我們來看下它是如何生成vnode的。

先克隆一份snabbdom的代碼下來，打開 src|h.ts 文件，直接來看 h 函數，具體代碼如下：

export function h(sel: string): VNode; export function h(sel: string, data: VNodeData | null): VNode; export function h(sel: string, children: VNodeChildren): VNode; export function h(sel: string,data: VNodeData | null,children: VNodeChildren ): VNode; export function h(sel: any, b?: any, c?: any): VNode {let data: VNodeData = {};let children: any;let text: any;let i: number;if (c !== undefined) {if (b !== null) {data = b;}if (is.array(c)) {children = c;} else if (is.primitive(c)) {text = c;} else if (c && c.sel) {children = [c];}} else if (b !== undefined && b !== null) {if (is.array(b)) {children = b;} else if (is.primitive(b)) {text = b;} else if (b && b.sel) {children = [b];} else {data = b;}}if (children !== undefined) {for (i = 0; i < children.length; ++i) {if (is.primitive(children[i]))children[i] = vnode(undefined,undefined,undefined,children[i],undefined);}}if (sel[0] === "s" &&sel[1] === "v" &&sel[2] === "g" &&(sel.length === 3 || sel[3] === "." || sel[3] === "#")) {addNS(data, children, sel);}// 返回vnode，這個vnode對應patch下的vnodereturn vnode(sel, data, children, text, undefined); }

我們看到最后一行， h 函數返回的是一個 vnode 函數。之后我們繼續找 vnode 的文件，在 src|vnode.ts 文件中。附上最關鍵部分代碼：

export function vnode(sel: string | undefined,data: any | undefined,children: Array<VNode | string> | undefined,text: string | undefined,elm: Element | Text | undefined ): VNode {const key = data === undefined ? undefined : data.key;// 返回一個對象// elm表示vnode結構對應的是哪一個DOM元素// key可以理解為v-for時我們使用的keyreturn { sel, data, children, text, elm, key }; }

同樣定位到最后一行，大家可以發現， vnode 實際上是返回一個對象。而這個對象里，有6個元素。其中， sel, data, children, text 四個元素對應我們上面講 vnode 時對應的結構（第一點的第5點）。而 elm 表示 vnode 結構對應的是哪一個 DOM 元素，最后的 key 大家可以理解為是我們使用 v-for 時用的 key ，同時需要注意是， key 不一定只有在 v-for 時可以使用，在定義組件等各種場景時均可使用。

2、patch函數

看完 vnode ，我們來看下如何用patch函數來對比 vnode 。從官方文檔中我們可以定位到， patch 函數在 src|init.ts 文件下，我們找到 init.ts 文件。同樣，我們定位到 patch 函數部分，具體代碼如下：

// 返回一個patch函數return function patch(oldVnode: VNode | Element, vnode: VNode): VNode {let i: number, elm: Node, parent: Node;const insertedVnodeQueue: VNodeQueue = [];// 執行pre hook，hook 即 DOM 節點的生命周期for (i = 0; i < cbs.pre.length; ++i) cbs.pre[i]();// 第一個參數不是vnode，是一個DOM元素if (!isVnode(oldVnode)) {// 創建一個空的 vnode，關聯到這個DOM元素oldVnode = emptyNodeAt(oldVnode);}// 相同的vnode（key 和 sel 都相等）if (sameVnode(oldVnode, vnode)) {// vnode進行對比patchVnode(oldVnode, vnode, insertedVnodeQueue);} // 不同的 vnode ，直接刪掉重建else {elm = oldVnode.elm!;parent = api.parentNode(elm) as Node;// 重建createElm(vnode, insertedVnodeQueue);if (parent !== null) {api.insertBefore(parent, vnode.elm!, api.nextSibling(elm));removeVnodes(parent, [oldVnode], 0, 0);}}for (i = 0; i < insertedVnodeQueue.length; ++i) {insertedVnodeQueue[i].data!.hook!.insert!(insertedVnodeQueue[i]);}for (i = 0; i < cbs.post.length; ++i) cbs.post[i]();return vnode;};

閱讀以上代碼我們可以知道，我們剛開始創建時，第一個參數不是 vnode ，而是一個 DOM 元素，這個時候我們需要先創建一個空的 vnode ，來關聯到這個 DOM 元素上。

有了第一個 vnode 之后，我們在第二次 patch 時，就可以對新舊節點進行比較。而新舊節點的比較是先判斷 key 和 sel 是否相同，如果相同，則用 pathVNode 函數對新舊節點進行比較。如果是不同的 vnode ，則直接刪掉重建。

3、patchVnode函數

上面我們說到了 patchVnode 函數進行新舊節點的比較，下面來對 patchVnode 進行詳細剖析。同樣在 src|init.ts 文件中，附上patchVnode函數的代碼：

閱讀以上源碼我們可以知道：

（1） 當舊的 vnode 有 text 時，則說明舊的 children 沒有值，且新的 vnode 的 text 有值。這個時候我們就把舊的 vnode 的 children 進行刪除，刪除結束給新的 vnode 設置 text ；

（2） 當新舊節點都有 children 時，我們需要對其進行更新操作，也就是操作 updateChildren 函數。這個我們將在下面進行講解。

（3） 如果新的 vnode 有 children ，舊的 vnode 沒有 children ，則說明舊的 vnode 有 text ，所以此時需要清空舊的 vnode 的 text ，并添加新的 children 上去。

（4） 如果舊的 vnode有 children ，新的 vnode 沒有 children ，則移除舊的 vnode 的 children 。

（5） 如果新舊節點都有 text ，則直接把新的 vnode 的 text 值賦值給舊的 vnode 的 text 。

來看下圖的呈現：

4、updateChildren函數

上面分析 pathVnode 時我們講到了用 updateChildren 函數來更新新舊節點的 children 。接下來我們來看下這個函數：

我們先來看兩張圖：

大家先看圖1， updateChildren 要做得事情就是，將新舊節點進行對比，如果相同則不進行更新，如果不同則對其進行更新操作。

再看圖2，而更新的方式就是，通過對oldStartIdx，newStartIdx，oldEndIdx和newEndIdx這四個值進行比較，來得出是否需要更新操作。

那這四個值如何進行比較呢？接下來我們繼續看。

閱讀源碼我們可以分析出，通過對4種類型的節點進行比較，來判斷如何更新節點。

第一種，舊的開始節點 oldStartIdx 和新的開始節點 newStartIdx 比較。第二種，舊的開始節點 oldStartIdx 和新的結束節點 newEndIdx 比較。第三種，舊的結束節點 oldEndIdx 和新的開始節點 newStartIdx 比較。第四種，舊的結束節點 oldEndIdx 和新的結束節點 newEndIdx 比較。

如果以上這四種比較都沒有命中，則拿取新節點的key ，之后將這個 key 查看是否對應上 oldCh 中某個節點的 key 。如果沒有對應上，則直接重建元素。如果對應上了，還要再判斷 sel 和 key 是否相等，如果相等，則執行patchVnode函數，如果不相等，那跟前面一樣，也只能重建元素。

四、結束語

vdom的核心概念主要在 h 、 vnode 、 patch 、 diff 、 key 這幾個內容，個人覺得，整個 diff 的比較都在圍繞著這幾個函數進行，所以了解這幾個核心概念很重要。同時，vdom存在的另一個更重要的價值莫過于數據驅動視圖了， vdom 通過控制 DOM 的操作來使得數據可以去驅動視圖。

關于虛擬DOM和diff的講解到此就結束啦！如有不理解或有誤的地方歡迎評論區評論或私信我交流~

關注公眾號 星期一研究室 ，不定期分享學習干貨，學習路上不迷路~
如果這篇文章對你有用，記得點個贊加個關注再走哦~

總結

以上是生活随笔為你收集整理的面试中的网红虚拟DOM，你知多少呢？深入解读diff算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。

上一篇： GELID 推出 HeatPhase U
下一篇： TypeScript，从0到入门带你进入