摘要：算法的本質(zhì)是對傳統(tǒng)遍歷算法的優(yōu)化策略用三大策略將復雜度轉(zhuǎn)化為復雜度策略一中節(jié)點跨層級的移動操作特別少，可以忽略不計。當節(jié)點處于同一層級時，提供三種節(jié)點操作刪除插入移動。在舊的節(jié)點中的，它的，不滿足的條件，因此不做移動操作。

一、react diff算法

diff算法的作用
計算出Virtual DOM中真正變化的部分，并只針對該部分進行原生DOM操作，而非重新渲染整個頁面。

傳統(tǒng)diff算法
通過循環(huán)遞歸對節(jié)點進行依次對比，算法復雜度達到 O(n^3) ，n是樹的節(jié)點數(shù)，這個有多可怕呢？——如果要展示1000個節(jié)點，得執(zhí)行上億次比較。。即便是CPU快能執(zhí)行30億條命令，也很難在一秒內(nèi)計算出差異。

備注：傳統(tǒng)算法的復雜度計算方法有興趣可以參考如下地址：https://grfia.dlsi.ua.es/ml/a...

React的diff算法（React16以下版本）
（1）什么是調(diào)和？

將Virtual DOM樹轉(zhuǎn)換成actual DOM樹的最少操作的過程 稱為 調(diào)和 。

（2）什么是React diff算法？

 diff算法是調(diào)和的具體實現(xiàn)。diff算法的本質(zhì)是對傳統(tǒng)tree遍歷算法的優(yōu)化

（3）diff策略

 React用 三大策略 將O(n^3)復雜度 轉(zhuǎn)化為 O(n)復雜度

策略一（tree diff）：

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

策略二（component diff）：

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

策略三（element diff）：

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

tree diff
（1）React通過updateDepth對Virtual DOM樹進行層級控制。
（2）對樹分層比較，兩棵樹 只對同一層次節(jié)點 進行比較。如果該節(jié)點不存在時，則該節(jié)點及其子節(jié)點會被完全刪除，不會再進一步比較。
（3）只需遍歷一次，就能完成整棵DOM樹的比較。

如下圖所示：

那么問題來了，如果DOM節(jié)點出現(xiàn)了跨層級操作,diff會咋辦呢？
答：diff只簡單考慮同層級的節(jié)點位置變換，如果是跨層級的話，只有創(chuàng)建節(jié)點和刪除節(jié)點的操作。

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

component diff
React對不同的組件間的比較，有三種策略
（1）同一類型的兩個組件，按原策略（層級比較）繼續(xù)比較Virtual DOM樹即可。
（2）同一類型的兩個組件，組件A變化為組件B時（A、B類型相同、結(jié)構(gòu)相同），可能Virtual DOM沒有任何變化，如果知道這點（變換的過程中，Virtual DOM沒有改變），可節(jié)省大量計算時間，所以 用戶 可以通過 shouldComponentUpdate() 來判斷是否需要 判斷計算。
（3）不同類型的組件，將一個（將被改變的）組件判斷為dirty component（臟組件），從而替換 整個組件的所有節(jié)點。
注意：如果組件D和組件G的結(jié)構(gòu)相似，但是 React判斷是 不同類型的組件，則不會比較其結(jié)構(gòu)，而是刪除 組件D及其子節(jié)點，創(chuàng)建組件G及其子節(jié)點。

element diff
當節(jié)點處于同一層級時，diff提供三種節(jié)點操作：刪除、插入、移動。

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

刪除：
（1）組件 D 在集合（A,B,D）中，但 D的節(jié)點已經(jīng)更改，不能復用和更新，所以需要刪除 舊的 D ，再創(chuàng)建新的。
（2）組件 D 之前在 集合（A,B,D）中，但集合變成新的集合（A,B）了，D 就需要被刪除。

