摘要：通過對樹進行層級控制，同一個父節(jié)點下的所有子節(jié)點。新老集合進行差異化對比，發(fā)現(xiàn)，則創(chuàng)建并插入至新集合，刪除老集合以此類推，創(chuàng)建并插入和，刪除和。

Jsx 表面寫的是html，其實內(nèi)部執(zhí)行的是一段js
createElement

React.createElement(
  type,
  [props],
  [...children]
)

createElement把這個樹形結(jié)構(gòu)，存在內(nèi)存里面
Jsx最終以這樣的一個個對象遞歸的存在內(nèi)存中，執(zhí)行diff算法

多層結(jié)構(gòu)

簡單的createElement實現(xiàn)

reactElement - 生成的是一個對象來描述這個節(jié)點

與傳統(tǒng)樹的diff的區(qū)別

計算一棵樹形結(jié)構(gòu)轉(zhuǎn)換成另一棵樹形結(jié)構(gòu)的最少操作，是一個復(fù)雜且值得研究的問題。傳統(tǒng) diff 算法通過循環(huán)遞歸對節(jié)點進行依次對比，效率低下，算法復(fù)雜度達到 O(n^3)

react diff策略

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

擁有相同類的兩個組件將會生成相似的樹形結(jié)構(gòu)，擁有不同類的兩個組件將會生成不同的樹形結(jié)構(gòu)。

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

tree diff

 基于策略一，對樹進行分層比較，兩棵樹只會對同一層次的節(jié)點進行比較。  
 React 通過 updateDepth 對 Virtual DOM 樹進行層級控制，同一個父節(jié)點下的所有子節(jié)點。
 

什么是 DOM 節(jié)點跨層級的移動操作？

A 節(jié)點（包括其子節(jié)點）整個被移動到 D 節(jié)點下

如果出現(xiàn)了 DOM 節(jié)點跨層級的移動操作，React diff 會有怎樣的表現(xiàn)呢？

React 只會簡單的考慮同層級節(jié)點的位置變換，而對于不同層級的節(jié)點，只有創(chuàng)建和刪除操作。

當根節(jié)點發(fā)現(xiàn)子節(jié)點中 A 消失了，就會直接銷毀 A；當 D 發(fā)現(xiàn)多了一個子節(jié)點 A，則會創(chuàng)建新的 A（包括子節(jié)點）作為其子節(jié)點。此時，React diff 的執(zhí)行情況：create A -> create B -> create C -> delete A。

注意：

在開發(fā)組件時，保持穩(wěn)定的 DOM 結(jié)構(gòu)會有助于性能的提升。例如，可以通過 CSS 隱藏或顯示節(jié)點，而不是真的移除或添加 DOM 節(jié)點。

component diff

依據(jù)策略二

如果是同一類型的組件，按照原策略繼續(xù)比較 virtual DOM tree。

如果不是，則將該組件判斷為 dirty component，從而替換整個組件下的所有子節(jié)點。

對于同一類型的組件，有可能其 Virtual DOM 沒有任何變化，如果能夠確切的知道這點那可以節(jié)省大量的 diff 運算時間，因此 React 允許用戶通過 shouldComponentUpdate() 來判斷該組件是否需要進行 diff。

React 判斷 D 和 G 是不同類型的組件，就不會比較二者的結(jié)構(gòu)，而是直接刪除 component D，重新創(chuàng)建 component G 以及其子節(jié)點，即使D 和 G的結(jié)構(gòu)很相似

element diff

當節(jié)點處于同一層級時，React diff 提供了三種節(jié)點操作，分別為：INSERT_MARKUP（插入）、MOVE_EXISTING（移動）和 REMOVE_NODE（刪除）。

INSERT_MARKUP，新的 component 類型不在老集合里， 即是全新的節(jié)點，需要對新節(jié)點執(zhí)行插入操作。

MOVE_EXISTING，在老集合有新 component 類型，且 element 是可更新的類型，generateComponentChildren 已調(diào)用 receiveComponent，這種情況下 prevChild=nextChild，就需要做移動操作，可以復(fù)用以前的 DOM 節(jié)點。

REMOVE_NODE，老 component 類型，在新集合里也有，但對應(yīng)的 element 不同則不能直接復(fù)用和更新，需要執(zhí)行刪除操作，或者老 component 不在新集合里的，也需要執(zhí)行刪除操作。

