diff 算法是渲染器中最復(fù)雜的部分，本篇文章帶大家了解一下Vue中的雙端diff 算法，希望對(duì)大家有所幫助！

Vue 和 React 都是基于 vdom 的前端框架，組件渲染會(huì)返回 vdom，渲染器再把 vdom 通過增刪改的 api 同步到 dom。（學(xué)習(xí)視頻分享：vuejs視頻教程）

當(dāng)再次渲染時(shí)，會(huì)產(chǎn)生新的 vdom，渲染器會(huì)對(duì)比兩棵 vdom 樹，對(duì)有差異的部分通過增刪改的 api 更新到 dom。

這里對(duì)比兩棵 vdom 樹，找到有差異的部分的算法，就叫做 diff 算法。

diff 算法是渲染器中最復(fù)雜的部分，也是面試的熱點(diǎn)問題。今天我們就通過 Vue 的 diff 算法來(lái)探究下 diff 算法吧。

diff 算法

我們知道，兩棵樹做 diff，復(fù)雜度是 O(n^3) 的，因?yàn)槊總€(gè)節(jié)點(diǎn)都要去和另一棵樹的全部節(jié)點(diǎn)對(duì)比一次，這就是 n 了，如果找到有變化的節(jié)點(diǎn)，執(zhí)行插入、刪除、修改也是 n 的復(fù)雜度。所有的節(jié)點(diǎn)都是這樣，再乘以 n，所以是 O(n * n * n) 的復(fù)雜度。

這樣的復(fù)雜度對(duì)于前端框架來(lái)說是不可接受的，這意味著 1000 個(gè)節(jié)點(diǎn)，渲染一次就要處理 1000 * 1000 * 1000，一共 10 億次。

所以前端框架的 diff 約定了兩種處理原則：只做同層的對(duì)比，type 變了就不再對(duì)比子節(jié)點(diǎn)。

因?yàn)?dom 節(jié)點(diǎn)做跨層級(jí)移動(dòng)的情況還是比較少的，一般情況下都是同一層級(jí)的 dom 的增刪改。

這樣只要遍歷一遍，對(duì)比一下 type 就行了，是 O(n) 的復(fù)雜度，而且 type 變了就不再對(duì)比子節(jié)點(diǎn)，能省下一大片節(jié)點(diǎn)的遍歷。另外，因?yàn)?vdom 中記錄了關(guān)聯(lián)的 dom 節(jié)點(diǎn)，執(zhí)行 dom 的增刪改也不需要遍歷，是 O(1)的，整體的 diff 算法復(fù)雜度就是 O(n) 的復(fù)雜度。

1000 個(gè)節(jié)點(diǎn)渲染一次最多對(duì)比 1000 次，這樣的復(fù)雜度就是可接受的范圍了。

但是這樣的算法雖然復(fù)雜度低了，卻還是存在問題的。

比如一組節(jié)點(diǎn)，假設(shè)有 5 個(gè)，類型是 ABCDE，下次渲染出來(lái)的是 EABCD，這時(shí)候逐一對(duì)比，發(fā)現(xiàn) type 不一樣，就會(huì)重新渲染這 5 個(gè)節(jié)點(diǎn)。

而且根據(jù) type 不同就不再對(duì)比子節(jié)點(diǎn)的原則，如果這些節(jié)點(diǎn)有子節(jié)點(diǎn)，也會(huì)重新渲染。

dom 操作是比較慢的，這樣雖然 diff 的算法復(fù)雜度是低了，重新渲染的性能也不高。

所以，diff 算法除了考慮本身的時(shí)間復(fù)雜度之外，還要考慮一個(gè)因素：dom 操作的次數(shù)。

上面那個(gè)例子的 ABCDE 變?yōu)?EABCD，很明顯只需要移動(dòng)一下 E 就行了，根本不用創(chuàng)建新元素。

但是怎么對(duì)比出是同個(gè)節(jié)點(diǎn)發(fā)生了移動(dòng)呢？

判斷 type 么？ 那不行，同 type 的節(jié)點(diǎn)可能很多，區(qū)分不出來(lái)的。

最好每個(gè)節(jié)點(diǎn)都是有唯一的標(biāo)識(shí)。

所以當(dāng)渲染一組節(jié)點(diǎn)的時(shí)候，前端框架會(huì)讓開發(fā)者指定 key，通過 key 來(lái)判斷是不是有點(diǎn)節(jié)點(diǎn)只是發(fā)生了移動(dòng)，從而直接復(fù)用。

