react diff 算法

diff 算法作為 Virtual DOM 的加速器，其算法的改進優化是 React 整個界面渲染的基礎和性能的保障，同時也是 React 源碼中最神秘的，最不可思議的部分

diff 算法會幫助我們就算出 VirtualDOM 中真正變化的部分，并只針對該部分進行原生 DOM 操作，而不是渲染整個頁面。從而保證了每次操作更新后頁面的高效渲染

一、傳統算法

計算一棵樹形結構轉換為另一棵樹形結構需要最少步驟，如果使用傳統的 diff 算法通過循環遞歸遍歷節點進行對比，其復雜度要達到 O(n^3)，其中 n 是樹中節點總數，效率十分低下，假設我們要展示 1000 個節點，那么我們就要依次執行上十億次的比較

1. 核心代碼

// 差異比較函數，比較兩個樹的葉子節點
const diffLeafs = (beforeLeaf, afterLeaf) => {// 用于存放差異比較結果的數組let res = [];// 獲取較大節點樹的長度const count = Math.max(beforeLeaf.children.length, afterLeaf.children.length);// 循環遍歷節點for (let i = 0; i < count; i++) {const beforeTag = beforeLeaf.children[i];const afterTag = afterLeaf.children[i];if (beforeTag === undefined) {// 添加 afterTag 節點res.push({ type: 'add', element: afterTag });} else if (afterTag === undefined) {// 刪除 beforeTag 節點res.push({ type: 'remove', element: beforeTag });} else if (beforeTag.tagName !== afterTag.tagName) {// 節點名改變時，刪除 beforeTag 節點，添加 afterTag 節點res.push({ type: 'remove', element: beforeTag });res.push({ type: 'add', element: afterTag });} else if (beforeTag.innerHTML !== afterTag.innerHTML) {if (beforeTag.children.length === 0) {// 內容改變時，不再有子節點，直接標記為內容改變res.push({type: 'changed',beforeElement: beforeTag,afterElement: afterTag,HTML: afterTag.innerHTML,});} else {// 遞歸比較子節點res = res.concat(diffLeafs(beforeTag, afterTag));}}}return res; // 返回差異比較結果數組
};

2. 使用

