深度對比 React 與 Vue 的 Diff 算法

昨天接了個廣子，恰了點飯。你們的吐槽我的認了，哎呀，你們都說得對。所以我今晚連夜爆肝寫了一篇專門用來面試的干貨，總計 7000 字左右，分享給大家，必須要搶救一下想要取關(guān)的大佬們！

許多朋友會在簡歷上同時寫自己會 React、Vue，但是倒霉的面試官一看到這種簡歷，就喜歡問它們有什么區(qū)別。其中頻率比較高的一個問題就是 React 與 Vue 的 diff 算法有啥相同之處和不同之處...

很顯然，這種問題對于面試考驗開發(fā)者能力而言，沒啥營養(yǎng)，就算知道了，對開發(fā)能力也不會有什么明顯的提高，還不如更具體的問 key 值有什么用呢，但是沒辦法，有的面試官就是愛問，既然這樣，那我們就答給他們看。

假說論

我們在思考算法問題的時候，一定要謹記一個前提，那就是沒有完美的算法可以解決所有問題。 因此，在設(shè)計一個算法時，我們需要充分考慮應(yīng)用場景，然后提出一個假說，從而極大的減少問題的復(fù)雜性，讓解決方案變得更加簡單。

在 React/Vue 的 diff 算法中，當我們要對比前后兩棵樹的差異時，我們的目標是盡可能少的創(chuàng)建節(jié)點。但是由于 DOM 操作的可能性太復(fù)雜了，因此如果要全部對比出來，復(fù)雜度就非常高。達到了 O(n^ 3) 這個級別。

之所以這么復(fù)雜的原因，就是因為節(jié)點不僅可以增加刪除，還可以移動。我們要分辨節(jié)點是否從子元素移動到了父元素，或者增加了一個父元素，判斷過程非常復(fù)雜。因此，在設(shè)計 dfiff 算法的時候，React/Vue 都放棄了這種情況的識別。

他們根據(jù)實際情況提出的假說是：在實際情況中，整棵 DOM 樹里，關(guān)于父子節(jié)點移動的情況是比較少的，因此，沒有必要為了這種少部分情況加劇算法的壓力。只要放棄識別這種情況，算法就能夠得到極大的簡化。

幾乎相同的比較策略

在上面我們提到的假說論之下，React/Vue 在 diff 算法上，都使用了非常類似的策略。

一、同層比較

如下圖所示，diff 算法只需要比較相同層級的節(jié)點是否相同

比較之后又兩種情況

• 如果相同：則直接復(fù)用，而不需要重新創(chuàng)建
• 如果不同：則直接默認為從該節(jié)點開始，以下的全部節(jié)點都發(fā)生了變化，需要重新創(chuàng)建。

如下圖所示，雖然節(jié)點只是發(fā)生了移動，但是在 diff 過程中，會被認為 A 節(jié)點已經(jīng)被刪除，然后重新創(chuàng)建它。

因此，在開發(fā)過程中，我們可以通過避免跨層級操作節(jié)點的方式，來提高你應(yīng)用程序的性能。

二、節(jié)點比較

在對比節(jié)點是否相同時，React 與 Vue 的處理策略也比較類似。了解節(jié)點的比較方式，是我們在做性能優(yōu)化時的重要依據(jù)。

節(jié)點比較有兩種情況，一種節(jié)點是默認支持的 DOM 節(jié)點，一種是通過自定義創(chuàng)造出來的自定義節(jié)點，在 React 中會區(qū)分這兩種情況，但是在 Vue 中會統(tǒng)一只識別標簽名 tag。

除了這個情況之外，在結(jié)構(gòu)類型上，還分為兩種情況，一種是正常的樹狀結(jié)構(gòu)，另外一種是列表結(jié)構(gòu)。列表結(jié)構(gòu)通常情況下我們就不能直接忽視移動這種情況。因此，針對于這種列表結(jié)構(gòu)，React 和 Vue 都優(yōu)先提倡使用傳入 key 值的方式進行標記，從而極大的減小比較壓力。

因此，在列表節(jié)點的比較中，React、Vue 都優(yōu)先比較 key 值。

!

不過針對列表的比較方式處理，是 React 和 Vue 在 diff 算法上最大的差別。我們后面單獨介紹

