1. 為什么要用Diff算法

由于在瀏覽器中操作DOM的代價是非常“昂貴”的，所以才在Vue引入了Virtual DOM焰枢，Virtual DOM是對真實DOM的一種抽象描述钾埂，不懂的朋友可以自行查閱相關(guān)資料。

1.1為什么需要VD

VD 最大的特點是將頁面的狀態(tài)抽象為 JS 對象的形式腋寨，配合不同的渲染工具，使跨平臺渲染成為可能。如 React 就借助 VD 實現(xiàn)了服務(wù)端渲染拘鞋、瀏覽器渲染和移動端渲染等功能。

此外矢门，在進行頁面更新的時候盆色，借助VD，DOM 元素的改變可以在內(nèi)存中進行比較祟剔，再結(jié)合框架的事務(wù)機制將多次比較的結(jié)果合并后一次性更新到頁面隔躲，從而有效地減少頁面渲染的次數(shù)，提高渲染效率物延。我們先來看下頁面的更新一般會經(jīng)過幾個階段宣旱。

從上面的例子中，可以看出頁面的呈現(xiàn)會分以下3個階段：

JS計算

生成渲染樹

繪制頁面

這個例子里面叛薯，JS計算用了691毫秒浑吟，生成渲染樹578毫秒，繪制73毫秒耗溜。如果能有效的減少生成渲染樹和繪制所花的時間组力，更新頁面的效率也會隨之提高。

通過VD的比較抖拴，我們可以將多個操作合并成一個批量的操作燎字，從而減少dom重排的次數(shù)，進而縮短了生成渲染樹和繪制所花的時間城舞。至于如何基于VD更有效率的更新dom轩触，是一個很有趣的話題，日后有機會將另寫一篇文章介紹家夺。

即使使用了Virtual DOM來進行真實DOM的渲染脱柱，在頁面更新的時候，也不能全量地將整顆Virtual DOM進行渲染拉馋，而是去渲染改變的部分榨为，這時候就需要一個計算Virtual DOM樹改變部分的算法了惨好，這個算法就是Diff算法。

2. 傳統(tǒng)的Diff算法

傳統(tǒng)的Diff算法通過循環(huán)遞歸對節(jié)點進行比較随闺，然后判斷每個節(jié)點的狀態(tài)以及要做的操作（add日川，remove，change）矩乐，最后 根據(jù)Virtual DOM進行DOM的渲染龄句。大體流程如下圖（圖來源）：

傳統(tǒng)Diff算法的復(fù)雜度為O(n^3)，這個復(fù)雜度相對來說還是較高的散罕。后來React開發(fā)者提供了一種復(fù)雜度僅為O(n) 的Diff算法分歇。下面就來看一下O(n)復(fù)雜度的Diff算法是如何實現(xiàn)的。

3. 更高效的Diff算法

React的開發(fā)者結(jié)合Web界面的特點做出了兩個大膽的假設(shè)欧漱，使得Diff算法復(fù)雜度直接從O(n^3)降低到O(n)职抡，假設(shè)如下：

兩個相同組件產(chǎn)生類似的DOM結(jié)構(gòu)，不同的組件產(chǎn)生不同的DOM結(jié)構(gòu)误甚；

對于同一層次的一組子節(jié)點缚甩，它們可以通過唯一的id進行區(qū)分。

通過這兩個假設(shè)窑邦，他們提供了下面的Diff算法思路擅威。

同層比較

新的Diff算法是逐層進行比較，只比較同一層次的節(jié)點奕翔，大大降低了復(fù)雜度裕寨，具體如下圖。在后面的內(nèi)容中也會介紹Vue中同層節(jié)點比較的具體實現(xiàn)派继。

不同類型節(jié)點的比較

如果發(fā)現(xiàn)新舊兩個節(jié)點類型不同時宾袜，Diff算法會直接刪除舊的節(jié)點及其子節(jié)點并插入新的節(jié)點，這是由于前面提出的不同組件產(chǎn)生的DOM結(jié)構(gòu)一般是不同的驾窟，所以可以不用浪費時間去比較庆猫。注意的是，刪除節(jié)點意味著徹底銷毀該節(jié)點绅络，并不會將該節(jié)點去與后面的節(jié)點相比較月培。

相同類型節(jié)點的比較

若是兩個節(jié)點類型相同時，Diff算法會更新節(jié)點的屬性實現(xiàn)轉(zhuǎn)換恩急。

列表節(jié)點的比較

列表節(jié)點的操作一般包括添加杉畜、刪除和排序，列表節(jié)點需要我們給它一個key才能進行高效的比較衷恭。

4.Vue Diff算法的實現(xiàn)

了解了Diff算法的大體思路后此叠，我們回過頭來看下Vue中的Diff算法是如何實現(xiàn)的。

Vue的Diff算法與上面的思路大體相似随珠，只比較同級的節(jié)點灭袁，若找不到與新節(jié)點類型相同的節(jié)點猬错，則插入一個新節(jié)點，若有相同類型的節(jié)點則進行節(jié)點屬性的更新茸歧，最后刪除新節(jié)點列表中不包含的舊節(jié)點倦炒。具體的實現(xiàn)在vue源碼的src/core/vdom/patch.js中的updateChildren方法中，由于代碼較長软瞎，下面簡單說一下整個的比較流程逢唤。

如上圖，有一組新舊節(jié)點數(shù)組before：[A, B, C, D]铜涉、after：[E, C, F, G]智玻，我們設(shè)置了四個哨兵節(jié)點，oldStartIdx芙代、newStartIdx、oldEndIdx盖彭、newEndIdx分別指向新舊節(jié)點數(shù)組的起始下標(biāo)和開始下標(biāo)纹烹，值為0,0,3,3；oldStartVnode召边，newStartVnode铺呵，oldEndVnode，newEndVnode則分別指向了before和after節(jié)點列表中對應(yīng)哨兵節(jié)點下標(biāo)的值隧熙，值為before[oldStartVnode],after[newStartIdx],before[oldEndIdx],after[newEndIdx]片挂。

總結(jié)

Vue中的Diff算法采用了React相似的思路，都是同層節(jié)點進行比較贞盯，在比較的過程中音念，使用了一些優(yōu)先判斷和就地復(fù)用策略，提高了Diff算法的效率躏敢。