這樣，diff 算法處理一組節(jié)點(diǎn)的對(duì)比的時(shí)候，就要根據(jù) key 來(lái)再做一次算法的優(yōu)化。

我們會(huì)把基于 key 的兩組節(jié)點(diǎn)的 diff 算法叫做多節(jié)點(diǎn) diff 算法，它是整個(gè) vdom 的 diff 算法的一部分。

接下來(lái)我們來(lái)學(xué)習(xí)一下多節(jié)點(diǎn) diff 算法：

簡(jiǎn)單 diff

假設(shè)渲染 ABCD 一組節(jié)點(diǎn)，再次渲染是 DCAB，這時(shí)候怎么處理呢？

多節(jié)點(diǎn) diff 算法的目的是為了盡量復(fù)用節(jié)點(diǎn)，通過移動(dòng)節(jié)點(diǎn)代替創(chuàng)建。

所以新 vnode 數(shù)組的每個(gè)節(jié)點(diǎn)我們都要找下在舊 vnode 數(shù)組中有沒有對(duì)應(yīng) key 的，有的話就移動(dòng)到新的位置，沒有的話再創(chuàng)建新的。

也就是這樣的：

const oldChildren = n1.children const newChildren = n2.children  let lastIndex = 0 // 遍歷新的 children for (let i = 0; i < newChildren.length; i++) {     const newVNode = newChildren[i]     let j = 0     let find = false     // 遍歷舊的 children     for (j; j < oldChildren.length; j++) {       const oldVNode = oldChildren[j]       // 如果找到了具有相同 key 值的兩個(gè)節(jié)點(diǎn)，則調(diào)用 patch 函數(shù)更新       if (newVNode.key === oldVNode.key) {         find = true         patch(oldVNode, newVNode, container)                  處理移動(dòng)...                  break //跳出循環(huán)，處理下一個(gè)節(jié)點(diǎn)       }    }    // 沒有找到就是新增了    if (!find) {       const prevVNode = newChildren[i - 1]       let anchor = null       if (prevVNode) {         anchor = prevVNode.el.nextSibling       } else {         anchor = container.firstChild       }       patch(null, newVNode, container, anchor)    } }

這里的 patch 函數(shù)的作用是更新節(jié)點(diǎn)的屬性，重新設(shè)置事件監(jiān)聽器。如果沒有對(duì)應(yīng)的舊節(jié)點(diǎn)的話，就是插入節(jié)點(diǎn)，需要傳入一個(gè)它之后的節(jié)點(diǎn)作為錨點(diǎn) anchor。

我們遍歷處理新的 vnode：

先從舊的 vnode 數(shù)組中查找對(duì)應(yīng)的節(jié)點(diǎn)，如果找到了就代表可以復(fù)用，接下來(lái)只要移動(dòng)就好了。

如果沒找到，那就執(zhí)行插入，錨點(diǎn)是上一個(gè)節(jié)點(diǎn)的 nextSibling。

那如果找到了可復(fù)用的節(jié)點(diǎn)之后，那移動(dòng)到哪里呢？

其實(shí)新的 vnode 數(shù)組中記錄的順序就是目標(biāo)的順序。所以把對(duì)應(yīng)的節(jié)點(diǎn)按照新 vnode 數(shù)組的順序來(lái)移動(dòng)就好了。

const prevVNode = newChildren[i - 1] if (prevVNode) {     const anchor = prevVNode.el.nextSibling     insert(newVNode.el, container, anchor) }

要插入到 i 的位置，那就要取 i-1 位置的節(jié)點(diǎn)的 nextSibling 做為錨點(diǎn)來(lái)插入當(dāng)前節(jié)點(diǎn)。

但是并不是所有的節(jié)點(diǎn)都需要移動(dòng)，比如處理到第二個(gè)新的 vnode，發(fā)現(xiàn)它在舊的 vnode 數(shù)組中的下標(biāo)為 4，說明本來(lái)就是在后面了，那就不需要移動(dòng)了。反之，如果是 vnode 查找到的對(duì)應(yīng)的舊的 vnode 在當(dāng)前 index 之前才需要移動(dòng)。

也就是這樣：

let j = 0 let find = false // 遍歷舊的 children for (j; j < oldChildren.length; j++) {     const oldVNode = oldChildren[j]     // 如果找到了具有相同 key 值的兩個(gè)節(jié)點(diǎn)，則調(diào)用 patch 函數(shù)更新之     if (newVNode.key === oldVNode.key) {         find = true         patch(oldVNode, newVNode, container)          if (j < lastIndex) { // 舊的 vnode 數(shù)組的下標(biāo)在上一個(gè) index 之前，需要移動(dòng)           const prevVNode = newChildren[i - 1]           if (prevVNode) {             const anchor = prevVNode.el.nextSibling             insert(newVNode.el, container, anchor)           }         } else {// 不需要移動(dòng)           // 更新 lastIndex           lastIndex = j         }         break     } }

