前言

都說“雙端對比算法”，那么雙端對比算法，到底是怎么樣的呢？跟 React 中的 Diff 算法又有什么不同呢？

要了解這些，我們先了解 React 中的 Diff 算法，然后再了解 Vue3 中的 Diff 算法，最后講一下 Vue2 中的 Diff 算法，才能去比較一下他們的區(qū)別。

最后講一下為什么 Vue 中不需要使用 Fiber 架構(gòu)。

React 官方的解析

其實(shí)為什么 React 不采用 Vue 的雙端對比算法，React 官方已經(jīng)在源碼的注釋里已經(jīng)說明了，我們來看一下 React 官方是怎么說的。

function reconcileChildrenArray(
returnFiber: Fiber,
 currentFirstChild: Fiber | null,
 newChildren: Array<*>,
 expirationTime: ExpirationTime,
): Fiber | null {
    // This algorithm can't optimize by searching from boths ends since we
    // don't have backpointers on fibers. I'm trying to see how far we can get
    // with that model. If it ends up not being worth the tradeoffs, we can
    // add it later.

    // Even with a two ended optimization, we'd want to optimize for the case
    // where there are few changes and brute force the comparison instead of
    // going for the Map. It'd like to explore hitting that path first in
    // forward-only mode and only go for the Map once we notice that we need
    // lots of look ahead. This doesn't handle reversal as well as two ended
    // search but that's unusual. Besides, for the two ended optimization to
    // work on Iterables, we'd need to copy the whole set.

    // In this first iteration, we'll just live with hitting the bad case
    // (adding everything to a Map) in for every insert/move.

    // If you change this code, also update reconcileChildrenIterator() which
    // uses the same algorithm.
｝

大概的意思就是說：

React 不能通過雙端對比進(jìn)行 Diff 算法優(yōu)化是因?yàn)槟壳?Fiber 上沒有設(shè)置反向鏈表，而且想知道就目前這種方案能持續(xù)多久，如果目前這種模式不理想的話，那么也可以增加雙端對比算法。

即使是雙端對比算法，我們也要對這種情況進(jìn)行優(yōu)化，我們應(yīng)該使用 Map 這種數(shù)據(jù)結(jié)構(gòu)方案去替代原來那種幾乎沒有什么變化也進(jìn)行暴力比較的方案。它第一次搜索循環(huán)是通過 forward-only 這種模式（就是只從左向右查找），（第一次循環(huán)可能還沒有結(jié)束，還有節(jié)點(diǎn)沒有比對的時候）如果還要繼續(xù)向前循環(huán)查找那么就要通過 Map 這種數(shù)據(jù)類型了。（就目前這個單向鏈表的數(shù)據(jù)結(jié)構(gòu)，如果采用）雙端對比查找算法比較難控制它反向查找的，但它確實(shí)是一種成功的算法。此外，雙端對比算法的實(shí)現(xiàn)也在我們的工作迭代當(dāng)中。

第一次迭代，我們就先將就使用這種不好的方案吧，每次新增/移動都要添加所有的數(shù)據(jù)到一個 Map 的數(shù)據(jù)類型對象中。

“we'd need to copy the whole set”，這一句，每一個單詞都懂，但就是不知道他想說什么，所以就不翻譯了，有知道的大神嗎？

本人水平有限，錯漏難免，如有錯漏，懇請各位斧正。

React 的官方雖然解析了，但我們想要徹底理解到底為什么，還是要去詳細(xì)了解 React 的 Diff 算法是怎么樣的。在了解 React Diff 算法之前，我們首先要了解什么是 Fiber，為什么 React 中要使用 Fiber？

Fiber 的結(jié)構(gòu)

在 React15 以前 React 的組件更新創(chuàng)建虛擬 DOM 和 Diff 的過程是不可中斷，如果需要更新組件樹層級非常深的話，在 Diff 的過程會非常占用瀏覽器的線程，而我們都知道瀏覽器執(zhí)行JavaScript 的線程和渲染真實(shí) DOM 的線程是互斥的，也就是同一時間內(nèi)，瀏覽器要么在執(zhí)行 JavaScript 的代碼運(yùn)算，要么在渲染頁面，如果 JavaScript 的代碼運(yùn)行時間過長則會造成頁面卡頓。 基于以上原因 React 團(tuán)隊(duì)在 React16 之后就改寫了整個架構(gòu)，將原來數(shù)組結(jié)構(gòu)的虛擬DOM，改成叫 Fiber 的一種數(shù)據(jù)結(jié)構(gòu)，基于這種 Fiber 的數(shù)據(jù)結(jié)構(gòu)可以實(shí)現(xiàn)由原來不可中斷的更新過程變成異步的可中斷的更新。

Fiber 的數(shù)據(jù)結(jié)構(gòu)主要長成以下的樣子，主要通過 Fiber 的一些屬性去保存組件相關(guān)的信息。

