0 前言

React的VirtualDOM可謂是前端領(lǐng)域中革命性的創(chuàng)新谢谦，而高效的Diff算法又極大的優(yōu)化了狀態(tài)的對(duì)比，不同的狀態(tài)對(duì)應(yīng)的就是不同的UI界面窟绷。本文將簡(jiǎn)要介紹Diff算法中的精華脖咐。

1 Diff算法

1.1背景

"樹(shù)"是一種常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)，對(duì)比"樹(shù)"的結(jié)構(gòu)在計(jì)算機(jī)相關(guān)相關(guān)領(lǐng)域有廣泛的應(yīng)用拂酣。具體到前端開(kāi)發(fā)而言，Web的UI界面就是由DOM樹(shù)構(gòu)成仲义，DOM作為一種有序樹(shù)結(jié)構(gòu)婶熬，當(dāng)DOM樹(shù)結(jié)構(gòu)發(fā)生變化時(shí)，瀏覽器會(huì)重新解析渲染DOM樹(shù)埃撵。造成有序樹(shù)的節(jié)點(diǎn)變化的基本操作方式有三種：重標(biāo)記(relabel)赵颅，刪除(delete)和插入(insert)，如下圖自上而下所示暂刘。

重標(biāo)記(relabel L1 to L2)

重標(biāo)記

刪除節(jié)點(diǎn)(delete node L2)

刪除節(jié)點(diǎn)

插入節(jié)點(diǎn)(insert L2 to L1)

插入節(jié)點(diǎn)

1.2 標(biāo)準(zhǔn)的Diff算法

標(biāo)準(zhǔn)的Tree-Diff算法饺谬，使用了嚴(yán)謹(jǐn)?shù)拇鷥r(jià)函數(shù)(Cost Function)，適用于很多需要樹(shù)結(jié)構(gòu)對(duì)比的場(chǎng)景谣拣，如：計(jì)算生物學(xué)募寨、圖像分析、結(jié)構(gòu)化文本數(shù)據(jù)庫(kù)等森缠。然而其算法的時(shí)間復(fù)雜度為O(n^3)拔鹰，在瀏覽器環(huán)境中，要達(dá)到每次更新都可以整體刷新界面的目的贵涵，這樣高的算法復(fù)雜度會(huì)有性能問(wèn)題列肢。

2 React Diff算法（reconciliation algorithm）

React開(kāi)發(fā)團(tuán)隊(duì)結(jié)合Web界面的特點(diǎn)對(duì)標(biāo)準(zhǔn)的Diff算法做出了優(yōu)化恰画，使得其時(shí)間復(fù)雜度降低為O(n)。這一算法例书，即reconciliation algorithm锣尉，常見(jiàn)中文翻譯為“協(xié)調(diào)算法”，個(gè)人更傾向于“權(quán)衡算法”這一更形象的翻譯决采，因?yàn)樵撍惴ㄋ鶎?shí)現(xiàn)的就是權(quán)衡利弊之后的簡(jiǎn)化自沧。這種算法的基本假設(shè)如下：

• Web UI中DOM節(jié)點(diǎn)跨層級(jí)的移動(dòng)操作較少，可以忽略树瞭。
• 兩個(gè)相同組件產(chǎn)生類似的DOM結(jié)構(gòu)拇厢，不同的組件產(chǎn)生不同的DOM結(jié)構(gòu)。
• 對(duì)于同一層次的一組相同類型的子節(jié)點(diǎn)晒喷，它們可以通過(guò)唯一的key進(jìn)行區(qū)分孝偎。

2.1 單一節(jié)點(diǎn)對(duì)比

為了對(duì)比兩個(gè)樹(shù)結(jié)構(gòu)，需要先能夠比較兩個(gè)節(jié)點(diǎn)凉敲，在React中就是Virtual DOM樹(shù)(以下簡(jiǎn)稱“VD樹(shù)”)的節(jié)點(diǎn)衣盾，而VD樹(shù)節(jié)點(diǎn)的不同又分兩種情況：

• 節(jié)點(diǎn)類型不同
• 節(jié)點(diǎn)類型相同但屬性(props)不同

2.1.1 節(jié)點(diǎn)類型不同

