Vue—關于響應式（三、Diff Patch原理分析）

上一節我們學習了Vue中異步渲染隊列的原理，本節我們沿着響應式圖譜學習下一個部分——渲染頁面。

如上圖所示，Vue會根據之前得到的變更通知生成一顆新的Virtual DOM樹，然後再将新的Virtual DOM樹和舊的Virtual DOM樹進行diff patch操作。

本節的目标是學習Virtual DOM以及Vue是如何對新舊兩顆Virtual DOM樹進行diff patch算法。

前面小節的連結在這裡：

Vue—關于響應式（一、依賴收集原理分析）

Vue—關于響應式（二、異步更新隊列原理分析）

一、Virtual DOM

1.1. 什麼是Virtual DOM

一聽到"虛拟DOM"這個詞彙，自然的會升起一種它很進階的感覺。沒錯，它确實很進階，但是穩住不要慌，你可以把它當成我們吃飯用的筷子，對于外國人而言，中國的筷子也是一種進階（共同點：都是外國人發明的【手動滑稽】）。你天天用筷子當然就不會覺得筷子很進階，這個道理是：你越熟悉它，它對你而言就越不神秘。

在js中，簡單了解Virtual DOM就是通過 

JS的對象結構

 來描述 

DOM樹結構

的一種工具。

1.2. 為什麼要使用Virtual DOM

這個問題很多文章是這麼回答的：操作DOM是很耗費性能的一件事情，我們可以考慮通過JS對象來模拟DOM對象，畢竟操作JS對象比操作DOM省時的多。

事實上這種說法是不對的，操作JS對象确實比操作DOM省時，但是在Virtual DOM中并不能減少DOM操作，這一步DOM操作是由Virtual DOM在diff patch的過程中完成的，通過這一步事實上它減少的是我們前端人員直接通過DOM API去增删改查DOM節點的操作，進而提高了我們的開發效率而并非産品性能。

在計算機界一直流傳着這麼一句話：

翻譯過來就是說：軟體開發中遇到的所有問題都可以通過增加一層抽象而得以解決。

Virtual DOM也是類似，它也是分層思想的一種展現，為什麼這麼說？當我們在開發的時候是基于一定的DSL的，比方說我們前端會使用HTML、JS、CSS來寫代碼，那麼架構幫我們抽象出一層Virtual DOM，通過這層Virtual DOM，架構可以将不同的Virtual DOM節點适配到不同的view顯示端，其中包括像H5、小程式以及App native，進而使我們的代碼具備一次編寫多端執行的可能性。

看完抽象的概念，我們再來看一下Virtual DOM在代碼中具體是怎麼展現的。

1.3. Virtual DOM的具體表現形式

以下面這段html代碼為例：

<ul id='list'>
  <li class='item'>Item 1</li>
  <li class='item'>Item 2</li>
  <li class='item'>Item 3</li>
</ul>
           

Virtual DOM抽象出來的js對象為：

var VNode = {
  tagName: 'ul', // 标簽名
  props: { // 屬性用對象存儲鍵值對
    id: 'list'
  },
  children: [ // 子節點
    {tagName: 'li', props: {class: 'item'}, children: ["Item 1"]},
    {tagName: 'li', props: {class: 'item'}, children: ["Item 2"]},
    {tagName: 'li', props: {class: 'item'}, children: ["Item 3"]},
  ]
}
           

對比上面的代碼，很容易看出來它們之間的映射關系。既然DOM節點可以轉換成JS對象，反之亦然，Virtual DOM需要做的就是：

1. 将你編寫好的DOM樹結構（如.vue檔案中的template）轉換成JS對象樹結構，然後再将JS對象樹建構成真正的DOM樹即可。
2. 當檢測到狀态變更時，生成新的JS對象樹并與舊的對象樹進行比對，通過diff算法最終确認要進行多少更新。

小結

• Virtual DOM是分層思想的一種展現，通過增加抽象層來幫助我們完成一次編寫多端通用的功能。
• Virtual DOM是通過JS對象結構來描述DOM樹結構的工具。
• Virtual DOM檢測到狀态變更時會生成新的對象樹，通過diff算法比對新舊對象樹來最終确認DOM更新政策。

二、Diff Patch

2.1. 什麼是diff算法