然后，在 React 中，diff 算法會優(yōu)先比較節(jié)點類型是否相同。例如下面的代碼，div 與 span 屬于不同的節(jié)點類型，那么就表示不是同一個節(jié)點。

<div>
  <Counter />
</div>

<span>
  <Counter />
</span>

然后會比較 props、state、context 等外部傳入的參數(shù)是否相同，從而判斷是否是同一個節(jié)點。當然，這里還有一個重要的細節(jié)，對于性能優(yōu)化至關(guān)重要。

由于在 React 中，props 的傳入都是通過類似于函數(shù)傳參的方式傳入，例如

function Counter({ a: 1 }) {...}

前后兩次執(zhí)行

Counter({a: 1})
Counter({a: 1})

這里的細節(jié)就是，雖然兩次都入?yún)⒍际?{a: 1}，但是他們是不同的內(nèi)存地址，因此前后兩次 props 的比較結(jié)果始終為 false

{a: 1} === {a: 1} // false

如果不解決這個問題，任何比較方式都是沒有意義的，結(jié)果都是為 false。

所里這里 React 設(shè)計了一個巧妙的規(guī)則，那就是當我們判定元素節(jié)點的父節(jié)點未發(fā)生變化時，就不比較 props，從而跳過 props 的比較，來提高性能。我們可以利用這樣的特性在 React 中寫出性能非常高的代碼。

除此之外，React 還設(shè)計了一個 api，React.memo，該 api 可以改變 props 的比較規(guī)則。使用方式如下所示，memo 接收組件聲明作為參數(shù)

function Counter({ a: 1, b: 2 }) {...}

export default React.memo(Counter)

使用 memo 包裹之后，props 的比較規(guī)則變成了依次比較第一層 key 值所對應(yīng)的值。例如，上面的案例中，包裹之前的比較方式為

{ a: 1, b: 2 } === { a: 1, b: 2 } // 始終為 false

包裹之后的比較方式為

p1.a === p2.a && p1.b === p2.b // true

因此，在特定的場景中，使用 memo 可以有效命中可復(fù)用節(jié)點。

在 Vue 中，由于并不是那么強依賴 diff 算法，因此它的節(jié)點比較邏輯相對而言會簡單直接一些，通過一個 sameVnode 方法來比較節(jié)點是否相同。

// Vue2 /src/core/vdom/patch.js
// 主要通過對key和標簽名做比較
function sameVnode (a, b) {
  return (
    a.key === b.key && // 標簽名是否一樣
    a.asyncFactory === b.asyncFactory && ( // 是否都是異步工廠方法
      (
        a.tag === b.tag && // 標簽名是否一樣
        a.isComment === b.isComment && // 是否都為注釋節(jié)點
        isDef(a.data) === isDef(b.data) && // 是否都定義了data
        sameInputType(a, b)  // 當標簽為input時，type必須是否相同
      ) || (
        isTrue(a.isAsyncPlaceholder) && // 是否都有異步占位符節(jié)點
        isUndef(b.asyncFactory.error)
      )
    )
  )
}

function sameInputType(a, b) {
  if (a.tag !== 'input') return true
  let i
  const typeA = isDef((i = a.data)) && isDef((i = i.attrs)) && i.type
  const typeB = isDef((i = b.data)) && isDef((i = i.attrs)) && i.type
  return typeA === typeB || (isTextInputType(typeA) && isTextInputType(typeB))
}

這里需要注意的是，如果我們要詳細的聊清楚 React 和 Vue 在節(jié)點是否相同的比較方式上時，就要明白 React 是強依賴于這個，但是 Vue 依賴較弱，因為 Vue 的實現(xiàn)原理中更多的是通過依賴收集的方式來找到需要更新的節(jié)點，這也導(dǎo)致了 React 在這個上面的邏輯要更加復(fù)雜，Vue 則更加簡單。因此，我們需要對他們各自的原理背景有一定的了解。

最大的區(qū)別，在列表上的處理

列表是性能問題頻發(fā)的重要場景，因此，React 和 Vue 都針對長列表設(shè)計了特殊的處理方式。在聊之前，我們要明確處理場景，那就是，在列表中，我們就不能再忽視節(jié)點位置的移動了。