當(dāng)VD樹(shù)中同一節(jié)點(diǎn)位置前后節(jié)點(diǎn)類型不同時(shí)，React直接刪除舊的節(jié)點(diǎn)爷抓，然后創(chuàng)建并插入新的節(jié)點(diǎn)势决，使用的節(jié)點(diǎn)基本操作方法為刪除和插入。

renderA: <OldNode />
renderB: <NewNode />
=> [removeNode <OldNode />], [insertNode <NewNode />]

在React組建的生命周期方法中蓝撇，老節(jié)點(diǎn)OldNode的componentWillUnmount()方法最先觸發(fā)果复，之后新節(jié)點(diǎn)NewNode的componentWillMount()和componentDidMount()方法依次觸發(fā)。

2.1.2 節(jié)點(diǎn)類型相同但屬性不同

節(jié)點(diǎn)類型相同但屬性不同的情況下渤昌，React會(huì)對(duì)VD數(shù)節(jié)點(diǎn)的屬性進(jìn)行重設(shè)虽抄，從而實(shí)現(xiàn)節(jié)點(diǎn)的轉(zhuǎn)換，使用的節(jié)點(diǎn)基本操作方法為重標(biāo)記独柑。因?yàn)镽eact組件的實(shí)例保持不變迈窟，該組件的state也會(huì)保持不變，組件的componentWillReceiveProps()忌栅、componentWillUpdate()菠隆、render()方法依次觸發(fā)。

renderA: <Node className="old" />
renderB: <Node className="new" />
=> [replaceAttribute className "new"]

VD樹(shù)節(jié)點(diǎn)的style屬性稍有不同狂秘，因?yàn)閭魅氲氖菍?duì)象而不是字符串，React會(huì)只更新改變了的樣式屬性躯肌。

如果開(kāi)發(fā)者能夠明確節(jié)點(diǎn)是否有變化者春，則可以通過(guò)shouldComponentUpdate(nextProp, nextState)方法來(lái)決定是否進(jìn)行Diff運(yùn)算。

2.2 逐層進(jìn)行節(jié)點(diǎn)對(duì)比（分層求異）

React只會(huì)對(duì)同一層級(jí)（下圖中相同顏色方框內(nèi)）的DOM節(jié)點(diǎn)進(jìn)行比較清女，即同一個(gè)父節(jié)點(diǎn)下的所有子節(jié)點(diǎn)钱烟。如果發(fā)現(xiàn)已經(jīng)不存在的節(jié)點(diǎn)，則該節(jié)點(diǎn)及其子節(jié)點(diǎn)會(huì)被完全刪除掉，不再作進(jìn)一步的比較拴袭。這樣只需要對(duì)樹(shù)進(jìn)行一次遍歷读第，便能完成整個(gè)DOM樹(shù)的比較。這一方法正是基于前一假設(shè)拥刻，即不同類型的組件產(chǎn)生不同的VD樹(shù)結(jié)構(gòu)怜瞒。

逐層進(jìn)行節(jié)點(diǎn)對(duì)比

例如，在下圖的VD樹(shù)結(jié)構(gòu)轉(zhuǎn)換過(guò)程中般哼，看似應(yīng)該是把整個(gè)A節(jié)點(diǎn)從根節(jié)點(diǎn)插入到D節(jié)點(diǎn)中吴汪，最直觀的操作方式應(yīng)該是：

Root.remove(A).find(D).append(A)

然而，React的“權(quán)衡算法”只會(huì)簡(jiǎn)單對(duì)比同一層級(jí)的節(jié)點(diǎn)蒸眠，不同層級(jí)的節(jié)點(diǎn)只有刪除和插入漾橙。所以，React實(shí)際的操作方式卻是直接刪除節(jié)點(diǎn)A楞卡，至于A的子節(jié)點(diǎn)B和C則直接被忽略了霜运；而當(dāng)發(fā)現(xiàn)D節(jié)點(diǎn)多了一個(gè)子節(jié)點(diǎn)A時(shí)，則會(huì)插入一個(gè)新的節(jié)點(diǎn)A作為自己點(diǎn)蒋腮。過(guò)程如下：