作為面向百度工程師，第一步當然是你們懂的了【手動滑稽】

百度百科給出的答案是：

• Virtual DOM中采用的算法
• 将樹結構按層級劃分，隻比較同級元素，不同層級的節點隻有建立和删除操作
• 為清單結構的每個單元添加唯一的key

有了這個概念我們繼續往下學習。

那到底什麼是diff算法？

打個比方，把老虎變成大象最短需要幾步？換種說法，把Tiger這個字元串變成Elephant字元串最短需要幾步？從Tom到Michael到Sunny呢？

為了解出這個題，你需要設計一種最優的字元串變更和匹對的算法，而Virtual DOM為了确定最優的DOM變更政策，它的解題算法就是diff。

2.2. Virtual DOM為什麼要選擇diff算法

我們都知道DOM操作的開銷非常昂貴，輕微的操作都有可能引起頁面重排損耗性能，是以要盡量減少DOM操作，diff算法的作用就是通過比對新舊Virtual DOM樹的差異，最小化的執行DOM操作，進而提高開發人員的效率。

最小化操作dom的過程，我們就不用再考慮那麼多直接操作DOM帶來的問題了，主要目的是為了提效，開發者的水準參差不齊，不用手動操作DOM了，從側面來講也是對性能的優化。

2.3. diff政策

我們的應用通過Vue架構其實會轉換成一顆虛拟DOM樹，當我們進行了一些頁面上的操作時，或者說我們得到了一些異步資料更新響應之後，其實是将左邊的DOM樹轉化成右邊的DOM樹，這個轉化過程中就要應用到diff的政策。

現在主流的MVVM架構基本都會按照以下政策：

1. 按tree層級diff
2. 按類型進行diff（元件類型或者是元素類型）
3. 清單diff

2.3.1. 按tree層級diff

如下圖所示，對每一層進行diff。這主要是因為在web UI當中很少會出現DOM節點跨層級移動，這種情況少的可以忽略不計，是以Virtual DOM的diff政策是在新舊節點樹之間按層級進行diff進而得到差異。

2.3.2. 按類型進行diff

無論Virtual DOM中的節點資料對應的是一個原生DOM節點還是Vue的一個元件，不同類型的節點所具有的子樹節點之間結構往往差異明顯，是以對不同類型的節點子樹進行遞歸diff的投入成本與産出比将會比較高昂，為了提升diff效率，Virtual DOM隻對相同類型的節點進行diff，當新舊節點發生了類型的改變時則并不進行子樹的比較，而是直接建立新類型的Virtual DOM替換舊節點。

如下圖所示，假設我們diff到了這一層

現在要将父節點的五角星轉換成下圖的三角形節點

按照規則，首先是同層級進行diff，可以看到在這一層中五角星和三角形不是一個類型，如下圖所示：

那麼這個元件以及它的子元件都會被完全的銷毀，哪怕這個元件下面的兩個五角星子元件跟原來的元件是同一個元件，它們仍然需要再一次被建立，如下圖所示：

2.3.3. 清單diff

在清單diff的過程中，可以給每一項都設定一個key，通過key可以提升diff的效率。如下圖所示，左圖沒有key，是以老的節點全部删除，新的節點再全部建立；右圖添加key值，是以隻需要将A移動到B，将C移動到D即可。

我們來看一下源碼中是怎麼進行清單diff的，以vue 2.6.11版本為例，源碼在src/vdom/patch.js中

關于updateChildren函數的源碼解析參考文章：

https://zhuanlan.zhihu.com/p/225105999

具體細節很多，我們通過圖解來看一下它具體的思想是什麼樣的。

如下圖所示，假設我們舊的Virtual DOM層級上面的節點數是這麼一個排列，現在要變成新的排列，淺灰色圓圈代表Virtual Node，也就是我們的虛拟節點，裡面的深灰色小圓圈代表的是DOM的實體

現在我們頁面上的DOM實體是以123456來排列的，我們來看圖解過程，在算法開始之前，vue裡面首先會定義四個指針，這四個指針分别是oldStartIdx/oldEndIdx、newStartIdx/newEndIdx，它們的名字其實也就代表了它們的意思，就是老的Virtual DOM節點開始的位置和結束的位置、新的Virtual DOM開始的位置以及結束的位置

