摘要：對于同一層級的一組子節點，它們可以通過唯一進行區分。基于以上三個前提策略，分別對以及進行算法優化。鏈表的每一個節點是，而不是在之前的虛擬節點。是當前層的第一個節點。再次提醒，是的一層。

文章首發于個人博客

這是我 Deep In React 系列的第二篇文章，如果還沒有讀過的強烈建議你先讀第一篇：詳談 React Fiber 架構(1)。

我相信在看這篇文章的讀者一般都已經了解過 React 16 以前的 Diff 算法了，這個算法也算是 React 跨時代或者說最有影響力的一點了，使 React 在保持了可維護性的基礎上性能大大的提高，但 Diff 過程不僅不是免費的，而且對性能影響很大，有時候更新頁面的時候往往 Diff 所花的時間 js 運行時間比 Rendering 和 Painting 花費更多的時間，所以我一直傳達的觀念是 React 或者說框架的意義是為了提高代碼的可維護性，而不是為了提高性能的，現在所做的提升性能的操作，只是在可維護性的基礎上對性能的優化。具體可以參考我公眾號以前發的這兩篇文章：

別再說虛擬 DOM 快了，要被打臉的

深入理解虛擬 DOM，它真的不快

如果你對標題不滿意，請把文章看完，至少也得把文章最后的結論好好看下

在上一篇將 React Fiber 架構中，已經說到過，React 現在將整體的數據結構從樹改為了鏈表結構。所以相應的 Diff 算法也得改變，以為以前的 Diff 算法就是基于樹的。

老的 Diff 算法提出了三個策略來保證整體界面構建的性能，具體是：

Web UI 中 DOM 節點跨層級的移動操作特別少，可以忽略不計。

擁有相同類的兩個組件將會生成相似的樹形結構，擁有不同類的兩個組件將會生成不同的樹形結構。

對于同一層級的一組子節點，它們可以通過唯一 id 進行區分。

基于以上三個前提策略，React 分別對 tree diff、component diff 以及 element diff 進行算法優化。

具體老的算法可以見這篇文章：React 源碼剖析系列 － 不可思議的 react diff

說實話，老的 Diff 算法還是挺復雜的，你僅僅看上面這篇文章估計一時半會都不能理解，更別說看源碼了。對于 React 16 的 Diff 算法(我覺得都不能把它稱作算法，最多叫個 Diff 策略)其實還是蠻簡單的，React 16 是整個調度流程感覺比較難，我在前面將 Fiber 的文章已經簡單的梳理過了，后面也會慢慢的逐個攻破。

接下來就開始正式的講解 React 16 的 Diff 策略吧！

做 Diff 的目的就是為了復用節點。

鏈表的每一個節點是 Fiber，而不是在 16 之前的虛擬DOM 節點。

我這里說的虛擬 DOM 節點是指 React.createElement 方法所產生的節點。虛擬 DOM tree 只維護了組件狀態以及組件與 DOM 樹的關系，Fiber Node 承載的東西比 虛擬 DOM 節點多很多。

Diff 就是新舊節點的對比，在上一篇中也說道了，這里面的 Diff 主要是構建 currentInWorkProgress 的過程，同時得到 Effect List，給下一個階段 commit 做準備。

React16 的 diff 策略采用從鏈表頭部開始比較的算法，是層次遍歷，算法是建立在一個節點的插入、刪除、移動等操作都是在節點樹的同一層級中進行的。

對于 Diff， 新老節點的對比，我們以新節點為標準，然后來構建整個 currentInWorkProgress，對于新的 children 會有四種情況。

TextNode(包含字符串和數字)

單個 React Element(通過該節點是否有 $$typeof 區分)

數組

可迭代的 children，跟數組的處理方式差不多

那么我們就來一步一步的看這四種類型是如何進行 diff 的。

這篇文章主要是從 React 的源碼的邏輯出發介紹的，所以介紹之前了解下只怎么進入到這個 diff 函數的，react 的 diff 算法是從 reconcileChildren 開始的

