一、vue2的diff

1.認識

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

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

diff策略：

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

認知模型：

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

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

我們可以舉一個簡單的例子，假設我們渲染了一個列表，用vue的方式表達是這樣子的：

<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)我改變是通過在內存中創(chuàng)建了一個新的數組來實現的，但是列表的更新則不一定是全量的，因為那樣太耗費性能量，diff就是致力于找出一種盡可能好的策略來滿足這個需求，我們接下來就來細細剖析一下vue2的diff策略。

2.vue2的diff

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

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

我們需要寫一個函數，入參是兩個數組newArr以及oldArr，請將oldArr變?yōu)樾碌膎ewArr，并在函數中體現調整策略。

我們準備幾個變量：

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

開啟一個循環(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變成新的，所以會慢慢調整old朝著new去擬合，將oldStart移動到oldEnd的下一個。

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

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

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

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

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

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

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

循環(huán)2:

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

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

循環(huán)3:

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

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

循環(huán)4:

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

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

循環(huán)5:

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

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

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

實際上，我們可以看到，old已經在相對次序上和new一模一樣了，雖然在數據結構上有兩個空在那里，而實際上的DOM結構已經移動到了正確的位置上，空對應在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é)點已經發(fā)生了移動會出現為undeifined的現象
      } 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對應的DOM移動到oldEnd對應DOM的下一個。
        nodeOps.insertBefore(
          parentElm,
          oldStartVnode.elm,
          nodeOps.nextSibling(oldEndVnode.elm)
        )
        ++oldStartIdx
        --newEndIdx
      } else if (sameVnode(oldEndVnode, newStartVnode)) { // 分支4
        patchVnode(...)
        // 將oldEnd對應的DOM移動到oldStart對應DOM的上一個。
        nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm)
        --oldEndIdx
        ++newStartIdx
      } else {
        if (發(fā)現了新的節(jié)點) {
          createElm(...) // 創(chuàng)建一個DOM節(jié)點
        } else { 
          vnodeToMove = oldCh[idxInOld] // 找到在old中對應的位置
          if (sameVnode(vnodeToMove, newStartVnode)) {  // 分支5
            patchVnode(...)
            oldCh[idxInOld] = undefined // 置空
            // 將old所在位置的DOM移動到oldStart所在DOM的上一個。
            nodeOps.insertBefore(
              parentElm,
              vnodeToMove.elm,
              oldStartVnode.elm
            )
          } 
        }
        ++newStartIdx
      }
    }
  }

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

二、算法模型

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

數據結構

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

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

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

心智模型

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

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

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

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

優(yōu)化

但是可能細心的同學會說，他為什么vue2用了4個指針?。?/p>

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

三、最后的話

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

最新評論