一、vue2的diff

1.認(rèn)識(shí)

本篇文章將會(huì)嘗試從算法的角度主要聊一聊vue2的diff策略，幫助讀者朋友在遇到相關(guān)的面試題時(shí)可以和面試官談笑風(fēng)生。

如果讀者朋友還沒(méi)有了解過(guò)什么是diff的話！我給你畫一張圖來(lái)幫助各位理解一下：

diff策略：

通俗來(lái)講就是通過(guò)某種策略找到新舊兩種數(shù)據(jù)狀況的不同來(lái)實(shí)現(xiàn)最小量更新的辦法，其實(shí)diff的本質(zhì)是希望實(shí)現(xiàn)最小量的更新，也就是說(shuō)對(duì)于給定的兩組新舊節(jié)點(diǎn)，他們的變化能夠被diff策略察覺(jué)到，并且以盡可能小的代價(jià)去更新他們，而不是全部清除后，重新基于新的狀態(tài)去創(chuàng)建。

認(rèn)知模型：

對(duì)于現(xiàn)代前端框架都有這樣的一個(gè)范式：UI = f(state)

也就是所謂的 狀態(tài)驅(qū)動(dòng)視圖 ，state即狀態(tài)，f即框架，UI即用戶看到的界面?；谶@個(gè)范式，當(dāng)用戶更新了狀態(tài)的時(shí)候，state的改變可以是全量的更改，但是UI并不一定會(huì)全量的更改。

我們可以舉一個(gè)簡(jiǎn)單的例子，假設(shè)我們渲染了一個(gè)列表，用vue的方式表達(dá)是這樣子的：

<script>
  const vm = new Vue({
    name: "App",
    template: `
    <div>
      <button @click="onChange">改變</button>
      <ul>
        <li v-for="item in list" :key="item">{{ item }}</li> 
      </ul>
    </div>
  `,
    data: {
      list: ["A", "B", "C", "D"],
    },
    methods: {
      onChange() {
        this.list = ["B", "A", "D", "C"];
      },
    },
  }).$mount("#app");
</script>

可以看到狀態(tài)的改變是全量的，因?yàn)槲覡顟B(tài)我改變是通過(guò)在內(nèi)存中創(chuàng)建了一個(gè)新的數(shù)組來(lái)實(shí)現(xiàn)的，但是列表的更新則不一定是全量的，因?yàn)槟菢犹馁M(fèi)性能量，diff就是致力于找出一種盡可能好的策略來(lái)滿足這個(gè)需求，我們接下來(lái)就來(lái)細(xì)細(xì)剖析一下vue2的diff策略。

2.vue2的diff

我們現(xiàn)在可以來(lái)回顧一下vue2的diff是如何運(yùn)作的，首先我們要在心中有一個(gè)明確的目標(biāo)，知道我們的問(wèn)題是什么，拿上面舉過(guò)的例子來(lái)講，我們的目標(biāo)就是將 A B C D 變成 B A D C。

然后我們來(lái)看看vue2是怎么做的，它的源碼在這里，我們先不看源碼，先用一個(gè)流程來(lái)梳理一下思路，然后在對(duì)照源碼進(jìn)行確認(rèn)，這樣子循序漸進(jìn)的過(guò)程可能會(huì)比較好一些，當(dāng)我們將問(wèn)題抽象成為這樣一個(gè)模型的時(shí)候，就比較明確了：

我們需要寫一個(gè)函數(shù)，入?yún)⑹莾蓚€(gè)數(shù)組newArr以及oldArr，請(qǐng)將oldArr變?yōu)樾碌膎ewArr，并在函數(shù)中體現(xiàn)調(diào)整策略。

我們準(zhǔn)備幾個(gè)變量：

接下來(lái)開(kāi)始我們的調(diào)整策略，調(diào)整的過(guò)程就是移動(dòng)指針的過(guò)程：

開(kāi)啟一個(gè)循環(huán)，循環(huán)的條件就是 oldStart 不能大于oldEnd ，newStart不能大于newEnd

