DOM diff 原理詳解

DOM diff 作爲工程問題，需要具有一定算法思維，因此經常出現在面試場景中，畢竟這是難得出現在工程領域的算法問題。

無論出於面試目的，還是深入學習目的，都有必要將這個問題搞懂，因此前端精讀我們就專門用一個章節說清楚此問題。

精讀

Dom diff 是所有現在框架必須做的事情，這背後的原因是，由 Jquery 時代的面向操作過程轉變爲數據驅動視圖導致的。

爲什麼 Jquery 時代不需要 Dom diff？因爲 Dom diff 交給業務處理了，我們調用 .append 或者 .move 之類 Dom 操作函數，就是顯式申明瞭如何做 Dom diff，這種方案是最高效的，因爲怎麼移動 Dom 只有業務最清楚。

但這樣的問題也很明顯，就是業務心智負擔太重，對於複雜系統，需要做 Dom diff 的地方太多，不僅寫起來繁瑣，當狀態存在交錯時，面向過程的手動 Dom diff 容易出現狀態遺漏，導致邊界錯誤，就算你沒有寫出 bug，代碼的可維護性也絕對算不上好。

解決方案就是數據驅動，我們只需要關注數據如何映射到 UI，這樣無論業務邏輯再複雜，我們永遠只需要解決局部狀態的映射，這極大降低了複雜系統的維護複雜度，以前需要一個老手寫的邏輯，現在新手就能做了，這是非常了不起的變化。

但有利也有弊，這背後 Dom diff 就要交給框架來做了，所以是否能高效的做 Dom diff，是一個數據驅動框架能否應用於生產環境的重要指標，接下來，我們來看看 Dom diff 是如何做的吧。

理想的 Dom diff

如圖所示，理想的 Dom diff 自然是滴水不漏的複用所有能複用的，實在遇到新增或刪除時，才執行插入或刪除。這樣的操作最貼近 Jquery 時代我們手寫的 Dom diff 性能。

可惜程序無法猜到你的想法，想要精確複用就必須付出高昂的代價：時間複雜度 O(n³) 的 diff 算法，這顯然是無法接受的，因此理想的 Dom diff 算法無法被使用。

關於 O(n³) 的由來。由於左樹中任意節點都可能出現在右樹，所以必須在對左樹深度遍歷的同時，對右樹進行深度遍歷，找到每個節點的對應關係，這裏的時間複雜度是 O(n²)，之後需要對樹的各節點進行增刪移的操作，這個過程簡單可以理解爲加了一層遍歷循環，因此再乘一個 n。

簡化的 Dom diff

如圖所示，只按層比較，就可以將時間複雜度降低爲 O(n)。按層比較也不是廣度遍歷，其實就是判斷某個節點的子元素間 diff，跨父節點的兄弟節點也不必比較。

這樣做確實非常高效，但代價就是，判斷的有點傻，比如 ac 明明是一個移動操作，卻被誤識別爲刪除 + 新增。

好在跨 DOM 複用在實際業務場景中很少出現，因此這種笨拙出現的頻率實際上非常低，這時候我們就不要太追求學術思維上的嚴謹了，畢竟框架是給實際項目用的，實際項目中很少出現的場景，算法是可以不考慮的。

下面是同層 diff 可能出現的三種情況，非常簡單，看圖即可：

那麼同層比較是怎麼達到 O(n) 時間複雜度的呢？我們來看具體框架的思路。

Vue 的 Dom diff

Vue 的 Dom diff 一共 5 步，我們結合下圖先看前三步：

如圖所示，第一和第二步分別從首尾兩頭向中間逼近，儘可能跳過首位相同的元素，因爲我們的目的是 儘量保證不要發生 dom 位移。

這種算法一般採用雙指針。如果前兩步做完後，發現舊樹指針重合了，新樹還未重合，說明什麼？說明新樹剩下來的都是要新增的節點，批量插入即可。很簡單吧？那如果反過來呢？如下圖所示：

第一和第二步完成後，發現新樹指針重合了，但舊樹還未重合，說明什麼？說明舊樹剩下來的在新樹都不存在了，批量刪除即可。

當然，如果 1、2、3、4 步走完之後，指針還未處理完，那麼就進入一個小小算法時間了，我們需要在 O(n) 時間複雜度內把剩下節點處理完。熟悉算法的同學應該很快能反映出，一個數組做一些檢測操作，還得把時間複雜度控制在 O(n)，得用一個 Map 空間換一下時間，實際上也是如此，我們看下圖具體做法：

如圖所示，1、2、3、4 步走完後，Old 和 New 都有剩餘，因此走到第五步，第五步分爲三小步：

1. 遍歷 Old 創建一個 Map，這個就是那個換時間的空間消耗，它記錄了每個舊節點的 index 下標，一會好在 New 裏查出來。