export function reconcileChildren(
  current: Fiber | null,
  workInProgress: Fiber,
  nextChildren: any,
  renderExpirationTime: ExpirationTime,
) {
  if (current === null) {
    workInProgress.child = mountChildFibers(
      workInProgress,
      null,
      nextChildren,
      renderExpirationTime,
    );
  } else {
    workInProgress.child = reconcileChildFibers(
      workInProgress,
      current.child,
      nextChildren,
      renderExpirationTime,
    );
  }
}

reconcileChildren 只是一個入口函數，如果首次渲染，current 空 null，就通過 mountChildFibers 創建子節點的 Fiber 實例。如果不是首次渲染，就調用 reconcileChildFibers去做 diff，然后得出 effect list。

接下來再看看 mountChildFibers 和 reconcileChildFibers 有什么區別：

export const reconcileChildFibers = ChildReconciler(true);
export const mountChildFibers = ChildReconciler(false);

他們都是通過 ChildReconciler 函數來的，只是傳遞的參數不同而已。這個參數叫shouldTrackSideEffects，他的作用是判斷是否要增加一些effectTag，主要是用來優化初次渲染的，因為初次渲染沒有更新操作。

function reconcileChildFibers(
  returnFiber: Fiber,
  currentFirstChild: Fiber | null,
  newChild: any,
  expirationTime: ExpirationTime,
): Fiber | null {
  // 主要的 Diff 邏輯
}

reconcileChildFibers 就是 Diff 部分的主體代碼，這個函數超級長，是一個包裝函數，下面所有的 diff 代碼都在這里面，詳細的源碼注釋可以見這里。

參數介紹

returnFiber 是即將 Diff 的這層的父節點。

currentFirstChild是當前層的第一個 Fiber 節點。

newChild 是即將更新的 vdom 節點(可能是 TextNode、可能是 ReactElement，可能是數組)，不是 Fiber 節點

expirationTime 是過期時間，這個參數是跟調度有關系的，本系列還沒講解，當然跟 Diff 也沒有關系。

再次提醒，reconcileChildFibers 是 reconcile(diff) 的一層。

前置知識介紹完畢，就開始詳細介紹每一種節點是如何進行 Diff 的。

首先看 TextNode，因為它是最簡單的，擔心直接看到難的，然后就打擊你的信心。

看下面兩個小 demo：

// demo1：當前 ui 對應的節點的 jsx
return (
  

  // ...
      

          
          
      
  //...
    
)

// demo2：更新成功后的節點對應的 jsx

return (
  

  // ...
      

          前端桃園
      
  //...
    
)

對應的單鏈表結構圖：

對于 diff TextNode 會有兩種情況。

currentFirstNode 是 TextNode

currentFirstNode 不是 TextNode

currentFirstNode 是當前該層的第一個節點，reconcileChildFibers 傳進來的參數。

為什么要分兩種情況呢？原因就是為了復用節點

第一種情況。xxx 是一個 TextNode，那么就代表這這個節點可以復用，有復用的節點，對性能優化很有幫助。既然新的 child 只有一個 TextNode，那么復用節點之后，就把剩下的 aaa 節點就可以刪掉了，那么 div 的 child 就可以添加到 workInProgress 中去了。

源碼如下：

if (currentFirstChild !== null && currentFirstChild.tag === HostText) {
      // We already have an existing node so let"s just update it and delete
      // the rest.
      deleteRemainingChildren(returnFiber, currentFirstChild.sibling);
      const existing = useFiber(currentFirstChild, textContent, expirationTime);
      existing.return = returnFiber;
      return existing;
}

在源碼里 useFiber 就是復用節點的方法，deleteRemainingChildren 就是刪除剩余節點的方法，這里是從 currentFirstChild.sibling 開始刪除的。

第二種情況。xxx 不是一個 TextNode，那么就代表這個節點不能復用，所以就從 currentFirstChild開始刪掉剩余的節點，對應到上面的圖中就是刪除掉 xxx 節點和 aaa 節點。

對于源碼如下：

deleteRemainingChildren(returnFiber, currentFirstChild);
const created = createFiberFromText(
    textContent,
    returnFiber.mode,
    expirationTime,
);
created.return = returnFiber;