查找新的 vnode 在舊的 vnode 數(shù)組中的下標(biāo)，如果找到了的話，說明對(duì)應(yīng)的 dom 就是可以復(fù)用的，先 patch 一下，然后移動(dòng)。

移動(dòng)的話判斷下下標(biāo)是否在 lastIndex 之后，如果本來(lái)就在后面，那就不用移動(dòng)，更新下 lastIndex 就行。

如果下標(biāo)在 lastIndex 之前，說明需要移動(dòng)，移動(dòng)到的位置前面分析過了，就是就是新 vnode 數(shù)組 i-1 的后面。

這樣，我們就完成了 dom 節(jié)點(diǎn)的復(fù)用和移動(dòng)。

新的 vnode 數(shù)組全部處理完后，舊的 vnode 數(shù)組可能還剩下一些不再需要的，那就刪除它們：

// 遍歷舊的節(jié)點(diǎn) for (let i = 0; i < oldChildren.length; i++) {     const oldVNode = oldChildren[i]     // 拿著舊 VNode 去新 children 中尋找相同的節(jié)點(diǎn)     const has = newChildren.find(       vnode => vnode.key === oldVNode.key     )     if (!has) {       // 如果沒有找到相同的節(jié)點(diǎn)，則移除       unmount(oldVNode)     } }

這樣，我們就完成了兩組 vnode 的 diff 和對(duì)應(yīng) dom 的增刪改。

小結(jié)一下：

diff 算法的目的是根據(jù) key 復(fù)用 dom 節(jié)點(diǎn)，通過移動(dòng)節(jié)點(diǎn)而不是創(chuàng)建新節(jié)點(diǎn)來(lái)減少 dom 操作。

對(duì)于每個(gè)新的 vnode，在舊的 vnode 中根據(jù) key 查找一下，如果沒查找到，那就新增 dom 節(jié)點(diǎn)，如果查找到了，那就可以復(fù)用。

復(fù)用的話要不要移動(dòng)要判斷下下標(biāo)，如果下標(biāo)在 lastIndex 之后，就不需要移動(dòng)，因?yàn)楸緛?lái)就在后面，反之就需要移動(dòng)。

最后，把舊的 vnode 中在新 vnode 中沒有的節(jié)點(diǎn)從 dom 樹中刪除。

這就是一個(gè)完整的 diff 算法的實(shí)現(xiàn)。

這個(gè) diff 算法我們是從一端逐個(gè)處理的，叫做簡(jiǎn)單 diff 算法。

簡(jiǎn)單 diff 算法其實(shí)性能不是最好的，比如舊的 vnode 數(shù)組是 ABCD，新的 vnode 數(shù)組是 DABC，按照簡(jiǎn)單 diff 算法，A、B、C 都需要移動(dòng)。

那怎么優(yōu)化這個(gè)算法呢？

從一個(gè)方向順序處理會(huì)有這個(gè)問題，那從兩個(gè)方向同時(shí)對(duì)比呢？

這就是雙端 diff 算法：

雙端 diff

簡(jiǎn)單 diff 算法能夠?qū)崿F(xiàn) dom 節(jié)點(diǎn)的復(fù)用，但有的時(shí)候會(huì)做一些沒必要的移動(dòng)。雙端 diff 算法解決了這個(gè)問題，它是從兩端進(jìn)行對(duì)比。

我們需要 4 個(gè)指針，分別指向新舊兩個(gè) vnode 數(shù)組的頭尾：

頭和尾的指針向中間移動(dòng)，直到 oldStartIdx <= oldEndIdx 并且 newStartIdx <= newEndIdx，說明就處理完了全部的節(jié)點(diǎn)。

每次對(duì)比下兩個(gè)頭指針指向的節(jié)點(diǎn)、兩個(gè)尾指針指向的節(jié)點(diǎn)，頭和尾指向的節(jié)點(diǎn)，是不是 key是一樣的，也就是可復(fù)用的。

如果是可復(fù)用的話就直接用，調(diào)用 patch 更新一下，如果是頭尾這種，還要移動(dòng)下位置。