代碼的判斷邏輯是，首先vue會判斷oldStartIdx以及newStartIdx這兩個指針所對應的節點的Virtual DOM是否為同一個，如下圖所示

圖示中我們發現它們就是同一個（舊樹是1，新樹是1），這時候第一輪循環就完成了，此時oldStartIdx指針往後移動了一位，newStartIdx也會往後移動了一位，如下圖所示

然後進入到第二個循環，對比下一個Virtual Node，按照上一步的邏輯，還是先比對oldStartIdx和newStartIdx的值是否相等，這個時候我們發現2和5并不是同一個Virtual Node

接下來就換一種方式比較，去比較oldEndIdx和newEndIdx，靠近末尾的兩個節點是否為同一個節點？這個時候我們發現它們又是同一個節點（舊樹是6，新樹是6）

與前面相似，第二輪循環完成，此時oldEndIdx減一，newEndIdx也進行減一，兩個結束下标向前移動一位，如下圖所示：

接下來比較第三個循環，還是先比較兩個開始下标oldStartIdx/newStartIdx所指向的Virtual Node是否一緻，我們可以看到不一緻（舊樹是2，新樹是5），如下圖所示：

然後再比較兩個結束下标oldEndIdx/newEndIdx指向的Virtual Node是否一緻，可以看到也不一緻（舊樹是5，新樹是2），如下圖所示：

之前的兩種比對方式節點都不同，這個時候就會比較oldStartIdx和newEndIdx，進行捺向比較，這個時候發現這兩個節點是一緻的（舊樹是2，新樹是2），但是它的位置發生了改變，是以這個時候就需要把oldStartIdx所指向的Virtual DOM節點裡面的真實DOM節點（深灰色2）挪到oldEndIdx所指向的Virtual DOM節點的真實DOM節點之後，同時oldStartIdx也會向後移動一位（加一），newEndIdx也會向前移動一位（減一），如下圖所示：

（捺向對比）

（挪動真實dom節點2位置）

（oldStartIdx後移一位，newEndIdx前移一位）

接下來進入第四個循環，同樣的先判斷兩個開始下标oldStartIdx/newStartIdx，可以看到節點不一緻（舊樹是3，新樹是5），如下圖所示：

然後再比較兩個結束下标oldEndIdx/newEndIdx指向的Virtual Node是否一緻，可以看到也不一緻（舊樹是5，新樹是7），如下圖所示：

接着進行捺向比較，比較oldStartIdx跟newEndIdx指向的Virtual Node是否一緻，可以看到不一緻（舊樹是3，新樹是7），如下圖所示：

這個時候就會再進行另外一種交叉方向比對，就是oldEndIdx和newStartIdx的對比，這是一個撇方向的對比，這時候發現對應的節點是一緻的（舊樹是5，新樹是5），然後就會把oldEndIdx所指向的實際的DOM節點（深灰色5）挪到oldStartIdx所指向的實際節點的前面，同時，我們的oldEndIdx向前移動一位（減一），newStartIdx往後移動一位（加一），如下圖所示：

（撇向對比）

（挪動真實dom節點5位置）

（oldStartIdx前移一位，newEndIdx後移一位）

然後進入第五個循環，同樣的先判斷兩個開始下标oldStartIdx/newStartIdx，可以看到節點不一緻（舊樹是3，新樹是7），如下圖所示：

然後再比較兩個結束下标oldEndIdx/newEndIdx指向的Virtual Node是否一緻，可以看到也不一緻（舊樹是4，新樹是7），如下圖所示：

接着進行捺向比較，oldStartIdx和newEndIdx比較，發現3和7也不一緻

然後就會進行撇向比較，也就是oldEndIdx和newStartIdx所指向的節點，4和7也不一緻

這個時候vue就會對oldStartIdx和oldEndIdx這兩個指針所指向的節點之間的所有節點進行一次周遊，然後尋找newStartIdx所指向的節點是否存在于這些老的Virtual DOM當中，如果找到的話就會把它挪到oldStartIdx所指向的節點之前。

這裡我們會發現其實是找不到的，7不在oldStartIdx和oldEndIdx這兩個指針之間，這時候就需要新建立一個節點7，在完成了這一步之後我們的newEndIdx也會向前移動一位（減一）