因為，一個簡單的移動，就很容易會造成整個組件被判定為需要全部重新創(chuàng)建。所以，我們需要判斷出來節(jié)點是只發(fā)生了移動，而不是需要重新創(chuàng)建。

給列表中的每一個節(jié)點，引入唯一 key 值，是他們都共同采用的技術(shù)手段。通過唯一key 值，我們可以在舊列表中找到新列表的節(jié)點是否已經(jīng)存在，從而決定是移動節(jié)點的位置還是創(chuàng)建新的節(jié)點。我們通常會在數(shù)組中設(shè)定一個 id 用于表示唯一 key 值。

const todoItems = todos.map((todo) =>
  <li key={todo.id}>
    {todo.text}
  </li>
);

需要注意的是，這里的唯一 key 值，盡量不要使用遞增的數(shù)字序列來表示。

const todoItems = todos.map((todo, index) =>
  // Only do this if items have no stable IDs
  <li key={index}>
    {todo.text}
  </li>
);

這個問題也是面試中經(jīng)常會聊到的話題：為什么盡量不要使用 index 序列作為 key。這是因為當我們在列表中新增一個內(nèi)容時，每一項的 index 每次都會發(fā)生變化，從而讓渲染結(jié)果出現(xiàn)混亂。

例如有一個數(shù)組為  [a, b, c]，此時我們將 index 作為key值，那么數(shù)組項與 key 值的對應(yīng)關(guān)系就是

[a:0, b:1, c:2]

此時，我們往數(shù)組頭部添加一個數(shù)據(jù)，這個時候數(shù)組變成了 [p, a, b, c]，然后再執(zhí)行，數(shù)組項與 key 的對應(yīng)關(guān)系就變成了

[p:0, a:1, b:2, c:3]

新增的項是 p，但是最終導(dǎo)致了數(shù)組項與key 之間的對應(yīng)關(guān)系錯亂，結(jié)果導(dǎo)致緩存的節(jié)點掛到了錯誤的數(shù)組項上去了。我們可以通過如下案例演示觀察在 UI 上的表現(xiàn)差別

首先，我們的默認情況如下，上面的列表使用 index 作為 key 值，下面的列表使用 唯一 id 作為key 值。

當我新增一個項時，仔細觀察兩個列表的差異。

在引入了 key 值之后，為了追求在某些情況下更少的移動次數(shù)，Vue 中使用了更復(fù)雜的算法設(shè)計：雙端比較以及最長子序列遞增，這是他們最大的區(qū)別。

React 的比較方式

首先，我們假定有一個已經(jīng)渲染好的列表節(jié)點如下

// 使用 _ 表示舊節(jié)點列表
[_A] [_B] [_C] [_D]

然后，我們在 A 的前面新增的了一個節(jié)點，P，理想的結(jié)果如下所示

[P] [A] [B] [C] [D]

在比較的過程中，我們會首先創(chuàng)建一個變量 lastIndex，默認值為 0。然后使用一個指針 index 用來記錄新數(shù)組中的當前項在舊列表中的索引值。

在比較的過程中，lastIndex 的變化規(guī)則如下

lastIndex = max(index, lastIndex)

例如，我們開始遍歷新數(shù)據(jù) [P, A, B, C D]

1、第一個目標項為 P，我們會去舊列表中查詢是否存在相同的 key=P 的項。發(fā)現(xiàn)沒有，此時創(chuàng)建新節(jié)點

lastIndex = 0

[P]

2、第二個目標項為 A，我們?nèi)ヅf列表中查詢是否存在相同的，發(fā)現(xiàn)有，此時 index = 0，可復(fù)用節(jié)點

當滿足條件 index < lastIndex 時，移動節(jié)點。此時 index = 0，lastIndex = 0，不滿足條件，不移動，此時結(jié)果為

// 結(jié)果為 0
lastIndex = max(index, lastIndex)

[P] [A]

i

注意：這里說的移動節(jié)點，指的是對真實 DOM 的操作。

?

這里需要多花點時間感受一下這個判斷條件的合理性， index < lastIndex，他是為了確保索引的正確順序而設(shè)計的規(guī)則

3、第三個目標項為 B，我們?nèi)ヅf列表中查詢是否存在相同的key，發(fā)現(xiàn)有，此時 index = 1，可復(fù)用節(jié)點