移動：組件D已經(jīng)在集合（A,B,C,D）里了，且集合更新時，D沒有發(fā)生更新，只是位置改變，如新集合（A,D,B,C），D在第二個，無須像傳統(tǒng)diff，讓舊集合的第二個B和新集合的第二個D 比較，并且刪除第二個位置的B，再在第二個位置插入D，而是 （對同一層級的同組子節(jié)點） 添加唯一key進行區(qū)分，移動即可。

重點說下移動的邏輯：
情形一：新舊集合中存在相同節(jié)點但位置不同時，如何移動節(jié)點
移動1、

（1）看著上圖的 B，React先從新中取得B，然后判斷舊中是否存在相同節(jié)點B，當發(fā)現(xiàn)存在節(jié)點B后，就去判斷是否移動B。
B在舊的節(jié)點中的index=1，它的lastIndex=0，不滿足 index < lastIndex 的條件，因此 B 不做移動操作。此時，一個操作是，lastIndex=(index,lastIndex)中的較大數(shù)=1.
注意：lastIndex有點像浮標，或者說是一個map的索引，一開始默認值是0，它會與map中的元素進行比較，比較完后，會改變自己的值的（取index和lastIndex的較大數(shù)）。
（2）看著 A，A在舊的index=0，此時的lastIndex=1（因為先前與新的B比較過了），滿足index（3）看著D，同（1），不移動，由于D在舊的index=3，比較時，lastIndex=1，所以改變lastIndex=max(index,lastIndex)=3
（4）看著C，同（2），移動，C在舊的index=2，滿足index由于C已經(jīng)是最后一個節(jié)點，所以diff操作結(jié)束。

情形二：新集合中有新加入的節(jié)點，舊集合中有刪除的節(jié)點

移動2、

（1）B不移動，不贅述，更新l astIndex=1
（2）新集合取得 E，發(fā)現(xiàn)舊不存在，故在lastIndex=1的位置 創(chuàng)建E，更新lastIndex=1
（3）新集合取得C，C不移動，更新lastIndex=2
（4）新集合取得A，A移動，同上，更新lastIndex=2
（5）新集合對比后，再對舊集合遍歷。判斷 新集合 沒有，但 舊集合 有的元素（如D，新集合沒有，舊集合有），發(fā)現(xiàn) D，刪除D，diff操作結(jié)束。

diff的不足與待優(yōu)化的地方

移動3、

看圖的 D，此時D不移動，但它的index是最大的，導致更新lastIndex=3，從而使得其他元素A,B,C的index理想情況是只移動D，不移動A,B,C。因此，在開發(fā)過程中，盡量減少類似將最后一個節(jié)點移動到列表首部的操作，當節(jié)點數(shù)量過大或更新操作過于頻繁時，會影響React的渲染性能。

二、 React Fiber（React16版本）
引言：
diff算法相對傳統(tǒng)算法已經(jīng)是比較高效的計算機制了，但是人總是要有追求，三年前左右react就發(fā)現(xiàn)了reconciliation的一個潛在問題，就是在對比兩顆樹的時候，花費的時間太長，可能導致瀏覽器假死，所以就啟動了一個項目來重寫reconciliation，那就是react fiber.

為什么？
這里不得不提瀏覽器的渲染機制，現(xiàn)在基本上公認的是60fps，也就是說瀏覽器會在每秒內(nèi)渲染60次，也就是基本上16.7ms渲染一次。
(為什么是60fps呢，這里和硬件的刷新頻率有關(guān)系，有興趣的可以查下)
基本渲染流程如下
1，執(zhí)行js
2，樣式計算
3，計算布局，執(zhí)行
4，pait，繪制各層
5，合成各層的繪制結(jié)果，呈現(xiàn)在瀏覽器上。
所以基本上就是在16.7ms內(nèi)執(zhí)行完這些操作，就是比較完美的啦，但是事情不可能這么完美，比如如果js代碼執(zhí)行時間特別長的話，一直在等你的js執(zhí)行完之后，才會去渲染，頁面就是一直空白。

