深度對比 React 與 Vue 的 Diff 算法

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

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

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

假說論

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

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

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

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

幾乎相同的比較策略

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

一、同層比較

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

比較之後又兩種情況

• 如果相同：則直接複用，而不需要重新創建

• 如果不同：則直接默認爲從該節點開始，以下的全部節點都發生了變化，需要重新創建。

如下圖所示，雖然節點只是發生了移動，但是在 diff 過程中，會被認爲 A 節點已經被刪除，然後重新創建它。

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

二、節點比較

在對比節點是否相同時，React 與 Vue 的處理策略也比較類似。瞭解節點的比較方式，是我們在做性能優化時的重要依據。

節點比較有兩種情況，一種節點是默認支持的 DOM 節點，一種是通過自定義創造出來的自定義節點，在 React 中會區分這兩種情況，但是在 Vue 中會統一隻識別標籤名 tag。

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

因此，在列表節點的比較中，React、Vue 都優先比較 key 值。

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

然後，在 React 中，diff 算法會優先比較節點類型是否相同。例如下面的代碼，div 與 span 屬於不同的節點類型，那麼就表示不是同一個節點。

<div>
  <Counter />
</div>

<span>
  <Counter />
</span>

然後會比較 props、state、context 等外部傳入的參數是否相同，從而判斷是否是同一個節點。當然，這裏還有一個重要的細節，對於性能優化至關重要。

由於在 React 中，props 的傳入都是通過類似於函數傳參的方式傳入，例如

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

前後兩次執行

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

這裏的細節就是，雖然兩次都入參都是 {a: 1}，但是他們是不同的內存地址，因此前後兩次 props 的比較結果始終爲 false

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

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

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

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

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

export default React.memo(Counter)

使用 memo 包裹之後，props 的比較規則變成了依次比較第一層 key 值所對應的值。例如，上面的案例中，包裹之前的比較方式爲

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

包裹之後的比較方式爲

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

因此，在特定的場景中，使用 memo 可以有效命中可複用節點。

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

