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

一、react diff算法

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

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

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

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

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

（2）什么是React diff算法？

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

（3）diff策略

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

策略一（tree diff）：

  Web UI中DOM節(jié)點(diǎn)跨層級(jí)的移動(dòng)操作特別少，可以忽略不計(jì)。

策略二（component diff）：

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

策略三（element diff）：

  對(duì)于同一層級(jí)的一組子節(jié)點(diǎn)，通過(guò)唯一id區(qū)分。
  

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

如下圖所示：

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

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

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

element diff
當(dāng)節(jié)點(diǎn)處于同一層級(jí)時(shí)，diff提供三種節(jié)點(diǎn)操作：刪除、插入、移動(dòng)。

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

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

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

重點(diǎn)說(shuō)下移動(dòng)的邏輯：
情形一：新舊集合中存在相同節(jié)點(diǎn)但位置不同時(shí)，如何移動(dòng)節(jié)點(diǎn)
移動(dòng)1、

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

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

移動(dòng)2、

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

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

移動(dòng)3、

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

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

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

1、 React從版本16開(kāi)始棄用diff算法，改為Fiber渲染方式進(jìn)行組件差異化比較

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

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

這個(gè)就是以前的diff算法渲染圖：

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

這個(gè)是新的Fiber渲染機(jī)制：

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

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

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

diff 具體過(guò)程
這里就是根據(jù)信息，來(lái)遍歷fibertree樹(shù)然后找不不同，這里不一樣的一點(diǎn)是因?yàn)榧恿撕芏嗟闹羔槪愃萍恿撕芏嘀边_(dá)電梯，節(jié)省了很多時(shí)間，可以直接到達(dá)。
任何一項(xiàng)工作都會(huì)有下面幾步， 首先獲取該在哪里做，然后開(kāi)始做，再接著就是花時(shí)間干完這項(xiàng)工作，最后退出，繼續(xù)尋找下一步該在哪里工作。
對(duì)應(yīng)關(guān)系就是
獲取該在哪里做： performUnitOfWork
開(kāi)始做： 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 的時(shí)候，就會(huì)調(diào)用一次 requestIdeCallback，這個(gè) api 會(huì)進(jìn)行循環(huán)
這個(gè)循環(huán)，它負(fù)責(zé)變更 current fiber（當(dāng)前的 fiber 節(jié)點(diǎn)） 前面提到，鏈表天生可以拿到 節(jié)點(diǎn)本身，還能拿到父節(jié)點(diǎn)，兄弟節(jié)點(diǎn)，子節(jié)點(diǎn)

唯一要記住的一點(diǎn)就是這里的過(guò)程是異步的，隨時(shí)可能會(huì)暫停，或者停止，或者需要恢復(fù)過(guò)來(lái)重新執(zhí)行。

commit
這里就是同步的了，不過(guò)速度也會(huì)很快的，因?yàn)檫@里把哪些改變了的fiber node形成了一個(gè)鏈表，如果中間沒(méi)有更新的話，會(huì)快速的跳到下面去。

類似于下圖的鏈表

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

這兩個(gè)時(shí)期以render為分界，
render前的生命周期為phase1,
render后的生命周期為phase2

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

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

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

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

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

（所以react16目前都沒(méi)有把fiber enable，其實(shí)react16還是以 同步的方式在做組建的渲染，因?yàn)檫@樣的話，很多我們用老版本react寫的組件就有可能都會(huì)有問(wèn)題,包括用的很多開(kāi)源組件，但是后面應(yīng)該會(huì)enable,讓開(kāi)發(fā)者可以開(kāi)啟fiber異步渲染模式~）

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

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