不滿足 index(1) < lastIndex(0)，不移動，結(jié)果為

// 結(jié)果為 1
lastIndex = max(index, lastIndex)

[P] [A] [B]

依次類推，最終我們發(fā)現(xiàn)，這種情況下，只需要創(chuàng)建一個新節(jié)點 P，不需要移動任何節(jié)點。

第二個案例

新舊列表節(jié)點如下

舊列表：[A] [B] [C] [D] 
新列表：[B] [A] [D] [C]

新的數(shù)據(jù)為 [B, A, D, C]

1、第一個目標節(jié)點為 B，發(fā)現(xiàn)在舊列表中存在相同 key，那么復(fù)用節(jié)點，此時，index = 1，當前結(jié)果為

index = 1
lastIndex = 0
index < lastIndex // false，不移動

lastIndex = max(index, lastIndex) // 1

[B]

2、第二個目標節(jié)點為 A，發(fā)現(xiàn)在舊列表中存在相同 key，那么復(fù)用節(jié)點，此時，index = 0，當前結(jié)果為

index = 0
lastIndex = 1
index < lastIndex // true，移動

lastIndex = max(index, lastIndex) // 1

[B] [A]

3、第三個目標節(jié)點為 D，發(fā)現(xiàn)在舊列表中存在相同 key，那么復(fù)用節(jié)點，此時，index = 3，當前結(jié)果為

index = 3
lastIndex = 1
index < lastIndex // false，不移動

lastIndex = max(index, lastIndex) // 3

[B] [A] [D]

4、第四個目標節(jié)點為 C，發(fā)現(xiàn)在舊列表中存在相同 key，那么復(fù)用節(jié)點，此時，index = 2，當前結(jié)果為

index = 2
lastIndex = 3
index < lastIndex // true，移動

lastIndex = max(index, lastIndex) // 3

[B] [A] [D] [C]

這個案例在 diff 之后，只需要真實 DOM 移動兩次節(jié)點。就可以完成更新了。

相信通過這兩個案例，大家應(yīng)該能掌握 React 在列表中的對比規(guī)則，接下來，我們來了解一下 Vue 的雙端對比。

Vue 雙端比較

Vue 的雙端對比的設(shè)計有一個目標，那就是在特定的場景之下，減少真實 DOM 的移動次數(shù)。我們來看一下這樣一種場景。

舊：[A] [B] [C] [D]
新：[D] [A] [B] [C]

如果按照 React 的比較規(guī)則，此時由于第一個目標 D 的 index 為 3，從一開始就變成了最大，因此，后續(xù)的 lastIndex 都為 3，所有的目標項都會滿足 index < lastIndex，因此，真實 DOM 的移動就會執(zhí)行 3 次。

而 Vue 提出的雙端比較，目標就是希望可以識別出來這種情況，只需要讓移動只發(fā)生一次即可。就是 D 從最末尾移動到最前面。

雙端比較會使用 4 個指針，分別記錄舊列表和新列表的首尾兩個節(jié)點位置。

let oldStartIdx = 0
let oldEndIdx = prevChildren.length - 1
let newStartIdx = 0
let newEndIdx = nextChildren.length - 1

以及對應(yīng)的虛擬節(jié)點對象

let oldStartVNode = prevChildren[oldStartIdx]
let oldEndVNode = prevChildren[oldEndIdx]
let newStartVNode = nextChildren[newStartIdx]
let newEndVNode = nextChildren[newEndIdx]

比較的規(guī)則遵循：首-首比較，尾-尾比較，尾-首比較，首-尾比較的順序。通過這樣方式找出首尾是否有節(jié)點可以被復(fù)用。

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
  if (oldStartVNode.key === newStartVNode.key) {
    // ...
  } else if (oldEndVNode.key === newEndVNode.key) {
    // ...
  } else if (oldStartVNode.key === newEndVNode.key) {
    // ...
  } else if (oldEndVNode.key === newStartVNode.key) {
    // ...
  }
}

例如下面案例

舊：[A] [B] [C] [D]
新：[D] [A] [B] [C]

在首次經(jīng)過四次比較之后，發(fā)現(xiàn) 新首-舊尾 key 值相同，可以復(fù)用，此時需要通過移動首尾索引指針構(gòu)建新的新舊節(jié)點數(shù)組