也就是這樣的：

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {   if (oldStartVNode.key === newStartVNode.key) { // 頭頭     patch(oldStartVNode, newStartVNode, container)     oldStartVNode = oldChildren[++oldStartIdx]     newStartVNode = newChildren[++newStartIdx]   } else if (oldEndVNode.key === newEndVNode.key) {//尾尾     patch(oldEndVNode, newEndVNode, container)     oldEndVNode = oldChildren[--oldEndIdx]     newEndVNode = newChildren[--newEndIdx]   } else if (oldStartVNode.key === newEndVNode.key) {//頭尾，需要移動(dòng)     patch(oldStartVNode, newEndVNode, container)     insert(oldStartVNode.el, container, oldEndVNode.el.nextSibling)      oldStartVNode = oldChildren[++oldStartIdx]     newEndVNode = newChildren[--newEndIdx]   } else if (oldEndVNode.key === newStartVNode.key) {//尾頭，需要移動(dòng)     patch(oldEndVNode, newStartVNode, container)     insert(oldEndVNode.el, container, oldStartVNode.el)      oldEndVNode = oldChildren[--oldEndIdx]     newStartVNode = newChildren[++newStartIdx]   } else {          // 頭尾沒有找到可復(fù)用的節(jié)點(diǎn)   } }

頭頭和尾尾的對(duì)比比較簡(jiǎn)單，頭尾和尾頭的對(duì)比還要移動(dòng)下節(jié)點(diǎn)。

比如舊 vnode 的頭節(jié)點(diǎn)是新的 vnode 的尾節(jié)點(diǎn)，那就要把它移動(dòng)到舊的 vnode 的尾節(jié)點(diǎn)的位置。

也就是：

insert(oldStartVNode.el, container, oldEndVNode.el.nextSibling)

插入節(jié)點(diǎn)的錨點(diǎn)節(jié)點(diǎn)是 oldEndVNode 對(duì)應(yīng)的 dom 節(jié)點(diǎn)的 nextSibling。

如果舊 vnode 的尾節(jié)點(diǎn)是新 vnode 的頭結(jié)點(diǎn)，那就要把它移動(dòng)到舊 vnode 的頭結(jié)點(diǎn)的位置。

也就是：

insert(oldEndVNode.el, container, oldStartVNode.el)

插入節(jié)點(diǎn)的錨點(diǎn)節(jié)點(diǎn)是 oldStartVNode 對(duì)應(yīng)的 dom 節(jié)點(diǎn)（因?yàn)橐逶谒埃?/p>

從雙端進(jìn)行對(duì)比，能盡可能的減少節(jié)點(diǎn)移動(dòng)的次數(shù)。

當(dāng)然，還要處理下如果雙端都沒有可復(fù)用節(jié)點(diǎn)的情況：

如果雙端都沒有可復(fù)用節(jié)點(diǎn)，那就在舊節(jié)點(diǎn)數(shù)組中找，找到了就把它移動(dòng)過來(lái)，并且原位置置為 undefined。沒找到的話就插入一個(gè)新的節(jié)點(diǎn)。

也就是這樣：

const idxInOld = oldChildren.findIndex(   node => node.key === newStartVNode.key ) if (idxInOld > 0) {   const vnodeToMove = oldChildren[idxInOld]   patch(vnodeToMove, newStartVNode, container)   insert(vnodeToMove.el, container, oldStartVNode.el)   oldChildren[idxInOld] = undefined } else {   patch(null, newStartVNode, container, oldStartVNode.el) }

因?yàn)橛辛艘恍?undefined 的節(jié)點(diǎn)，所以要加上空節(jié)點(diǎn)的處理邏輯：

if (!oldStartVNode) {     oldStartVNode = oldChildren[++oldStartIdx] } else if (!oldEndVNode) {     oldEndVNode = newChildren[--oldEndIdx] }

這樣就完成了節(jié)點(diǎn)的復(fù)用和移動(dòng)的邏輯。

那確實(shí)沒有可復(fù)用的節(jié)點(diǎn)的那些節(jié)點(diǎn)呢？

經(jīng)過前面的移動(dòng)之后，剩下的節(jié)點(diǎn)都被移動(dòng)到了中間，如果新 vnode 有剩余，那就批量的新增，如果舊 vnode 有剩余那就批量的刪除。

因?yàn)榍懊嬉粋€(gè)循環(huán)的判斷條件是 oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx，這樣如果 old vnode 多了，最后 newStartIdx 會(huì)小于 newEndIdx。如果 new vnode 多了，最后 oldStartIdx 會(huì)小于 oldEndIdx。

所以判斷條件是這樣的：