function FiberNode(
  tag: WorkTag,
  pendingProps: mixed,
  key: null | string,
  mode: TypeOfMode,
) {
  // 作為靜態(tài)數(shù)據(jù)結(jié)構(gòu)的屬性
  this.tag = tag;
  this.key = key;
  this.elementType = null;
  this.type = null;
  this.stateNode = null;

  // 用于連接其他Fiber節(jié)點(diǎn)形成Fiber樹
  this.return = null;
  this.child = null;
  this.sibling = null;
  this.index = 0;

  this.ref = null;

  // 作為動態(tài)的工作單元的屬性
  this.pendingProps = pendingProps;
  this.memoizedProps = null;
  this.updateQueue = null;
  this.memoizedState = null;
  this.dependencies = null;

  this.mode = mode;

  this.effectTag = NoEffect;
  this.nextEffect = null;

  this.firstEffect = null;
  this.lastEffect = null;

  // 調(diào)度優(yōu)先級相關(guān)
  this.lanes = NoLanes;
  this.childLanes = NoLanes;

  // 指向該fiber在另一次更新時對應(yīng)的fiber
  this.alternate = null;
}

Fiber 主要靠以下屬性連成一棵樹結(jié)構(gòu)的數(shù)據(jù)的，也就是 Fiber 鏈表。

// 指向父級Fiber節(jié)點(diǎn)
this.return = null;
// 指向子Fiber節(jié)點(diǎn)
this.child = null;
// 指向右邊第一個兄弟Fiber節(jié)點(diǎn)
this.sibling = null;

舉個例子，如下的組件結(jié)構(gòu)：

function App() {
  return (
    <div>
      i am
      <span>Coboy</span>
    </div>
  )
}

對應(yīng)的 Fiber 鏈表結(jié)構(gòu)：

那么以上的 Fiber 鏈表的數(shù)據(jù)結(jié)構(gòu)有什么特點(diǎn)，就是任何一個位置的 Fiber 節(jié)點(diǎn)，都可以非常容易知道它的父 Fiber, 第一個子元素的 Fiber,和它的兄弟節(jié)點(diǎn) Fiber。卻不容易知道它前一個 Fiber 節(jié)點(diǎn)是誰，這就是 React 中單向鏈表 Fiber 節(jié)點(diǎn)的特點(diǎn)。也正是因?yàn)檫@些即便在協(xié)調(diào)的過程被中斷了，再恢復(fù)協(xié)調(diào)的時候，依然知道當(dāng)前的 父節(jié)點(diǎn)和孩子節(jié)點(diǎn)等信息。

那么 React 是將對應(yīng)組件怎么生成一個 Fiber 鏈表數(shù)據(jù)的呢？

Fiber 鏈表的生成

上面的組件在經(jīng)過 JSX 的編譯之后，初始化的時候會生成成一個類似于 React 15 或者 Vue 那種虛擬 DOM 的數(shù)據(jù)結(jié)構(gòu)。然后創(chuàng)建一個叫 fiberRoot 的 Fiber 節(jié)點(diǎn)，然后開始從 fiberRoot 這個根 Fiber 開始進(jìn)行協(xié)調(diào)，生成一棵 Fiber 樹，這個棵樹被稱為：workInProgress Fiber 樹 ，意思是正在工作的 Fiber 樹，接下來我們詳細(xì)了解一下具體是怎么生成一棵 Fiber 樹的。要先了解 Fiber 樹的生成原理才更好去理解 Fiber 樹 diff 的過程。

以下是一段簡單版的 Fiber 鏈表生成的代碼片段。 這個協(xié)調(diào)子節(jié)點(diǎn)的函數(shù)接收兩個參數(shù)，returnFiber 是父 Fiber，children 是這個節(jié)點(diǎn)的子元素的虛擬 DOM數(shù)據(jù)。

// 這個協(xié)調(diào)子節(jié)點(diǎn)的函數(shù)接收兩個參數(shù)，returnFiber 是父 Fiber，children 是這個節(jié)點(diǎn)的子元素的虛擬 DOM數(shù)據(jù)。
export function reconcileChildren(returnFiber, children) {
    // 如果是字符串或者數(shù)字則不創(chuàng)建 Fiber
    if(isStringOrNumber(children)) {
        return
    }
    const newChildren = isArray(children) ? children : [children]
    // 上一輪的 fiber 節(jié)點(diǎn)
    let previousNewFiber = null;
    // 初次渲染（false）還是更新（true）
    let shouldTrackSideEffects = !!returnFiber.alternate
    // 老 Fiber 節(jié)點(diǎn)
    let oldFiber = returnFiber.alternate && returnFiber.alternate.child
    let nextOldFiber = null
    // 上一次協(xié)調(diào)返回的位置
    let lastPlacedIndex = 0;
    // 記錄每個 fiber 節(jié)點(diǎn)的位置
    let newIdx = 0;
    // 如果不存在老 Fiber 則是初始化的過程，進(jìn)行 Fiber 鏈表的創(chuàng)建
    if(!oldFiber) {
        for (; newIdx < newChildren.length; newIdx++) {
            // 獲取節(jié)點(diǎn)元素內(nèi)容
            const newChild = newChildren[newIdx]
            // 如果節(jié)點(diǎn)為 null 則不需要創(chuàng)建 fiber 節(jié)點(diǎn)
            if(newChild === null) {
                continue
            }
            // 創(chuàng)建新 fiber 的時候記錄了關(guān)鍵的父 fiber 等重要信息
            const newFiber = createFiber(newChild, returnFiber)
            // 記錄當(dāng)前每一個 fiber 的位置
            lastPlacedIndex = placeChild(
                newFiber,
                lastPlacedIndex,
                newIdx,
                shouldTrackSideEffects // 初次渲染（false）還是更新（true）
            )
		    // 當(dāng)上一輪的 fiber 節(jié)點(diǎn)為 null 的時候，這一輪的 fiber 就是頭節(jié)點(diǎn)
            if(previousNewFiber === null) {
                // 父 fiber 的 child 就是第一個節(jié)點(diǎn)
                returnFiber.child = newFiber
            } else {
                // 如果不是第一個節(jié)點(diǎn)，那么就是兄弟節(jié)點(diǎn)
                // 上一輪 fiber 的兄弟節(jié)點(diǎn)是這一輪的 fiber 節(jié)點(diǎn)
                previousNewFiber.sibling = newFiber;
            }
		   // 記錄上一輪的 fiber，既是這一輪的 fiber 便是下一輪的上一輪 fiber
            previousNewFiber = newFiber
        }
        return
    }
}

