diff算法是一種通過同層的樹節(jié)點進行比較的高效算法，避免了對樹進行逐層搜索遍歷。那么大家對diff算法嗎有多少了解？下面本篇文章就來帶大家深入解析下vue2的diff算法，希望對大家有所幫助！
(資料圖片)
因為之前看面試直播也經(jīng)常問到 Diff 算法，然后作者本人用 Vue2 比較多，所以打算研究一下 Vue2 的 Diff 算法，其實很早就想學的，但是可能因為感覺 Diff 算法比較深奧，就一直拖著沒學，但是最近在準備面試，就想著遲早都要學的，趁這個機會把 Diff 算法搞懂吧 ?，作者就花了一天的時間研究了一下，可能沒有完全理解 Diff 算法的精髓，請各位見諒。
因為 Vue2 底層是用虛擬 DOM 來表示頁面結(jié)構的，虛擬 DOM其實就是一個對象，如果想知道怎么生成的，其實大概流程就是：
首先解析模板字符串，也就是.vue文件然后轉(zhuǎn)換成 AST 語法樹接著生成 render 函數(shù)最后調(diào)用 render 函數(shù)，就能生成虛擬 DOM 【相關推薦：vuejs視頻教程、web前端開發(fā)】其實框架為了性能才使用的虛擬 DOM，因為 js 生成 DOM 然后展示頁面是很消耗性能的，如果每一次的更新都把整個頁面重新生成一遍那體驗肯定不好，所以需要找到兩個頁面中變化的地方，然后只要把變化的地方用 js 更新 (可能是增加、刪除或者更新)一下就行了，也就是最小量更新。那么怎么實現(xiàn)最小量更新呢？那么就要用 Diff 算法了，那么 Diff 算法對比的到底是什么呢？可能這是剛學 Diff 算法比較容易誤解的地方，其實比對的是新舊虛擬 DOM，所以 Diff 算法就是找不同，找到兩次虛擬 DOM 的不同之處，然后將不同反應到頁面上，這就實現(xiàn)了最小量更新，如果只更新變化的地方那性能肯定更好。
其實這個比較難解釋，作者也就大致說一下，學了 Vue 的都知道這個框架的特點之一就有數(shù)據(jù)響應式，什么是響應式，也就是數(shù)據(jù)更新頁面也更新，那么頁面是怎么知道自己要更新了呢？其實這就是這個框架比較高明的地方了，大致流程如下：
之前也說了會運行 render 函數(shù)，那么運行 render 函數(shù)的時候會被數(shù)據(jù)劫持，也就是進入Object.defineProperty的 get，那么在這里收集依賴，那么是誰收集依賴呢？是每個組件，每個組件就是一個 Watcher，會記錄這個組件內(nèi)的所有變量 (也就是依賴)，當然每個依賴 (Dep)也會收集自己所在組件的 Watcher；然后當頁面中的數(shù)據(jù)發(fā)生變化，那么就會出發(fā) Object.defineProperty的 set，在這個函數(shù)里面數(shù)據(jù)就會通知每個 Watcher 更新頁面，然后每個頁面就會調(diào)用更新方法，這個方法就是 patch；接著，就要找到兩個頁面之間的變化量，那么就要用到 Diff 算法了最后找到變化量后就可以進行更新頁面了其實是邊找邊更新的，為了讓大家理解容易就將這兩個部分分開了
面試問到 Diff 算法是什么，大家肯定會說兩句，比如 頭頭、尾尾、尾頭、頭尾、深度優(yōu)先遍歷(dfs)、同層比較類似這些話語，雖然能說一兩句其實也是淺嘗輒止。其實作者看了 CSDN 上發(fā)的關于 Diff 算法的文章，就是閱讀量很高的文章，作者覺得他也沒講明白，可能他自己沒明白，或者自己明白了但是沒講清楚，那么作者會用自己的感悟和大家分享一下。
為了讓大家能夠了解清楚，這里先說明一下函數(shù)調(diào)用流程：
patchpatchVnodeupdateChildrenDiff 算法的 前提這個是很重要的，可能大家會問什么是前提？不就是之前說的那些比較嘛？說的沒錯但也不對，因為 Diff 算法到達之前說的 頭頭、尾尾、尾頭、頭尾這一步的前提就是兩次對比的節(jié)點是 相同的，這里的相同不是大家想的完全相同，只是符合某些條件就是相同了，為了簡化說明，文章就只考慮一個標簽只包含 key和 標簽名(tag)，那么之前說的相同就是 key 相同以及 tag 相同，為了證明作者的說法是有點正確的，那么這里也貼上源碼：
// https://github.com/vuejs/vue/blob/main/src/core/vdom/patch.ts// 36行function sameVnode(a, b) { return ( a.key === b.key && a.asyncFactory === b.asyncFactory && ((a.tag === b.tag && a.isComment === b.isComment && isDef(a.data) === isDef(b.data) && sameInputType(a, b)) || (isTrue(a.isAsyncPlaceholder) && isUndef(b.asyncFactory.error))) )}如果怕亂了，下面的可以省略不看也沒事不影響整體了解，下面只是為了考慮所有情況才加的一個判斷：那么如果兩個虛擬 DOM 不相同其實就不用繼續(xù)比較了，而且如果相同也不用比較了，這里的相同是真的完全相同，也就是兩個虛擬 DOM 的地址是一樣的，那么也貼上源碼：
function patchVnode(......) { if (oldVnode === vnode) { return } ......}到目前為止大家可能會比較亂，現(xiàn)在總結(jié)一下：
在patch函數(shù)里比較的是新老虛擬 DOM 是否是 key 相同以及 tag 相同，如果不相同那么就直接替換，如果相同用 patchVnode說了這么多，其實作者也就想表達一個觀點，就是只有當兩次比較的虛擬 DOM 是 相同的才會考慮 Diff 算法，如果不符合那直接把原來的刪除，替換新的 DOM 就行了。
這個函數(shù)里的才是真正意義上的 Diff 算法，那么接下來會結(jié)合源碼向大家介紹一下。
源碼中核心代碼在 patch.ts 的 638 行至 655 行。
其實，目前介紹 patchVnode 的都是直接對著源碼來介紹的，但是大家可能不清楚為啥要這么分類，那么作者在這里就讓大家明白為什么這么分類，首先在這里說一個結(jié)論：
就是text屬性和 children屬性不可能同時存在，這個需要大家看模板解析源碼部分那么在對比新舊節(jié)點的情況下，主要比較的就是是否存在 text和 children的情況，那么會有如下九種情況
| 情況 | 老節(jié)點 text | 老節(jié)點 children | 新節(jié)點 text | 新節(jié)點 children |
|---|---|---|---|---|
| 1 | ? | ? | ? | ? |
| 2 | ? | ? | ? | ? |
| 3 | ? | ? | ? | ? |
| 4 | ? | ? | ? | ? |
| 5 | ? | ? | ? | ? |
| 6 | ? | ? | ? | ? |
| 7 | ? | ? | ? | ? |
| 8 | ? | ? | ? | ? |
| 9 | ? | ? | ? | ? |
按照上面的表格，因為如果新節(jié)點有文本節(jié)點，其實老節(jié)點不管是什么都會被替換掉，那么就可以按照 新節(jié)點 text是否存在來分類，其實 Vue 源碼也是這么來分類的：
if (isUndef(vnode.text)) { // 新虛擬 DOM 有子節(jié)點} else if (oldVnode.text !== vnode.text) { // 如果新虛擬 DOM 是文本節(jié)點，直接用 textContent 替換掉 nodeOps.setTextContent(elm, vnode.text)}那么如果有子節(jié)點的話，那應該怎么分類呢？我們可以按照每種情況需要做什么來進行分類，比如說：
第一種情況，我們啥都不用做，因此也可以不用考慮第二種情況，我們應該把原來 DOM 的textContent設置為 ""第三種情況，我們也應該把原來 DOM 的 textContent設置為 ""第四種情況，我們應該加入新的子節(jié)點第五種情況，這個情況比較復雜，需要對比新老子節(jié)點的不同第六種情況，我們應該把原來的 textContent設置為 ""后再加入新的子節(jié)點那么通過以上六種情況 (新虛擬 DOM 不含有 text，也就是不是文本節(jié)點的情況)，我們可以很容易地進行歸類：
分類 1??：第二種情況和 第三種情況。進行的是操作是：把原來 DOM 的 textContent設置為 ""分類 2??： 第四種情況和 第六種情況。進行的是操作是：如果老虛擬 DOM 有 text，就置空，然后加入新的子節(jié)點分類 3??：第五種情況。進行的是操作是：需要進行精細比較，即對比新老子節(jié)點的不同其實源碼也是這么來進行分類的，而且之前說的 同層比較也就得出來了，因為每次比較都是比較的同一個父節(jié)點每一個子元素 (這里的子元素包括文本節(jié)點和子節(jié)點)是否相同，而 深度優(yōu)先遍歷(dfs)是因為每次比較中，如果該節(jié)點有子節(jié)點 (這里的子節(jié)點指的是有 children 屬性，而不包括文本節(jié)點)的話需要進行遞歸遍歷，知道最后到文本節(jié)點結(jié)束。
?? 這里需要搞清楚子節(jié)點和子元素的區(qū)別和聯(lián)系
然后我們來看看源碼是怎么寫吧，只看新虛擬 DOM 不含有 text，也就是不是文本節(jié)點的情況：
if (isUndef(vnode.text)) { if (isDef(oldCh) && isDef(ch)) { if (oldCh !== ch) // 遞歸處理，精細比較 // 對應分類 3?? updateChildren(elm, oldCh, ch, insertedVnodeQueue, removeOnly) } else if (isDef(ch)) { if (__DEV__) { checkDuplicateKeys(ch) // 可以忽略不看 } // 對應分類 2?? if (isDef(oldVnode.text)) nodeOps.setTextContent(elm, "") addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue) } else if (isDef(oldCh)) { // 對應分類 1?? removeVnodes(oldCh, 0, oldCh.length - 1) } else if (isDef(oldVnode.text)) { // 對應分類 1?? nodeOps.setTextContent(elm, "") }}?我們可以看到源碼把分類 1?? 拆開來了，這是因為如果老虛擬 DOM 有子節(jié)，那么可能綁定了一些函數(shù)，需要進行解綁等一系列操作，作者也沒自信看，大致瞄了一眼，但是如果我們要求不高，如果只是想自己手動實現(xiàn) Diff 算法，那么沒有拆開的必要。
作者覺得這么講可能比網(wǎng)上其他介紹 Diff 算法的要好，其他的可能直接給你說源碼是怎么寫的，可能沒有說明白為啥這么寫，但是通過之前這么分析講解后可能你對為什么這么寫會有更深的理解和幫助吧。
同層比較
因為當都含有子節(jié)點，即都包含 children 屬性后，需要精細比較不同，不能像之前那些情況一樣進行簡單處理就可以了那么這個函數(shù)中就會介紹大家經(jīng)常說的 頭頭、尾尾、尾頭、頭尾比較了，其實這不是 Vue 提出來的，是很早就提出來的算法，就一直沿用至今，大家可以參考【snabbdom 庫】
? 在這之前我們要定義四個指針 newStartIdx、newEndIdx、oldStartIdx和 oldEndIdx，分別指向 新頭節(jié)點、新尾節(jié)點、舊頭節(jié)點與 舊尾節(jié)點
循環(huán)條件如下：
while(oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) { ......}其實這個比較也就是按人類的習慣來進行比較的，比較順序如下 ：
1??新頭節(jié)點與舊頭節(jié)點：++newStartIdx和 ++oldStartIdx2?? 新尾節(jié)點與舊尾節(jié)點：--newEndIdx和 --oldEndIdx3?? 新尾節(jié)點與舊頭節(jié)點：需要將 舊頭節(jié)點移動到 舊尾節(jié)點之前，為什么要這么做，講起來比較復雜，記住就好，然后 --newEndIdx和 ++oldStartIdx4?? 新頭節(jié)點與舊尾節(jié)點：需要將 舊尾節(jié)點移動到 舊頭節(jié)點之前，為什么要這么做，講起來比較復雜，記住就好，然后 ++newStartIdx和 --oldEndIdx5?? 如果都沒有匹配的話，就把 新頭節(jié)點在舊節(jié)點列表 (也就是 children 屬性的值)中進行查找，查找方式按照如下：如果有 key就把 key在 oldKeyToIdx進行匹配，oldKeyToIdx根據(jù)舊節(jié)點列表中元素的 key生成對應的下標如果沒有，就按順序遍歷舊節(jié)點列表找到該節(jié)點所在的下標如果在舊節(jié)點列表是否找到也分為兩種情況：找到了，那么只要將 新頭節(jié)點添加到 舊頭節(jié)點之前即可沒找到，那么需要創(chuàng)建新的元素然后添加到 舊頭節(jié)點之前然后把這個節(jié)點設置為 undefined根據(jù)循環(huán)條件我們可以得到兩種剩余情況，如下：
6?? 如果oldStartIdx > oldEndIdx說明老節(jié)點先遍歷完成，那么新節(jié)點比老節(jié)點多，就要把 newStartIdx與 newEndIdx之間的元素添加7?? 如果 newStartIdx > newEndIdx說明新節(jié)點先遍歷完成，那么老節(jié)點比新節(jié)點多，就要把 oldStartIdx與 oldEndIdx之間的元素刪除其實我們上面還沒有考慮如果節(jié)點為 undefined的情況，因為在上面也提到過，如果四種都不匹配后會將該節(jié)點置為 undefined，也只有舊節(jié)點列表中才有，因此要在開頭考慮這兩種情況：
oldStartVnode為 undefined：++oldStartIdx9?? 當 oldEndVnode為 undefined：--oldEndIdx那么我們來看源碼怎么寫的吧，其中用到的函數(shù)可以查看源碼附錄：
// https://github.com/vuejs/vue/blob/main/src/core/vdom/patch.ts// 439 行至 556 行while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) { if (isUndef(oldStartVnode)) { // 情況 8?? oldStartVnode = oldCh[++oldStartIdx] // Vnode has been moved left } else if (isUndef(oldEndVnode)) { // 情況 9?? oldEndVnode = oldCh[--oldEndIdx] } else if (sameVnode(oldStartVnode, newStartVnode)) { // 情況 1?? patchVnode(...) oldStartVnode = oldCh[++oldStartIdx] newStartVnode = newCh[++newStartIdx] } else if (sameVnode(oldEndVnode, newEndVnode)) { // 情況 2?? patchVnode(...) oldEndVnode = oldCh[--oldEndIdx] newEndVnode = newCh[--newEndIdx] } else if (sameVnode(oldStartVnode, newEndVnode)) { // Vnode moved right // 情況 3?? patchVnode(...) canMove && nodeOps.insertBefore( parentElm, oldStartVnode.elm, nodeOps.nextSibling(oldEndVnode.elm) ) oldStartVnode = oldCh[++oldStartIdx] newEndVnode = newCh[--newEndIdx] } else if (sameVnode(oldEndVnode, newStartVnode)) { // Vnode moved left // 情況 4?? patchVnode(...) canMove && nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm) oldEndVnode = oldCh[--oldEndIdx] newStartVnode = newCh[++newStartIdx] } else { // 情況 5?? if (isUndef(oldKeyToIdx)) // 創(chuàng)建 key -> index 的 Map oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx) // 找到 新頭節(jié)點 的下標 idxInOld = isDef(newStartVnode.key) ? oldKeyToIdx[newStartVnode.key] : findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx) if (isUndef(idxInOld)) { // New element // 如果沒找到 createElm(...) } else { // 如果找到了 vnodeToMove = oldCh[idxInOld] if (sameVnode(vnodeToMove, newStartVnode)) { patchVnode(...) oldCh[idxInOld] = undefined canMove && nodeOps.insertBefore( parentElm, vnodeToMove.elm, oldStartVnode.elm ) } else { // same key but different element. treat as new element createElm(...) } } newStartVnode = newCh[++newStartIdx] }}if (oldStartIdx > oldEndIdx) { // 情況 6?? refElm = isUndef(newCh[newEndIdx + 1]) ? null : newCh[newEndIdx + 1].elm addVnodes(...)} else if (newStartIdx > newEndIdx) { // 情況 7?? removeVnodes(...)}如果問為什么這么比較，回答就是經(jīng)過很多人很多年的討論得出的，其實只要記住過程就行了，如果想要更深了解 Diff 算法，可以去 B 站看【尚硅谷】Vue源碼解析之虛擬DOM和diff算法
這個問題面試很常見，但是可能大部分人也就只會背八股，沒有完全理解，那么經(jīng)過以上的介紹，我們可以得到自己的理解：
首先，如果不加 key 的話，那么就不會去 Map 里匹配 (O(1))，而是循環(huán)遍歷整個列表 (O(n))，肯定加 key 要快一點，性能更高其次，如果不加 key 那么在插入或刪除的時候就會出現(xiàn)，原本不是同一個節(jié)點的元素被認為是相同節(jié)點，上面也有說過是sameVnode函數(shù)判斷的，因此可能會有額外 DOM 操作為什么說可能有額外 DOM 操作呢？這個和插入的地方有關，之后會討論，同理刪除也一樣
我們分為三個實驗：沒有 key、key 為 index、key 唯一，僅證明加了 key 可以進行最小化更新操作。
實驗代碼
有小伙伴評論說可以把代碼貼上這樣更好，那么作者就把代碼附上 ?：
<!DOCTYPE html><html><head> <meta charset="UTF-8"> <meta http-equiv="X-UA-Compatible" content="IE=edge"> <meta name="viewport" content="width=device-width, initial-scale=1.0"> <title>Document</title> <script src="https://cdn.jsdelivr.net/npm/vue@2/dist/vue.js"></script> <style> .box { display: flex; flex-direction: row; } .item { flex: 1; } </style></head><body> <div id="app"> <div> <div> <h3>沒有 key</h3> <p v-for="(item, index) in list">{{ item }}</p> </div> <div> <h3>key 為 index</h3> <p v-for="(item, index) in list" :key="index">{{ item }}</p> </div> <div> <h3>key 唯一</h3> <p v-for="(item, index) in list" :key="item">{{ item }}</p> </div> </div> <button @click="click1">push(4)</button> <button @click="click2">splice(1, 0, 666)</button> <button @click="click3">unshift(999)</button> <br /><br /> <button @click="click4">pop()</button> <button @click="click5">splice(1, 1)</button> <button @click="click6">shift()</button> </div> <script> var app = new Vue({ el: "#app", data: { show: false, list: [1, 2, 3], }, methods: { click1() { this.list.push(4); }, click2() { this.list.splice(1, 0, 666); }, click3() { this.list.unshift(999); }, click4() { this.list.pop(); }, click5() { this.list.splice(1, 1); }, click6() { this.list.shift(); } }, }) </script></body></html>實驗如下所示，我們首先更改原文字，然后點擊按鈕**「觀察節(jié)點發(fā)生變化的個數(shù)」**：
表格為每次實驗中，每種情況的最小更新量，假設列表原來的長度為 n
| 實驗 | 沒有 key | key 為 index | key 唯一 |
|---|---|---|---|
| 在隊尾增加 | 1 | 1 | 1 |
| 在隊中增加 | n - i + 1 | n - i + 1 | 1 |
| 在隊首增加 | n + 1 | n + 1 | 1 |
表格為每次實驗中，每種情況的最小更新量，假設列表原來的長度為 n
| 實驗 | 沒有 key | key 為 index | key 唯一 |
|---|---|---|---|
| 在隊尾刪除 | 1 | 1 | 1 |
| 在隊中刪除 | n - i | n - i | 1 |
| 在隊首刪除 | n | n | 1 |
通過以上實驗和表格可以得到加上 key 的性能和最小量更新的個數(shù)是最小的，雖然在 在隊尾增加和 在隊尾刪除的最小更新量相同，但是之前也說了，如果沒有 key 是要循環(huán)整個列表查找的，時間復雜度是 O(n)，而加了 key 的查找時間復雜度為 O(1)，因此總體來說加了 key 的性能要更好。
本文從源碼和實驗的角度介紹了 Diff 算法，相信大家對 Diff 算法有了更深的了解了，如果有問題可私信交流或者評論區(qū)交流，如果大家喜歡的話可以點贊 ? 收藏 ?
列舉一些源碼中出現(xiàn)的簡單函數(shù)
setTextContent
function setTextContent(node: Node, text: string) { node.textContent = text}isUndef
function isUndef(v: any): v is undefined | null { return v === undefined || v === null}isDef
function isDef<T>(v: T): v is NonNullable<T> { return v !== undefined && v !== null}insertBefore
function insertBefore( parentNode: Node, newNode: Node, referenceNode: Node) { parentNode.insertBefore(newNode, referenceNode)}nextSibling
function nextSibling(node: Node) { return node.nextSibling}createKeyToOldIdx
function createKeyToOldIdx(children, beginIdx, endIdx) { let i, key const map = {} for (i = beginIdx; i <= endIdx; ++i) { key = children[i].key if (isDef(key)) map[key] = i } return map}（學習視頻分享：vuejs入門教程、編程基礎視頻）
以上就是深入淺析Vue2中的Diff算法的詳細內(nèi)容，更多請關注php中文網(wǎng)其它相關文章！
營業(yè)執(zhí)照公示信息