詳解 Diff 演算法以及循環要加 key 值問題
- 2019 年 10 月 3 日
- 筆記
上一篇文章我簡述了什麼是 Virtual DOM，這一章我會詳細講 Diff 演算法以及為什麼在 React 和 Vue 中循環都需要 key 值。
什麼是 DOM Diff 演算法
Web 介面其實就是一個 DOM 樹的結構，當其中某個部分發生變化的時候，實質上就是對應的某個 DOM 節點發生了變化。而在 React/Vue 中，都採用了 Virtual DOM 來模擬真實的樹結構，他們都擁有兩個 Virtual DOM，一顆是真實 DOM 結構的映射，另一顆則是改動後生成的 Virtual DOM，然後利用高效的 Diff 演算法來遍歷分析新舊 Virtual DOM 結構的差異，最後 Patch 不同的節點。
但是給定兩個 Virtual DOM，利用標準的 Diff 演算法肯定是不行的，使用傳統的 Diff 演算法通過循環遞歸遍歷節點進行對比，其複雜度要達到O(n^3)，其中 n 是節點總數，效率十分低下，假設我們要展示 1000 個節點，那麼我們就要依次執行上十億次的比較，這肯定無法滿足性能要求。
這裡附上一則傳統的 Diff 演算法：
// 存儲比較結果 let result = [] // 比較兩棵樹 const diffTree = function (beforeTree, afterTree) { // 獲取較大樹的 長度 let count = Math.max(beforeTree.children.length, afterTree.children.length) // 進行循環遍歷 for (let i = 0; i < count; i++) { const beforeChildren = beforeTree.children[i] const afterChildren = afterTree.children[i] // 如果原樹沒有，新樹有，則添加 if (beforeChildren === undefined) { result.push({ type: 'add', element: afterChildren }) // 如果原樹有，新樹沒有，則刪除 } else if (afterChildren === undefined) { result.push({ type: 'remove', element: beforeChildren }) // 如果節點名稱對應不上，則刪除原樹節點並添加新樹節點 } else if (beforeChildren.tagName !== afterChildren.tagName) { result.push({ type: 'remove', elevation: beforeChildren }) result.push({ type: 'add', element: beforeChildren }) // 如果節點名稱一樣，但內容改變，則修改原樹節點的內容 } else if (beforeChildren.innerTHML !== afterChildren.innerTHML) { // 如果沒有其他子節點，則直接改變 if (beforeChildren.children.length === 0) { result.push({ type: 'changed', beforeElement: beforeChildren, afterElement: afterChildren, html: afterChildren.innerTHML }); } else { // 否則進行遞歸比較 diffTree(beforeChildren, afterChildren) } } } // 最後返回結果 return result }然而優化過後的 Diff 演算法的複雜度只有O(n)，這歸結於 DIff 演算法的優化，工程師們將 Diff 演算法根據實際 DOM 樹結構特點做了以下優化。
- Tree Diff（層級的比較）
- Component Diff（組件的比較）
- Element Diff（元素/節點的比較）
簡單來說就是兩個概念：
- 相同組件會產生類似的 DOM 結構，不同的組件產生的 DOM 結構也不同
- 同一層級的子節點，可以通過唯一的 id 來進行區分
Tree Diff 層級的比較（樹結構的比較）
利用一張常見的圖可以完全看出 Tree Diff 的比較規則：
左右兩棵樹，分別為舊樹和新樹，先進行樹結構的層級比較，並且只會對相同顏色方框內的 DOM 節點進行比較，即同一個父節點下的所有子節點。
如果有任一一個節點不匹配，則該節點和其子節點就會被完全刪除，不會繼續遍歷。
基於這個策略，演算法複雜度降低為O(n)。
這時有同學要問了，那如果我想移動一個節點到另一個節點下，即跨層級操作，DIff 會怎樣表現呢？
如下圖所示：
以 C 為根節點，整棵樹會被新創建，而不是簡單的移動，創建的流程為 create C->`create F->create G->delete C。
這是一種很影響性能的操作，官方建議不要進行DOM節點跨層級操作，可以通過CSS隱藏、顯示節點，而不是真正地移除、添加DOM節點。
注意：在開發組件時，保持穩定的 DOM 結構會有助於性能的提升。例如，可以通過 CSS 隱藏或顯示節點，而不是真的移除或添加 DOM 節點。
Component Diff 組件比較
React/Vue是基於組件構建應用的，對於組件間的比較所採用的策略也是非常簡潔和高效的。
對此，有以下三種策略：
- 同類型組件（即：兩節點是同一個組件類的兩個不同實例）
- 若組件相同，則繼續按照層級比較其 Virtual DOM 的結構。
- 若組件 A 轉變為組件 B，但是組件 A 和組件 B 渲染出來的 Virtual DOM 沒有任何變化(即，子節點的順序、狀態state等，都未發生變化)，如果開發者能夠提前知道這一點，那麼可以省下大量 Diff 的時間。React 中，允許用戶通過
shouldComponentUpdate()來判斷該組件是否需要進行diff演算法分析。
- 不同類型組件
- 直接判斷為
dirty component，繼而替換整個組件的所有內容。
- 直接判斷為
注意：
- 如果組件 A 和組件 B 的結構相似，但是 React 判斷是 不同類型的組件，則不會比較其結構，而是刪除組件 A 及其子節點，創建組件 B 及其子節點。
舉個栗子：就算組件 D 和組件 G 的結構一模一樣，但是改變時仍然會刪除並且重新創建。
- Component Diff 只會比較同組節點集合的內容是否改變。即，若舊樹里，A 有 B 和 C 兩個節點，新樹里 A 有 C 和 B 兩個節點，無論 B 和 C 的位置是否改變，都會認為 component 層未改變。但是若 A 里的 state 發生了改變，則會認為 component 改變，繼而進行組件的更新。
Element Diff 元素的比較（同一層級同一父元素下的節點集合，進行比較）
當 DOM 處於同一層級時，Diff 提供三個節點操作，即 刪除（REMOVE_NODE）、插入（INSERT_MARKUP）、移動（MOVE_EXISTING）。
刪除（REMOVE_NODE）
舊組件類型，在新集合里也有，但對應的element不同則不能直接復用和更新，需要執行刪除操作，或者舊組件不在新集合里的，也需要執行刪除操作。
如圖所示：
插入（INSERT_MARKUP）
新的組件類型不在舊集合中，即全新的節點，需要對新節點進行插入操作。
如圖所示：
移動（MOVE_EXISTING）
舊集合中有新組件類型，且element是可更新的類型，這時候就需要做移動操作，可以復用以前的DOM節點。
沒有 Key 值的問題
如下圖，老集合中包含節點：A、B、C、D，更新後的新集合中包含節點：B、A、D、C，此時新老集合進行 diff 差異化對比，發現 B != A，則創建並插入 B 至新集合，刪除老集合 A；以此類推，創建並插入 A、D 和 C，刪除 B、C 和 D。
React 發現這類操作繁瑣冗餘，因為這些都是相同的節點，但由於位置發生變化，導致需要進行繁雜低效的刪除、創建操作，其實只要對這些節點進行位置移動即可。
針對這一現象，React 提出優化策略：允許開發者對同一層級的同組子節點，添加唯一 key 進行區分，雖然只是小小的改動，性能上卻發生了翻天覆地的變化！
為什麼循環需要添加唯一 Key值
給元素加了 Key 值之後，React/Vue 在做 Diff 的時候會進行差異化對比，即通過 key 發現新老集合中的節點都是相同的節點，因此無需進行節點刪除和創建，只需要將老集合中節點的位置進行移動，更新為新集合中節點的位置，此時 React 給出的 diff 結果為：B、D 不做任何操作，A、C 進行移動操作，即可。
那麼，如此高效的 diff 到底是如何運作的呢？
簡單來說有以下幾步：
-
對新集合的節點進行遍歷，通過唯一 key 可以判斷新老集合中是否存在相同節點。
-
如果存在相同節點，則進行移動操作，但在移動前，需要將當前節點在老集合中的位置與 lastIndex 進行比較，如果不同，則進行節點移動，否則不執行該操作。
這是一種順序優化手段，lastIndex 一直在更新，表示訪問過的節點在老集合中最右的位置（即最大的位置），如果新集合中當前訪問的節點比 lastIndex 大，說明當前訪問節點在老集合中就比上一個節點位置靠後，則該節點不會影響其他節點的位置，因此不用添加到差異隊列中，即不執行移動操作，只有當訪問的節點比 lastIndex 小時，才需要進行移動操作。
這裡給出一整圖作為示例。
如上圖所示，以新樹為循環基準：
- B 在老集合的下標為
BIndex=1，此時lastIndex=0，這時，lastIndex < BIndex，不進行任何處理，並且取值lastIndex=Math.max(BIndex, lastIndex) - A 在老集合的下標為
AIndex=0，此時lastIndex=1，這時，lastIndex > AIndex，這時，需要把老樹中的 A 移動到下標為lastIndex的位置，並且取值lastIndex=Math.max(AIndex, lastIndex) - D 在老集合的下標為
DIndex=3，此時lastIndex=1，這時，lastIndex < DIndex，不進行任何處理，並且取值lastIndex=Math.max(DIndex, lastIndex) - C 在老集合的下標為
CIndex=2，此時lastIndex=3，這時，lastIndex > CIndex，需要把老樹中的 C 移動到下標為lastIndex的位置，並且取值lastIndex=Math.max(CIndex, lastIndex) - 由於 C 已經是最後一個節點，因此 Diff 至此結束。
以上主要分析新老集合中存在相同節點但位置不同時，對節點進行位置移動的情況，如果新集合中有新加入的節點且老集合存在需要刪除的節點，那麼 React diff 又是如何對比運作的呢？
以此圖為例：
同上的流程：
- B 同上流程
- 老集合中沒有 E 集合，則判斷老集合中不存在相同節點 E，則創建新節點 E，更新 lastIndex ＝ 1，並將 E 的位置更新為新集合中的位置。
- C 同上
- A 同上
- 當完成集合 Diff 時，最後還需要對老集合進行循環遍歷，判斷是否存在新集合中沒有但老集合中仍然存在的節點，如果有，則刪除，循環發現，D 就是這樣的節點，因此刪除 D，完成 Diff。
這種循環方式，眼尖的讀者會發現一個問題，如果是集合的首尾位置互換，那開銷就大了。
如上圖所示，此時的 DIff 演算法，會將 A，B，C 全部移動到 D 的後面，造成大量DOM 的移動，而實際上我們只需要將 D 移動到集合的頭部僅一次即可。
由此可看出，在開發過程中，盡量減少類似將最後一個節點移動到列表首部的操作，當節點數量過大或更新操作過於頻繁時，在一定程度上會影響 React 的渲染性能。
沒有 key 值的更新問題
除了上述不添加 Key 值會造成整個集合刪除再新增，不會進行移動 DOM 操作，導致大量無謂的開銷外，但是結合上述 Component Diff 聯想，如果 A、B、C、D都是同類型組件且不加 Key 值會發生什麼情況呢？
我們看圖說話：
這是 Vue 的：
這是 React 的：
我們發現，無論是 React 還是 Vue 刪除了第二項之後，第三項列表內部的 state 仍然沿用的第二個列表的內容。
這是因為，React/Vue 判斷是變化前後是同類型組件，並且 props 的內容並沒有改變，不會觸發改變。
其流程如下：
- 既然 1 沒有變，那麼就就地復用之前的 1
- 既然 2 變成了 3，裡面的子孫元素就地復用。有人不理解為什麼子孫元素就地復用，那麼是因為子孫元素的 data/state 屬性不受 2 變成 3 的影響
- 既然 3 沒了，那麼連其子孫元素全部刪除
破解方法就是加上唯一的 key，讓 Diff 知道就算是同類型的組件，也是有名字區分的。
在做動態改變的時候，盡量不要使用 index 作為循環的 key，如果你用 index 作為 key，那麼在刪除第二項的時候，index 就會從 1，2，3 變為 1，2（而不是 1，3），那麼仍有可能引起更新錯誤。
總結
- React/Vue 的 DIff 策略使遍歷複雜度降低為 O(n)，是一個重大的優化
- React/Vue 在做循環時，一定要加上唯一的 key 值，這樣不僅能有效提高 Diff 效率，減少 DOM 的重繪，還能避免一些稀奇古怪的錯誤
- 盡量減少跨層級的組件改動，盡量使用 v-show/display:none 來保持 DOM 結構的穩定性，防止新增、刪除等消耗大量性能的操作
- 盡量減少將節點尾部移動到節點頭部等操作，當節點數量過大或更新操作過於頻繁時，在一定程度上會影響 React 的渲染性能。
- 另外，React 從 16 版本開始使用了 Fiber 架構，這個架構解決了大型 React 項目的性能問題及一些之前框架的痛點，我會在下一章詳細介紹 Fiber 架構的奧秘和其與之前架構的區別