// 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 && // 是否都爲註釋節點
        isDef(a.data) === isDef(b.data) && // 是否都定義了data
        sameInputType(a, b)  // 當標籤爲input時，type必須是否相同
      ) || (
        isTrue(a.isAsyncPlaceholder) && // 是否都有異步佔位符節點
        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 在節點是否相同的比較方式上時，就要明白 React 是強依賴於這個，但是 Vue 依賴較弱，因爲 Vue 的實現原理中更多的是通過依賴收集的方式來找到需要更新的節點，這也導致了 React 在這個上面的邏輯要更加複雜，Vue 則更加簡單。因此，我們需要對他們各自的原理背景有一定的瞭解。

最大的區別，在列表上的處理

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

因爲，一個簡單的移動，就很容易會造成整個組件被判定爲需要全部重新創建。所以，我們需要判斷出來節點是隻發生了移動，而不是需要重新創建。

給列表中的每一個節點，引入唯一 key 值，是他們都共同採用的技術手段。通過唯一 key 值，我們可以在舊列表中找到新列表的節點是否已經存在，從而決定是移動節點的位置還是創建新的節點。我們通常會在數組中設定一個 id 用於表示唯一 key 值。

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

需要注意的是，這裏的唯一 key 值，儘量不要使用遞增的數字序列來表示。

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

這個問題也是面試中經常會聊到的話題：爲什麼儘量不要使用 index 序列作爲 key。這是因爲當我們在列表中新增一個內容時，每一項的 index 每次都會發生變化，從而讓渲染結果出現混亂。

例如有一個數組爲  [a, b, c]，此時我們將 index 作爲 key 值，那麼數組項與 key 值的對應關係就是

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

此時，我們往數組頭部添加一個數據，這個時候數組變成了 [p, a, b, c]，然後再執行，數組項與 key 的對應關係就變成了

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

新增的項是 p，但是最終導致了數組項與 key 之間的對應關係錯亂，結果導致緩存的節點掛到了錯誤的數組項上去了。我們可以通過如下案例演示觀察在 UI 上的表現差別

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

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

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

React 的比較方式

首先，我們假定有一個已經渲染好的列表節點如下

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

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

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

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

在比較的過程中，lastIndex 的變化規則如下

lastIndex = max(index, lastIndex)

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

1、第一個目標項爲 P，我們會去舊列表中查詢是否存在相同的 key=P 的項。發現沒有，此時創建新節點

lastIndex = 0

[P]

2、第二個目標項爲 A，我們去舊列表中查詢是否存在相同的，發現有，此時 index = 0，可複用節點

當滿足條件 index < lastIndex 時，移動節點。此時 index = 0，lastIndex = 0，不滿足條件，不移動，此時結果爲

// 結果爲 0
lastIndex = max(index, lastIndex)

[P] [A]

注意：這裏說的移動節點，指的是對真實 DOM 的操作。

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

3、第三個目標項爲 B，我們去舊列表中查詢是否存在相同的 key，發現有，此時 index = 1，可複用節點

不滿足 index(1) < lastIndex(0)，不移動，結果爲

// 結果爲 1
lastIndex = max(index, lastIndex)

[P] [A] [B]

依次類推，最終我們發現，這種情況下，只需要創建一個新節點 P，不需要移動任何節點。

第二個案例

新舊列表節點如下

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

新的數據爲 [B, A, D, C]

1、第一個目標節點爲 B，發現在舊列表中存在相同 key，那麼複用節點，此時，index = 1，當前結果爲

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

lastIndex = max(index, lastIndex) // 1

[B]

2、第二個目標節點爲 A，發現在舊列表中存在相同 key，那麼複用節點，此時，index = 0，當前結果爲

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

lastIndex = max(index, lastIndex) // 1

[B] [A]

3、第三個目標節點爲 D，發現在舊列表中存在相同 key，那麼複用節點，此時，index = 3，當前結果爲

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

lastIndex = max(index, lastIndex) // 3

[B] [A] [D]

4、第四個目標節點爲 C，發現在舊列表中存在相同 key，那麼複用節點，此時，index = 2，當前結果爲

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

lastIndex = max(index, lastIndex) // 3

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

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

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

Vue 雙端比較

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

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

如果按照 React 的比較規則，此時由於第一個目標 D 的 index 爲 3，從一開始就變成了最大，因此，後續的 lastIndex 都爲 3，所有的目標項都會滿足 index < lastIndex，因此，真實 DOM 的移動就會執行 3 次。

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

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

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

以及對應的虛擬節點對象

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

比較的規則遵循：首 - 首比較，尾 - 尾比較，尾 - 首比較，首 - 尾比較的順序。通過這樣方式找出首尾是否有節點可以被複用。

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]

在首次經過四次比較之後，發現 新首 - 舊尾 key 值相同，可以複用，此時需要通過移動首尾索引指針構建新的新舊節點數組

// 發現複用節點，update
patch(oldEndVNode, newStartVNode, container)
// 移動
container.insertBefore(oldEndVNode.el, oldStartVNode.el)
// 更新索引指針
oldEndVNode = prevChildren[--oldEndIdx]
newStartVNode = nextChildren[++newStartIdx]

然後新的新舊數組爲

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

演變爲

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

得到新的新舊數組，繼續重複首 - 首比較，尾 - 尾比較，尾 - 首比較，首 - 尾比較。直到比較結束。

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

這裏需要特別注意的是，這樣的比較方式雖然快，但這是不充分比較，因此，在許多情況下，會導致節點存在複用，但是沒有找出來。因此，如果沒找到可複用的節點，比較還沒有結束，還有後續的邏輯。

我們構建一個新的案例，如下所示

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

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

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

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

移動之後，通過改變指針位置，再將新的雙端列表演變爲

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

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

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

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

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

先處理左側相同部分，再處理右側相同部分，鎖定可複用的節點之後，再針對中間亂序部分，採用最長遞增子序列的算法，計算出亂序部分可以複用的最長連續節點。通過這個遞增數組，我們就可以知道哪些節點在變化前後的相對位置沒有發生變化，哪些需要移動。

關於最長遞增子序列大家可以通過力扣的算法題了解。涉及到的動態規劃、二分、回朔等方式在評論都有大量的提到。他的目標依然是爲了減少真實 DOM 的移動次數

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

總結

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

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

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

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/D_Yh4uTRTa8QeDZHR8KkMw