構(gòu)建完的 workInProgress Fiber樹 會在 commit階段 渲染到頁面。

在組件狀態(tài)數(shù)據(jù)發(fā)生變更的時候，會根據(jù)最新的狀態(tài)數(shù)據(jù)先會生成新的虛擬DOM，再去構(gòu)建一棵新的 workInProgress Fiber 樹 ，而在重新協(xié)調(diào)構(gòu)建新的 Fiber 樹的過程也就是 React Diff 發(fā)生的地方。接下來，我們就看看 React Diff 算法是怎么樣的。

React 的 Diff 算法

深度優(yōu)先，有子節(jié)點(diǎn)，就遍歷子節(jié)點(diǎn)，沒有子節(jié)點(diǎn)，就找兄弟節(jié)點(diǎn)，沒有兄弟節(jié)點(diǎn)，就找叔叔節(jié)點(diǎn)，叔叔節(jié)點(diǎn)也沒有的話，就繼續(xù)往上找，它爺爺?shù)男值?，如果一直沒找到，就代表所有的更新任務(wù)都更新完畢了。

重點(diǎn)是在更新自己的同時需要去協(xié)調(diào)子節(jié)點(diǎn)，也就是傳說中進(jìn)行 Diff 的地方。

進(jìn)入?yún)f(xié)調(diào)的時候它自己就是父 Fiber，它的子節(jié)點(diǎn)在協(xié)調(diào)之前，是剛剛通過更新的狀態(tài)數(shù)據(jù)生成的最新的虛擬DOM數(shù)據(jù)，是個數(shù)組結(jié)構(gòu)的元素數(shù)據(jù)。

那么要進(jìn)行更新，就肯定是以為最新的節(jié)點(diǎn)數(shù)據(jù)為準(zhǔn)了，又因?yàn)樽钚碌墓?jié)點(diǎn)數(shù)據(jù)是一個數(shù)組，所以可以進(jìn)行循環(huán)對比每一個節(jié)點(diǎn)，很明顯這個循環(huán)是從左向右進(jìn)行查找比對的。

第一輪，常見情況的比對

那么第一個節(jié)點(diǎn)的老 Fiber 怎么拿到呢？可以通過 父 Fiber 的 child 屬性拿到，這樣第一個節(jié)點(diǎn)的老 Fiber 就拿到了，那么第二節(jié)點(diǎn)的老 Fiber，很明顯可以通過第一個節(jié)點(diǎn)的老 Fiber 節(jié)點(diǎn)的 sibling 屬性拿到，后面的以此類推。

怎么比對呢？

在循環(huán)的新節(jié)點(diǎn)虛擬DOM數(shù)據(jù)的時候，拿到新節(jié)點(diǎn)虛擬DOM信息，然后就去和老 Fiber 節(jié)點(diǎn)進(jìn)行比對，如果兩個節(jié)點(diǎn)相同則創(chuàng)建一個新的 Fiber 節(jié)點(diǎn)并復(fù)用一些老 Fiber 節(jié)點(diǎn)的信息，比如真實(shí) DOM，并給這個新的 Fiber 節(jié)點(diǎn)打上一個 Update 的標(biāo)記，代表這個節(jié)點(diǎn)需要更新即可。

接著去更新協(xié)調(diào)位置信息。

在循環(huán)的最后進(jìn)行 Fiber 鏈表的處理：

如果是頭節(jié)點(diǎn)，則把新 Fiber 設(shè)置為父 Fiber 的 child 屬性的值； 如果不是頭節(jié)點(diǎn)，則把新 Fiber 設(shè)置為上一輪循環(huán)的創(chuàng)建的 Fiber 節(jié)點(diǎn)的 sibing 屬性的值； 更新上一輪 Fiber 變量的值，就是把這一輪的 Fiber 設(shè)置成下一輪的 Fiber; 更新比對的老 Fiber 的值。

如果新節(jié)點(diǎn)都能找到能復(fù)用的節(jié)點(diǎn)，則判斷是否還存在老節(jié)點(diǎn)，有則刪除。

第二輪，不常見的情況的比對

