一、vue2的diff

1.認(rèn)識

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

如果讀者朋友還沒有了解過什么是diff的話！我給你畫一張圖來幫助各位理解一下：

diff策略：

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

認(rèn)知模型：

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

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

我們可以舉一個簡單的例子，假設(shè)我們渲染了一個列表，用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)的改變是全量的，因為我狀態(tài)我改變是通過在內(nèi)存中創(chuàng)建了一個新的數(shù)組來實現(xiàn)的，但是列表的更新則不一定是全量的，因為那樣太耗費性能量，diff就是致力于找出一種盡可能好的策略來滿足這個需求，我們接下來就來細(xì)細(xì)剖析一下vue2的diff策略。

2.vue2的diff

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

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

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

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

接下來開始我們的調(diào)整策略，調(diào)整的過程就是移動指針的過程：

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

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

  • 分支0：遇到空，指針向右移動

  • 分支1：比較oldStart和newStart是否一致，如果一致，兩個指針向右移動即可

  • 分支2：比較oldEnd和newEnd是否一致，如果一致，兩個指針向左移動即可

  • 分支3：比較oldStart和newEnd是否一致，如果一致，就需要移動節(jié)點，移動節(jié)點都針對old的操作，因為需要將old變成新的，所以會慢慢調(diào)整old朝著new去擬合，將oldStart移動到oldEnd的下一個。

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

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

以上便是vue2的diff的核心流程了，我們通過一個例子再來感受一下，對于以下這樣的調(diào)整目標(biāo)來說：

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第三步：自動進(jìn)入分支5，newStart在old中是否存在，在vue2中是這樣判斷的：

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

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

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

循環(huán)2:

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

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

循環(huán)3:

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

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

循環(huán)4:

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

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

循環(huán)5:

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

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

這時候循環(huán)已經(jīng)結(jié)束，因為oldStart已經(jīng)大于oldEnd。

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

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é)點已經(jīng)發(fā)生了移動會出現(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對應(yīng)的DOM移動到oldEnd對應(yīng)DOM的下一個。
        nodeOps.insertBefore(
          parentElm,
          oldStartVnode.elm,
          nodeOps.nextSibling(oldEndVnode.elm)
        )
        ++oldStartIdx
        --newEndIdx
      } else if (sameVnode(oldEndVnode, newStartVnode)) { // 分支4
        patchVnode(...)
        // 將oldEnd對應(yīng)的DOM移動到oldStart對應(yīng)DOM的上一個。
        nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm)
        --oldEndIdx
        ++newStartIdx
      } else {
        if (發(fā)現(xiàn)了新的節(jié)點) {
          createElm(...) // 創(chuàng)建一個DOM節(jié)點
        } else { 
          vnodeToMove = oldCh[idxInOld] // 找到在old中對應(yīng)的位置
          if (sameVnode(vnodeToMove, newStartVnode)) {  // 分支5
            patchVnode(...)
            oldCh[idxInOld] = undefined // 置空
            // 將old所在位置的DOM移動到oldStart所在DOM的上一個。
            nodeOps.insertBefore(
              parentElm,
              vnodeToMove.elm,
              oldStartVnode.elm
            )
          } 
        }
        ++newStartIdx
      }
    }
  }

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

二、算法模型

在前面我們主要講述了vue2———diff算法的代碼流程，接下來我會聊一下這個diff算法的心智模型，因為在大多數(shù)情況下我們不能滿足于它的流程就可以了，最好我們能夠知道它為什么可以解決問題。

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

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

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

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

心智模型

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

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

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

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

優(yōu)化

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

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

三、最后的話

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

最新評論