Reconciliation

React 的關鍵設計目標是使 API 看起來就像每一次有數(shù)據(jù)更新的時候，整個應用重新渲染了一樣。這就極大地簡化了應用的編寫，但是同時使 React 易于駕馭，也是一個很大的挑戰(zhàn)。這篇文章解釋了我們如何使用強大的試探法來將 O(n³) 復雜度的問題轉換成 O(n) 復雜度的問題。

動機（Motivation）

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

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

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

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

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

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

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

不同的節(jié)點類型

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

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

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

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

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

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

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

DOM 節(jié)點

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

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

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

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

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

自定義組件

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

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

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

問題點（Problematic Case）

為了完成子級更新，React 選用了一種很原始的方法。React 同時遍歷兩個子級列表，當發(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é)點都是 span，因此直接修改已有 span 的文本內容，然后在后面插入一個新的 span 節(jié)點。

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

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

鍵（Keys）

為了解決這個看起來很棘手的問題，引入了一個可選的屬性?？梢越o每個子級一個鍵值，用于將來的匹配比較。如果指定了一個鍵值，React 就能夠檢測出節(jié)點插入、移除和替換，并且借助哈希表使節(jié)點移動復雜度為 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)有一個唯一的標識了。當沒有唯一標識的時候，可以給組件模型添加一個新的 ID 屬性，或者計算部分內容的哈希值來生成一個鍵值。記住，鍵值僅需要在兄弟節(jié)點中唯一，而不是全局唯一。

權衡（Trade-offs）

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

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

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

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

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