// 創建兩棵樹的結構
const beforeTree = {tagName: 'div',children: [{tagName: 'h1',innerHTML: 'Hello, World!',},{tagName: 'p',innerHTML: 'This is a sample text.',},],
};const afterTree = {tagName: 'div',children: [{tagName: 'h1',innerHTML: 'Hello, Universe!', // 改變內容},{tagName: 'p',innerHTML: 'This is a sample text.',},{tagName: 'a', // 添加節點innerHTML: 'Learn More',},],
};// 運行差異比較函數
const differences = diffLeafs(beforeTree, afterTree);// 輸出差異比較結果
console.log(differences);

二、算法實現

React 將 Virtual DOM 樹轉換為 Actual DOM 的最少操作過程稱為調和（Reconciliation），diff 算法便是調和的具體實現。

React 通過制定大膽的策略，將 O(n^3) 復雜度的問題轉換成 O(n) 復雜度的問題。

首先需要明確，只有 React 更新階段才會有 diff 算法的運用

三、算法策略

Web UI 中 DOM 節點跨層級的移動操作特別少，可以忽略不計
擁有相同類的兩個組件將會生成相似的樹形結構，擁有不同類的兩個組件將會生成不同的樹形結構。
對于同一層級的一組子節點，它們可以通過 UUID（key）進行區分。

基于以上三個前提策略，React 分別對 Tree Diff、Component Diff、Element Diff 進行算法優化，事實也證明這三個前提策略是合理且準確的，它保證了整體界面構建的性能

四、算法粒度

1. Tree Diff

Tree Diff 即對樹進行逐層對比的過程，兩棵樹只會對同層次的節點進行比較。

既然 WebUI 中的 DOM 節點跨層級的移動操作少到可以忽略不計，針對這一現象，React 通過 updateDepth 對 Virtual DOM 樹進行層級控制，只會對相同顏色方框內的 DOM 節點進行比較，即同一個父節點下的所有子節點。當發現節點已經不存在，則該節點及其子節點會被完全刪除掉，不會用于進一步的比較。這樣只需要對樹進行一次遍歷，便能完成整個 DOM 樹的比較

1.1. 原理

如下圖所示，A 節點（包括其子節點）被整個移動到 D 節點下面去，由于 React 只會簡單的考慮同級節點的位置變換，而對于不同層級的節點，只有創建和刪除操作，所以當根節點發現 A 節點消失了，就會刪除 A 節點及其子節點，當 D 發現多了一個子節點 A，就會創建新的 A 作為其子節點。

此時，diff 算法的執行情況是：create A => create B => create C => delete A

由此可見，當出現節點跨層級的移動時，并不會出現想象中移動操作，而是會進行刪除，重新創建的動作，這是一種很影響 React 性能的操作。因此 React 官方也不建議進行 DOM 節點跨層級的操作

提示：在開發組件時，保持穩定的 DOM 結構會有助于性能的提升。例如，可以通過 CSS 隱藏或顯示節點，而不是真的移除或添加 DOM 節點。

2. Component Diff

在進行 Tree Diff 過程中，每層組件級別的對比，叫做 Component Diff。

如果對比前后，組件的類型相同，則按照原策略繼續進行 Virtual DOM 比較
如果對比前后，組件的類型不相同，則需要移除舊組件，創建新組件，并追加到頁面上

如果是同類型的組件，有可能經過一輪 Virtual DOM 比較下來，并沒有發生變化。如果我們能夠提前確切知道這一點，那么就可以省下大量的 diff 運算時間。因此，React 允許用戶通過 shouldComponentUpdate 來判斷該組件是否需要進行 diff 算法分析

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

3. Element Diff

在進行組件對比的時候，如果兩個組件類型相同，則需要進行元素級別的對比，這叫做 Element Diff。

Element Diff 對應三種節點操作，分別為 INSERT_MARKUP（插入）、MOVE_EXISTING（移動） 和 REMOVE_NODE（刪除）。

INSERT_MARKUP：新的組件類型不在舊集合中，即全新的節點，需要對新節點進行插入操作。
MOVE_EXISTING：舊集合中有新組件類型，且 element 是可更新的類型，generateComponent 已調用 recevieComponent，這種情況下 prevChild = nextChild，這時候就需要做移動操作，可以復用以前的 DOM 節點。
REMOVE_NODE：舊組件類型，在新集合里也有，但對應的 element 不同則不能直接復用和更新，需要執行刪除操作，或者舊組件不在新集合里的，也需要執行刪除操作。

如下圖，老集合中包含節點：A、B、C、D，更新后的新集合中包含節點：B、A、D、C，此時新老集合進行 diff 差異化對比，發現 B != A，則創建并插入 B 至新集合，刪除老集合 A；以此類推，創建并插入 A、D 和 C，刪除 B、C 和 D

React 發現這類操作繁瑣冗余，因為這些都是相同的節點，但由于位置發生變化，導致需要進行繁雜低效的刪除、創建操作，其實只要對這些節點進行位置移動即可。

針對這種情況，React 提出優化策略：允許開發者對同一層級的同組子節點，添加唯一 key 進行區分，雖然只是小小的改動，性能上卻發生了翻天覆地的變化。

新老集合所包含的節點，如下圖所示，新老集合進行 diff 差異化對比，通過 key 發現新老集合中的節點都是相同的節點，因此無需進行節點刪除和創建，只需要將老集合中節點的位置進行移動，更新為新集合中節點的位置，此時 React 給出的 diff 結果為：B、D 不做任何操作，A、C 進行移動操作，即可

那么，如此高效的 diff 到底是如何運作的呢？讓我們通過源碼進行詳細分析。

先搞清楚 3 個 index 索引：

nextId：遍歷 nextChildren 時候的 index，每遍歷一個元素加 1

lastIndex：默認為 0，表示上次從 prevChildren 中取出元素時，這個元素在 prevChildren 中的 index

_mountIndex：元素在數組中的位置

4. element diff 邏輯概括

首先對新集合的節點進行循環遍歷，for (name in nextChildren)，通過唯一 key 可以判斷新老集合中是否存在相同的節點，if (prevChild === nextChild)。

如果存在相同節點，則進行移動操作，但在移動前需要將當前節點在老集合中的位置與 lastIndex 進行比較，if (child._mountIndex < lastIndex)，則進行節點移動操作，否則不執行該操作。

這是一種順序優化手段，lastIndex 一直在更新，表示訪問過的節點在老集合中最右的位置（即最大的位置），如果新集合中當前訪問的節點比 lastIndex 大，說明當前訪問節點在老集合中就比上一個節點位置靠后，則該節點不會影響其他節點的位置，因此不用添加到差異隊列中，即不執行移動操作，只有當訪問的節點比 lastIndex 小時，才需要進行移動操作

5. element diff 差異對比過程

以上圖為例，可以更為清晰直觀的描述 diff 的差異對比過程：

從新集合中取得 B，判斷老集合中存在相同節點 B，通過對比節點位置判斷是否進行移動操作

- 判斷過程：B 在老集合中的位置 B._mountIndex = 1，此時 lastIndex = 0(首次遍歷時默認為 0)，不滿足child._mountIndex < lastIndex 的條件，因此不對 B 進行移動操作
- 更新索引：更新 lastIndex = Math.max(prevChild._mountIndex, lastIndex)，其中 prevChild._mountIndex 表示 B 在老集合中的位置，則 lastIndex ＝ 1，并將 B 的位置更新為新集合中的位置 prevChild._mountIndex = nextIndex，此時新集合中 B._mountIndex = 0，nextIndex++ 進入下一個節點的判斷。

從新集合中取得 A，判斷老集合中存在相同節點 A，通過對比節點位置判斷是否進行移動操作

- 判斷過程：A 在老集合中的位置 A._mountIndex = 0，此時 lastIndex = 1，滿足 child._mountIndex < lastIndex 的條件，因此對 A 進行移動操作 enqueueMove(this, child._mountIndex, toIndex)，其中 toIndex 其實就是 nextIndex，表示 A 需要移動到的位置
- 更新索引：更新 lastIndex = Math.max(prevChild._mountIndex, lastIndex)，則 lastIndex ＝ 1，并將 A 的位置更新為新集合中的位置 prevChild._mountIndex = nextIndex，此時新集合中 A._mountIndex = 1，nextIndex++ 進入下一個節點的判斷。

從新集合中取得 D，判斷老集合中存在相同節點 D，通過對比節點位置判斷是否進行移動操作

- 判斷過程：D 在老集合中的位置 D._mountIndex = 3，此時 lastIndex = 1，不滿足 child._mountIndex < lastIndex 的條件，因此不對 D 進行移動操作
- 更新索引：更新 lastIndex = Math.max(prevChild._mountIndex, lastIndex)，則 lastIndex ＝ 3，并將 D 的位置更新為新集合中的位置 prevChild._mountIndex = nextIndex，此時新集合中 D._mountIndex = 2，nextIndex++ 進入下一個節點的判斷。

從新集合中取得 C，判斷老集合中存在相同節點 C，通過對比節點位置判斷是否進行移動操作

- 判斷過程：C 在老集合中的位置 C._mountIndex = 2，此時 lastIndex = 3，滿足 child._mountIndex < lastIndex 的條件，因此對 C 進行移動操作 enqueueMove(this, child._mountIndex, toIndex)
- 更新索引：更新 lastIndex = Math.max(prevChild._mountIndex, lastIndex)，則 lastIndex ＝ 3，并將 C 的位置更新為新集合中的位置 prevChild._mountIndex = nextIndex，此時新集合中 C._mountIndex = 3，nextIndex++ 進入下一個節點的判斷，由于 C 已經是最后一個節點，因此 diff 到此完成

6. 算法源碼

_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，需要進行移動操作// 移動已有的子節點// 注意：這里根據nextIndex, lastIndex決定是否移動updates = enqueue(updates,this.moveChild(prevChild, lastPlacedNode, nextIndex, lastIndex));// 更新lastIndexlastIndex = Math.max(prevChild._mountIndex, lastIndex);// 更新component的.mountIndex屬性prevChild._mountIndex = nextIndex;} else {if (prevChild) {// 更新lastIndexlastIndex = Math.max(prevChild._mountIndex, lastIndex);}// 添加新的子節點在指定的位置上updates = enqueue(updates,this._mountChildAtIndex(nextChild,mountImages[nextMountIndex],lastPlacedNode,nextIndex,transaction,context));nextMountIndex++;}// 更新nextIndexnextIndex++;lastPlacedNode = ReactReconciler.getHostNode(nextChild);}// 移除掉不存在的舊子節點，和舊子節點和新子節點不同的舊子節點for (name in removedNodes) {if (removedNodes.hasOwnProperty(name)) {updates = enqueue(updates,this._unmountChild(prevChildren[name], removedNodes[name]));}}
}

五、更新渲染

1. 合并操作

當調用 component 的 setState 方法的時候，React 將其標記為 dirty，到每一個事件循環結束，React 檢查所有標記 dirty 的 component 重新繪制。

這里的合并操作是指，在一個事件循環當中，DOM 只會被更新一次，這個特性是構建高性能應用的關鍵，而且用通常的 JavaScript 代碼難以實現，而在 React 應用里，你默認就能實現

2. 子樹渲染

調用 setState 方法時，component 會重新構建包括子節點的 Virtual DOM。如果你在根節點調用 setState，整個 React 的應用都會被重新渲染。所有的 component 即便沒有更新，都會調用他們的 render 方法。這個聽起來可怕，性能貌似很低，但實際上我們不會觸碰真實的 DOM，運行起來沒那樣的問題。

首先，我們討論的是展示用戶界面。因為屏幕空間有限，通常你需要一次渲染成百上千條指令，JavaScript 對于能處理的整個界面，在業務路基上已經足夠快了。

令一點，在寫 React 代碼時，每當有數據更新，你不是都調用根節點的 setState。你會在需要接收對應更新的 component 上調用，或者在上面的幾個 component。你很少要一直在根節點上，就是說界面更新只出現在用戶產生交互的局部

3. 選擇性子樹渲染

最后，你還有可能去掉一些子樹的重新渲染。如果你在 component 上實現以下方法的話：

boolean shouldComponentUpdate(object nextProps, object nextState)

根據 component 的前一個和下一個 props/state，你可以告訴 React 這個 component 沒有更新，也不需要重新繪制，實現得好的話，可以帶來巨大的性能提升。

要用這個方法，你要能夠對 JavaScript Object 進行比對，這樣有很多細節的因素，比

如對比應該是深度的還是淺層的。如果要深的，我們是用不可變數結構，還是進行深度拷貝。

而且你要注意，這個函數每次都會被調用，所以你要確保運行起來花的時間更少，比 React 的做法時間少，還有比計算 component 需要的時間少，即使重新繪制并不是必要的

六、總結

React 通過制定大膽的 diff 策略，將 O(n^3) 復雜度的問題轉換成 O(n) 復雜度的問題
React 通過分層求異的策略，對 tree diff 進行算法優化
React 通過相同類生成相似樹形結構，不同類生成不同樹形結構的策略，對 component diff 進行算法優化
React 通過設置唯一 key 的策略，對 element diff 進行算法優化
建議，在開發過程中，保持穩定的 DOM 結構會有助于性能的提升
建議，在開發過程中，盡量減少類似將最后一個節點移動到列表首部的操作，當節點數量過大或更新操作過于頻繁時，在一定程度上會影響 React 的渲染性能

七、結論

幫助 React 變快的技術并不新穎，長久以來，我們知道觸碰 DOM 是費時的，你應該合并處理讀和寫的操作，事件代理會更快。

人們還是會經常討論他們，因為在實際當中用 JavaScript 進行實現還是挺難的，React 突出的一個原因是這些優化默認就啟動了，這就讓你避免掉不小心把 App 寫得很慢。

React 消耗性能的模型很簡單，很好理解：每次調用 setState 會重新計算整個子樹。如果你想要提高性能，盡量少調用 setState，還有用 shouldComponentUpdate 減少大的子樹的重新計算。

總結一下 Diff 算法的大致流程：

又一個全局變量 updateDepth 來標識遞歸的深度，進行 diff 算法之前 +1，diff 算法結束之后 -1。當其重新變為 0 的時候表示整個 diff 算法結束了，可以拿更新隊列 diffQueue 來更新 DOM 了
Diff 算法只對同個父元素的同級子元素進行對比。如果元素的 type 和 key（如果有的話）相同，視為同一個元素，進行更新；否則替換掉。
Diff 使用了一個局部變量：lastIndex ——記錄已經處理的就列表中最靠后的元素。當元素的 ._mountIndex 大于 lastIndex 的時候，不需要移動元素。因為移動元素不會對前面對元素產生任何影響，因此可以省略這個動作，由于很多時候大部分元素處于這種情況下，因此這個局部變量提升了性能（有時候很明顯）。需要注意的是如果把列表中最后一個元素移到最前面，那么 lastIndex 就會大于后面對比的所有元素，導致的后果就是列表中所有元素都將被移動