基于Dom Diff算法分析React刷新機(jī)制

嚴(yán)新巧　白俊峰

摘要：React組件化思想為開(kāi)發(fā)者前端開(kāi)發(fā)提供了新的思路，由于React的Visual Dom讓開(kāi)發(fā)者不用擔(dān)心刷新頁(yè)面帶來(lái)渲染方面性能問(wèn)題，而Visual Dom的核心算法就是React Diff算法，它確保只對(duì)界面上需要刷新的部分進(jìn)行刷新，讓開(kāi)發(fā)者只需關(guān)注于業(yè)務(wù)本身。該文基于對(duì)React Diff算法的研究來(lái)分析React組件的生命周期，理解Virtual Dom的核心算法，方便以后React程序優(yōu)化。

關(guān)鍵詞：React組件；虛擬Dom算法；渲染

中圖分類號(hào)：TP312 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2017）18-0076-03

1背景介紹

對(duì)于動(dòng)態(tài)網(wǎng)站，需要經(jīng)常對(duì)網(wǎng)頁(yè)的元素進(jìn)行操作，一般通過(guò)Dom樹(shù)結(jié)點(diǎn)的操作來(lái)更新界面，對(duì)于一些比較復(fù)雜的界面，需頻繁操作Dom結(jié)點(diǎn)會(huì)導(dǎo)致性能問(wèn)題，并且對(duì)開(kāi)發(fā)者而言，增加了開(kāi)發(fā)的難度?；诖耍琑eact專門實(shí)現(xiàn)了一套Visual Dom機(jī)制?；赗eact開(kāi)發(fā)程序的操作都是通過(guò)內(nèi)置的Visual Dom來(lái)實(shí)現(xiàn)，當(dāng)有數(shù)據(jù)狀態(tài)發(fā)生改變時(shí)，會(huì)將前后兩個(gè)Dom樹(shù)進(jìn)行對(duì)比，對(duì)比后的結(jié)果只對(duì)有區(qū)別的部分進(jìn)行更新?；谝恍┎呗?，React能更好地處理Dom樹(shù)發(fā)生改變的部分。

Visual Dom的核心算法就是React Diff，它通過(guò)算法的優(yōu)化，讓Dom樹(shù)的更新不再是難題，這也讓開(kāi)發(fā)者不用擔(dān)心由于Dom結(jié)點(diǎn)更新而導(dǎo)致的性能問(wèn)題，通過(guò)計(jì)算出每次更新的Dom結(jié)點(diǎn)，只需要對(duì)局部進(jìn)行操作就可以渲染出界面，這樣保證了更新的效率。

2傳統(tǒng)的Diff算法與Virtual Dom算法介紹

傳統(tǒng)web應(yīng)用，一般是直接更新DOM操作，但是DOM更新通常比較昂貴。React為盡可能減少對(duì)DOM的操作，提供一種不同且強(qiáng)大的方式來(lái)更新DOM，從而代替直接DOM操作。Vir-tual DOM，一個(gè)輕量級(jí)虛擬的DOM，是React抽象出來(lái)的一個(gè)對(duì)象，描述DOM的樣子，以及如何呈現(xiàn)。通過(guò)Virtual DOM更新真實(shí)DOM，由VirtualDOM管理真實(shí)DOM的更新。

Virtual DOM操作更新更快，因?yàn)镽eact的diff算法如圖1，更新Virtual DOM并不一定立即影響真實(shí)DOM，React會(huì)等到事件循環(huán)結(jié)束，然后利用diff算法，通過(guò)當(dāng)前新DOM表述與之前的作比較，計(jì)算出最少步驟更新真實(shí)DOM。

對(duì)于一次刷新操作，傳統(tǒng)的計(jì)算方法是通過(guò)循環(huán)遞歸進(jìn)行一一對(duì)比，從而分析出需要改變的Dom樹(shù)，其中的算法復(fù)雜度是O（n³），這就意味著如果對(duì)1000個(gè)節(jié)點(diǎn)進(jìn)行比較的話，傳統(tǒng)算法就需要進(jìn)行十億次操作。

