前言

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

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

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

React 官方的解析

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

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

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

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

本人水平有限，錯(cuò)漏難免，如有錯(cuò)漏，懇請(qǐng)各位斧正。

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

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

在 React15 以前 React 的組件更新創(chuàng)建虛擬 DOM 和 Diff 的過程是不可中斷，如果需要更新組件樹層級(jí)非常深的話，在 Diff 的過程會(huì)非常占用瀏覽器的線程，而我們都知道瀏覽器執(zhí)行JavaScript 的線程和渲染真實(shí) DOM 的線程是互斥的，也就是同一時(shí)間內(nèi)，瀏覽器要么在執(zhí)行 JavaScript 的代碼運(yùn)算，要么在渲染頁面，如果 JavaScript 的代碼運(yùn)行時(shí)間過長(zhǎng)則會(huì)造成頁面卡頓。 基于以上原因 React 團(tuán)隊(duì)在 React16 之后就改寫了整個(gè)架構(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)主要長(zhǎng)成以下的樣子，主要通過 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;

  // 作為動(dòng)態(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)先級(jí)相關(guān)
  this.lanes = NoLanes;
  this.childLanes = NoLanes;

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

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

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

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

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

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

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

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

Fiber 鏈表的生成

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

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

// 這個(gè)協(xié)調(diào)子節(jié)點(diǎn)的函數(shù)接收兩個(gè)參數(shù)，returnFiber 是父 Fiber，children 是這個(gè)節(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;
    // 記錄每個(gè) 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 則不需要?jiǎng)?chuàng)建 fiber 節(jié)點(diǎn)
            if(newChild === null) {
                continue
            }
            // 創(chuàng)建新 fiber 的時(shí)候記錄了關(guān)鍵的父 fiber 等重要信息
            const newFiber = createFiber(newChild, returnFiber)
            // 記錄當(dāng)前每一個(gè) fiber 的位置
            lastPlacedIndex = placeChild(
                newFiber,
                lastPlacedIndex,
                newIdx,
                shouldTrackSideEffects // 初次渲染（false）還是更新（true）
            )
		    // 當(dāng)上一輪的 fiber 節(jié)點(diǎn)為 null 的時(shí)候，這一輪的 fiber 就是頭節(jié)點(diǎn)
            if(previousNewFiber === null) {
                // 父 fiber 的 child 就是第一個(gè)節(jié)點(diǎn)
                returnFiber.child = newFiber
            } else {
                // 如果不是第一個(gè)節(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樹 會(huì)在 commit階段 渲染到頁面。

在組件狀態(tài)數(shù)據(jù)發(fā)生變更的時(shí)候，會(huì)根據(jù)最新的狀態(tài)數(shù)據(jù)先會(huì)生成新的虛擬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)是在更新自己的同時(shí)需要去協(xié)調(diào)子節(jié)點(diǎn)，也就是傳說中進(jìn)行 Diff 的地方。

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

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

第一輪，常見情況的比對(duì)

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

怎么比對(duì)呢？

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

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

第二輪，不常見的情況的比對(duì)

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

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

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

在循環(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; 更新比對(duì)的老 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)需要?jiǎng)?chuàng)建，就給當(dāng)前新的 Fiber 節(jié)點(diǎn)打上一個(gè) Placement 的標(biāo)記，如果有老 Fiber 節(jié)點(diǎn)，則判斷老 Fiber 節(jié)點(diǎn)的位置是否比上一次協(xié)調(diào)的返回的位置小，如果是，則說明該節(jié)點(diǎn)需要移動(dòng)，給新 Fiber 節(jié)點(diǎn)打上一個(gè) Placement 的標(biāo)記，并繼續(xù)返回上一次協(xié)調(diào)返回的位置；如果老 Fiber 節(jié)點(diǎn)的位置大或者等于上一次協(xié)調(diào)返回的位置，則說明該節(jié)點(diǎn)不需要進(jìn)行位置移動(dòng)操作，就返回老 Fiber 的位置即可。

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

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