• 在每個(gè)循環(huán)單元中，我們執(zhí)行下面的策略：

  • 分支0：遇到空，指針向右移動(dòng)

  • 分支1：比較oldStart和newStart是否一致，如果一致，兩個(gè)指針向右移動(dòng)即可

  • 分支2：比較oldEnd和newEnd是否一致，如果一致，兩個(gè)指針向左移動(dòng)即可

  • 分支3：比較oldStart和newEnd是否一致，如果一致，就需要移動(dòng)節(jié)點(diǎn)，移動(dòng)節(jié)點(diǎn)都針對(duì)old的操作，因?yàn)樾枰獙ld變成新的，所以會(huì)慢慢調(diào)整old朝著new去擬合，將oldStart移動(dòng)到oldEnd的下一個(gè)。

  • 分支4：比較newStart和oldEnd是否一致，如果一致，就需要移動(dòng)節(jié)點(diǎn)，將oldEnd移動(dòng)到oldStart的前一個(gè)。

  • 分支5：如果以上都沒(méi)有命中，看看newStart是否在old中存在，如果存在，找到是第幾個(gè)，假設(shè)是在old中的第i個(gè)位置，接下來(lái)將第i個(gè)位置的元素移動(dòng)到oldStart的前一位，然后將當(dāng)前第i位置空。如果不存在說(shuō)明創(chuàng)建了一個(gè)新的元素，需要執(zhí)行創(chuàng)建策略。

以上便是vue2的diff的核心流程了，我們通過(guò)一個(gè)例子再來(lái)感受一下，對(duì)于以下這樣的調(diào)整目標(biāo)來(lái)說(shuō)：

old: A B C D

new: B A D C

初始化：oldStart指向A，oldEnd指向D，newStart指向B，newEnd指向C。

循環(huán)1:

第一步：A不等于B ，且D不等于C 未命中分支1和2第二步：A不等于C ，且B不等于D 未命中分支3和4第三步：自動(dòng)進(jìn)入分支5，newStart在old中是否存在，在vue2中是這樣判斷的：

//創(chuàng)建一個(gè)old的key和對(duì)應(yīng)index的map表，在這個(gè)案例中就是：
const map = {
  A:0,
  B:1,
  C:2,
  D:3
}

newStart顯然在map中存在，且index為1，所以根據(jù)策略，我們就需要將old中的第1位置的元素向oldStart的前一個(gè)移動(dòng)，并且newStart向右移動(dòng)。

第一輪循環(huán)結(jié)束：oldStart指向A，oldEnd指向D，newStart指向A，newEnd指向C

循環(huán)2:

第一步：判斷 A 等于 A，命中分支1，指針都向右移動(dòng)。

第二輪循環(huán)結(jié)束：oldStart指向空，oldEnd指向D，newStart指向D，newEnd指向C

循環(huán)3:

第一步：oldStart遇到空，命中分支0，指針向右移動(dòng)，oldStart指向C。

第3輪循環(huán)結(jié)束；

循環(huán)4:

第一步：判斷 D不等于C，并且C不等于D，未命中分支1分支2。第二步：判斷 C等于C，命中分支3，將oldStart向oldEnd下一個(gè)移動(dòng)，oldStart++。

第4輪循環(huán)結(jié)束：oldStart指向D，oldEnd指向D，newStart指向A，newEnd指向C。

循環(huán)5:

第一步：判斷 D等于D ，命中分支1，指針向右移動(dòng)，oldStart++。

第5輪循環(huán)結(jié)束：oldStart指向C，oldEnd指向D，newStart指向C，newEnd指向C。

這時(shí)候循環(huán)已經(jīng)結(jié)束，因?yàn)閛ldStart已經(jīng)大于oldEnd。

