diff作為Virtual DOM的加速器，其算法上的改進(jìn)優(yōu)化是React整個界面渲染的基礎(chǔ)和性能保障。傳統(tǒng)的diff算法，計(jì)算一棵樹形結(jié)構(gòu)轉(zhuǎn)換成另一顆樹形結(jié)構(gòu)的最少操作是通過循環(huán)遞歸對節(jié)點(diǎn)進(jìn)行依次對比，這種方式效率低下，算法復(fù)雜度達(dá)到O(n^3)，其中n是樹中節(jié)點(diǎn)的總數(shù)。而React diff將O(n^3)復(fù)雜度的問題轉(zhuǎn)換成O(n)復(fù)雜度的問題。

1. diff策略

• 策略一： Web UI中DOM節(jié)點(diǎn)跨層級的移動操作特別少，可以忽略不計(jì)。
• 策略二：擁有相同類的兩個組件將會生成相似的樹形結(jié)構(gòu)，擁有不同類的兩個組件將會生成不同的樹形結(jié)構(gòu)。
• 策略三：對于同一層級的一組子節(jié)點(diǎn)，它們可以通過唯一id進(jìn)行區(qū)分。

基于以上策略，React分別對tree diff、component diff以及element diff進(jìn)行算法優(yōu)化。

1.1 tree diff

基于策略一，React的做法是把dom tree分層級，對于兩個dom tree只比較同一層次的節(jié)點(diǎn)，忽略Dom中節(jié)點(diǎn)跨層級移動操作，只對同一個父節(jié)點(diǎn)下的所有的子節(jié)點(diǎn)進(jìn)行比較。如果對比發(fā)現(xiàn)該父節(jié)點(diǎn)不存在則直接刪除該節(jié)點(diǎn)下所有子節(jié)點(diǎn)，不會做進(jìn)一步比較，這樣只需要對dom tree進(jìn)行一次遍歷就完成了兩個tree的比較。

DOM層級變換

1.2 component diff

React應(yīng)用是基于組件構(gòu)建的，對于組件的比較優(yōu)化側(cè)重于以下幾點(diǎn)：

• 同一類型組件遵從tree diff比較v-dom樹
• 不通類型組件，先將該組件歸類為dirty component，替換下整個組件下的所有子節(jié)點(diǎn)

• 同一類型組件Virtual Dom沒有變化，React允許開發(fā)者使用shouldComponentUpdate（）來判斷該組件是否進(jìn)行diff，運(yùn)用得當(dāng)可以節(jié)省diff計(jì)算時(shí)間，提升性能

  
  
  component diff
  
  

  如上圖，當(dāng)組件D → 組件G時(shí)，diff判斷為不同類型的組件，雖然它們的結(jié)構(gòu)相似甚至一樣，diff仍然不會比較二者結(jié)構(gòu)，會直接銷毀D及其子節(jié)點(diǎn)，然后新建一個G相關(guān)的子tree，這顯然會影響性能，官方雖然認(rèn)定這種情況極少出現(xiàn)，但是開發(fā)中的這種現(xiàn)象造成的影響是非常大的。
  對于同一類型組件合理使用shouldComponentUpdate（），應(yīng)該避免結(jié)構(gòu)相同類型不同的組件

1.3 element diff

對于同一層級的element節(jié)點(diǎn)，diff提供了以下3種節(jié)點(diǎn)操作：

• INSERT_MARKUP 插入節(jié)點(diǎn)：對全新節(jié)點(diǎn)執(zhí)行節(jié)點(diǎn)插入操作
• MOVE_EXISING 移動節(jié)點(diǎn)：組件新集合中有組件舊集合中的類型，且element可更新，即組件調(diào)用了receiveComponent，這時(shí)可以復(fù)用之前的dom，執(zhí)行dom移動操作
• REMOVE_NODE 移除節(jié)點(diǎn)：此時(shí)有兩種情況：組件新集合中有組件舊集合中的類型，但對應(yīng)的element不可更新、舊組建不在新集合里面，這兩種情況需要執(zhí)行節(jié)點(diǎn)刪除操作
  
  element diff
  
  一般diff在比較集合[A,B,C,D]和[B，A，D，C]的時(shí)候會進(jìn)行全部對比，即按對應(yīng)位置逐個比較，發(fā)現(xiàn)每個位置對應(yīng)的元素都有所更新，則把舊集合全部移除，替換成新的集合，如上圖，但是這樣的操作在React中顯然是復(fù)雜、低效、影響性能的操作，因?yàn)樾录现兴械脑囟伎梢赃M(jìn)行復(fù)用，無需刪除重新創(chuàng)建，耗費(fèi)性能和內(nèi)存，只需要移動元素位置即可。
  React對這一現(xiàn)象做出了一個高效的策略：允許開發(fā)者對同一層級的同組子節(jié)點(diǎn)添加唯一key值進(jìn)行區(qū)分。意義就是代碼上的一小步，性能上的一大步，甚至是翻天覆地的變化！
  React通過key是如何進(jìn)行element管理的呢？為何如此高效？
  React會先進(jìn)行新集合遍歷，for(name in nextChildren)，通過key值判斷兩個對比集合中是否存在相同的節(jié)點(diǎn)，即if(prevChild === nextChild)，如何為true則進(jìn)行移動操作，在此之前，需要執(zhí)行被移動節(jié)點(diǎn)在新舊（child._mountIndex）集合中的位置比較，if(child._mountIndex < lastIndex)為true時(shí)進(jìn)行移動，否則不執(zhí)行該操作，這實(shí)際上是一種順序優(yōu)化，lastIndex是不斷更新的，表示訪問過的節(jié)點(diǎn)在集合中的最右的位置。若當(dāng)前訪問節(jié)點(diǎn)在舊集合中的位置比lastIndex大，即靠右，說明它不會影響其他元素的位置，因此不用添加到差異隊(duì)列中，不執(zhí)行移動操作，反之則進(jìn)行移動操作。
  
  image.png
  
  nextIndex = 0，lastIndex = 0，從新集合中獲取B，在舊集合中發(fā)現(xiàn)相同節(jié)點(diǎn)B，舊集合中：B._mountIndex = 1，child._mountIndex < lastIndex ==> false，不執(zhí)行移動操作，更新lastIndex = Math.max(prevChild._mountIndex, lastIndex), prevChild._mountIndex === B._mountIndex ==> true，更新B在新集合中的位置：prevChild._mountIndex = nextIndex，在新集合中：B._mountIndex = 0，nextIndex++，進(jìn)行下一個節(jié)點(diǎn)判斷。

