原文：https://segmentfault.com/a/1190000010686582
React框架使用的目的，就是為了維護(hù)狀態(tài)绢陌，更新視圖。
為什么會說傳統(tǒng)DOM操作效率低呢熔恢？當(dāng)使用document.createElement()創(chuàng)建了一個(gè)空的Element時(shí)脐湾，會需要按照標(biāo)準(zhǔn)實(shí)現(xiàn)一大堆的東西，如下圖所示叙淌。此外秤掌，在對DOM進(jìn)行操作時(shí)，如果一不留神導(dǎo)致回流鹰霍，性能可能就很難保證了闻鉴。
相比之下，JS對象的操作卻有著很高的效率茂洒，通過操作JS對象孟岛，根據(jù)這個(gè)用 JavaScript 對象表示的樹結(jié)構(gòu)來構(gòu)建一棵真正的DOM樹，正是React對上述問題的解決思路督勺。之前的文章中可以看出渠羞，使用React進(jìn)行開發(fā)時(shí)， DOM樹是通過Virtual DOM構(gòu)造的智哀，并且次询，React在Virtual DOM上實(shí)現(xiàn)了DOM diff算法，當(dāng)數(shù)據(jù)更新時(shí)瓷叫，會通過diff算法計(jì)算出相應(yīng)的更新策略屯吊，盡量只對變化的部分進(jìn)行實(shí)際的瀏覽器的DOM更新，而不是直接重新渲染整個(gè)DOM樹赞辩，從而達(dá)到提高性能的目的雌芽。在保證性能的同時(shí)，使用React的開發(fā)人員就不必再關(guān)心如何更新具體的DOM元素辨嗽，而只需要數(shù)據(jù)狀態(tài)和渲染結(jié)果的關(guān)系世落。
傳統(tǒng)的diff算法通過循環(huán)遞歸來對節(jié)點(diǎn)進(jìn)行依次比較還計(jì)算一棵樹到另一棵樹的最少操作，算法復(fù)雜度為O(n^3)，其中n是樹中節(jié)點(diǎn)的個(gè)數(shù)屉佳。盡管這個(gè)復(fù)雜度并不好看谷朝，但是確實(shí)一個(gè)好的算法，只是在實(shí)際前端渲染的場景中武花，隨著DOM節(jié)點(diǎn)的增多圆凰，性能開銷也會非常大。而React在此基礎(chǔ)之上体箕，針對前端渲染的具體情況進(jìn)行了具體分析专钉，做出了相應(yīng)的優(yōu)化，從而實(shí)現(xiàn)了一個(gè)穩(wěn)定高效的diff算法累铅。
diff算法有如下三個(gè)策略：
DOM節(jié)點(diǎn)跨層級的移動操作發(fā)生頻率很低跃须，是次要矛盾；
擁有相同類的兩個(gè)組件將會生成相似的樹形結(jié)構(gòu)娃兽，擁有不同類的兩個(gè)組件將會生成不同的樹形結(jié)構(gòu)菇民，這里也是抓前者放后者的思想；
對于同一層級的一組子節(jié)點(diǎn)投储，通過唯一id進(jìn)行區(qū)分第练，即沒事就warn的key。
基于各自的前提策略玛荞，React也分別進(jìn)行了算法優(yōu)化娇掏，來保證整體界面構(gòu)建的性能。
虛擬DOM樹分層比較
兩棵樹只會對同一層次的節(jié)點(diǎn)進(jìn)行比較冲泥，忽略DOM節(jié)點(diǎn)跨層級的移動操作驹碍。React只會對相同顏色方框內(nèi)的DOM節(jié)點(diǎn)進(jìn)行比較壁涎，即同一個(gè)父節(jié)點(diǎn)下的所有子節(jié)點(diǎn)凡恍。當(dāng)發(fā)現(xiàn)節(jié)點(diǎn)已經(jīng)不存在，則該節(jié)點(diǎn)及其子節(jié)點(diǎn)會被完全刪除掉怔球，不會用于進(jìn)一步的比較嚼酝。這樣只需要對樹進(jìn)行一次遍歷，便能完成整個(gè)DOM樹的比較竟坛。由此一來闽巩，最直接的提升就是復(fù)雜度變?yōu)榫€型增長而不是原先的指數(shù)增長。
值得一提的是担汤，如果真的發(fā)生跨層級移動(如下圖)涎跨，例如某個(gè)DOM及其子節(jié)點(diǎn)進(jìn)行移動掛到另一個(gè)DOM下時(shí)，React是不會機(jī)智的判斷出子樹僅僅是發(fā)生了移動崭歧，而是會直接銷毀隅很，并重新創(chuàng)建這個(gè)子樹，然后再掛在到目標(biāo)DOM上率碾。從這里可以看出叔营，在實(shí)現(xiàn)自己的組件時(shí)屋彪，保持穩(wěn)定的DOM結(jié)構(gòu)會有助于性能的提升。事實(shí)上绒尊，React官方也是建議不要做跨層級的操作畜挥。因此在實(shí)際使用中，比方說婴谱，我們會通過CSS隱藏或顯示某些節(jié)點(diǎn)蟹但，而不是真的移除或添加DOM節(jié)點(diǎn)。其實(shí)一旦接受了React的寫法谭羔，就會發(fā)現(xiàn)前面所說的那種移動的寫法幾乎不會被考慮矮湘，這里可以說是React限制了某些寫法，不過遵守這些實(shí)踐確實(shí)會使得React有更好的渲染性能口糕。如果真的需要有移動某個(gè)DOM的情況缅阳，或許考慮考慮盡量用CSS3來替代會比較好吧。
關(guān)于這一部分的源碼景描，首先需要提到的是十办，React是如何控制“層”的。在許多源碼閱讀的文章里(搜到的講的比較細(xì)的一般都是兩三年前啦)超棺，都是說用一個(gè)updateDepth或者某種控制樹深的變量來記錄跟蹤向族。事實(shí)上就目前版本來看，已經(jīng)不是這樣了(如果我沒看錯(cuò)…)棠绘。ReactDOMComponent .updateComponent方法用來更新已經(jīng)分配并掛載到DOM上的DOM組件件相，并在內(nèi)部調(diào)用ReactDOMComponent._updateDOMChildren。而ReactDOMComponent通過_assign將ReactMultiChild.Mixin掛到原型上氧苍，獲得ReactMultiChild中定義的方法updateChildren（事實(shí)上還有updateTextContent等方法也會在不同的分支里被使用夜矗，React目前已經(jīng)對這些情形做了很多細(xì)化了）。ReactMultiChild包含著diff算法的核心部分让虐，接下來會慢慢進(jìn)行梳理紊撕。到這里我們暫時(shí)不必再繼續(xù)往下看，可以注意prevChildren和nextChildren這兩個(gè)變量赡突，當(dāng)然removedNodes对扶、mountImages也是意義比較明顯且很重要的變量：
prevChildren和nextChildren都是ReactElement，也就是virtual DOM惭缰，從它們的$$typeof: Symbol(react.element)就可看出浪南；removedNodes保存刪除的節(jié)點(diǎn)，mountImages則是保存對真實(shí)DOM的映射漱受，或者可以理解為要掛載的真實(shí)節(jié)點(diǎn)络凿，這些變量會隨著調(diào)用棧一層層往下作為參數(shù)傳下去并被修改和包裝。
而控制樹的深度的方法就是靠傳入nextNestedChildrenElements，把整個(gè)樹的索引一層層遞歸的傳下去喷众，同時(shí)傳入prevChildren這個(gè)虛擬DOM各谚，進(jìn)入_reconcilerUpdateChildren方法，會在里面通過flattenChildren方法（當(dāng)然里面還有個(gè)traverse方法）來訪問我們的子樹指針nextNestedChildrenElements到千，得到與prevChildren同層的nextChildren昌渤。然后ReactChildReconciler.updateChildren就會將prevChildren、nextChildren封裝成ReactDOMComponent類型憔四，并進(jìn)行后續(xù)比較和操作膀息。
至此，同層比較敘述結(jié)束了赵，后面會繼續(xù)討論針對組件的diff和對元素本身的diff潜支。
組件間的比較
參考官方文檔及其他資料，可以講組件間的比較策略總結(jié)如下：
如果是同類型組件柿汛，則按照原策略繼續(xù)比較virtual DOM樹冗酿；
如果不是，則將該組件判斷為dirty component络断，然后整個(gè)unmount這個(gè)組件下的子節(jié)點(diǎn)對其進(jìn)行替換裁替；
對于同類型組件，virtual DOM可能并沒有發(fā)生任何變化貌笨，這時(shí)我們可以通過shouldCompoenentUpdate鉤子來告訴該組件是否進(jìn)行diff弱判，從而提高大量的性能。
這里可以看出React再次抓了主要矛盾锥惋，對于不同組件但結(jié)構(gòu)相似的情形不再去關(guān)注昌腰，而是對相同組件、相似結(jié)構(gòu)的情形進(jìn)行diff算法膀跌，并提供鉤子來進(jìn)一步優(yōu)化遭商。可以說淹父，對于頁面結(jié)構(gòu)基本沒有變化的情況株婴，確實(shí)是有著很大的優(yōu)勢怎虫。
元素間的比較
這一節(jié)算是diff算法最核心的部分暑认，我會嘗試著對算法的思想進(jìn)行分析，并結(jié)合自己的demo來增進(jìn)理解大审。
例子很簡單蘸际，是一個(gè)涉及到新集合中有新加入的節(jié)點(diǎn)且老集合存在需要刪除的節(jié)點(diǎn)的情形。如下圖所示徒扶。
也就是說粮彤，通過點(diǎn)擊來控制文字和數(shù)字的顯示與消失。這種JSX可以說是太常用了。正好借學(xué)習(xí)diff算法的機(jī)會导坟，來看看就這種最基本的結(jié)構(gòu)屿良，React是怎么做的。
首先先在ReactMultiChild中的_updateChildren中打上第一個(gè)debugger惫周。
斷點(diǎn)之前的代碼會得到prevChildren和nextChildren尘惧，他們經(jīng)過處理會從ReactElement數(shù)組變成一個(gè)奇怪的對象，key為“.0”递递、“.1”這樣的帶點(diǎn)序號(這里不妨先多說一句喷橙，這是React為一個(gè)個(gè)組件們默認(rèn)分配的key，如果這里我強(qiáng)行設(shè)置一個(gè)key給h2h3標(biāo)簽登舞，那么它就會擁有如’$123’這樣的key)贰逾，值為ReactDOMComponent 組件，前面寫初次渲染的文章中提到過ReactDOMComponent就是最終渲染到DOM之前的那一環(huán)菠秒。而在本demo中疙剑，prevChildren存放著“哈哈哈的h1標(biāo)簽”和“142567的h3標(biāo)簽”，而nextChildren存放著“哈哈哈的h1標(biāo)簽”和“你好啊的h2標(biāo)簽”践叠。
先不看若干index變量核芽，看到for循環(huán)的in寫法，即可明白是在遍歷存放了新的ReactDOMComponent的對象酵熙，并且通過hasOwnProperty來過濾掉原型上的屬性和方法轧简。接著各自拿到同層節(jié)點(diǎn)的第一個(gè)，并對二者進(jìn)行比較匾二。如果相同哮独，則enqueue一個(gè)moveChild方法返回的type為MOVE_EXISTING的對象到updates里，即把更新放入一個(gè)隊(duì)列察藐，moveChild也就是移動已有節(jié)點(diǎn)皮璧，但是是否真的移動會根據(jù)整體diff算法的結(jié)果來決定(本例當(dāng)然是沒移動了)，然后修改若干index量分飞；否則悴务，就會計(jì)算一堆index(這里其實(shí)是算法的核心，此處先不細(xì)說)譬猫，然后再次enqueue一個(gè)update讯檐，事實(shí)上是一個(gè)type屬性為INSERT_MARKUP的對象。對于本例而言染服，h1標(biāo)簽不變别洪，則會先來一個(gè)MOVE_EXISTING對象，然后h3變h2柳刮，再來一個(gè)INSERT_MARKUP挖垛，然后通過ReactReconciler.getHostNode根據(jù)nextChild得到真實(shí)DOM痒钝。
這個(gè)for-in結(jié)束后，則是會把需要刪除的節(jié)點(diǎn)用enqueue的方法繼續(xù)入隊(duì)unmount操作痢毒，這里this._unmountChild返回的是REMOVE_NODE對象送矩，至此，整個(gè)更新的diff流程就走完了哪替，而updates保存了全部的更新隊(duì)列益愈，最終由processQueue來挨個(gè)執(zhí)行更新。
那么細(xì)節(jié)在哪里夷家？慢慢來蒸其。
首先，React為同層節(jié)點(diǎn)比較提供了若干操作库快。早期版本有INSERT_MARKUP摸袁、MOVE_EXISTING、REMOVE_NODE這三個(gè)增义屏、移靠汁、刪操作，現(xiàn)在又加入了SET_MARKUP和TEXT_CONTENT這倆操作闽铐。
INSERT_MARKUP蝶怔，新的component類型(nextChildren里的)不在老集合(prevChildren)里，即是全新的節(jié)點(diǎn)兄墅，需要對新節(jié)點(diǎn)執(zhí)行插入操作踢星；
MOVE_EXISTING，在老集合有新component類型隙咸，且element是可更新的類型沐悦，這種情況下prevChild===nextChild，就需要做移動操作五督，可以復(fù)用以前的DOM節(jié)點(diǎn)藏否。
REMOVE_NODE，老component類型在新集合里也有充包，但對應(yīng)的element不同則不能直接復(fù)用和更新副签，需要執(zhí)行刪除操作；或者老component不在新集合里的基矮，也需要執(zhí)行刪除操作淆储。
所有的操作都會通過enqueue來入隊(duì)，把更新細(xì)節(jié)隱藏愈捅，而如何判斷做出何種更新操作遏考，則是diff算法之所在。我們回到前面的代碼重新再看蓝谨，并分情況討論其中的原理灌具。
代碼分析
首先對新集合的節(jié)點(diǎn)(nextChildren)進(jìn)行in循環(huán)遍歷，通過唯一的key(這里是變量name譬巫，前面提到過nextChildren和prevChildren是以對象的形式存儲ReactDOMComponent的)可以取得新老集合中相同的節(jié)點(diǎn)咖楣，如果不存在，prevChildren即為undefined芦昔。根據(jù)圖中代碼诱贿，如果存在相同節(jié)點(diǎn)，也即prevChild === nextChild咕缎，則進(jìn)行移動操作珠十，但在移動前需要將當(dāng)前節(jié)點(diǎn)在老集合中的位置與 lastIndex 進(jìn)行比較，見moveChild函數(shù)凭豪，如下圖：
if (child._mountIndex < lastIndex)焙蹭，則進(jìn)行節(jié)點(diǎn)移動操作，否則不執(zhí)行該操作嫂伞。這是一種順序優(yōu)化手段孔厉，lastIndex一直在更新，表示訪問過的節(jié)點(diǎn)在老集合中最右的位置（即最大的位置）帖努，如果新集合中當(dāng)前訪問的節(jié)點(diǎn)比lastIndex大撰豺，說明當(dāng)前訪問節(jié)點(diǎn)在老集合中就比上一個(gè)節(jié)點(diǎn)位置靠后，則該節(jié)點(diǎn)不會影響其他節(jié)點(diǎn)的位置拼余，因此不用添加到差異隊(duì)列中污桦，即不執(zhí)行移動操作，只有當(dāng)訪問的節(jié)點(diǎn)比lastIndex小時(shí)匙监，才需要進(jìn)行移動操作寡润。
新老集合節(jié)點(diǎn)相同、只需要移動的情形
圖是直接拷來的…畫那么好我就不重復(fù)畫輪子了舅柜。還是源碼梭纹，就按上面的圖來講。
源碼中會開始對nextChildren(即新的節(jié)點(diǎn)狀態(tài) 對象形式)進(jìn)行遍歷致份，并且對象本身是以鍵值對的形式存儲這些節(jié)點(diǎn)的狀態(tài)变抽。首先，key=’b’時(shí)氮块，通過prevChildren[name]的方式(name即為key)取老集合節(jié)點(diǎn)中是否存在key為b的節(jié)點(diǎn)绍载，顯然，如果存在滔蝉，則取得击儡，不存在，則為undefined蝠引。然后阳谍，判斷是否相等蛀柴。當(dāng)我們兩個(gè)key值相同的B節(jié)點(diǎn)被判定相等時(shí)，enqueue一個(gè)’ MOVE_EXISTING’操作矫夯。這一操作內(nèi)部會作如下判斷：
child即為prevChild鸽疾，也就是判斷B._mountIndex < lastIndex，lastIndex是prevChildren最近訪問的最新index训貌，初始為0(其實(shí)因?yàn)檫@些個(gè)children都是對象制肮，所以index更多的是計(jì)數(shù)而非下標(biāo))。這里递沪，B._mountIndex=1豺鼻，lastIndex為0，所以不做移動操作更新款慨。然后更新lastIndex儒飒，如下圖所示：
我們知道prevChild就是B，則prevChild._mountIndex如前所示為1樱调，所以lastIndex更新為1约素，這樣lastIndex就可以記錄著prevChildren中最后訪問的那個(gè)的序號。再然后笆凌，更新B的位置為信集合中的位置：
nextIndex隨著nextChildren中遍歷的子元素遞增圣猎，此時(shí)為1，也就是說乞而，把B的掛載位置設(shè)置為0送悔，就相當(dāng)于告訴B你的位置從1移動到了0。
最后更新nextIndex爪模，準(zhǔn)備為下一個(gè)放在位置1的元素準(zhǔn)備序號欠啤。這里getHostNode方法會返回一個(gè)真正的DOM，它主要是給enqueue使用屋灌，可以理解為開始執(zhí)行更新隊(duì)列時(shí)能讓React知道這些更新的節(jié)點(diǎn)要放到的DOM的位置洁段。
第二輪，從新集合取到A共郭，判斷到老集合中存在相同節(jié)點(diǎn)祠丝，同樣是對比位置來判斷是否進(jìn)行移動操作。只不過除嘹，這一次A._mountIndex=0,lastIndex在上一輪更新為1写半，滿足child._mountIndex
其中toIndex就是nextIndex，目前為1尉咕，很正確嘛叠蝇。然后繼續(xù)更新lastIndex為1，并更新A._mountIndex=1年缎，然后后續(xù)基本一致悔捶。
剩下兩輪判斷铃慷，不出上述情形。在此不再細(xì)表炎功。
存在需要插入枚冗、刪除節(jié)點(diǎn)的情形
還是拿了大佬的圖缓溅，哈哈蛇损。這里其實(shí)就是更完整的情形，也就會涉及到整個(gè)代碼流程坛怪，當(dāng)然也并不復(fù)雜淤齐。
首先，還是從新集合先取到B袜匿，判斷出老集合中有B更啄，于是本輪與上面的第一輪就一樣了（同一段代碼嘛）。
第二輪居灯，從新集合取到E祭务，但是老集合中不存在，于是走入新流程：
講白了怪嫌，就是enqueue來創(chuàng)建節(jié)點(diǎn)到指定位置义锥，然后更新E的位置，并nextIndex++來進(jìn)入下一個(gè)節(jié)點(diǎn)的執(zhí)行岩灭。
第三輪拌倍，從新集合取到C，C在老集合中有噪径，但是判斷之后并不進(jìn)行移動操作柱恤，繼續(xù)各種更新然后進(jìn)入下一個(gè)節(jié)點(diǎn)的判斷。
第四輪找爱，從新集合中取到A梗顺，A也存在，所以enqueue移動操作车摄。
至此寺谤，diff已經(jīng)完成，這之后會對removedNodes進(jìn)行循環(huán)遍歷练般，這個(gè)對象是在this._reconcilerUpdateChildren就對比新老集合得到的矗漾。
這樣一來，新集合中不存在的D也就被清除了薄料。整體上看敞贡，是先創(chuàng)建，后刪除的方式摄职。
Ok誊役，差不多啦获列，diff算法的核心就是這么回事啦。
總結(jié)
通過diff策略蛔垢，將算法從O(n^3)簡化為O(n)
分層求異击孩，對tree diff進(jìn)行優(yōu)化
分組件求異，相同類生成相似樹形結(jié)構(gòu)鹏漆、不同類生成不同樹形結(jié)構(gòu)巩梢，對component diff進(jìn)行優(yōu)化
設(shè)置key，對element diff進(jìn)行優(yōu)化
盡量保持穩(wěn)定的DOM結(jié)構(gòu)艺玲、避免將最后一個(gè)節(jié)點(diǎn)移動到列表首部括蝠、避免節(jié)點(diǎn)數(shù)量過大或更新過于頻繁