如果經(jīng)過第一輪比對，新節(jié)點(diǎn)還存在未比對的，則繼續(xù)循環(huán)查找。

先將剩下未比對的老 Fiber 節(jié)點(diǎn)全部處理成一個 老 Fiber 的 key 或老 Fiber 的 index 為 key，F(xiàn)iber 節(jié)點(diǎn)為 value 的 Map 中，這樣就可以，以 O(1) 復(fù)雜度，通過新 Fiber 的 key 去 Map 對象中查找匹配的 Fiber，找到了，則刪除 Map 對象中的老 Fiber 數(shù)據(jù)，然后復(fù)用匹配到的 Fiber 數(shù)據(jù)。

接下來，不管有沒有匹配到都進(jìn)行位置協(xié)調(diào)，記錄最新的位置信息，新增的 Fiber 因?yàn)闆]有存在老 Fiber 而會被打上 Placement 的標(biāo)記，在將來提交的階段將會被進(jìn)行新增操作。這個過程跟第一輪最后的處理是一樣的。

在循環(huán)的最后進(jìn)行 Fiber 鏈表的處理：

如果是頭節(jié)點(diǎn)，則把新 Fiber 設(shè)置為父 Fiber 的 child 屬性的值； 如果不是頭節(jié)點(diǎn)，則把新 Fiber 設(shè)置為上一輪循環(huán)的創(chuàng)建的 Fiber 節(jié)點(diǎn)的 sibing 屬性的值； 更新上一輪 Fiber 變量的值，就是把這一輪的 Fiber 設(shè)置成下一輪的 Fiber; 更新比對的老 Fiber 的值。

重點(diǎn)如何協(xié)調(diào)更新位置信息

如果是初始渲染，那么協(xié)調(diào)位置就只是記錄當(dāng)前元素下標(biāo)的位置到 Fiber 節(jié)點(diǎn)上。如果是更新階段，就先判斷有沒有老 Fiber 節(jié)點(diǎn)，如果沒有老 Fiber 節(jié)點(diǎn)，則說明該節(jié)點(diǎn)需要創(chuàng)建，就給當(dāng)前新的 Fiber 節(jié)點(diǎn)打上一個 Placement 的標(biāo)記，如果有老 Fiber 節(jié)點(diǎn)，則判斷老 Fiber 節(jié)點(diǎn)的位置是否比上一次協(xié)調(diào)的返回的位置小，如果是，則說明該節(jié)點(diǎn)需要移動，給新 Fiber 節(jié)點(diǎn)打上一個 Placement 的標(biāo)記，并繼續(xù)返回上一次協(xié)調(diào)返回的位置；如果老 Fiber 節(jié)點(diǎn)的位置大或者等于上一次協(xié)調(diào)返回的位置，則說明該節(jié)點(diǎn)不需要進(jìn)行位置移動操作，就返回老 Fiber 的位置即可。

這里需要說明的一點(diǎn)，為什么移動和新增節(jié)點(diǎn)都是 Placement 的標(biāo)記呢？

因?yàn)槲覀兪窃趨f(xié)調(diào)一個子節(jié)點(diǎn)列表，所以不管是新增還是移動都是屬于位置是需要發(fā)生變化的，所以新增和移動都是同一種操作情況。

小結(jié)

總個來說，React Diff 算法分以下幾個步驟：

• 第一輪，從左向右新老節(jié)點(diǎn)進(jìn)行比對查找能復(fù)用的舊節(jié)點(diǎn)，如果有新老節(jié)點(diǎn)比對不成功的，則停止這一輪的比對，并記錄了停止的位置。
• 如果第一輪比對，能把所有的新節(jié)點(diǎn)都比對完畢，則刪除舊節(jié)點(diǎn)還沒進(jìn)行比對的節(jié)點(diǎn)。
• 如果第一輪的比對，沒能將所有的新節(jié)點(diǎn)都比對完畢，則繼續(xù)從第一輪比對停止的位置繼續(xù)開始循環(huán)新節(jié)點(diǎn)，拿每一個新節(jié)點(diǎn)去老節(jié)點(diǎn)里面進(jìn)行查找，有匹配成功的則復(fù)用，沒匹配成功的則在協(xié)調(diào)位置的時候打上 Placement 的標(biāo)記。
• 在所有新節(jié)點(diǎn)比對完畢之后，檢查還有沒有沒進(jìn)行復(fù)用的舊節(jié)點(diǎn)，如果有，則全部刪除。

圖文解釋 React Diff 算法

接下來我們使用圖文進(jìn)行 React Diff 算法講解，希望可以更進(jìn)一步了解 React 的 Diff 算法。

最簡單的 Diff 場景

上圖的 Diff 場景是最簡單的一種，新虛擬DOM 從左到右都能和老 Fiber 的節(jié)點(diǎn)一一匹配成功，協(xié)調(diào)位置的時候，老 Fiber A 的位置是 0，默認(rèn)上一次協(xié)調(diào)返回的位置也是 0，根據(jù)協(xié)調(diào)位置規(guī)則，老 Fiber 的位置不比上一次協(xié)調(diào)返回的位置小，則只需要返回老 Fiber A 的位置 0 即可；