傳統(tǒng)diff算法的復(fù)雜度為O（n³），顯然這無(wú)法滿足性能要求。React通過(guò)制定策略，將O（n³）復(fù)雜度轉(zhuǎn)換成0（n）復(fù)雜度。

由于傳統(tǒng)算法的復(fù)雜度無(wú)法滿足性能要求，而React通過(guò)算法的優(yōu)化，將指數(shù)的復(fù)雜度變成線性的復(fù)雜度，因?yàn)镈om樹(shù)在應(yīng)用中具有以下特點(diǎn)，才讓Visual Dom得以實(shí)現(xiàn)：

1）對(duì)于一些節(jié)點(diǎn)操作來(lái)說(shuō)，Dom結(jié)點(diǎn)之間的跨層操作是非常少的

2）對(duì)于同一個(gè)類生成相同Dom的樹(shù)形結(jié)構(gòu)，不同的類生成不同的Dom樹(shù)結(jié)構(gòu)。

3）對(duì)于同一層次的子結(jié)點(diǎn)，他們的ID是不一樣的

3Diff策略分析

基于以上三個(gè)Dom的特點(diǎn)，React分別用三種不同的算法tree diff、component diff以及element diff進(jìn)行Visual Dom操作。

3.1treediff策略

對(duì)于特點(diǎn)1，React采用了tree diff算法，因?yàn)楦露际腔谕粚哟蔚慕Y(jié)點(diǎn)進(jìn)行比較，即每一次只對(duì)同一層次的節(jié)點(diǎn)進(jìn)行比較。這樣的操作對(duì)于Dom而言操作較少，React通過(guò)updat-eDepth算法來(lái)對(duì)Virtual Dom進(jìn)行比較，即它會(huì)對(duì)同一個(gè)父結(jié)點(diǎn)進(jìn)行子結(jié)點(diǎn)比較，當(dāng)發(fā)現(xiàn)節(jié)點(diǎn)不存在了，則把該節(jié)點(diǎn)以及子結(jié)點(diǎn)都刪除，通過(guò)這個(gè)算法，只需要一次遍歷操作就可以完成對(duì)整個(gè)Dom樹(shù)的比較。

下面通過(guò)一個(gè)例子來(lái)說(shuō)明這種情況，如圖2，需要將A結(jié)點(diǎn)以及A下面的結(jié)點(diǎn)移到到D結(jié)點(diǎn)下，由于React只對(duì)同一層次的結(jié)點(diǎn)考慮位置變換，所以對(duì)于這種情況，就會(huì)存在著創(chuàng)建與刪除的操作。當(dāng)根結(jié)點(diǎn)發(fā)現(xiàn)A結(jié)點(diǎn)消失后，就會(huì)直接刪除A，而當(dāng)發(fā)現(xiàn)D多了一個(gè)結(jié)點(diǎn)后，就會(huì)在D下面創(chuàng)建結(jié)點(diǎn)與子結(jié)點(diǎn)，所以它們的執(zhí)行順序是：create A→create B→create C→de-leteA。

由上面例子說(shuō)明，當(dāng)節(jié)點(diǎn)出現(xiàn)跨層次的移動(dòng)時(shí)，是通過(guò)創(chuàng)建與刪除操作來(lái)執(zhí)行的，這樣比較影響性能，所以在使用React開(kāi)發(fā)的時(shí)候盡量不要使用這個(gè)跨層次操作，如果在實(shí)際應(yīng)用中必須有此需求，建議采用CSS隱藏或者顯示節(jié)點(diǎn)操作。

3.2 component diff算法