小結(jié)

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

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

圖文解釋 React Diff 算法

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

最簡(jiǎn)單的 Diff 場(chǎng)景

上圖的 Diff 場(chǎng)景是最簡(jiǎn)單的一種，新虛擬DOM 從左到右都能和老 Fiber 的節(jié)點(diǎn)一一匹配成功，協(xié)調(diào)位置的時(shí)候，老 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)位置的時(shí)候，老 Fiber B 位置 1 不比上一次協(xié)調(diào)返回的位置 0 小，則只需返回老 Fiber B 的位置 1 即可；到了 C 進(jìn)行協(xié)調(diào)位置的時(shí)候，老 Fiber C 位置 2 不比上一次協(xié)調(diào)返回的位置 1 小，則只需要返回老 Fiber C 的位置 2 即可；

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

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

復(fù)雜的 Diff 場(chǎng)景

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

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

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

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

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

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

老 Fiber C 的位置是 2，然后上一次新 Fiber A 協(xié)調(diào)比對(duì)返回的位置信息是 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 的時(shí)候，是沒有進(jìn)行老 Fiber 的復(fù)用的，去協(xié)調(diào)比對(duì)位置的時(shí)候，根據(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 中匹配成功了，那么匹配成功之后，就對(duì)老 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 中還存在一個(gè) D 節(jié)點(diǎn)沒處理，則需要對(duì)其進(jìn)行刪除標(biāo)記操作。

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

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

Vue3 的 Diff 算法

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

第一輪，常見情況的比對(duì)

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

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

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

先把剩下的新節(jié)點(diǎn)處理成節(jié)點(diǎn)的 key 為 key, 節(jié)點(diǎn)下標(biāo)為 value 的 Map； 接著初始化一個(gè)長(zhǎng)度為剩下未比對(duì)的新節(jié)點(diǎn)的長(zhǎng)度的數(shù)組 newIndexToOldIndexMap，初始化每個(gè)數(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)對(duì)應(yīng)存儲(chǔ)到上述的數(shù)組 newIndexToOldIndexMap 中，然后更新比對(duì)匹配到的新老節(jié)點(diǎn)。

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

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

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

Vue2 的 Diff 算法

Vue2 的 Diff 算法就是以新的虛擬DOM為準(zhǔn)進(jìn)行與老虛擬DOM的比對(duì)，繼而進(jìn)行各種情況的處理。大概可以分為 4 種情況：更新節(jié)點(diǎn)、新增節(jié)點(diǎn)、刪除節(jié)點(diǎn)、移動(dòng)節(jié)點(diǎn)位置。比對(duì)新老兩個(gè)虛擬DOM，就是通過循環(huán)，每循環(huán)到一個(gè)新節(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)位置不同，則需要移動(dòng)節(jié)點(diǎn)等。

第一輪，簡(jiǎn)單情況的比對(duì)

其中為了快速查找到節(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 種方式都查找不到的時(shí)候，再進(jìn)行循環(huán)查找。

第二輪，不常見的情況的比對(duì)

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

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

如果是新節(jié)點(diǎn)列表先循環(huán)完畢，這個(gè)時(shí)候如果老節(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 算法對(duì)比

相同點(diǎn)

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

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

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

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

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

不同點(diǎn)

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

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

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

另外 Vue2 和 Vue3 都使用了雙端對(duì)比算法，而 React 的 Fiber 由于是單向鏈表的結(jié)構(gòu)，所以在 React 不設(shè)置由右向左的鏈表之前，都無法實(shí)現(xiàn)雙端對(duì)比。那么雙端對(duì)比目前 React 的 Diff 算法要好嗎？接下來我們來看看一個(gè)例子，看看它分別在 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)行比對(duì)的，在上述這種情況，React 需要把 A, B, C 三個(gè)節(jié)點(diǎn)分別移動(dòng)到 D 節(jié)點(diǎn)的后面。

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

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

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

為什么 Vue 中不需要使用 Fiber

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

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

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

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

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

總結(jié)

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

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

最新評(píng)論