Reconciliation

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

動機(jī)（Motivation）

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

當(dāng)比較兩個 DOM 節(jié)點(diǎn)的時候，我們查看兩者的屬性，然后能夠找出哪一個屬性隨著時間產(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']

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

自定義組件

我們決定兩個自定義組件是相同的。因為組件是狀態(tài)化的，不可能每次狀態(tài)改變都要創(chuàng)建一個新的組件實例。React 利用新組件上的所有屬性，然后在之前的組件實例上調(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 同時遍歷兩個子級列表，當(dāng)發(fā)現(xiàn)差異的時候，就產(chǎn)生一次 DOM 修改。

例如在末尾添加一個元素：

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

在開始處插入元素比較麻煩。React 發(fā)現(xiàn)兩個節(jié)點(diǎn)都是 span，因此直接修改已有 span 的文本內(nèi)容，然后在后面插入一個新的 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算法能夠找出這個最小的操作集合，使用單一元素插入、刪除和替換，復(fù)雜度為 O(n²) 。即使使用 Levenshtein 算法，不會檢測出一個節(jié)點(diǎn)已經(jīng)移到了另外一個位置去了，要實現(xiàn)這個檢測算法，會引入更加糟糕的復(fù)雜度。

鍵（Keys）

為了解決這個看起來很棘手的問題，引入了一個可選的屬性?？梢越o每個子級一個鍵值，用于將來的匹配比較。如果指定了一個鍵值，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>]

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

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

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

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

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

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

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