對(duì)同一個(gè)組件更新時(shí)，如果內(nèi)部沒(méi)有發(fā)生變化，則繼續(xù)后面的更新，同時(shí)React也會(huì)提供特定的算法來(lái)進(jìn)行組件更新。若非同一個(gè)類型的組件，則會(huì)將該組件判斷為dirty組件，會(huì)直接替換組件下的所有節(jié)點(diǎn)如圖3。

當(dāng)結(jié)點(diǎn)D需要替換成結(jié)點(diǎn)G時(shí)，即使他們的結(jié)構(gòu)很類似，并且子結(jié)點(diǎn)都相同，但是React還是會(huì)直接刪除結(jié)點(diǎn)D，并且重新創(chuàng)建結(jié)點(diǎn)G，而不是直接進(jìn)行簡(jiǎn)單的替換。雖然這種算法會(huì)影響性能，但是對(duì)于這種情況相對(duì)較少，React沒(méi)有進(jìn)行優(yōu)化，因?yàn)樵趯?shí)際應(yīng)用中很難因?yàn)榇瞬僮鞫绊懙叫阅軉?wèn)題。

3.3 element diff

React對(duì)同一層次結(jié)點(diǎn)進(jìn)行大量的操作，因?yàn)榛诖瞬僮鞯那闆r最多，React會(huì)提供三種不同節(jié)點(diǎn)的操作：IN-SERT_MARKUP（插入）、MOVE_EXISTING（移動(dòng)）和RE-MOVE_NODE（刪除）。

如果是全新的節(jié)點(diǎn)，則直接進(jìn)行插入操作，而如果是可以移動(dòng)的操作，則復(fù)用以前的操作，如果不能直接進(jìn)行復(fù)用與更新操作，則進(jìn)行刪除操作。

如圖4，如果之前的Dom樹(shù)上包含結(jié)點(diǎn)ABCD，更新后的順序?yàn)锽ADC，這個(gè)時(shí)候就會(huì)進(jìn)行diff差異化比較，發(fā)現(xiàn)新的結(jié)點(diǎn)是B，這時(shí)會(huì)先刪除A，再插入B，然后刪除BCD，插入ADC，由些可見(jiàn)，這個(gè)操作也是比較繁瑣，并且沒(méi)有效率，執(zhí)行移動(dòng)操作會(huì)比執(zhí)行插入與刪除有效率得多，React針對(duì)這種情況提出了優(yōu)化操作，允許對(duì)同一層次的同一個(gè)位置的結(jié)點(diǎn)，通過(guò)不同的Key來(lái)進(jìn)行區(qū)分。

如圖5，與上例相同，對(duì)新老集合的節(jié)點(diǎn)進(jìn)行diff差異化對(duì)比，通過(guò)key值來(lái)發(fā)現(xiàn)新老Dom組的節(jié)點(diǎn)都是相同結(jié)點(diǎn)，所以不需要進(jìn)行刪除與創(chuàng)建操作，只需進(jìn)行簡(jiǎn)單的移動(dòng)操作就可以達(dá)到目標(biāo)。下面通過(guò)源碼進(jìn)行詳細(xì)分析利用diff達(dá)到上述操作。

首先對(duì)新老Dom樹(shù)的節(jié)點(diǎn)進(jìn)行一次循環(huán)遍歷，通過(guò)唯一的key值來(lái)判斷新老Dom樹(shù)的節(jié)點(diǎn)是否相同。如果結(jié)點(diǎn)相同，則進(jìn)行移動(dòng)操作，但在移動(dòng)操作之前會(huì)將當(dāng)前節(jié)點(diǎn)順序與最后一個(gè)結(jié)點(diǎn)順序進(jìn)行比較，若非最后一個(gè)節(jié)點(diǎn)，才會(huì)進(jìn)行移動(dòng)操作。

以上圖5為例，更為清晰直觀描述diff差異對(duì)比過(guò)程：

從新集合中取得B，判斷老集合中存在相同節(jié)點(diǎn)B，通過(guò)對(duì)比節(jié)點(diǎn)位置判斷是否進(jìn)行移動(dòng)操作，B在老集合中的位置B._mountlndex=1，此時(shí)lastIndex=0，不滿足child._mountIn-dex