其中 createFiberFromText 就是根據 textContent 來創建節點的方法。

注意：刪除節點不會真的從鏈表里面把節點刪除，只是打一個 delete 的 tag，當 commit 的時候才會真正的去刪除。

有了上面 TextNode 的 Diff 經驗，那么來理解 React Element 的 Diff 就比較簡單了，因為他們的思路是一致的：先找有沒有可以復用的節點，如果沒有就另外創建一個。

那么就有一個問題，如何判斷這個節點是否可以復用呢？

有兩個點：1. key 相同。 2. 節點的類型相同。

如果以上兩點相同，就代表這個節點只是變化了內容，不需要創建新的節點，可以復用的。

對應的源碼如下：

if (child.key === key) {
  if (
    child.tag === Fragment
    ? element.type === REACT_FRAGMENT_TYPE
    : child.elementType === element.type
  ) {
    // 為什么要刪除老的節點的兄弟節點？
    // 因為當前節點是只有一個節點，而老的如果是有兄弟節點是要刪除的，是多于的。刪掉了之后就可以復用老的節點了
    deleteRemainingChildren(returnFiber, child.sibling);
    // 復用當前節點
    const existing = useFiber(
      child,
      element.type === REACT_FRAGMENT_TYPE
      ? element.props.children
      : element.props,
      expirationTime,
    );
    existing.ref = coerceRef(returnFiber, child, element);
    existing.return = returnFiber;
    return existing;
}

相信這些代碼都很好理解了，除了判斷條件跟前面 TextNode 的判斷條件不一樣，其余的基本都一樣，只是 React Element 多了一個跟新 ref 的過程。

同樣，如果節點的類型不相同，就將節點從當前節點開始把剩余的都刪除。

deleteRemainingChildren(returnFiber, child);

到這里，可能你們就會覺得接下來應該就是講解當沒有可以復用的節點的時候是如果創建節點的。

不過可惜你們猜錯了。因為 Facebook 的工程師很厲害，另外還做了一個工作來優化，來找到復用的節點。

我們現在來看這種情況：

這種情況就是有可能更新的時候刪除了一個節點，但是另外的節點還留著。

那么在對比 xxx 節點和 AAA 節點的時候，它們的節點類型是不一樣，按照我們上面的邏輯，還是應該把 xxx 和 AAA 節點刪除，然后創建一個 AAA 節點。

但是你看，明明 xxx 的 slibling 有一個 AAA 節點可以復用，但是被刪了，多浪費呀。所以還有另外有一個策略來找 xxx 的所有兄弟節點中有沒有可以復用的節點。

這種策略就是從 div 下面的所有子節點去找有沒有可以復用的節點，而不是像 TextNode 一樣，只是找第一個 child 是否可以復用，如果當前節點的 key 不同，就代表肯定不是同一個節點，所以把當前節點刪除，然后再去找當前節點的兄弟節點，直到找到 key 相同，并且節點的類型相同，否則就刪除所有的子節點。

你有木有這樣的問題：為什么 TextNode 不采用這樣的循環策略來找可以復用的節點呢？這個問題留給你思考，歡迎在評論區留下你的答案。

對應的源碼邏輯如下：

// 找到 key 相同的節點，就會復用當前節點
while (child !== null) {
  if (child.key === key) {
    if (
      child.tag === Fragment
      ? element.type === REACT_FRAGMENT_TYPE
      : child.elementType === element.type
    ) {
      // 復用節點邏輯，省略該部分代碼，和上面復用節點的代碼相同
      // code ...
      return existing;
    } else {
      deleteRemainingChildren(returnFiber, child);
      break;
    }
  } else {
    // 如果沒有可以復用的節點，就把這個節點刪除
    deleteChild(returnFiber, child);
  }
  child = child.sibling;
}

在上面這段代碼我們需要注意的是，當 key 相同，React 會認為是同一個節點，所以當 key 相同，節點類型不同的時候，React 會認為你已經把這個節點重新覆蓋了，所以就不會再去找剩余的節點是否可以復用。只有在 key 不同的時候，才會去找兄弟節點是否可以復用。

接下來才是我們前面說的，如果沒有找到可以復用的節點，然后就重新創建節點，源碼如下：

// 前面的循環已經把該刪除的已經刪除了，接下來就開始創建新的節點了
if (element.type === REACT_FRAGMENT_TYPE) {
  const created = createFiberFromFragment(
    element.props.children,
    returnFiber.mode,
    expirationTime,
    element.key,
  );
  created.return = returnFiber;
  return created;
} else {
  const created = createFiberFromElement(
    element,
    returnFiber.mode,
    expirationTime,
  );
  created.ref = coerceRef(returnFiber, currentFirstChild, element);
  created.return = returnFiber;
  return created;
}

對于 Fragment 節點和一般的 Element 節點創建的方式不同，因為 Fragment 本來就是一個無意義的節點，他真正需要創建 Fiber 的是它的 children，而不是它自己，所以 createFiberFromFragment 傳遞的不是 element ，而是 element.props.children。

Diff Array 算是 Diff 中最難的一部分了，比較的復雜，因為做了很多的優化，不過請你放心，認真看完我的講解，最難的也會很容易理解，廢話不多說，開始吧！

因為 Fiber 樹是單鏈表結構，沒有子節點數組這樣的數據結構，也就沒有可以供兩端同時比較的尾部游標。所以React的這個算法是一個簡化的兩端比較法，只從頭部開始比較。

前面已經說了，Diff 的目的就是為了復用，對于 Array 就不能像之前的節點那樣，僅僅對比一下元素的 key 或者 元素類型就行，因為數組里面是好多個元素。你可以在頭腦里思考兩分鐘如何進行復用節點，再看 React 是怎么做的，然后對比一下孰優孰劣。

相同位置進行對比，這個是比較容易想到的一種方式，還是舉個例子加深一下印象。

這已經是一個非常簡單的例子了，div 的 child 是一個數組，有 AAA、BBB 然后還有其他的兄弟節點，在做 diff 的時候就可以從新舊的數組中按照索引一一對比，如果可以復用，就把這個節點從老的鏈表里面刪除，不能復用的話再進行其他的復用策略。

那如果判斷節點是否可以復用呢？有了前面的 ReactElement 和 TextNode 復用的經驗，這個也類似，因為是一一對比嘛，相當于是一個節點一個節點的對比。

不過對于 newChild 可能會有很多種類型，簡單的看下源碼是如何進行判斷的。

 const key = oldFiber !== null ? oldFiber.key : null;

前面的經驗可得，判斷是否可以復用，常常會根據 key 是否相同來決定，所以首先獲取了老節點的 key 是否存在。如果不存在老節點很可能是 TextNode 或者是 Fragment。

接下來再看 newChild 為不同類型的時候是如何進行處理的。

當 newChild 是 TextNode 的時候

if (typeof newChild === "string" || typeof newChild === "number") {
  // 對于新的節點如果是 string 或者 number，那么都是沒有 key 的，
  // 所有如果老的節點有 key 的話，就不能復用，直接返回 null。
  // 老的節點 key 為 null 的話，代表老的節點是文本節點，就可以復用
  if (key !== null) {
    return null;
  }

  return updateTextNode(
    returnFiber,
    oldFiber,
    "" + newChild,
    expirationTime,
  );
}

如果 key 不為 null，那么就代表老節點不是 TextNode，而新節點又是 TextNode，所以返回 null，不能復用，反之則可以復用，調用 updateTextNode 方法。

注意，updateTextNode 里面包含了首次渲染的時候的邏輯，首次渲染的時候回插入一個 TextNode，而不是復用。

當 newChild 是 Object 的時候

newChild 是 Object 的時候基本上走的就是 ReactElement 的邏輯了，判斷 key 和 元素的類型是否相等來判斷是否可以復用。

if (typeof newChild === "object" && newChild !== null) {
  // 有 $$typeof 代表就是 ReactElement
  switch (newChild.$$typeof) {
    case REACT_ELEMENT_TYPE: {
                // ReactElement 的邏輯 
    }
    case REACT_PORTAL_TYPE: {
                // 調用 updatePortal
    }
  }

  if (isArray(newChild) || getIteratorFn(newChild)) {
    if (key !== null) {
      return null;
    }

    return updateFragment(
      returnFiber,
      oldFiber,
      newChild,
      expirationTime,
      null,
    );
  }
}

首先判斷是否是對象，用的是 typeof newChild === "object" && newChild !== null ，注意要加 !== null，因為 typeof null 也是 object。

然后通過 $$typeof 判斷是 REACT_ELEMENT_TYPE 還是 REACT_PORTAL_TYPE，分別調用不同的復用邏輯，然后由于數組也是 Object ，所以這個 if 里面也有數組的復用邏輯。

我相信到這里應該對于應該對于如何相同位置的節點如何對比有清晰的認識了。另外還有問題，那就是如何循環一個一個對比呢？

這里要注意，新的節點的 children 是虛擬 DOM，所以這個 children 是一個數組，而對于之前提到的老的節點樹是鏈表。

那么循環一個一個對比，就是遍歷數組的過程。

let newIdx = 0 // 新數組的索引
for (; oldFiber !== null && newIdx < newChildren.length; newIdx++) {
  // 遍歷老的節點
  nextOldFiber = oldFiber.sibling; 
  // 返回復用節點的函數，newFiber 就是復用的節點。
  // 如果為空，就代表同位置對比已經不能復用了，循環結束。
  const newFiber = updateSlot(
    returnFiber,
    oldFiber,
    newChildren[newIdx],
    expirationTime,
  );
  
  if (newFiber === null) {
    break;
  }
  
  // 其他 code，比如刪除復用的節點
}

這并不是源碼的全部源碼，我只是把思路給貼出來了。

這是第一次遍歷新數組，通過調用 updateSlot 來對比新老元素，前面介紹的如何對比新老節點的代碼都是在這個函數里。這個循環會把所以的從前面開始能復用的節點，都復用到。比如上面我們畫的圖，如果兩個鏈表里面的 ？？？節點，不相同，那么 newFiber 為 null，這個循環就會跳出。

跳出來了，就會有兩種情況。

新節點已經遍歷完畢

老節點已經遍歷完畢

如果新節點已經遍歷完畢的話，也就是沒有要更新的了，這種情況一般就是從原來的數組里面刪除了元素，那么直接把剩下的老節點刪除了就行了。還是拿上面的圖的例子舉例，老的鏈表里？？？還有很多節點，而新的鏈表？？？已經沒有節點了，所以老的鏈表？？？不管是有多少節點，都不能復用了，所以沒用了，直接刪除。

if (newIdx === newChildren.length) {
  // 新的 children 長度已經夠了，所以把剩下的刪除掉
  deleteRemainingChildren(returnFiber, oldFiber);
  return resultingFirstChild;
}

注意這里是直接 return 了哦，沒有繼續往下執行了。

如果老的節點在第一次循環的時候就被復用完了，新的節點還有，很有可能就是新增了節點的情況。那么這個時候只需要根據把剩余新的節點直接創建 Fiber 就行了。

if (oldFiber === null) {
  // 如果老的節點已經被復用完了，對剩下的新節點進行操作
  for (; newIdx < newChildren.length; newIdx++) {
    const newFiber = createChild(
      returnFiber,
      newChildren[newIdx],
      expirationTime,
    );
  }
  return resultingFirstChild;
}

oldFiber === null 就是用來判斷老的 Fiber 節點變量完了的代碼，Fiber 鏈表是一個單向鏈表，所以為 null 的時候代表已經結束了。所以就直接把剩余的 newChild 通過循環創建 Fiber。

到這里，目前簡單的對數組進行增、刪節點的對比還是比較簡單，接下來就是移動的情況是如何進行復用的呢？

對于移動的情況，首先要思考，怎么能判斷數組是否發生過移動操作呢？

如果給你兩個數組，你是否能判斷出來數組是否發生過移動。

答案是：老的數組和新的數組里面都有這個元素，而且位置不相同。

從兩個數組中找到相同元素(是指可復用的節點)，方法有很多種，來看看 React 是如何高效的找出來的。

把所有老數組元素按 key 或者是 index 放 Map 里，然后遍歷新數組，根據新數組的 key 或者 index 快速找到老數組里面是否有可復用的。

function mapRemainingChildren(
 returnFiber: Fiber,
 currentFirstChild: Fiber,
): Map {
  const existingChildren: Map = new Map();

  let existingChild = currentFirstChild; // currentFirstChild 是老數組鏈表的第一個元素
  while (existingChild !== null) {
  // 看到這里可能會疑惑怎么在 Map 里面的key 是 fiber 的key 還是 fiber 的 index 呢？
  // 我覺得是根據數據類型，fiber 的key 是字符串，而 index 是數字，這樣就能區分了
  // 所以這里是用的 map，而不是對象，如果是對象的key 就不能區分 字符串類型和數字類型了。
    if (existingChild.key !== null) {
      existingChildren.set(existingChild.key, existingChild);
    } else {
      existingChildren.set(existingChild.index, existingChild);
    }
    existingChild = existingChild.sibling;
    }
    return existingChildren;
}

這個 mapRemainingChildren 就是將老數組存放到 Map 里面。元素有 key 就 Map 的鍵就存 key，沒有 key 就存 index，key 一定是字符串，index 一定是 number，所以取的時候是能區分的，所以這里用的是 Map，而不是對象，如果是對象，屬性是字符串，就沒辦法區別是 key 還是 index 了。

現在有了這個 Map，剩下的就是循環新數組，找到 Map 里面可以復用的節點，如果找不到就創建，這個邏輯基本上跟 updateSlot 的復用邏輯很像，一個是從老數組鏈表中獲取節點對比，一個是從 Map 里獲取節點對比。

// 如果前面的算法有復用，那么 newIdx 就不從 0 開始
for (; newIdx < newChildren.length; newIdx++) {
  const newFiber = updateFromMap(
    existingChildren,
    returnFiber,
    newIdx,
    newChildren[newIdx],
    expirationTime,
  );
 // 省略刪除 existingChildren 中的元素和添加 Placement 副作用的情況
}

到這里新數組遍歷完畢，也就是同一層的 Diff 過程完畢，接下來進行總結一下。

以下效果動態演示來自于文章：React Diff 源碼分析，我覺得這個演示非常的形象，有助于理解。

這里渲染一個可輸入的數組。

當第一種情況，新數組遍歷完了，老數組剩余直接刪除（12345→1234 刪除 5）：

新數組沒完，老數組完了（1234→1234567 插入 567）：

移動的情況，即之前就存在這個元素，后續只是順序改變（123 → 4321 插入4，移動2 1）：

最后刪除沒有涉及的元素。

對于數組的 diff 策略，相對比較復雜，最后來梳理一下這個策略，其實還是很簡單，只是看源碼的時候比較難懂。

我們可以把整個過程分為三個階段：

第一遍歷新數組，新老數組相同 index 進行對比，通過 updateSlot方法找到可以復用的節點，直到找到不可以復用的節點就退出循環。

第一遍歷完之后，刪除剩余的老節點，追加剩余的新節點的過程。如果是新節點已遍歷完成，就將剩余的老節點批量刪除；如果是老節點遍歷完成仍有新節點剩余，則將新節點直接插入。

把所有老數組元素按 key 或 index 放 Map 里，然后遍歷新數組，插入老數組的元素，這是移動的情況。

剛開始閱讀源碼的過程是非常的痛苦的，但是當你一遍一遍的把作者想要表達的理解了，為什么要這么寫 理解了，會感到作者的設計是如此的精妙絕倫，每一個變量，每一行代碼感覺都是精心設計過的，然后感受到自己與大牛的差距，激發自己的動力。

更多的對于 React 原理相關，源碼相關的內容，請關注我的 github：Deep In React 或者 個人博客：桃園

我是桃翁，一個愛思考的前端er，想了解關于更多的前端相關的，請關注我的公號：「前端桃園」