到了 B 進(jìn)行協(xié)調(diào)位置的時候，老 Fiber B 位置 1 不比上一次協(xié)調(diào)返回的位置 0 小，則只需返回老 Fiber B 的位置 1 即可；到了 C 進(jìn)行協(xié)調(diào)位置的時候，老 Fiber C 位置 2 不比上一次協(xié)調(diào)返回的位置 1 小，則只需要返回老 Fiber C 的位置 2 即可；

最后全部的新虛擬DOM 比對完畢，但老 Fiber 上還存在節(jié)點(diǎn)信息，則需要將剩下的老 Fiber 進(jìn)行刪除標(biāo)記。

接下來我們看看復(fù)雜的 Diff 場景。

復(fù)雜的 Diff 場景

在上圖中，第一輪循環(huán)比對的時候，新虛擬節(jié)點(diǎn)A 和第一個老 Fiber 節(jié)點(diǎn)是可以匹配的，所以就可以復(fù)用老 Fiber 的節(jié)點(diǎn)信息了，并且在協(xié)調(diào)的位置信息的時候，是存在老 Fiber 的，那么就去比較老 Fiber 的位置和上一次協(xié)調(diào)返回的位置進(jìn)行比較（上一次協(xié)調(diào)返回的位置默認(rèn)為 0），老 Fiber 的位置是等于新 Fiber 的位置，根據(jù)協(xié)調(diào)規(guī)則，位置不需要移動，返回老 Fiber 的位置信息即可，很明顯這次返回的協(xié)調(diào)位置是 0。

到了第二個新虛擬節(jié)點(diǎn) C 的時候，C 和老 Fiber 中的 B 是不匹配的，則第一輪比對結(jié)束。

第一輪比對結(jié)束之后，新虛擬DOM是還存在未比對的節(jié)點(diǎn)的，那么繼續(xù)開始第二輪的比對。

在第二輪比對開始之前，會先將剩下未比對的老 Fiber 節(jié)點(diǎn)全部處理成一個 老 Fiber 的 key 或老 Fiber 的 index 為 key，F(xiàn)iber 節(jié)點(diǎn)為 value 的 Map 中。

然后進(jìn)行第二輪的比對。

虛擬DOM C 可以通過 C 的 key 值在老 Fiber 的 Map 中找到老 Fiber C 節(jié)點(diǎn)，這個時候會 C 進(jìn)行暫存，然后把 Map 中的 C 進(jìn)行刪除，再進(jìn)行老 Fiber 的節(jié)點(diǎn)信息復(fù)用，然后去協(xié)調(diào)比對位置信息。

老 Fiber C 的位置是 2，然后上一次新 Fiber A 協(xié)調(diào)比對返回的位置信息是 0，那么這一次協(xié)調(diào)的位置是老 Fiber 的位置比上一次協(xié)調(diào)返回的位置大，那么這次協(xié)調(diào)是不用標(biāo)記 Placement 標(biāo)記的，直接返回老 Fiber C 的位置 2。

虛擬DOM E，在老 Fiber 的 Map 中是沒有匹配成功的，所以在創(chuàng)建 Fiber E 的時候，是沒有進(jìn)行老 Fiber 的復(fù)用的，去協(xié)調(diào)比對位置的時候，根據(jù)協(xié)調(diào)位置規(guī)則，沒有老 Fiber，就標(biāo)記 Placement 并返回上一次協(xié)調(diào)返回的位置，那么上一次 C 協(xié)調(diào)位置返回的位置信息是 2，這一次 E 協(xié)調(diào)位置依然返回 2。

虛擬DOM B 也在 Fiber 的 Map 中匹配成功了，那么匹配成功之后，就對老 Fiber B 進(jìn)行暫存，然后刪除老 Fiber B,再進(jìn)行信息復(fù)用，然后又進(jìn)行位置協(xié)調(diào)，老 Fiber B 的位置是 1，上一次協(xié)調(diào)返回的位置是 2，根據(jù)協(xié)調(diào)位置規(guī)則，老 Fiber 的位置小于上一次協(xié)調(diào)返回的位置，則標(biāo)記 Placement 并返回上一次協(xié)調(diào)返回的位置 2。

最后，老 Fiber 的 Map 中還存在一個 D 節(jié)點(diǎn)沒處理，則需要對其進(jìn)行刪除標(biāo)記操作。

最終新 Fiber 將被協(xié)調(diào)成下面的樣子：

那么根據(jù)圖片，我們又可以得出一個結(jié)論，匹配到的老 Fiber 如果和新 Fiber 相同或者在新 Fiber 位置的右邊則不需要進(jìn)行移動標(biāo)記。

Vue3 的 Diff 算法

在我看來 Vue3 的 Diff 算法是 Vue2、Vue3、React 的 Diff 算法中最復(fù)雜的一種。 下面我們來簡單說一下 Vue3 的 Diff 算法，只說數(shù)組和數(shù)組比對的情況。

第一輪，常見情況的比對

