React中的Diff演演算法你瞭解嗎

2022-03-14 10:00:40

一、Diff演演算法的作用

渲染真實DOM的開銷很大，有時候我們修改了某個資料，直接渲染到真實dom上會引起整個dom樹的重繪和重排。我們希望只更新我們修改的那一小塊dom，而不是整個dom，diff演演算法就幫我們實現了這點。

diff演演算法的本質就是：找出兩個物件之間的差異，目的是儘可能做到節點複用。

注：此處說到的物件，指的其實就是vue中的virtual dom（虛擬dom樹），即使用js物件來表示頁面中的dom結構。

二、React的Diff演演算法

1、什麼是調和？

將Virtual DOM樹轉換成Actual DOM樹的最少操作的過程稱為調和。

2、什麼是React diff演演算法？

diff演演算法是調和的具體實現。

3、diff策略

React用三大策略將O(n3)複雜度轉化為O(n)複雜度

(1)策略一（tree diff）：Web UI中DOM節點跨層級的移動操作特別少，可以忽略不計。

(2)策略二（component diff）：擁有相同類的兩個元件生成相似的樹形結構，擁有不同類的兩個元件生成不同的樹形結構。

(3)策略三（element diff）：對於同一層級的一組子節點，通過唯一id區分。

4、tree diff：

(1)React通過updateDepth對Virtual DOM樹進行層級控制。

(2)對樹分層比較，兩棵樹只對同一層次節點進行比較。如果該節點不存在時，則該節點及其子節點會被完全刪除，不會再進一步比較。

(3)只需遍歷一次，就能完成整棵DOM樹的比較。

如果DOM 節點出現了跨層級操作，Diff會怎麼辦？

答：Tree DIFF是對樹的每一層進行遍歷，如果某元件不存在了，則會直接銷燬。如圖所示，左邊是舊屬，右邊是新屬，第一層是R元件，一模一樣，不會發生變化；第二層進入Component DIFF，同一型別元件繼續比較下去，發現A元件沒有，所以直接刪掉A、B、C元件；繼續第三層，重新建立A、B、C元件。

如上圖所示，以A為根節點的整棵樹會被重新建立，而不是移動，因此官方建議不要進行DOM節點跨層級操作，可以通過CSS隱藏、顯示節點，而不是真正地移除、新增DOM節點。

5、component diff :

React對不同的元件間的比較，有三種策略

(1)同一型別的兩個元件，按原策略（層級比較）繼續比較Virtual DOM樹即可。

(2)同一型別的兩個元件，元件A變化為元件B時，可能Virtual DOM沒有任何變化，如果知道這點（變換的過程中，Virtual DOM沒有改變），可節省大量計算時間，所以使用者可以通過 shouldComponentUpdate() 來判斷是否需要判斷計算。

(3)不同型別的元件，將一個（將被改變的）元件判斷為dirtycomponent（髒元件），從而替換整個元件的所有節點。

注意：如上圖所示，當元件D變為元件G時，即使這兩個元件結構相似，一旦React判斷D和G是不用型別的元件，就不會比較兩者的結構，而是直接刪除元件D，重新建立元件G及其子節點。雖然當兩個元件是不同型別但結構相似時，進行diff演演算法分析會影響效能，但是畢竟不同型別的元件存在相似DOM樹的情況在實際開發過程中很少出現，因此這種極端因素很難在實際開發過程中造成重大影響。

6、element diff

當節點處於同一層級時，diff提供三種節點操作：刪除、插入、移動。

插入：元件 C 不在集合（A,B）中，需要插入

刪除：

(1)元件 D 在集合（A,B,D）中，但 D的節點已經更改，不能複用和更新，所以需要刪除舊的D ，再建立新的。

(2)元件D之前在集合（A,B,D）中，但集合變成新的集合（A,B）了，D 就需要被刪除。

移動：元件D已經在集合（A,B,C,D）裡了，且集合更新時，D沒有發生更新，只是位置改變，如新集合（A,D,B,C），D在第二個，無須像傳統diff，讓舊集合的第二個B和新集合的第二個D 比較，並且刪除第二個位置的B，再在第二個位置插入D，而是（對同一層級的同組子節點）新增唯一key進行區分，移動即可。

移動情形一：新舊集合中存在相同節點但位置不同時，如何移動節點

(1)B不移動，不贅述，更新l astIndex=1

(2)新集合取得 E，發現舊不存在，故在lastIndex=1的位置建立E，更新lastIndex=1

(3)新集合取得C，C不移動，更新lastIndex=2

(4)新集合取得A，A移動，同上，更新lastIndex=2

(5)新集合對比後，再對舊集合遍歷。判斷新集合沒有，但舊集合有的元素（如D，新集合沒有，舊集合有），發現 D，刪除D，diff操作結束。

React中Diff演演算法實現的程式碼：

_updateChildren: function(nextNestedChildrenElements, transaction, context) {
    var prevChildren = this._renderedChildren;
    var removedNodes = {};
    var mountImages = [];
    // 獲取新的子元素陣列
    var nextChildren = this._reconcilerUpdateChildren(
      prevChildren,
      nextNestedChildrenElements,
      mountImages,
      removedNodes,
      transaction,
      context
    );
    if (!nextChildren && !prevChildren) {
      return;
    }
    var updates = null;
    var name;
    var nextIndex = 0;
    var lastIndex = 0;
    var nextMountIndex = 0;
    var lastPlacedNode = null;
    for (name in nextChildren) {
      if (!nextChildren.hasOwnProperty(name)) {
        continue;
      }
      var prevChild = prevChildren && prevChildren[name];
      var nextChild = nextChildren[name];
      if (prevChild === nextChild) {
        // 同一個參照，說明是使用的同一個component,所以我們需要做移動的操作
        // 移動已有的子節點
        // NOTICE：這裡根據nextIndex, lastIndex決定是否移動
        updates = enqueue(
          updates,
          this.moveChild(prevChild, lastPlacedNode, nextIndex, lastIndex)
        );
        // 更新lastIndex
        lastIndex = Math.max(prevChild._mountIndex, lastIndex);
        // 更新component的.mountIndex屬性
        prevChild._mountIndex = nextIndex;
      } else {
        if (prevChild) {
          // 更新lastIndex
          lastIndex = Math.max(prevChild._mountIndex, lastIndex);
        }
        // 新增新的子節點在指定的位置上
        updates = enqueue(
          updates,
          this._mountChildAtIndex(
            nextChild,
            mountImages[nextMountIndex],
            lastPlacedNode,
            nextIndex,
            transaction,
            context
          )
        );
        nextMountIndex++;
      }
      // 更新nextIndex
      nextIndex++;
      lastPlacedNode = ReactReconciler.getHostNode(nextChild);
    }
    // 移除掉不存在的舊子節點，和舊子節點和新子節點不同的舊子節點
    for (name in removedNodes) {
      if (removedNodes.hasOwnProperty(name)) {
        updates = enqueue(
          updates,
          this._unmountChild(prevChildren[name], removedNodes[name])
        );
      }
    }
  }