react 學習筆記——diff算法

diff算法是react中經典之作，他很巧妙，該算法是react整個界面渲染的基礎和保障。

将之前先介紹一下傳統的DIff的弊端：傳統的Diff算法通過循環遞歸依次對節點進行對比，效率比較低下，算法的時間複雜度為O(n^3)，n為樹的節點數，當節點比較多的時候，這種搜尋次數将會急劇增加，計算機的負荷開銷将會十分巨大。

DIFF的三種政策：DOM間的diff、元件間的diff、元素間的diff

1. tree diff（這種情況比較少）

react對樹的算法進行了簡單的優化：對樹進行分層的比較，兩棵樹隻會對同層的節點進行比較。

react通過updateDepth對Virtual DOM樹進行層級的控制，隻會對相同層級的DOM節點進行比較，即同一個父節點下的所有的子節點。當發現節點已經不存在的時候，則該節點即子節點會被完全的删除，不會進行進一步的比較了，這樣隻需要對樹周遊一次即可。

（注意：開發元件的時候，保持元件的DOM結構的穩定有助于提高性能，例如：可以通過CSS來隐藏節點，而不是真正的删除或者增加DOM節點）

2.component diff

元件間的比較算法：

·如果是相同類型的元件，按照tree diff的政策進行比較；

·如果不是，将該元件判斷為dirty component，然後将該節點下面的所有的子節點全部替換掉；

·對于相同類型的元件，可能他的Virtual DOM沒有任何的變化，如果知道這一點，将極大的節省計算diff的時間，是以，react允許使用者通過shouldComponentUpdate()來判斷該元件是否需要diff算法。

以上兩個都是比較簡單的情況：

3.element diff

當節點在同一層級的時候，diff提供三種操作：INSERT_MAPKUP（插入）、MOVE_EXISTING（移動）、REMOVE_NODE（删除）。

此處引進key值：這是由于，當層級中的節點元素沒有發生變化的時候，而是僅僅是位置的變化，如果按照上述的原則位置不同将會重新繪畫，這将影響渲染的性能，是以，為每個節點添加唯一的key值，當發現有相同的節點的時候，不需要進行重新的建立或删除節點的操作。

如圖所示：diff的操作的過程（就是舊節點更新為新節點的過程）

首先對新節點逐一進行周遊，通過唯一的key值來判斷舊的集合中是否存在相同的節點，圖中，先周遊新圖中的節點，首先取到節點B，發現B節點在舊圖中存在（B在舊圖中的index=1），此時比較lastIndex（通路過的節點的最右的位置，初始值為0）與B在舊圖中的index比較，if(index<lastIndex)，則進行移動操作，此時，index=1>lastIndex=0，是以B節點不移動，接下來更新lastIndex的值：lastIndex= max(lastIndex,index),此時lastIndex值更新為1；

接着取新節點A，A在舊節點中的位置index=0，此時，lastIndex= 1，滿足（index<lastIndex）的條件，是以，将A的值更新為新節點中的位置，此時lastIndex仍然為1；

接下來取到新節點的D，D在舊節點中的位置為index=3，此時lastIndex=1，不滿足（index<lastIndex）條件，是以，D的位置不更新，此時lastIndex = max(lastIndex,index) = 3;

最後取到節點C，C在舊節點的位置為index= 2，此時lastIndex=3，滿足（index<lastIndex）條件，是以對，C節點進行移動操作。

上述僅僅是，一種情況，如果出現周遊一遍新節點過程中，在舊節點中不存在該節點，應該添加該節點，最後周遊完新節點後，還要周遊一遍 舊節點，将舊節點中多餘的節點删除掉。