React 的關(guān)鍵設(shè)計(jì)目標(biāo)是使 API 看起來就像每一次有數(shù)據(jù)更新的時(shí)候，整個(gè)應(yīng)用重新渲染了一樣。這就極大地簡化了應(yīng)用的編寫，但是同時(shí)使 React 易于駕馭，也是一個(gè)很大的挑戰(zhàn)。這篇文章解釋了我們?nèi)绾问褂脧?qiáng)大的試探法來將 O(n³) 復(fù)雜度的問題轉(zhuǎn)換成 O(n) 復(fù)雜度的問題。

動機(jī)（Motivation）

生成最少的將一顆樹形結(jié)構(gòu)轉(zhuǎn)換成另一顆樹形結(jié)構(gòu)的操作，是一個(gè)復(fù)雜的，并且值得研究的問題。最優(yōu)算法的復(fù)雜度是 O(n³)，n 是樹中節(jié)點(diǎn)的總數(shù)。

這意味著要展示1000個(gè)節(jié)點(diǎn)，就要依次執(zhí)行上十億次的比較。這對我們的使用場景來說太昂貴了。準(zhǔn)確地感受下這個(gè)數(shù)字：現(xiàn)今的 CPU 每秒鐘能執(zhí)行大約三十億條指令。因此即便是最高效的實(shí)現(xiàn)，也不可能在一秒內(nèi)計(jì)算出差異情況。

既然最優(yōu)的算法都不好處理這個(gè)問題，我們實(shí)現(xiàn)一個(gè)非最優(yōu)的 O(n) 算法，使用試探法，基于如下兩個(gè)假設(shè)：

1、擁有相同類的兩個(gè)組件將會生成相似的樹形結(jié)構(gòu)，擁有不同類的兩個(gè)組件將會生成不同的樹形結(jié)構(gòu)。 2、可以為元素提供一個(gè)唯一的標(biāo)志，該元素在不同的渲染過程中保持不變。

實(shí)際上，這些假設(shè)會使在幾乎所有的應(yīng)用場景下，應(yīng)用變得出奇地快。

兩個(gè)節(jié)點(diǎn)的差異檢查（Pair-wise diff）

為了進(jìn)行一次樹結(jié)構(gòu)的差異檢查，首先需要能夠檢查兩個(gè)節(jié)點(diǎn)的差異。此處有三種不同的情況需要處理：

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

如果節(jié)點(diǎn)的類型不同，React 將會把它們當(dāng)做兩個(gè)不同的子樹，移除之前的那棵子樹，然后創(chuàng)建并插入第二棵子樹。

renderA: <div />
renderB: <span />
=> [removeNode <div />], [insertNode <span />]

該方法也同樣應(yīng)用于傳統(tǒng)的組件。如果它們不是相同的類型，React 甚至將不會嘗試計(jì)算出該渲染什么，僅會從 DOM 中移除之前的節(jié)點(diǎn)，然后插入新的節(jié)點(diǎn)。

renderA: <Header />
renderB: <Content />
=> [removeNode <Header />], [insertNode <Content />]

具備這種高級的知識點(diǎn)對于理解為什么 React 的差異檢測邏輯既快又精確是很重要的。它對于避開樹形結(jié)構(gòu)大部分的檢測，然后聚焦于似乎相同的部分，提供了啟發(fā)。

一個(gè) <Header> 元素與一個(gè) <Content> 元素生成的 DOM 結(jié)構(gòu)不太可能一樣。React 將重新創(chuàng)建樹形結(jié)構(gòu)，而不是耗費(fèi)時(shí)間去嘗試匹配這兩個(gè)樹形結(jié)構(gòu)。

如果在兩個(gè)連續(xù)的渲染過程中的相同位置都有一個(gè) <Header> 元素，將會希望生成一個(gè)非常相似的 DOM 結(jié)構(gòu)，因此值得去做一做匹配。

DOM 節(jié)點(diǎn)

當(dāng)比較兩個(gè) DOM 節(jié)點(diǎn)的時(shí)候，我們查看兩者的屬性，然后能夠找出哪一個(gè)屬性隨著時(shí)間產(chǎn)生了變化。

renderA: <div id="before" />
renderB: <div id="after" />
=> [replaceAttribute id "after"]

React 不會把 style 當(dāng)做難以操作的字符串，而是使用鍵值對對象。這就很容易地僅更新改變了的樣式屬性。

renderA: <div style={{'{{'}}color: 'red'}} />
renderB: <div style={{'{{'}}fontWeight: 'bold'}} />
=> [removeStyle color], [addStyle font-weight 'bold']

