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ù)據(jù)結(jié)構(gòu)，對(duì)比"樹"的結(jié)構(gòu)在計(jì)算機(jī)相關(guān)相關(guān)領(lǐng)域有廣泛的應(yīng)用。具體到前端開發(fā)而言，Web的UI界面就是由DOM樹構(gòu)成，DOM作為一種有序樹結(jié)構(gòu)，當(dāng)DOM樹結(jié)構(gòu)發(fā)生變化時(shí)，瀏覽器會(huì)重新解析渲染DOM樹。造成有序樹的節(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)，適用于很多需要樹結(jié)構(gòu)對(duì)比的場(chǎng)景，如：計(jì)算生物學(xué)、圖像分析、結(jié)構(gòu)化文本數(shù)據(jù)庫(kù)等。然而其算法的時(shí)間復(fù)雜度為O(n^3)，在瀏覽器環(huán)境中，要達(dá)到每次更新都可以整體刷新界面的目的，這樣高的算法復(fù)雜度會(huì)有性能問題。

2 React Diff算法（reconciliation algorithm）

React開發(fā)團(tuán)隊(duì)結(jié)合Web界面的特點(diǎn)對(duì)標(biāo)準(zhǔn)的Diff算法做出了優(yōu)化，使得其時(shí)間復(fù)雜度降低為O(n)。這一算法，即reconciliation algorithm，常見中文翻譯為“協(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)，它們可以通過唯一的key進(jìn)行區(qū)分。

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

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

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

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

當(dāng)VD樹中同一節(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樹節(jié)點(diǎn)的style屬性稍有不同，因?yàn)閭魅氲氖菍?duì)象而不是字符串，React會(huì)只更新改變了的樣式屬性。

如果開發(fā)者能夠明確節(jié)點(diǎn)是否有變化，則可以通過shouldComponentUpdate(nextProp, nextState)方法來決定是否進(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ì)樹進(jìn)行一次遍歷，便能完成整個(gè)DOM樹的比較。這一方法正是基于前一假設(shè)，即不同類型的組件產(chǎn)生不同的VD樹結(jié)構(gòu)。

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

例如，在下圖的VD樹結(jié)構(gòu)轉(zhuǎn)換過程中，看似應(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)。過程如下：

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

這樣的操作看似是把簡(jiǎ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)也有助于性能提升，可以通過類名和CSS來控制節(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)的常見操作包含插入、刪除和排序。如果每個(gè)列表節(jié)點(diǎn)沒有唯一標(biāo)識(shí)，則React無法識(shí)別每一個(gè)節(jié)點(diǎn)，那么只能更新所有列表節(jié)點(diǎn)造成效率低下。

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

這時(shí)，“key”這個(gè)屬性就要登場(chǎng)了，React通過key這個(gè)屬性發(fā)現(xiàn)更新前后相同的列表節(jié)點(diǎn)，因此無需進(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ì)通過每個(gè)節(jié)點(diǎn)的唯一標(biāo)識(shí)(key)，準(zhǔn)確找到插入新節(jié)點(diǎn)F的位置，同時(shí)保留其他節(jié)點(diǎn)。

3 總結(jié)

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