if (oldEndIdx < oldStartIdx && newStartIdx <= newEndIdx) {   // 添加新節(jié)點(diǎn)   for (let i = newStartIdx; i <= newEndIdx; i++) {     patch(null, newChildren[i], container, oldStartVNode.el)   } } else if (newEndIdx < newStartIdx && oldStartIdx <= oldEndIdx) {   // 移除操作   for (let i = oldStartIdx; i <= oldEndIdx; i++) {     unmount(oldChildren[i])   } }

這樣就是一個(gè)完整的 diff 算法了，包括查找可復(fù)用節(jié)點(diǎn)和移動(dòng)節(jié)點(diǎn)、新增和刪除節(jié)點(diǎn)。

而且因?yàn)閺膬蓚?cè)查找節(jié)點(diǎn)，會(huì)比簡(jiǎn)單 diff 算法性能更好一些。

比如 ABCD 到 DABC，簡(jiǎn)單 diff 算法需要移動(dòng) ABC 三個(gè)節(jié)點(diǎn)，而雙端 diff 算法只需要移動(dòng) D 一個(gè)節(jié)點(diǎn)。

小結(jié)一下：

雙端 diff 是頭尾指針向中間移動(dòng)的同時(shí)，對(duì)比頭頭、尾尾、頭尾、尾頭是否可以復(fù)用，如果可以的話就移動(dòng)對(duì)應(yīng)的 dom 節(jié)點(diǎn)。

如果頭尾沒找到可復(fù)用節(jié)點(diǎn)就遍歷 vnode 數(shù)組來(lái)查找，然后移動(dòng)對(duì)應(yīng)下標(biāo)的節(jié)點(diǎn)到頭部。

最后還剩下舊的 vnode 就批量刪除，剩下新的 vnode 就批量新增。

雙端 diff 算法是 Vue2 采用的 diff 算法，性能還不錯(cuò)。

后來(lái)，Vue3 又對(duì) diff 算法進(jìn)行了一次升級(jí)，叫做快速 diff 算法。這個(gè)后面再講。

總結(jié)

React 和 Vue 都是基于 vdom 的前端框架，組件產(chǎn)生 vdom，渲染器再把 vdom 通過增刪改的 dom api 更新到 dom。

當(dāng)再次渲染出 vdom 時(shí)，就要新舊兩棵 vdom 樹做 diff，只更新變化的 dom 節(jié)點(diǎn)。

兩棵樹的 diff 是 O(n^3) 的，時(shí)間復(fù)雜度太高，因此前端框架規(guī)定了只做同層 diff，還有 type 不一樣就認(rèn)為節(jié)點(diǎn)不一樣，不再對(duì)比子節(jié)點(diǎn)。這樣時(shí)間復(fù)雜度一下子就降到了 O(n)。

但是對(duì)于多個(gè)子字節(jié)點(diǎn)的 diff 不能粗暴的刪除和新增，要盡量復(fù)用已有的節(jié)點(diǎn)，也就是通過移動(dòng)代替新增。

所以多節(jié)點(diǎn)的時(shí)候，要指定 key，然后 diff 算法根據(jù) key 來(lái)查找和復(fù)用節(jié)點(diǎn)。

簡(jiǎn)單 diff 算法是依次根據(jù) key 查找舊節(jié)點(diǎn)的，移動(dòng)的話通過 lastIndex 判斷，大于它就不用動(dòng)，小于它才需要移動(dòng)。剩下的節(jié)點(diǎn)再批量刪除和新增。

但是簡(jiǎn)單 diff 算法局限性還是比較大的，有些情況下性能并不好，所以 vue2 用的是雙端 diff 算法。

雙端 diff 算法是頭尾指針向中間移動(dòng)，分別判斷頭尾節(jié)點(diǎn)是否可以復(fù)用，如果沒有找到可復(fù)用的節(jié)點(diǎn)再去遍歷查找對(duì)應(yīng)節(jié)點(diǎn)的下標(biāo)，然后移動(dòng)。全部處理完之后也要對(duì)剩下的節(jié)點(diǎn)進(jìn)行批量的新增和刪除。

其實(shí) diff 算法最重要的就是找到可復(fù)用的節(jié)點(diǎn)，然后移動(dòng)到正確的位置。只不過不同的算法查找順序不一樣。

vue2 是用的雙端 diff 的算法，而 vue3 則通過最長(zhǎng)遞增子序列的算法做了進(jìn)一步的優(yōu)化，關(guān)于優(yōu)化后的 diff 算法，我們之后再聊。

【相關(guān)視頻教程推薦：web前端】