2. 遍歷 New，順便利用上面的 Map 記錄下下標，同時 Old 裏不存在的說明被刪除了，直接刪除。

3. 不存在的位置補 0，我們拿到 e:4 d:3 c:2 h:0 這樣一個數組，下標 0 是新增，非 0 就是移過來的，批量轉化爲插入操作即可。

最後一步的優化也很關鍵，我們不要看見不同就隨便移動，爲了性能最優，要保證移動次數儘可能的少，那麼怎麼才能儘可能的少移動呢？假設我們隨意移動，如下圖所示：

但其實最優的移動方式是下面這樣：

爲什麼呢？因爲移動的時候，其他元素的位置也在相對變化，可能做了 A 效果同時，也把 B 效果給滿足了，也就是說，找到那些相對位置有序的元素保持不變，讓那些位置明顯錯誤的元素挪動即是最優的。

什麼是相對有序？a c e 這三個字母在 Old 原始順序 a b c d e 中是相對有序的，我們只要把 b d 移走，這三個字母的位置自然就正確了。因此我們只需要找到 New 數組中的 最長連續子串。具體的找法可以當作一個小算法題了，由於知道每個元素的實際下標，比如這個例子中，下標是這樣的：

[b:1, d:3, a:0, c:2, e:4]

肉眼看上去，連續自增的子串有 b d 和 a c e，由於 a c e 更長，所以選擇後者。

換成程序去做，可以採用動態規劃，設 dp(i) 爲以第 i 個字符串結尾的最長連續子串長度，一次 O(n) 循環即可。

// dp(i) = num[i] > num[i - 1] ? dp(i - 1) + 1 : 1

React 的 Dom diff

假設這麼一種情況，我們將 a 移到了 c 後，那麼框架從最終狀態倒推，如何最快的找到這個動機呢？React 採用了 僅右移策略，即對元素髮生的位置變化，只會將其移動到右邊，那麼右邊移完了，其他位置也就有序了。

我們看圖說明：

遍歷 Old 存儲 Map 和 Vue 是一樣的，然後就到了第二步遍歷 New，b 下標從原來的 1 變成了 0，需要左移纔行，但我們不左移，我們只右移，因爲所有右移做完後，左移就等於自動做掉了（前面的元素右移後，自己自然被頂到前面去了，實現了左移的效果）。

同理，c 下標從 2 變成了 1，需要左移纔行，但我們繼續不動。

a 的下標從 0 變成 2，終於可以右移了！

後面的 d、e 下標沒變，就不用動。我們縱觀整體可以發現，b 和 c 因爲前面的 a 被抽走了，自然發生了左移。這就是用一個右移代替兩個左移的高效操作。

同時我們發現，這也確實找到了我們開始提到的最佳位移策略。

那這個算法真的有這麼聰明嗎？顯然不是，這個算法只是歪打誤撞碰對了而已，有用右移替代左移的算法，就有用左移替代右移的算法，既然選擇了右移替代左移，那麼一定丟失了左移代替右移的效率。

什麼時候用左移代替右移效率最高？就是把數組最後一位移到第一位的場景：

顯然左移只要一步，那麼右移就是 n-1 步，在這個例子就是 4 步，我們看右移算法圖解：

首先找到 e，位置從 4 變成了 0，但我們不能左移！所以只能保持不動，悲劇從此開始。

雖然算法已經不是最優了，但該做的還是要做，其實之前有一個 lastIndex 概念沒有說，因爲 e 已經在 4 的位置了，所以再把 a 從 0 挪到 1 已經不夠了，此時 a 應該從 0 挪到 5。

方法就是記錄 lastIndex = max(oldIndex, newIndex) => lastIndex = max(4, 0)，下一次移動到 lastIndex + 1 也就是 5：

發現 a 從 0 變成了 5（注意，此時考慮到 lastIndex 因素），所以右移。

同理，b、c、d 也一樣。我們最後發現，發生了 4 次右移，e 也因爲自然左移了 4 次到達了首位，符合預期。

所以這是一個有利有弊的算法。新增和刪除比較簡單，和 Vue 差不多。

PS：最新版 React Dom diff 算法如有更新，歡迎在評論區指出，因爲這種算法看來不如 Vue 的高效。

總結

Dom diff 總結有這麼幾點考慮：

1. 完全對比 O(n³) 無法接受，故降級爲同層對比的 O(n) 方案。

2. 爲什麼降級可行？因爲跨層級很少發生，可以忽略。

3. 同層級也不簡單，難點是如何高效位移，即最小步數完成位移。

4. Vue 爲了儘量不移動，先左右夾擊跳過不變的，再找到最長連續子串保持不動，移動其他元素。

5. React 採用僅右移方案，在大部分從左往右移的業務場景中，得到了較好的性能。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/t78RAWGYG-sbWw_VL_nswQ