// 發(fā)現(xiàn)復(fù)用節(jié)點，update
patch(oldEndVNode, newStartVNode, container)
// 移動
container.insertBefore(oldEndVNode.el, oldStartVNode.el)
// 更新索引指針
oldEndVNode = prevChildren[--oldEndIdx]
newStartVNode = nextChildren[++newStartIdx]

然后新的新舊數(shù)組為

舊：[A] [B] [C] -[D]
新：-[D] [A] [B] [C]

演變?yōu)?br>
舊：[A] [B] [C]
新：[A] [B] [C]

得到新的新舊數(shù)組，繼續(xù)重復(fù)首-首比較，尾-尾比較，尾-首比較，首-尾比較。直到比較結(jié)束。

指針的移動方向，總體趨勢是從兩端往中間移動。

這里需要特別注意的是，這樣的比較方式雖然快，但這是不充分比較，因此，在許多情況下，會導(dǎo)致節(jié)點存在復(fù)用，但是沒有找出來。因此，如果沒找到可復(fù)用的節(jié)點，比較還沒有結(jié)束，還有后續(xù)的邏輯。

我們構(gòu)建一個新的案例，如下所示

舊：[A] [B] [C] [D]
新：[B] [D] [A] [C]

此時我們發(fā)現(xiàn)，通過首位的 4 次比較，結(jié)果一個可復(fù)用的節(jié)點都沒找到，因此，此時需要回過頭來重新完整的遍歷，以新首 key 為當前目標，去舊列表中依次查找是否存在可復(fù)用節(jié)點

在這個案例中，可以找到，那么，我們就把 B 移動到首位

舊：[A] -[B] [C] [D]
新：-[B] [D] [A] [C]

移動之后，通過改變指針位置，再將新的雙端列表演變?yōu)?/p>

舊：[A] [C] [D]
新：[D] [A] [C]

然后再以新尾 key 作為當前目標，去舊列表中依次遍歷找尋。可以找到 C，將 C 移動到尾部。然后依次類推。

最后，如果雙端對比結(jié)束之后，舊列表中還存在節(jié)點，則表示這些節(jié)點需要被批量刪除

如果對比結(jié)束之后，新列表中還存在節(jié)點，則表示這些節(jié)點需要批量新增，簡單處理即可。

Vue3 中的處理方式又發(fā)生了變化，但是時間來不及太詳細的分析了，我這里就簡單說一下，可以用于面試的術(shù)語：

先處理左側(cè)相同部分，再處理右側(cè)相同部分，鎖定可復(fù)用的節(jié)點之后，再針對中間亂序部分，采用最長遞增子序列的算法，計算出亂序部分可以復(fù)用的最長連續(xù)節(jié)點。通過這個遞增數(shù)組，我們就可以知道哪些節(jié)點在變化前后的相對位置沒有發(fā)生變化，哪些需要移動。

?

關(guān)于最長遞增子序列大家可以通過力扣的算法題了解。涉及到的動態(tài)規(guī)劃、二分、回朔等方式在評論都有大量的提到。他的目標依然是為了減少真實 DOM 的移動次數(shù)

https://leetcode.cn/problems/longest-increasing-subsequence/description/

總結(jié)

本文比較了 React 和 Vue 在 diff 算法上的相同的考慮與差異的處理，主要的作用是為了應(yīng)對面試中的場景，在實踐應(yīng)用場景中用處不是很大。大家可以收藏起來慢慢看。

我在最后用了非常大量的篇幅介紹 React 與 Vue 在列表中對比的差異，Vue 由于在努力追求真實 DOM 能夠以最小的移動來更新 DOM，因此在算法上更加特殊。

不過需要特別注意的是，在同一次事件循環(huán)中，由于瀏覽器在渲染時本身就會對 DOM 樹進行統(tǒng)一的處理和繪制，因此，節(jié)點移動 1 次，還是移動 100 次，只要在這一幀中的最終結(jié)果是一樣的，那么在渲染階段所消耗的計算成本實際上是一樣的，沒有太大的區(qū)別。因此，我個人的觀點是 Vue 這種算法對于渲染性能的提升效果應(yīng)該是非常微弱的。