實(shí)際上，我們可以看到，old已經(jīng)在相對(duì)次序上和new一模一樣了，雖然在數(shù)據(jù)結(jié)構(gòu)上有兩個(gè)空在那里，而實(shí)際上的DOM結(jié)構(gòu)已經(jīng)移動(dòng)到了正確的位置上，空對(duì)應(yīng)在DOM上就是什么都沒(méi)有，所以這個(gè)移動(dòng)是正確的

3.源碼分析

function updateChildren(
    parentElm,
    oldCh,
    newCh,
    insertedVnodeQueue,
    removeOnly
) {
    let oldStartIdx = 0
    let newStartIdx = 0
    let oldEndIdx = oldCh.length - 1
    let newEndIdx = newCh.length - 1
    let oldKeyToIdx, idxInOld, vnodeToMove, refElm
    while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) { // 循環(huán)條件
      if (isUndef(oldStartVnode)) { // 排除空
        oldStartVnode = oldCh[++oldStartIdx] // 如果節(jié)點(diǎn)已經(jīng)發(fā)生了移動(dòng)會(huì)出現(xiàn)為undeifined的現(xiàn)象
      } else if (isUndef(oldEndVnode)) {// 排除空
        oldEndVnode = oldCh[--oldEndIdx]
      } else if (sameVnode(oldStartVnode, newStartVnode)) { // 分支1
        patchVnode(...) // 繼續(xù)深度patch
        oldStartVnode = oldCh[++oldStartIdx]
        newStartVnode = newCh[++newStartIdx]
      } else if (sameVnode(oldEndVnode, newEndVnode)) { // 分支2
        patchVnode(...) // 繼續(xù)深度patch
        oldEndVnode = oldCh[--oldEndIdx]
        newEndVnode = newCh[--newEndIdx]
      } else if (sameVnode(oldStartVnode, newEndVnode)) { // 分支3
        patchVnode(...)
        // 將oldStart對(duì)應(yīng)的DOM移動(dòng)到oldEnd對(duì)應(yīng)DOM的下一個(gè)。
        nodeOps.insertBefore(
          parentElm,
          oldStartVnode.elm,
          nodeOps.nextSibling(oldEndVnode.elm)
        )
        ++oldStartIdx
        --newEndIdx
      } else if (sameVnode(oldEndVnode, newStartVnode)) { // 分支4
        patchVnode(...)
        // 將oldEnd對(duì)應(yīng)的DOM移動(dòng)到oldStart對(duì)應(yīng)DOM的上一個(gè)。
        nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm)
        --oldEndIdx
        ++newStartIdx
      } else {
        if (發(fā)現(xiàn)了新的節(jié)點(diǎn)) {
          createElm(...) // 創(chuàng)建一個(gè)DOM節(jié)點(diǎn)
        } else { 
          vnodeToMove = oldCh[idxInOld] // 找到在old中對(duì)應(yīng)的位置
          if (sameVnode(vnodeToMove, newStartVnode)) {  // 分支5
            patchVnode(...)
            oldCh[idxInOld] = undefined // 置空
            // 將old所在位置的DOM移動(dòng)到oldStart所在DOM的上一個(gè)。
            nodeOps.insertBefore(
              parentElm,
              vnodeToMove.elm,
              oldStartVnode.elm
            )
          } 
        }
        ++newStartIdx
      }
    }
  }

上面是只展示了核心部分的代碼，我們可以看到，基本邏輯和我們前面描述的是一樣的。

二、算法模型

在前面我們主要講述了vue2———diff算法的代碼流程，接下來(lái)我會(huì)聊一下這個(gè)diff算法的心智模型，因?yàn)樵诖蠖鄶?shù)情況下我們不能滿足于它的流程就可以了，最好我們能夠知道它為什么可以解決問(wèn)題。

數(shù)據(jù)結(jié)構(gòu)

