參考資料
一玻孟、為什么需要 diffing 算法？
在某一時(shí)間節(jié)點(diǎn)調(diào)用 React 的 render() 方法段多，會(huì)創(chuàng)建一棵由 React 元素組成的樹(shù)。在下一次 state 或 props 更新時(shí)壮吩，相同的 render() 方法會(huì)返回一棵不同的樹(shù)进苍。React 需要基于這兩棵樹(shù)之間的差別來(lái)判斷如何有效率的更新 UI 以保證當(dāng)前 UI 與最新的樹(shù)保持同步。
這個(gè)算法問(wèn)題有一些通用的解決方案鸭叙，即生成將一棵樹(shù)轉(zhuǎn)換成另一棵樹(shù)的最小操作數(shù)觉啊。 然而，即使在最前沿的算法中沈贝，該算法的復(fù)雜程度為 O(n<sup> 3 </sup>)杠人，其中 n 是樹(shù)中元素的數(shù)量。
如果在 React 中使用了該算法宋下，那么展示 1000 個(gè)元素所需要執(zhí)行的計(jì)算量將在 十億 的量級(jí)范圍嗡善。這個(gè)開(kāi)銷(xiāo)實(shí)在是太過(guò)高昂。于是 React 在以下兩個(gè)假設(shè)的基礎(chǔ)之上提出了一套 O(n) 的啟發(fā)式算法：
二学歧、diffing 算法的復(fù)雜程度為罩引？
O(n)
三、能做到如此低的算法復(fù)雜程度的兩個(gè)假設(shè)基礎(chǔ)
- 兩個(gè)不同類(lèi)型的元素會(huì)產(chǎn)生出不同的樹(shù)枝笨；
- 開(kāi)發(fā)者可以通過(guò)
key袁铐、prop來(lái)暗示哪些子元素在不同的渲染下能保持穩(wěn)定；
在實(shí)踐中横浑，我們發(fā)現(xiàn)以上假設(shè)在幾乎所有實(shí)用的場(chǎng)景下都成立剔桨。
四、diffing 算法具體對(duì)比
總結(jié)：
- 對(duì)比不同類(lèi)型的普通元素：當(dāng)根節(jié)點(diǎn)為不同類(lèi)型的元素時(shí)徙融，
React會(huì)拆卸原有的樹(shù)并且建立起新的樹(shù)洒缀。 - 對(duì)比同一類(lèi)型的普通元素：① 元素的屬性改變時(shí)，
React會(huì)保留DOM節(jié)點(diǎn)欺冀，僅比對(duì)及更新有改變的屬性树绩。② 特殊的style屬性改變時(shí)，React僅更新有所更變的style里的屬性脚猾。 - 對(duì)比同一類(lèi)型的組件元素：不改變組件的
state葱峡；更新組件的props砚哗；調(diào)用實(shí)例的相關(guān)方法龙助；遞歸新舊結(jié)果。 - 對(duì)子節(jié)點(diǎn)進(jìn)行遞歸：① 在子元素列表末尾新增元素時(shí)，更新開(kāi)銷(xiāo)比較小提鸟，只新增末尾元素军援。② 將新增元素插入到表頭，那么更新開(kāi)銷(xiāo)會(huì)比較大称勋，會(huì)重建每一個(gè)子元素胸哥。
1. 對(duì)比不同類(lèi)型的元素
當(dāng)根節(jié)點(diǎn)為不同類(lèi)型的元素時(shí)，React 會(huì)拆卸原有的樹(shù)并且建立起新的樹(shù)赡鲜。舉個(gè)例子空厌，當(dāng)一個(gè)元素從 <a> 變成 <img>，從 <Article> 變成 <Comment>银酬，或從 <Button> 變成 <div> 都會(huì)觸發(fā)一個(gè)完整的重建流程嘲更。
當(dāng)拆卸一棵樹(shù)時(shí)，對(duì)應(yīng)的 DOM 節(jié)點(diǎn)也會(huì)被銷(xiāo)毀揩瞪。組件實(shí)例將執(zhí)行 componentWillUnmount() 方法赋朦。當(dāng)建立一棵新的樹(shù)時(shí)，對(duì)應(yīng)的 DOM 節(jié)點(diǎn)會(huì)被創(chuàng)建以及插入到 DOM 中李破。組件實(shí)例將執(zhí)行 UNSAFE_componentWillMount() 方法宠哄，緊接著 componentDidMount() 方法。所有跟之前的樹(shù)所關(guān)聯(lián)的 state 也會(huì)被銷(xiāo)毀嗤攻。
在根節(jié)點(diǎn)以下的組件也會(huì)被卸載毛嫉，它們的狀態(tài)會(huì)被銷(xiāo)毀。比如屯曹，當(dāng)比對(duì)以下更變時(shí)：
<div>
<Counter />
</div>
<span>
<Counter />
</span>
React 會(huì)銷(xiāo)毀 Counter 組件并且重新裝載一個(gè)新的組件狱庇。
注意：
這些方法被認(rèn)為是過(guò)時(shí)的，在新的代碼中應(yīng)該避免使用它們：
UNSAFE_componentWillMount()
2. 對(duì)比同一類(lèi)型的元素
當(dāng)對(duì)比兩個(gè)相同類(lèi)型的 React 元素時(shí)恶耽，React 會(huì)保留 DOM 節(jié)點(diǎn)密任，僅比對(duì)及更新有改變的屬性。比如：
<div className="before" title="stuff" />
<div className="after" title="stuff" />
過(guò)對(duì)比這兩個(gè)元素偷俭，React 知道只需要修改 DOM 元素上的 className 屬性浪讳。
當(dāng)更新 style 屬性時(shí)，React 僅更新有所更變的屬性涌萤。比如：
<div style={{color: 'red', fontWeight: 'bold'}} />
<div style={{color: 'green', fontWeight: 'bold'}} />
通過(guò)對(duì)比這兩個(gè)元素淹遵，React 知道只需要修改 DOM 元素上的 color 樣式，無(wú)需修改 fontWeight负溪。
在處理完當(dāng)前節(jié)點(diǎn)之后透揣，React 繼續(xù)對(duì)子節(jié)點(diǎn)進(jìn)行遞歸。
3. 對(duì)比同類(lèi)型的組件元素
當(dāng)一個(gè)組件更新時(shí)川抡，組件實(shí)例保持不變辐真，這樣 state 在跨越不同的渲染時(shí)保持一致。React 將更新該組件實(shí)例的 props 以跟最新的元素保持一致，并且調(diào)用該實(shí)例的 UNSAFE_componentWillReceiveProps()侍咱、UNSAFE_componentWillUpdate() 以及 componentDidUpdate() 方法耐床。
下一步，調(diào)用 render() 方法楔脯，diff 算法將在之前的結(jié)果以及新的結(jié)果中進(jìn)行遞歸撩轰。
注意：
這些方法已過(guò)時(shí)，在新代碼中應(yīng)避免使用它們：
UNSAFE_componentWillUpdate()UNSAFE_componentWillReceiveProps()
4. 對(duì)子節(jié)點(diǎn)進(jìn)行遞歸
在默認(rèn)條件下昧廷，當(dāng)遞歸 DOM 節(jié)點(diǎn)的子元素時(shí)堪嫂，React 會(huì)同時(shí)遍歷兩個(gè)子元素的列表；當(dāng)產(chǎn)生差異時(shí)木柬，生成一個(gè) mutation溉苛。
在子元素列表末尾新增元素時(shí)，更新開(kāi)銷(xiāo)比較小弄诲。比如：
<ul>
<li>first</li>
<li>second</li>
</ul>
<ul>
<li>first</li>
<li>second</li>
<li>third</li>
</ul>
React 會(huì)先匹配兩個(gè) <li>first</li> 對(duì)應(yīng)的樹(shù)愚战，然后匹配第二個(gè)元素 <li>second</li> 對(duì)應(yīng)的樹(shù)，最后插入第三個(gè)元素的 <li>third</li> 樹(shù)齐遵。
如果只是簡(jiǎn)單的將新增元素插入到表頭寂玲，那么更新開(kāi)銷(xiāo)會(huì)比較大。比如：
<ul>
<li>Duke</li>
<li>Villanova</li>
</ul>
<ul>
<li>Connecticut</li>
<li>Duke</li>
<li>Villanova</li>
</ul>
React 不會(huì)意識(shí)到應(yīng)該保留 <li>Duke</li> 和 <li>Villanova</li>梗摇，而是會(huì)重建每一個(gè)子元素 拓哟。這種情況會(huì)帶來(lái)性能問(wèn)題。
五伶授、diffing 算法對(duì)子節(jié)點(diǎn)進(jìn)行遞歸的優(yōu)化 —— Keys
為了解決對(duì)子元素進(jìn)行遞歸時(shí)更新開(kāi)銷(xiāo)會(huì)比較大的問(wèn)題断序，React 支持 key 屬性。
當(dāng)子元素?fù)碛?key 時(shí)糜烹，React 使用 key 來(lái)匹配原有樹(shù)上的子元素以及最新樹(shù)上的子元素违诗。以下例子在新增 key 之后使得之前的低效轉(zhuǎn)換變得高效：
<ul>
<li key="2015">Duke</li>
<li key="2016">Villanova</li>
</ul>
<ul>
<li key="2014">Connecticut</li>
<li key="2015">Duke</li>
<li key="2016">Villanova</li>
</ul>
現(xiàn)在 React 知道只有帶著 '2014' 的 key 元素是新元素，帶著 '2015' 以及 '2016' 的 key 元素僅僅移動(dòng)了疮蹦。
現(xiàn)實(shí)場(chǎng)景中诸迟，產(chǎn)生一個(gè) key 并不困難。你要展現(xiàn)的元素可能已經(jīng)有了一個(gè)唯一 ID愕乎，于是 key 可以直接從你的數(shù)據(jù)中提日笪：
<li key={item.id}>{item.name}</li>
當(dāng)以上情況不成立時(shí)，你可以新增一個(gè) ID 字段到你的模型中感论，或者利用一部分內(nèi)容作為哈希值來(lái)生成一個(gè) key绅项。這個(gè) key 不需要全局唯一，但在列表中需要保持唯一比肄。
最后快耿，你也可以使用元素在數(shù)組中的下標(biāo)作為 key湿硝。這個(gè)策略在元素不進(jìn)行重新排序時(shí)比較合適，如果有順序修改润努，diff 就會(huì)變得慢。
當(dāng)基于下標(biāo)的組件進(jìn)行重新排序時(shí)示括，組件 state 可能會(huì)遇到一些問(wèn)題铺浇。由于組件實(shí)例是基于它們的 key 來(lái)決定是否更新以及復(fù)用，如果 key 是一個(gè)下標(biāo)垛膝，那么修改順序時(shí)會(huì)修改當(dāng)前的 key鳍侣，導(dǎo)致非受控組件的 state（比如輸入框）可能相互篡改導(dǎo)致無(wú)法預(yù)期的變動(dòng)。
在 Codepen 有兩個(gè)例子吼拥，分別為 展示使用下標(biāo)作為 key 時(shí)導(dǎo)致的問(wèn)題倚聚，以及不使用下標(biāo)作為 key 的例子的版本，修復(fù)了重新排列凿可，排序惑折，以及在列表頭插入的問(wèn)題 。
六枯跑、性能會(huì)有所損耗的假設(shè)
請(qǐng)謹(jǐn)記協(xié)調(diào)算法是一個(gè)實(shí)現(xiàn)細(xì)節(jié)惨驶。React 可以在每個(gè) action 之后對(duì)整個(gè)應(yīng)用進(jìn)行重新渲染，得到的最終結(jié)果也會(huì)是一樣的敛助。在此情境下粗卜，重新渲染表示在所有組件內(nèi)調(diào)用 render 方法，這不代表 React 會(huì)卸載或裝載它們纳击。React 只會(huì)基于以上提到的規(guī)則來(lái)決定如何進(jìn)行差異的合并续扔。
我們定期探索優(yōu)化算法，讓常見(jiàn)用例更高效地執(zhí)行焕数。在當(dāng)前的實(shí)現(xiàn)中纱昧，可以理解為一棵子樹(shù)能在其兄弟之間移動(dòng)，但不能移動(dòng)到其他位置堡赔。在這種情況下砌些，算法會(huì)重新渲染整棵子樹(shù)。
由于 React 依賴(lài)探索的算法加匈，因此當(dāng)以下假設(shè)沒(méi)有得到滿(mǎn)足存璃，性能會(huì)有所損耗：
- 該算法不會(huì)嘗試匹配不同組件類(lèi)型的子樹(shù)。如果你發(fā)現(xiàn)你在兩種不同類(lèi)型的組件中切換雕拼，但輸出非常相似的內(nèi)容纵东，建議把它們改成同一類(lèi)型。在實(shí)踐中啥寇，我們沒(méi)有遇到這類(lèi)問(wèn)題偎球。
-
Key應(yīng)該具有穩(wěn)定洒扎，可預(yù)測(cè)，以及列表內(nèi)唯一的特質(zhì)衰絮。不穩(wěn)定的key（比如通過(guò)Math.random()生成的）會(huì)導(dǎo)致許多組件實(shí)例和DOM節(jié)點(diǎn)被不必要地重新創(chuàng)建袍冷，這可能導(dǎo)致性能下降和子組件中的狀態(tài)丟失。