首先從左往右進(jìn)行比對，如果是相同的就進(jìn)行更新比對，如果不相同則停止比對，并且記錄停止的下標(biāo)。 再從右往左進(jìn)行比對，如果是相同的就進(jìn)行更新比對，如果不相同也停止比對，也進(jìn)行記錄停止的下標(biāo)。 通過這樣左右進(jìn)行比對，最后就可以把真正復(fù)雜部分進(jìn)行范圍鎖定了。 左右比對完之后，如果新節(jié)點(diǎn)已經(jīng)比對完了，老節(jié)點(diǎn)列表還存在節(jié)點(diǎn)未比對，則刪除老節(jié)點(diǎn)列表上的未比對的節(jié)點(diǎn)，如果老節(jié)點(diǎn)已經(jīng)比對完了，新節(jié)點(diǎn)列表還存在未比對的節(jié)點(diǎn)則進(jìn)行創(chuàng)建。

第二輪，復(fù)雜情況的比對

如果新節(jié)點(diǎn)未比對完，老節(jié)點(diǎn)也未比對完，則進(jìn)行最后最復(fù)雜的處理。

先把剩下的新節(jié)點(diǎn)處理成節(jié)點(diǎn)的 key 為 key, 節(jié)點(diǎn)下標(biāo)為 value 的 Map； 接著初始化一個長度為剩下未比對的新節(jié)點(diǎn)的長度的數(shù)組 newIndexToOldIndexMap，初始化每個數(shù)組的下標(biāo)的默認(rèn)值為 0。 再循環(huán)剩下的舊節(jié)點(diǎn)，通過舊節(jié)點(diǎn)的 key 去剛剛創(chuàng)建的 Map 中查找，看看舊節(jié)點(diǎn)有沒有在新節(jié)點(diǎn)中，如果舊節(jié)點(diǎn)沒有 key 則需要通過循環(huán)剩下的新節(jié)點(diǎn)進(jìn)行查找。 如果舊節(jié)點(diǎn)在新節(jié)點(diǎn)中沒找到，則說明該舊節(jié)點(diǎn)需要進(jìn)行刪除。 如果找到了，則把找到的新節(jié)點(diǎn)的下標(biāo)對應(yīng)存儲到上述的數(shù)組 newIndexToOldIndexMap 中，然后更新比對匹配到的新老節(jié)點(diǎn)。

把所有的舊節(jié)點(diǎn)比對完成后，就會得到一個剛剛收集的新節(jié)點(diǎn)的下標(biāo)數(shù)組，然后對這個新節(jié)點(diǎn)的下標(biāo)數(shù)組進(jìn)行進(jìn)行最長遞增子序列查找得到一個最長遞增子序列的下標(biāo)數(shù)據(jù)。 然后再進(jìn)行循環(huán)左右對比完之后剩余新節(jié)點(diǎn)的下標(biāo)，然后判斷循環(huán)的下標(biāo)是否被上述的數(shù)組 newIndexToOldIndexMap 進(jìn)行收集了，如果沒被收集到則說明這個新節(jié)點(diǎn)需要進(jìn)行創(chuàng)建，如果已經(jīng)被收集了則判斷該循環(huán)的下標(biāo)是否在上面計算得到的最長遞增子序列中，如果不在則需要對該循環(huán)節(jié)點(diǎn)進(jìn)行移動操作。

以上就是 Vue3 Diff 算法大概過程了。

更加詳細(xì)的 Vue3 Diff 算法解析可以查看我這篇文章：vue3中的diff算法

Vue2 的 Diff 算法

Vue2 的 Diff 算法就是以新的虛擬DOM為準(zhǔn)進(jìn)行與老虛擬DOM的比對，繼而進(jìn)行各種情況的處理。大概可以分為 4 種情況：更新節(jié)點(diǎn)、新增節(jié)點(diǎn)、刪除節(jié)點(diǎn)、移動節(jié)點(diǎn)位置。比對新老兩個虛擬DOM，就是通過循環(huán)，每循環(huán)到一個新節(jié)點(diǎn)，就去老節(jié)點(diǎn)列表里面找到和當(dāng)前新節(jié)點(diǎn)相同的舊節(jié)點(diǎn)。如果在舊節(jié)點(diǎn)列表中找不到，說明當(dāng)前節(jié)點(diǎn)是需要新增的節(jié)點(diǎn)，我們就需要進(jìn)行創(chuàng)建節(jié)點(diǎn)并插入視圖的操作；如果找到了，就做更新操作；如果找到的舊節(jié)點(diǎn)與新節(jié)點(diǎn)位置不同，則需要移動節(jié)點(diǎn)等。

第一輪，簡單情況的比對

其中為了快速查找到節(jié)點(diǎn)，Vue2 的 Diff 算法設(shè)置了 4 種優(yōu)化策略，分別是：

• 老數(shù)組的開始與新數(shù)組的開始
• 老數(shù)組的結(jié)尾與新數(shù)組的結(jié)尾
• 老數(shù)組的開始與新數(shù)組的結(jié)尾
• 老數(shù)組的結(jié)尾與新數(shù)組的開始

通過這 4 種快捷的查找方式，我們就不需要循環(huán)來查找了，只有當(dāng)以上 4 種方式都查找不到的時候，再進(jìn)行循環(huán)查找。

第二輪，不常見的情況的比對

最后循環(huán)結(jié)束后需要對未處理的節(jié)點(diǎn)進(jìn)行處理。