從新集合中取得A，判斷老集合中存在相同節(jié)點(diǎn)A，通過(guò)對(duì)比節(jié)點(diǎn)位置判斷是否進(jìn)行移動(dòng)操作，A在老集合中的位置A.mountlndex=0，此時(shí)lastIndex=1，滿足child._mountIndex

從新集合中取得D，判斷老集合中存在相同節(jié)點(diǎn)D，通過(guò)對(duì)比節(jié)點(diǎn)位置判斷是否進(jìn)行移動(dòng)操作，D在老集合中的位置D._mountIndex=3，此時(shí)lastIndex=1，不滿足child._mountIn-dex

從新集合中取得C，判斷老集合中存在相同節(jié)點(diǎn)C，通過(guò)對(duì)比節(jié)點(diǎn)位置判斷是否進(jìn)行移動(dòng)操作，C在老集合中的位置c._mountIndex=2，此時(shí)lastIndex=3，滿足child._mountIndex

以上情況主要針對(duì)新老Dom存在節(jié)點(diǎn)相同，但位置不同時(shí)進(jìn)行的移動(dòng)操作，而當(dāng)新集合中存在新的節(jié)點(diǎn)插入并且需要執(zhí)行刪除操作時(shí)，需要進(jìn)行diff操作。

如圖6，新的Dom在判斷第一個(gè)節(jié)點(diǎn)是B時(shí)，會(huì)在老Dom里去查找是否有B，而B(niǎo)在老集合的位置序號(hào)是1，因?yàn)楫?dāng)前判斷節(jié)點(diǎn)是0，所以不需要進(jìn)行移動(dòng)操作，更新當(dāng)前節(jié)點(diǎn)位置為1，并將B的位置序號(hào)改為0，這樣依次循環(huán)。

從新集合中取得E，判斷老集合中不存在相同節(jié)點(diǎn)E，則創(chuàng)建新節(jié)點(diǎn)E；更新lastIndex=1，并將E的位置更新為新集合中的位置，nextIndex++進(jìn)入下一個(gè)節(jié)點(diǎn)的判斷。

依次進(jìn)行上述操作，對(duì)所有的結(jié)點(diǎn)進(jìn)行Diff操作后，最后需要對(duì)老Dom樹(shù)進(jìn)行遍歷操作，判斷是否有刪除操作，在上述例子中，需要?jiǎng)h除D，至此所有操作完成。

4總結(jié)

React通過(guò)模擬一個(gè)新的Visual Dom來(lái)解決更新問(wèn)題，從而將復(fù)雜度為O（n³）轉(zhuǎn)換成線性復(fù)雜度問(wèn)題，這樣非常適合處理一些復(fù)雜的應(yīng)用場(chǎng)景。但通過(guò)算法的具體分析發(fā)現(xiàn)，在寫(xiě)React時(shí)應(yīng)該盡量保持Dom樹(shù)的結(jié)構(gòu)，并盡量減少大范圍的移動(dòng)結(jié)點(diǎn)操作，從而使得React的渲染能力達(dá)到最優(yōu)。

5結(jié)束語(yǔ)

本文通過(guò)對(duì)React的Diff算法分析，深入剖析了Visual dom的更新原則，這讓開(kāi)發(fā)者在寫(xiě)代碼時(shí)無(wú)需關(guān)心這部分內(nèi)容，而只需注重業(yè)務(wù)邏輯問(wèn)題，從而簡(jiǎn)化了開(kāi)發(fā)過(guò)程。正是由于第2節(jié)中提到的Dom的三個(gè)基本特性，使得算法得以實(shí)現(xiàn)。通過(guò)對(duì)算法的深入研究，對(duì)今后React開(kāi)發(fā)優(yōu)化有了深入的理論基礎(chǔ)。