在屬性更新完畢之后，遞歸檢測所有的子級的屬性。

自定義組件

我們決定兩個(gè)自定義組件是相同的。因?yàn)榻M件是狀態(tài)化的，不可能每次狀態(tài)改變都要創(chuàng)建一個(gè)新的組件實(shí)例。React 利用新組件上的所有屬性，然后在之前的組件實(shí)例上調(diào)用 component[Will/Did]ReceiveProps()。

現(xiàn)在，之前的組件就是可操作了的。它的 render() 方法被調(diào)用，然后差異算法重新比較新的狀態(tài)和上一次的狀態(tài)。

子級優(yōu)化差異算法（List-wise diff）

問題點(diǎn)（Problematic Case）

為了完成子級更新，React 選用了一種很原始的方法。React 同時(shí)遍歷兩個(gè)子級列表，當(dāng)發(fā)現(xiàn)差異的時(shí)候，就產(chǎn)生一次 DOM 修改。

例如在末尾添加一個(gè)元素：

renderA: <div><span>first</span></div>
renderB: <div><span>first</span><span>second</span></div>
=> [insertNode <span>second</span>]

在開始處插入元素比較麻煩。React 發(fā)現(xiàn)兩個(gè)節(jié)點(diǎn)都是 span，因此直接修改已有 span 的文本內(nèi)容，然后在后面插入一個(gè)新的 span 節(jié)點(diǎn)。

renderA: <div><span>first</span></div>
renderB: <div><span>second</span><span>first</span></div>
=> [replaceAttribute textContent 'second'], [insertNode <span>first</span>]

有很多的算法嘗試找出變換一組元素的最小操作集合。Levenshtein distance算法能夠找出這個(gè)最小的操作集合，使用單一元素插入、刪除和替換，復(fù)雜度為 O(n²) 。即使使用 Levenshtein 算法，不會檢測出一個(gè)節(jié)點(diǎn)已經(jīng)移到了另外一個(gè)位置去了，要實(shí)現(xiàn)這個(gè)檢測算法，會引入更加糟糕的復(fù)雜度。

鍵（Keys）

為了解決這個(gè)看起來很棘手的問題，引入了一個(gè)可選的屬性?？梢越o每個(gè)子級一個(gè)鍵值，用于將來的匹配比較。如果指定了一個(gè)鍵值，React 就能夠檢測出節(jié)點(diǎn)插入、移除和替換，并且借助哈希表使節(jié)點(diǎn)移動復(fù)雜度為 O(n)。

renderA: <div><span key="first">first</span></div>
renderB: <div><span key="second">second</span><span key="first">first</span></div>
=> [insertNode <span>second</span>]

在實(shí)際開發(fā)中，生成一個(gè)鍵值不是很困難。大多數(shù)時(shí)候，要展示的元素已經(jīng)有一個(gè)唯一的標(biāo)識了。當(dāng)沒有唯一標(biāo)識的時(shí)候，可以給組件模型添加一個(gè)新的 ID 屬性，或者計(jì)算部分內(nèi)容的哈希值來生成一個(gè)鍵值。記住，鍵值僅需要在兄弟節(jié)點(diǎn)中唯一，而不是全局唯一。

權(quán)衡（Trade-offs）

同步更新算法只是一種實(shí)現(xiàn)細(xì)節(jié)，記住這點(diǎn)很重要。React 能在每次操作中重新渲染整個(gè)應(yīng)用，最終的結(jié)果將會是一樣的。我們定期優(yōu)化這個(gè)啟發(fā)式算法來使常規(guī)的應(yīng)用場景更加快速。

在當(dāng)前的實(shí)現(xiàn)中，能夠檢測到某個(gè)子級樹已經(jīng)從它的兄弟節(jié)點(diǎn)中移除，但是不能指出它是否已經(jīng)移到了其它某個(gè)地方。當(dāng)前算法將會重新渲染整個(gè)子樹。

由于依賴于兩個(gè)預(yù)判條件，如果這兩個(gè)條件都沒有滿足，性能將會大打折扣。

1、算法將不會嘗試匹配不同組件類的子樹。如果發(fā)現(xiàn)正在使用的兩個(gè)組件類輸出的 DOM 結(jié)構(gòu)非常相似，你或許想把這兩個(gè)組件類改成一個(gè)組件類。實(shí)際上， 這不是個(gè)問題。

2、如果沒有提供穩(wěn)定的鍵值（例如通過 Math.random() 生成），所有子樹將會在每次數(shù)據(jù)更新中重新渲染。通過給開發(fā)者設(shè)置鍵值的機(jī)會，能夠給特定場景寫出更優(yōu)化的代碼。