• nextIndex = 1，lastIndex = 1，從新集合中獲取A，在舊集合中發(fā)現(xiàn)相同節(jié)點(diǎn)A，舊集合中：A._mountIndex = 0，child._mountIndex < lastIndex ==> true，對A進(jìn)行移動操作enqueueMove(this, child._mountIndex, toIndex)，toIndex是A要被移動到的位置，更新lastIndex = Math.max(prevChild._mountIndex, lastIndex)，更新A在新集合中的位置prevChild._mountIndex = nextIndex，在新集合中：A._mountIndex = 1，nextIndex++，進(jìn)行下一個節(jié)點(diǎn)判斷。
• nextIndex = 2，lastIndex = 1，從新集合中獲取D，在舊集合中發(fā)現(xiàn)相同節(jié)點(diǎn)D，舊集合中：D._mountIndex = 3，child._mountIndex < lastIndex ==> false，不執(zhí)行移動操作，更新lastIndex = Math.max(prevChild._mountIndex, lastIndex), prevChild._mountIndex === D._mountIndex ==> true，更新D在新集合中的位置：prevChild._mountIndex = nextIndex，在新集合中：D._mountIndex = 2，nextIndex++，進(jìn)行下一個節(jié)點(diǎn)判斷。
• nextIndex = 3，lastIndex = 3，從新集合中獲取C，在舊集合中發(fā)現(xiàn)相同節(jié)點(diǎn)C，舊集合中：C._mountIndex = 2，child._mountIndex < lastIndex ==> true，對C進(jìn)行移動操作enqueueMove(this, child._mountIndex, toIndex)，toIndex是C要被移動到的位置，更新lastIndex = Math.max(prevChild._mountIndex, lastIndex)，更新C在新集合中的位置prevChild._mountIndex = nextIndex，在新集合中：A._mountIndex = 3，nextIndex++，進(jìn)行下一個節(jié)點(diǎn)判斷。
• 由于是最后一個節(jié)點(diǎn)，diff操作完成
  那么，除了有可復(fù)用節(jié)點(diǎn)，新集合當(dāng)有新插入節(jié)點(diǎn)，舊集合有需要刪除的節(jié)點(diǎn)呢？
  
  image.png
  
  對于這種情況，React則是執(zhí)行以下步驟：
• nextIndex = 0，lastIndex = 0，從新集合中獲取B，在舊集合中發(fā)現(xiàn)相同節(jié)點(diǎn)B，舊集合中：B._mountIndex = 1，child._mountIndex < lastIndex ==> false，不執(zhí)行移動操作，更新lastIndex = 1，更新B在新集合中的位置，nextIndex++，進(jìn)行下一個節(jié)點(diǎn)判斷。
• nextIndex = 1，lastIndex = 1，從新集合中獲取E，在舊集合中沒有發(fā)現(xiàn)相同節(jié)點(diǎn)E，nextIndex++進(jìn)入下一個節(jié)點(diǎn)判斷。
• nextIndex = 2，lastIndex = 1，從新集合中獲取C，在舊集合中發(fā)現(xiàn)相同節(jié)點(diǎn)C，舊集合中：C._mountIndex = 2，child._mountIndex < lastIndex ==> false，不對C進(jìn)行移動操作，更新lastIndex = 2，更新C在新集合的位置，nextIndex++，進(jìn)行下一個節(jié)點(diǎn)判斷。
• nextIndex = 3，lastIndex = 2，從新集合中獲取A，在舊集合中發(fā)現(xiàn)相同節(jié)點(diǎn)A，舊集合中：A._mountIndex = 0，child._mountIndex < lastIndex ==> true，對A進(jìn)行移動操作，更新lastIndex = 2，更新A在新集合中的位置，nextIndex++進(jìn)入下一個節(jié)點(diǎn)判斷。
• 當(dāng)完成新集合所有節(jié)點(diǎn)中的差異對比后，對舊集合進(jìn)行遍歷，判讀舊集合中是否存在新集合中不存在的節(jié)點(diǎn)，此時(shí)發(fā)現(xiàn)D節(jié)點(diǎn)符合判斷，執(zhí)行刪除D節(jié)點(diǎn)的操作，diff操作完成。

優(yōu)化后diff的不足

image.png

按照上述順序優(yōu)化，則舊集合中D的位置是最大的，最少的操作只是將D移動到第一位就可以了，實(shí)際上diff操作會移動D之前的三個節(jié)點(diǎn)到對應(yīng)的位置，這種情況會影響渲染的性能。

優(yōu)化建議

在開發(fā)過程中，同層級的節(jié)點(diǎn)添加唯一key值可以極大提升性能，盡量減少將最后一個節(jié)點(diǎn)移動到列表首部的操作，當(dāng)節(jié)點(diǎn)達(dá)到一定的數(shù)量以后或者操作過于頻繁，在一定程度上會影響React的渲染性能。比如大量節(jié)點(diǎn)拖拽排序的問題。