這個時候我們就會發現，newEndIdx已經小于newStartIdx了，這也标志着我們的New Vnode清單已經生成完畢了，接下來一步就是把我們的Old Vnode清單當中多餘的部分給删除掉。

多餘的部分其實就是oldStartIdx和oldEndIdx這兩個指針之間的那部分，也就是我們的3、4節點，删除掉這部分，如下圖所示：

這個時候我們就發現了新的Virtual DOM的清單其實就是下方的這個New Vnode清單，而實際頁面上的DOM節點1、5、7、2、6也是按照這個New Vnode清單順序來維持的，那麼Old Vnode上的Virtual DOM的生命周期也就到此為止了，也就是可以被銷毀了，如下圖所示：

2.3.3.1. key的作用

在vue的官方文檔上面着重的說了一句：

為了給Vue一個提示，以便它能跟蹤每個節點的身份，進而重用和重新排序現有元素，你需要為每一項提供一個唯一 key 屬性

文檔位址：https://cn.vuejs.org/v2/guide/list.html#%E7%BB%B4%E6%8A%A4%E7%8A%B6%E6%80%81

key屬性在這個算法當中又有什麼作用呢？

我們假設前面的Old Vnode當中多了一個節點7

當我們沒有設定key的時候，我們的匹對順序第一步還是按照兩個StartIdx所指向的節點進行比較

第二步是兩個EndIdx進行比較

第三步是捺向的方向進行比較，也就是oldStartIdx跟newEndIdx所指向的節點進行比較

第四步是撇向的方向進行比較，也就是oldEndIdx跟newStartIdx所指向的節點進行比較

這個時候發現都不一緻的時候，按照我們前面說的，如果沒有設定key的情況下就會去周遊oldStartIdx和oldEndIdx之間去尋找是否存在這麼一個節點，如果存在的話就會把它挪到前面去。

如果有設定了key屬性，首先會去尋找在這個key map當中是否存在着對應的一個序号如下圖，這裡我們可以發現7這個節點也就是key-7對應的就是我們上面的清單當中的第四項

這個時候我們就不需要再對oldStartIdx和oldEndIdx之間的節點進行周遊了，就減少了這次循環操作，可以直接把7這個節點挪到5這個節點後面去，最後删除多餘的節點就得到了新的節點樹1、5、7、2、6，如下圖所示：

從這裡我們就可以看出來，如果設定了一個key，算法複雜度為O(n)

當我們不設定key的時候，算法複雜度的最好情況才是一個O(n)，這種情況就是我們根本就沒有進行周遊，剛好完全就是匹對的情況，最壞的情況就會上升到O(n²)，其實就是說我們對每一個oldStartIdx跟oldEndIdx之間的區間都進行一次周遊。

關于key，官方文檔描述如下：

文檔位址：https://cn.vuejs.org/v2/api/#key

Vue的整個diff過程就是整個

patch

方法的流程，整個流程也會通過遞歸地調用

patchVnode

來完成對整棵Virtual DOM Tree的更新，正是因為它的節點操作是在diff過程中同時進行的，也正是因為這種形式提升了Vue在增删改查DOM節點時的效率。

2.4. 小結

• diff算法用來比對新舊Virtual DOM的差異，使我們盡可能少的操作真實DOM以提高開發效率。
• diff算法分為兩個粒度，一個是元件級别(Component diff)，另一個是元素級别(Element Diff)。元件級别的diff算法比較簡單，節點不相同就進行建立和替換，節點相同的話就會對其子節點進行更新；對子節點進行更新也就是元素級别的diff，通過插入、移動、删除等方式使舊清單與新清單一緻。
• Vue中的diff算法大緻分為5個步驟：
  1. 先從兩棵樹的開始下标進行比對
  2. 再從兩棵樹的結束下标進行比對
  3. 然後從捺向進行比對
  4. 接着從撇向進行比對
  5. 最後從Old Vnode開始下标位置和結束下标位置之間進行周遊查找（如果有設定key，則直接找到key對應的節點進行複用，無需再進行周遊）
• 清單渲染時，使用key可以很好的提高性能。

後面要學習的内容在這裡：

Vue—關于響應式（四、深入學習Vue響應式源碼）

三、參考

合格前端系列第五彈- Virtual Dom && Diff

深度了解 Virtual DOM

DIFF算法淺析（一）概念