如果是老節(jié)點(diǎn)列表先循環(huán)完畢，這個時候如果新節(jié)點(diǎn)列表還有剩余的節(jié)點(diǎn)，則說明這些節(jié)點(diǎn)都是需要新增的節(jié)點(diǎn)，直接把這些節(jié)點(diǎn)創(chuàng)建并插入到 DOM 中就行了。

如果是新節(jié)點(diǎn)列表先循環(huán)完畢，這個時候如果老節(jié)點(diǎn)列表還有剩余節(jié)點(diǎn)，則說明這些節(jié)點(diǎn)都是要被廢棄的節(jié)點(diǎn)，是應(yīng)該被刪除的節(jié)點(diǎn)，直接批量刪除就可以了。

更加詳細(xì)的 Vue2 diff 算法可以查看我這篇文章：Vue2 的 diff 算法詳解

React、Vue3、Vue2 的 Diff 算法對比

相同點(diǎn)

只有使用了虛擬DOM的這些框架，在進(jìn)行更新 Diff 對比的時候，都是優(yōu)先處理簡單的場景，再處理復(fù)雜的場景。

React 中是先處理左邊部分，左邊部分處理不了，再進(jìn)行復(fù)雜部分的處理；Vue2 則先進(jìn)行首尾、首首、尾尾部分的處理，然后再進(jìn)行中間復(fù)雜部分的處理；Vue3 則先處理首尾部分，然后再處理中間復(fù)雜部分，Vue2 和 Vue3 最大的區(qū)別就是在處理中間復(fù)雜部分使用了最長遞增子序列算法找出穩(wěn)定序列的部分。

在處理老節(jié)點(diǎn)部分，都需要把節(jié)點(diǎn)處理 key - value 的 Map 數(shù)據(jù)結(jié)構(gòu)，方便在往后的比對中可以快速通過節(jié)點(diǎn)的 key 取到對應(yīng)的節(jié)點(diǎn)。同樣在比對兩個新老節(jié)點(diǎn)是否相同時，key 是否相同也是非常重要的判斷標(biāo)準(zhǔn)。所以不同是 React, 還是 Vue，在寫動態(tài)列表的時候，都需要設(shè)置一個唯一值 key，這樣在 diff 算法處理的時候性能才最大化。

在移動或者創(chuàng)建節(jié)點(diǎn)的時候都使用了 insertBefore(newnode,existingnode) 這個 API：

• newnode 必需。需要插入的節(jié)點(diǎn)對象。
• existingnode 可選。在其之前插入新節(jié)點(diǎn)的子節(jié)點(diǎn)。如果未規(guī)定，則 insertBefore 方法會在結(jié)尾插入 newnode。

不同點(diǎn)

對靜態(tài)節(jié)點(diǎn)的處理不一樣。

由于 Vue 是通過 template 模版進(jìn)行編譯的，所以在編譯的時候可以很好對靜態(tài)節(jié)點(diǎn)進(jìn)行分析然后進(jìn)行打補(bǔ)丁標(biāo)記，然后在 Diff 的時候，Vue2 是判斷如果是靜態(tài)節(jié)點(diǎn)則跳過過循環(huán)對比，而 Vue3 則是把整個靜態(tài)節(jié)點(diǎn)進(jìn)行提升處理，Diff 的時候是不過進(jìn)入循環(huán)的，所以 Vue3 比 Vue2 的 Diff 性能更高效。而 React 因?yàn)槭峭ㄟ^ JSX 進(jìn)行編譯的，是無法進(jìn)行靜態(tài)節(jié)點(diǎn)分析的，所以 React 在對靜態(tài)節(jié)點(diǎn)處理這一塊是要遜色的。

Vue2 和 Vue3 的比對和更新是同步進(jìn)行的，這個跟 React15 是相同的，就是在比對的過程中，如果發(fā)現(xiàn)了那些節(jié)點(diǎn)需要移動或者更新或刪除，是立即執(zhí)行的，也就是 React 中常講的不可中斷的更新，如果比對量過大的話，就會造成卡頓，所以 React16 起就更改為了比對和更新是異步進(jìn)行的，所以 React16 以后的 Diff 是可以中斷，Diff 和任務(wù)調(diào)度都是在內(nèi)存中進(jìn)行的，所以即便中斷了，用戶也不會知道。

另外 Vue2 和 Vue3 都使用了雙端對比算法，而 React 的 Fiber 由于是單向鏈表的結(jié)構(gòu)，所以在 React 不設(shè)置由右向左的鏈表之前，都無法實(shí)現(xiàn)雙端對比。那么雙端對比目前 React 的 Diff 算法要好嗎？接下來我們來看看一個例子，看看它分別在 React、Vue2、Vue3 中的是怎么處理的。

比如說我們現(xiàn)在有以下兩組新老節(jié)點(diǎn)：

老：A, B, C, D

新：D, A, B, C

那么我們可以看到，新老兩組節(jié)點(diǎn)唯一的不同點(diǎn)就是，D 節(jié)點(diǎn)在新的節(jié)點(diǎn)中跑到開頭去了，像這種情況：