vue2底層的diff是基于vdom的，而vdom的數(shù)據(jù)結(jié)構(gòu)是一顆多叉樹(shù)，如果當(dāng)前級(jí)的節(jié)點(diǎn)有多個(gè)，那么就是個(gè)數(shù)組，因此本質(zhì)上就是比較兩個(gè)數(shù)組的不同。而vue2的diff算法的目的其實(shí)不是找到他們不同的結(jié)果集，因?yàn)榧热蛔罱K是為了讓新的虛擬dom體現(xiàn)在界面上，那么索性在diff的過(guò)程中vue2就在不斷的調(diào)整原來(lái)的dom樹(shù)，使其慢慢變得跟新的一模一樣。

上面可能理解起來(lái)有點(diǎn)抽象，我們舉個(gè)現(xiàn)實(shí)世界中的例子：假設(shè)有一個(gè)間諜要偽裝成一個(gè)人，潛入敵國(guó)偷取情報(bào)，所以他的目標(biāo)就是要變的和 這個(gè)人 一模一樣，他有兩種方法一種是先找出他和這個(gè)人有哪些不同，沒(méi)找到一個(gè)不同就拿個(gè)小本本記下來(lái)，這個(gè)尋找的過(guò)程可能需要一段時(shí)間，找完之后根據(jù)這個(gè)小本本一件件去調(diào)整，比如容貌不一樣，就去整容；說(shuō)話方式不一樣就去練習(xí)；學(xué)歷不一樣就去偽造等等，這種方式我們叫做策略一。間諜覺(jué)得策略一不好，他不喜歡拿小本本記下來(lái)，他喜歡直接觀察需要偽裝的人，每找到一個(gè)不同，就立馬調(diào)整偽裝自己，直到自己和這個(gè)人完全一樣為止，這種方式叫做策略二。

實(shí)際上vue系列用的都是策略二，在diff的過(guò)程中就直接調(diào)整自己（直接改變dom結(jié)構(gòu)）然后基于新的vdom逐漸把dom調(diào)整的和新的vdom一致即可，所以diff一旦完成，也就完成了真正意義上dom的調(diào)整。

心智模型

vue2的diff是一種非常接近自然智慧的一種算法，本質(zhì)上就是一種貪心策略，如果取一個(gè)比較貼近的名字，應(yīng)該就叫做最左移策略，且聽(tīng)我一一來(lái)解釋：

我們還是來(lái)看一下上面這個(gè)圖，如何讓old變的和新的越來(lái)越像呢？我們使用自然智慧來(lái)思考，其實(shí)很容易可以想到一個(gè)策略就是：

我們不去管old了，我們就直接看new，然后用一個(gè)指針指向new的第一個(gè)節(jié)點(diǎn)，遍歷new的每一個(gè)節(jié)點(diǎn)，然后每一次我都看一下new中的節(jié)點(diǎn)在old中的那一個(gè)位置，將這節(jié)點(diǎn)移動(dòng)到oldStart的左側(cè)。

用上面間諜的例子就是，我不去管我自己現(xiàn)在是什么樣子，我就盯著那個(gè)需要我偽裝的人，我從頭到腳把他看一遍，看到頭的時(shí)候，我發(fā)現(xiàn)我的臉和臉的頭不一樣，我去整個(gè)容，一樣的部分就跳過(guò)，直到變得和他完全一樣。

優(yōu)化

但是可能細(xì)心的同學(xué)會(huì)說(shuō)，他為什么vue2用了4個(gè)指針啊！

其實(shí)另外兩個(gè)指針的目的是為了加速用的，想象一下假設(shè)newStart和oldEnd如果是一樣的節(jié)點(diǎn)，如果沒(méi)有oldEnd這個(gè)指針，那么newStart要從old中找到oldEnd，必須把old全部遍歷一遍才能找到，而有了這個(gè)指針，則只需要O(1)的時(shí)間復(fù)雜度就可以直接找到這個(gè)節(jié)點(diǎn)，在diff的過(guò)程中可以大大提升diff的性能。

三、最后的話

以上就是一文詳解vue2的diff算法流程的詳細(xì)內(nèi)容，更多關(guān)于vue2 diff算法的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！