1、 React從版本16開始棄用diff算法，改為Fiber渲染方式進行組件差異化比較

舊版的diff算法是遞歸比較，對virtural dom的更新和渲染是同步的。就是當一次更新或者一次加載開始以后，virtual dom的diff比較并且渲染的過程是一口氣完成的。如果組件層級比較深，相應的堆棧也會很深，長時間占用瀏覽器主線程，一些類似用戶輸入、鼠標滾動等操作得不到響應。造成線程柱塞，因此React官方改變了之前的Virtual Dom的渲染機制，新架構(gòu)使用鏈表形式的虛擬 DOM，新的架構(gòu)使原來同步渲染的組件現(xiàn)在可以異步化，可中途中斷渲染，執(zhí)行更高優(yōu)先級的任務(wù)。釋放瀏覽器主線程。

我們使用兩張圖來區(qū)分兩種算法之間的區(qū)別

這個就是以前的diff算法渲染圖：

當所有的事情都等待reconciliation結(jié)束的時候，可能有其他更高級別的功能需求進來，比如用戶點擊輸入框，或者是點擊按鈕等操作，但是由于還在執(zhí)行，就會就一直卡住，讓用戶認為頁面在假死。
所以最好的辦法，也是用的最多的辦法，不管是在計算機系統(tǒng)還是哪里，那就是分片，我借了你的東西，我用一段時間，就得過來就還給你，等你用完了之后，我再過來借一次，好借好還，再借不難。

這個是新的Fiber渲染機制：

這基本就是react fiber的核心所在！

同時應該說明：React15與React16 兩個 DOM 的結(jié)構(gòu)和遍歷方式已經(jīng)完全不同。

2、 算法流程
fiber tree 算法
具體流程和原來的差不多，其實也還是找出兩次更新之間的差異，然后渲染到瀏覽器上面。
fiber會在首次render函數(shù)執(zhí)行完之后，react會保存一份react fiber樹，然后會循環(huán)利用，不會重復建立，稱為current 樹。
2，當有setstate或者其他更新的時候，就會根據(jù)現(xiàn)在的current樹重新生成一份包含變化的樹。這里最重要的就是在對比兩顆樹的過程中是異步的，隨時可以中斷，恢復，但是當更新的時候是同步的，也就是說 diff 過程中，是異步，commit是同步的。

diff 具體過程
這里就是根據(jù)信息，來遍歷fibertree樹然后找不不同，這里不一樣的一點是因為加了很多的指針，類似加了很多直達電梯，節(jié)省了很多時間，可以直接到達。
任何一項工作都會有下面幾步， 首先獲取該在哪里做，然后開始做，再接著就是花時間干完這項工作，最后退出，繼續(xù)尋找下一步該在哪里工作。
對應關(guān)系就是
獲取該在哪里做： performUnitOfWork
開始做： beginWork
完成工作： completeUnitOfWork
尋找下一步哪里做： completeWork
所有的函數(shù)都在(packages/react-reconciler/src/ReactFiberScheduler.js)
可以看下別人做的效果圖

tree的執(zhí)行順序： a1-b1-b1完成-b2-c1-d1-d1完成-d2-d2完成-c1完成-b2完成-b3-c2-c2完成-b3完成-a1完成。

fiber 首次 render 的時候，就會調(diào)用一次 requestIdeCallback，這個 api 會進行循環(huán)
這個循環(huán)，它負責變更 current fiber（當前的 fiber 節(jié)點） 前面提到，鏈表天生可以拿到 節(jié)點本身，還能拿到父節(jié)點，兄弟節(jié)點，子節(jié)點

唯一要記住的一點就是這里的過程是異步的，隨時可能會暫停，或者停止，或者需要恢復過來重新執(zhí)行。

commit
這里就是同步的了，不過速度也會很快的，因為這里把哪些改變了的fiber node形成了一個鏈表，如果中間沒有更新的話，會快速的跳到下面去。