React 是從左向右進(jìn)行比對的，在上述這種情況，React 需要把 A, B, C 三個節(jié)點(diǎn)分別移動到 D 節(jié)點(diǎn)的后面。

Vue2 在進(jìn)行老節(jié)點(diǎn)的結(jié)尾與新節(jié)點(diǎn)的開始比對的時候，就發(fā)現(xiàn)這兩個節(jié)點(diǎn)是相同的，所以直接把老節(jié)點(diǎn)結(jié)尾的 D 移動到新節(jié)點(diǎn)開頭就行了，剩下的就只進(jìn)行老節(jié)點(diǎn)的開始與新節(jié)點(diǎn)的開始進(jìn)行比對，就可以發(fā)現(xiàn)它們的位置并沒有發(fā)生變化，不需要進(jìn)行移動。

Vue3 是沒有了 Vue2 的新老首尾節(jié)點(diǎn)進(jìn)行比較，只是從兩組節(jié)點(diǎn)的開頭和結(jié)尾進(jìn)行比較，然后往中間靠攏，那么 Vue3 在進(jìn)行新老節(jié)點(diǎn)的開始和結(jié)尾比對的時候，都沒有比對成功，接下來就進(jìn)行中間部分的比較，先把老節(jié)點(diǎn)處理成 key - value 的 Map 數(shù)據(jù)結(jié)構(gòu)，然后又使用最長遞增子序列算法找出其中的穩(wěn)定序列部分，也就是：A, B, C，然再對新節(jié)點(diǎn)進(jìn)行循環(huán)比對，然后就會發(fā)現(xiàn)新節(jié)點(diǎn)的 A, B, C 都在穩(wěn)定序列部分，不需要進(jìn)行移動，然就只對 D，進(jìn)行移動即可。

最后上述的例子在 Vue2 和 Vue3 中都只需要移動一個節(jié)點(diǎn)就可以完成 Diff 算法比對，而 React 在這種極端例子中則沒辦法進(jìn)行很好的優(yōu)化，需要進(jìn)行多次節(jié)點(diǎn)移動操作。

為什么 Vue 中不需要使用 Fiber

其實(shí)這個問題也可以叫做：為什么 Vue 不需要時間分片？對于這個問題其實(shí)尤雨溪也在英文社區(qū)里回答過，也有前端大牛翻譯發(fā)布在公眾號上，那么下面我也進(jìn)行一下總結(jié)。

第一，首先時間分片是為了解決 CPU 進(jìn)行大量計算的問題，因?yàn)?React 本身架構(gòu)的問題，在默認(rèn)的情況下更新會進(jìn)行過多的計算，就算使用 React 提供的性能優(yōu)化 API，進(jìn)行設(shè)置，也會因?yàn)殚_發(fā)者本身的問題，依然可能存在過多計算的問題。

第二，而 Vue 通過響應(yīng)式依賴跟蹤，在默認(rèn)的情況下可以做到只進(jìn)行組件樹級別的更新計算，而默認(rèn)下 React 是做不到的（據(jù)說 React 已經(jīng)在進(jìn)行這方面的優(yōu)化工作了），再者 Vue 是通過 template 進(jìn)行編譯的，可以在編譯的時候進(jìn)行非常好的性能優(yōu)化，比如對靜態(tài)節(jié)點(diǎn)進(jìn)行靜態(tài)節(jié)點(diǎn)提升的優(yōu)化處理，而通過 JSX 進(jìn)行編譯的 React 是做不到的。

第三，React 為了解決更新的時候進(jìn)行過多計算的問題引入了時間分片，但同時又帶來了額外的計算開銷，就是任務(wù)協(xié)調(diào)的計算，雖然 React 也使用最小堆等的算法進(jìn)行優(yōu)化，但相對 Vue 還是多了額外的性能開銷，因?yàn)?Vue 沒有時間分片，所以沒有這方面的性能擔(dān)憂。

第四，根據(jù)研究表明，人類的肉眼對 100 毫秒以內(nèi)的時間并不敏感，所以時間分片只對于處理超過 100 毫秒以上的計算才有很好的收益，而 Vue 的更新計算是很少出現(xiàn) 100 毫秒以上的計算的，所以 Vue 引入時間分片的收益并不劃算。

總結(jié)

我們先由 “ React 的 Diff 算法為什么不采用 Vue 的雙端對比的 Diff 算法？” 這個問題引出對 React 中的一些知識點(diǎn)的學(xué)習(xí)理解，比如什么是 Fiber，F(xiàn)iber 鏈表是如何生成的，然后詳細(xì)解析了 React Diff 算法，還對 React Diff 算法進(jìn)行圖文并茂解析，讓我們可以更加理解 React 的 Diff 算法。 其后，我們又簡單介紹了 Vue3 和 Vue2 的 Diff 算法，之后對 React、Vue3、Vue2之間的算法的異同進(jìn)行了講解。 最后我們又總結(jié)了一下尤雨溪對 “為什么 Vue 不需要時間分片？” 這個問題的解析。

以上就是React Diff算法不采用Vue雙端對比算法原因詳解的詳細(xì)內(nèi)容，更多關(guān)于React Diff算法不采用Vue雙端對比的資料請關(guān)注腳本之家其它相關(guān)文章！

最新評論