eg: 新老集合進行 diff 差異化對比，發(fā)現(xiàn) B != A，則創(chuàng)建并插入 B 至新集合，刪除老集合 A；以此類推，創(chuàng)建并插入 A、D 和 C，刪除 B、C 和 D。

帶來的問題：都是相同的節(jié)點，但由于位置發(fā)生變化，導(dǎo)致需要進行繁雜低效的刪除、創(chuàng)建操作，其實只要對這些節(jié)點進行位置移動即可

react優(yōu)化策略：允許開發(fā)者對同一層級的同組子節(jié)點，添加唯一 key 進行區(qū)分

優(yōu)化后diff實現(xiàn)：

對新集合的節(jié)點進行循環(huán)遍歷，通過唯一 key 可以判斷新老集合中是否存在相同的節(jié)點

如果存在相同節(jié)點，則進行移動操作，但在移動前需要將當前節(jié)點在老集合中的位置child._mountIndex與lastIndex(訪問過的節(jié)點在老集合中最右的位置即最大的位置)進行比較，if (child._mountIndex < lastIndex)，則進行節(jié)點移動操作

分析：

element  _mountIndex  lastIndex  nextIndex  enqueueMove
B        1            0          0          false
A        0            1          1          true
D        3            1          2          false
C        2            3          3          true

step：

從新集合中取得 B，判斷老集合中存在相同節(jié)點 B
B 在老集合中的位置 B._mountIndex = 1
初始 lastIndex = 0
不滿足 child._mountIndex < lastIndex 的條件，因此不對 B 進行移動操作
更新 lastIndex = Math.max(prevChild._mountIndex, lastIndex) lastIndex更新為1
將 B 的位置更新為新集合中的位置prevChild._mountIndex = nextIndex，此時新集合中 B._mountIndex = 0，nextIndex++

以上主要分析新老集合中存在相同節(jié)點但位置不同時，對節(jié)點進行位置移動的情況，如果新集合中有新加入的節(jié)點且老集合存在需要刪除的節(jié)點，那么 React diff 又是如何對比運作的呢？

    element  _mountIndex  lastIndex  nextIndex  enqueueMove
    B        1            0          0          false
    E        no exist
    C        2            1          2          false
    A        0            2          3          true
    

step

新建：從新集合中取得 E，判斷老集合中不存在相同節(jié)點 E，則創(chuàng)建新節(jié)點 E
     lastIndex不做處理
     E 的位置更新為新集合中的位置，nextIndex++
刪除：當完成新集合中所有節(jié)點 diff 時，最后還需要對老集合進行循環(huán)遍歷，判斷是否存在新集合中沒有但老集合中仍存在的節(jié)點，發(fā)現(xiàn)存在這樣的節(jié)點 D，因此刪除節(jié)點 D

react diff的問題

理論上 diff 應(yīng)該只需對 D 執(zhí)行移動操作，然而由于 D 在老集合的位置是最大的，導(dǎo)致其他節(jié)點的 _mountIndex < lastIndex，造成 D 沒有執(zhí)行移動操作，而是 A、B、C 全部移動到 D 節(jié)點后面的現(xiàn)象

建議：在開發(fā)過程中，盡量減少類似將最后一個節(jié)點移動到列表首部的操作，當節(jié)點數(shù)量過大或更新操作過于頻繁時，在一定程度上會影響 React 的渲染性能。

總結(jié)：

React 通過制定大膽的 diff 策略，將 O(n3) 復(fù)雜度的問題轉(zhuǎn)換成 O(n) 復(fù)雜度的問題；

React 通過分層求異的策略，對 tree diff 進行算法優(yōu)化；

React 通過相同類生成相似樹形結(jié)構(gòu)，不同類生成不同樹形結(jié)構(gòu)的策略，對 component diff 進行算法優(yōu)化；

React 通過設(shè)置唯一 key的策略，對 element diff 進行算法優(yōu)化；

建議，在開發(fā)組件時，保持穩(wěn)定的 DOM 結(jié)構(gòu)會有助于性能的提升；

建議，在開發(fā)過程中，盡量減少類似將最后一個節(jié)點移動到列表首部的操作，當節(jié)點數(shù)量過大或更新操作過于頻繁時，在一定程度上會影響 React 的渲染性能。

https://zhuanlan.zhihu.com/p/...