類似于下圖的鏈表

看一下fiber架構(gòu) 組建的渲染順序：
加入fiber的react將組件更新分為兩個時期Reconciliation Phase和Commit Phase。Reconciliation Phase的任務(wù)干的事情是，找出要做的更新工作（Diff Fiber Tree），就是一個計算階段，計算結(jié)果可以被緩存，也就可以被打斷；Commmit Phase 需要提交所有更新并渲染，為了防止頁面抖動，被設(shè)置為不能被打斷。

這兩個時期以render為分界，
render前的生命周期為phase1,
render后的生命周期為phase2

phase1的生命周期是可以被打斷的，每隔一段時間它會跳出當前渲染進程，去確定是否有其他更重要的任務(wù)。此過程，React 在 workingProgressTree （并不是真實的virtualDomTree）上復用 current 上的 Fiber 數(shù)據(jù)結(jié)構(gòu)來一步地（通過requestIdleCallback）來構(gòu)建新的 tree，標記處需要更新的節(jié)點，放入隊列中。
phase2的生命周期是不可被打斷的，React 將其所有的變更一次性更新到DOM上。
這里最重要的是phase1這是時期所做的事。因此我們需要具體了解phase1的機制。

PS: componentWillMount componentWillReceiveProps componentWillUpdate 幾個生命周期方法，在Reconciliation Phase被調(diào)用，有被打斷的可能（時間用盡等情況），所以可能被多次調(diào)用。其實 shouldComponentUpdate 也可能被多次調(diào)用，只是它只返回true或者false，沒有副作用，可以暫時忽略。

如果不被打斷，那么phase1執(zhí)行完會直接進入render函數(shù)，構(gòu)建真實的virtualDomTree
如果組件再phase1過程中被打斷，即當前組件只渲染到一半（也許是在willMount,也許是willUpdate~反正是在render之前的生命周期），那么react會怎么干呢？ react會放棄當前組件所有干到一半的事情，去做更高優(yōu)先級更重要的任務(wù)（當然，也可能是用戶鼠標移動，或者其他react監(jiān)聽之外的任務(wù)），當所有高優(yōu)先級任務(wù)執(zhí)行完之后，react通過callback回到之前渲染到一半的組件，從頭開始渲染。（看起來放棄已經(jīng)渲染完的生命周期，會有點不合理，反而會增加渲染時長，但是react確實是這么干的）

看到這里，相信聰明的同學已經(jīng)發(fā)現(xiàn)一些問題啦~

也就是 所有phase1的生命周期函數(shù)都可能被執(zhí)行多次，因為可能會被打斷重來
這樣的話，就和react16版本之前有很大區(qū)別了，因為可能會被執(zhí)行多次，那么我們最好就得保證phase1的生命周期每一次執(zhí)行的結(jié)果都是一樣的，否則就會有問題，因此，最好都是純函數(shù)。

（所以react16目前都沒有把fiber enable，其實react16還是以 同步的方式在做組建的渲染，因為這樣的話，很多我們用老版本react寫的組件就有可能都會有問題,包括用的很多開源組件，但是后面應該會enable,讓開發(fā)者可以開啟fiber異步渲染模式~）

對了，還有一個問題，饑餓問題，即如果高優(yōu)先級的任務(wù)一直存在，那么低優(yōu)先級的任務(wù)則永遠無法進行，組件永遠無法繼續(xù)渲染。這個問題facebook目前好像還沒解決，但以后會解決~
所以，facebook在react16增加fiber結(jié)構(gòu)，其實并不是為了減少組件的渲染時間，事實上也并不會減少，最重要的是現(xiàn)在可以使得一些更高優(yōu)先級的任務(wù)，如用戶的操作能夠優(yōu)先執(zhí)行，提高用戶的體驗，至少用戶不會感覺到卡頓~

源碼解析：
https://blog.csdn.net/qiqingj...