A.destroy();
A = new A();
A.append(new B());
A.append(new C());
D.append(A);

這樣的操作看似是把簡(jiǎn)單的問(wèn)題變得復(fù)雜了淘捡，在這一例子中的確如此，畢竟根據(jù)NFL定理(no free lunch theorem)徽惋，任何優(yōu)化都是有代價(jià)的案淋，Reconciliation algorithm也不例外。之所以稱之為“權(quán)衡算法”险绘，也正是因?yàn)檫@一方法以忽略不同類型節(jié)點(diǎn)的子節(jié)點(diǎn)的對(duì)比為代價(jià)踢京，進(jìn)而大大降低了Diff算法的時(shí)間復(fù)雜度。

鑒于這一情況宦棺，為提高性能瓣距，應(yīng)盡量避免進(jìn)行DOM節(jié)點(diǎn)跨層級(jí)的操作。此外代咸，保持穩(wěn)定的DOM結(jié)構(gòu)也有助于性能提升蹈丸，可以通過(guò)類名和CSS來(lái)控制節(jié)點(diǎn)的顯示隱藏。

2.3 列表節(jié)點(diǎn)的對(duì)比

2.1和2.2中分別介紹了React diff算法對(duì)單一節(jié)點(diǎn)呐芥，和不在同一層中的節(jié)點(diǎn)的對(duì)比方式逻杖。與前兩者不同的是，一組列表節(jié)點(diǎn)往往有相同的類型和屬性思瘟，此外荸百，列表節(jié)點(diǎn)的常見(jiàn)操作包含插入、刪除和排序滨攻。如果每個(gè)列表節(jié)點(diǎn)沒(méi)有唯一標(biāo)識(shí)够话，則React無(wú)法識(shí)別每一個(gè)節(jié)點(diǎn)蓝翰，那么只能更新所有列表節(jié)點(diǎn)造成效率低下。

例如女嘲，要在下圖的列表節(jié)點(diǎn)B和C中間插入節(jié)點(diǎn)F畜份，如果React無(wú)法識(shí)別每一個(gè)節(jié)點(diǎn)，則只能依次更新所有節(jié)點(diǎn)欣尼，如果節(jié)點(diǎn)數(shù)量很大爆雹，會(huì)有明顯的性能損耗。

這時(shí)媒至，“key”這個(gè)屬性就要登場(chǎng)了顶别，React通過(guò)key這個(gè)屬性發(fā)現(xiàn)更新前后相同的列表節(jié)點(diǎn)，因此無(wú)需進(jìn)行相同節(jié)點(diǎn)刪除和創(chuàng)建拒啰，只需要將舊的節(jié)點(diǎn)的位置進(jìn)行移動(dòng)驯绎。如果有舊的節(jié)點(diǎn)被刪除或新的節(jié)點(diǎn)被插入，也不會(huì)造成其他節(jié)點(diǎn)被重新創(chuàng)建谋旦。
再上圖的例子中剩失，React會(huì)通過(guò)每個(gè)節(jié)點(diǎn)的唯一標(biāo)識(shí)(key)，準(zhǔn)確找到插入新節(jié)點(diǎn)F的位置册着，同時(shí)保留其他節(jié)點(diǎn)拴孤。

3 總結(jié)

• React Diff 通過(guò)“權(quán)衡算法”司顿，把復(fù)雜度O(n^3)的問(wèn)題轉(zhuǎn)化為復(fù)雜度O(n)的問(wèn)題芒粹；
• 通過(guò)”分層求異“策略進(jìn)行優(yōu)化，假設(shè)不同類型的組件產(chǎn)生不同的DOM樹(shù)結(jié)構(gòu)大溜，主動(dòng)放棄了對(duì)不同父節(jié)點(diǎn)的子節(jié)點(diǎn)的對(duì)比化漆；
• 開(kāi)發(fā)組建時(shí)，保持穩(wěn)定的DOM結(jié)構(gòu)钦奋、避免跨層級(jí)移動(dòng)DOM節(jié)點(diǎn)座云，有助于性能提升；
• 通過(guò)設(shè)置唯一key的策略付材，對(duì)列表節(jié)點(diǎn)進(jìn)行了diff算法優(yōu)化朦拖。