圖解Diff算法——Vue篇

一、虛擬dom

1. 虛擬 dom 是什么？

//?真實的dom結(jié)構(gòu)
<ul?id='list'>
????<li?class='item1'>111li>
????<li?class='item2'>222li>
????<li?class='item3'>333li>
ul>

//?舊的虛擬dom結(jié)構(gòu)
const?oldVDom?=?{?
?????tagName:?'ul',?//?標簽名
?????props:?{??//?標簽屬性
????????id:?'list'?
?????},
?????children:?[?//?標簽子節(jié)點
????????{?tagName:?'li',?props:?{?class:?'item1'?},?children:?['111']?},
????????{?tagName:?'li',?props:?{?class:?'item2'?},?children:?['222']?},
????????{?tagName:?'li',?props:?{?class:?'item3'?},?children:?['333']?},
?????]
}

<ul?id='list'>
????<li?class='item1'>111li>
????<li?class='item2'>222li>
????<li?class='item3'>three-threeli>
ul>

//?新的虛擬dom結(jié)構(gòu)
const?newVDom?=?{?
?????tagName:?'ul',?//?標簽名
?????props:?{??//?標簽屬性
????????id:?'list'?
?????},
?????children:?[?//?標簽子節(jié)點
?????????//?在diff中，會通過patch發(fā)現(xiàn)此處兩個節(jié)點沒有變化，并將其復用
????????{?tagName:?'li',?props:?{?class:?'item1'?},?children:?['111']?},
????????{?tagName:?'li',?props:?{?class:?'item2'?},?children:?['222']?},
????????//?在diff的過程中，會通過patch來找出此處發(fā)生了更改，并將其替換
????????{?tagName:?'li',?props:?{?class:?'item3'?},?children:?['three-three']},
?????]
}

2. 為什么要有虛擬 dom ？解決了什么問題？

由圖可以發(fā)現(xiàn)觸發(fā)一次重排的代價還是比較大的；如果頻繁觸發(fā)瀏覽器的重排，無疑會造成很大的性能成本。

我們都知道，在每一次事件循環(huán)后瀏覽器會有一個UI的渲染過程，那么在一次事件循環(huán)內(nèi)觸發(fā)的所有dom操作都會被當作為異步任務被放進異步任務隊列中等待被處理。

那么此例子只是更改了一次dom結(jié)構(gòu)，如果更改100+次呢？

雖然瀏覽器做了優(yōu)化，在一段時間內(nèi)頻繁觸發(fā)的dom不會被立即執(zhí)行，瀏覽器會積攢變動以最高60HZ的頻率更新視圖；但是難免還是會造成一定次數(shù)的重排。

這時候，虛擬dom就派上了用場：不管更改多少次，多少個地方的結(jié)構(gòu)，都會映射到新的虛擬dom結(jié)構(gòu)中去，然后進行diff的對比，最終渲染成真實的dom，在這一次render中只會操作一次真實的dom結(jié)構(gòu)，所以只會造成一次重排。

同時，采用JS對象去模擬DOM結(jié)構(gòu)的好處是，頁面的更新完全可以映射到JS對象中去處理，而操作內(nèi)存中的JS對象速度也會更快。

所以才有了虛擬dom的出現(xiàn)，可以看下圖虛擬dom工作原理：

• 先根據(jù)初始的dom結(jié)構(gòu)，生成一個 舊的虛擬dom：oldVDom；

• 再根據(jù)修改后的dom結(jié)構(gòu)，生成 一個新的虛擬dom：newVDom；

• 然后通過diff算法來對比新舊虛擬DOM，從而找出需要替換的節(jié)點，然后將其渲染為真實的dom結(jié)構(gòu)；

• 虛擬dom的缺點？

看了上述虛擬dom的優(yōu)點，我們來聊聊使用它的一些代價：

1. 首屏加載時間更長

由于我們需要根據(jù)當前的節(jié)點，來生成對應的虛擬dom，我們都知道虛擬dom是一個JS對象，所以在項目初始化的時候去生成對應的虛擬節(jié)點也是一筆時間上的開銷；因此項目的首次加載可能耗費更多時間

2. 極端場景下性能不是最優(yōu)解

栗子??：如果當前頁面的節(jié)點基本全都改變了，那我們?nèi)プ隽艘淮蝑iff的patch過程相當于做了無效操作；

二、Diff算法

了解了虛擬dom結(jié)構(gòu)之后，我們都清楚了diff的觸發(fā)時機是在新舊VDom進行對比的時候。

tips：既然所有的更改都被映射到了新的VDom上，那么為何不直接將新的VDom渲染成真實的dom呢？

answer：如果直接渲染的話，會默認把所有節(jié)點都更新一遍，造成不必要的節(jié)點更新；而經(jīng)過了diff的比較后可以精確的找出那些節(jié)點需要更新，從而實現(xiàn)按需更新的理念，節(jié)省性能；

那么Diff算法的比較規(guī)則有哪些呢？

同層比較

為什么要同層比較？

如果不同層比較的話，全部的對比完一整個dom結(jié)構(gòu)，時間復雜度是 O(n^3) ; 時間成本太大了；所以改用同層比較這樣的方法去犧牲了精度而提高了時間效率。

可以看到圖中每一層的節(jié)點，都是同層在進行對比，這樣的好處就是，不會每一層的對比都是相對獨立的，不會影響到下一層的對比；同時同層對比的時間復雜度也是 O(n)；

同時也是遵循一個深度優(yōu)先的原則；diff的過程是一個深度優(yōu)先遍歷節(jié)點，然后將該節(jié)點與newVDom中的同層節(jié)點進行對比，如果有差異，則記錄該節(jié)點到JS對象中。

在同層對比的過程中有這樣幾種情況：

<div>
????<p>pppp>
????<ul?id='list'?>
????????<li?class='item1'>111li>???
????????<li?class='item2'>222li>??
????????<li?class='item3'>333li>
????ul>
????<div>divdiv>
div>

<div>
????//?1.?節(jié)點類型發(fā)生了改變
????<h3>ppph3>
????//?2.?節(jié)點類型一樣，屬性發(fā)生變化
????<ul?id='list-change'>
????????<li?class='item1'>111li>???
????????<li?class='item2'>222li>??
????????//?3.?節(jié)點被刪除
????????//?<li?class='item3'>333li>?
????????//?4.?新增節(jié)點
????????<li?class='item4'>444li>??
????ul>
????//?4.?文本變化
????<div>屬性變化div>
div>

1. 節(jié)點類型變了

2. 節(jié)點類型一樣，屬性或者屬性值發(fā)生變化

3. 刪除/新增/改變 節(jié)點

4. 文本變化

三、vue中的diff算法

在了解了虛擬dom和diff算法的相關內(nèi)容后，我們來看看各大框架中是如何做處理的吧！

vue2--雙端比較

首先，數(shù)據(jù)改變會觸發(fā) setter，然后調(diào)用 Dep.notify(), 并且通過Dep.notify去通知所有訂閱者Watcher?， 訂閱者們就會調(diào)用patch方法?， 給真實 DOM 打補丁，更新相應的視圖。

接下來我們來分析幾個核心函數(shù)吧：

patch ()

function?patch(oldVnode,?newVnode)?{?//?傳入新、舊節(jié)點
??//?比較是否為一個類型的節(jié)點
??if?(sameVnode(oldVnode,?newVnode))?{
????//?是：繼續(xù)進行深層比較
????patchVnode(oldVnode,?newVnode)
??}?else?{
????//?否
????const?oldEl?=?oldVnode.el?//?舊虛擬節(jié)點的真實DOM節(jié)點
????const?parentEle?=?api.parentNode(oldEl)?//?獲取父節(jié)點
????createEle(newVnode)?//?創(chuàng)建新虛擬節(jié)點對應的真實DOM節(jié)點
????if?(parentEle?!==?null)?{
??????api.insertBefore(parentEle,?newVnode.el,?api.nextSibling(oldEl))?//?將新元素添加進父元素
??????api.removeChild(parentEle,?oldVnode.el)??//?移除以前的舊元素節(jié)點
??????//?設置null，釋放內(nèi)存
??????oldVnode?=?null
????}
??}
??return?newVnode
}

sameVNode ()

function?sameVnode(oldVnode,?newVnode)?{
??return?(
????oldVnode.key?===?newVnode.key?&&?//?key值是否一樣
????oldVnode.tagName?===?newVnode.tagName?&&?//?標簽名是否一樣
????oldVnode.isComment?===?newVnode.isComment?&&?//?是否都為注釋節(jié)點
????isDef(oldVnode.data)?===?isDef(newVnode.data)?&&?//?是否都定義了data
????sameInputType(oldVnode,?newVnode)?//?當標簽為input時，type必須是否相同
??)
}

patchVNode ()

• 拿到真實的dom節(jié)點el（即oldVnode）

• 判斷當前newVnode和oldVnode是否指向同一個對象，如果是則直接return

• 如果是文本節(jié)點，且文本有變化，則直接調(diào)用api 將文本替換；若文本沒有變化，則繼續(xù)對比新舊節(jié)點的子節(jié)點children

• 如果oldVnode有子節(jié)點而newVnode沒有，則刪除el的子節(jié)點

• 如果oldVnode沒有子節(jié)點而newVnode有，則將newVnode的子節(jié)點真實化之后添加到el

• 如果兩者都有子節(jié)點，則執(zhí)行updateChildren函數(shù)比較子節(jié)點，這一步很重要---diff的核心

function?patchVnode(oldVnode,?newVnode)?{
??const?el?=?newVnode.el?=?oldVnode.el?//?獲取真實DOM對象
??//?獲取新舊虛擬節(jié)點的子節(jié)點數(shù)組
??const?oldCh?=?oldVnode.children,?newCh?=?newVnode.children
??//?如果新舊虛擬節(jié)點是同一個對象，則終止
??if?(oldVnode?===?newVnode)?return
??//?如果新舊虛擬節(jié)點是文本節(jié)點，且文本不一樣
??if?(oldVnode.text?!==?null?&&?newVnode.text?!==?null?&&?oldVnode.text?!==?newVnode.text)?{
????//?則直接將真實DOM中文本更新為新虛擬節(jié)點的文本
????api.setTextContent(el,?newVnode.text)
??}?else?{
????if?(oldCh?&&?newCh?&&?oldCh?!==?newCh)?{
??????//?新舊虛擬節(jié)點都有子節(jié)點，且子節(jié)點不一樣
??????//?對比子節(jié)點，并更新
??????/*? diff核心！！*/??
??????updateChildren(el,?oldCh,?newCh)?
????}?else?if?(newCh)?{
??????//?新虛擬節(jié)點有子節(jié)點，舊虛擬節(jié)點沒有
??????//?創(chuàng)建新虛擬節(jié)點的子節(jié)點，并更新到真實DOM上去
??????createEle(newVnode)
????}?else?if?(oldCh)?{
??????//?舊虛擬節(jié)點有子節(jié)點，新虛擬節(jié)點沒有
??????//?直接刪除真實DOM里對應的子節(jié)點
??????api.removeChild(el)
????}
??}
}

updateChildren ()

下面就通過一些圖解來講解吧：

• 主要是通過 首尾指針法 ： 通過在新舊子節(jié)點的首尾定義四個指針，然后不斷的對比找到可復用的節(jié)點，同時判斷需要移動的節(jié)點。

????
a

????
b

????
c

????
b

?

修改數(shù)據(jù)后????//?a,b,c,d??->??d,b,a,c

????
d

????
b

????
a

????
c

1、理想情況下

可以看到在 oldCh 和 newCh 的首尾定義了四個指針：

• 1、oldS和 newS使用sameVnode方法進行比較，sameVnode(oldS, newS) ；如果相同，則 oldS++，newS++

• 2、oldE 和newE使用sameVnode方法進行比較，sameVnode(oldE, newE)；如果相同，則 oldE--，newS --

• 3、oldS和 newE使用sameVnode方法進行比較，sameVnode(oldS, newE)；如果相同，則 oldS ++，newS --

• 4、oldE 和 newS使用sameVnode方法進行比較，sameVnode(oldE, newS)；如果相同，則 oldE --，newS ++

這是一個不斷向內(nèi)部收縮的過程，直到對比完所有的節(jié)點；

function?vue2Diff(prevChildren,?nextChildren,?parent)?{
??//?在新舊首尾，分別定義四個指針
??let?oldStartIndex?=?0,
????oldEndIndex?=?prevChildren.length?-?1
????newStartIndex?=?0,
????newEndIndex?=?nextChildren.length?-?1;
??let?oldStartNode?=?prevChildren[oldStartIndex],
????oldEndNode?=?prevChildren[oldEndIndex],
????newStartNode?=?nextChildren[newStartIndex],
????newEndNode?=?nextChildren[newEndIndex];
???//?不斷向內(nèi)收縮
??while?(oldStartIndex?<=?oldEndIndex?&&?newStartIndex?<=?newEndIndex)?{
??????if?(oldStartNode.key?===?newStartNode.key)?{
????????...
??????}?else?if?(oldEndNode.key?===?newEndNode.key)?{
????????...
??????}?else?if?(oldStartNode.key?===?newEndNode.key)?{
????????...
??????}?else?if?(oldEndNode.key?===?newStartNode.key)?{
????????...
??????}
??}
}

以上圖中的為第一步，我們可以發(fā)現(xiàn)，d 節(jié)點原本在舊列表末尾的節(jié)點，卻是新列表中的開頭節(jié)點，沒有人比它更靠前，因為他是第一個，所以我們只需要把當前的節(jié)點移動到原本舊列表中的第一個節(jié)點之前，讓它成為第一個節(jié)點即可。

最終呢，我們就得到了對比后的 dbac 啦，同時發(fā)現(xiàn)只有 d 和 a 節(jié)點需要進行移動，而b 、c節(jié)點都是不需要移動的；那么至此，一個理想狀態(tài)下的diff比較過程就結(jié)束了，是不是感覺很清晰易懂呢？

2、非理想狀態(tài)下

• 如果這四種方式都沒有找到該怎么處理呢？

那么我們就以 newCh 的首節(jié)點的key值，去到 oldCh 的 key - index 的映射表中，去根據(jù)key值找到對應的節(jié)點，同時將 b 節(jié)點移動到首部去，因為在新列表中 b 就屬于首部，所以在oldCh中也需要移動到首部 ；同時，還需要將 oldCh 中的 b 節(jié)點設為 undefined , 因為已經(jīng)復用過了，就可以跳過比較了。

function?vue2Diff(prevChildren,?nextChildren,?parent)?{
??//...
??while?(oldStartIndex?<=?oldEndIndex?&&?newStartIndex?<=?newEndIndex)?{
????if?(oldStartNode.key?===?newStartNode.key)?{
????//...
????}?else?if?(oldEndNode.key?===?newEndNode.key)?{
????//...
????}?else?if?(oldStartNode.key?===?newEndNode.key)?{
????//...
????}?else?if?(oldEndNode.key?===?newStartNode.key)?{
????//...
????}?else?{
??????//?在舊列表中找到?和新列表頭節(jié)點key?相同的節(jié)點
??????let?newtKey?=?newStartNode.key,
????????oldIndex?=?prevChildren.findIndex(child?=>?child.key?===?newKey);
??????
??????if?(oldIndex?>?-1)?{
????????let?oldNode?=?prevChildren[oldIndex];
????????patch(oldNode,?newStartNode,?parent)
????????parent.insertBefore(oldNode.el,?oldStartNode.el)
????????//?復用后，設置為?undefined?
????????prevChildren[oldIndex]?=?undefined
??????}
??????newStartNode?=?nextChildren[++newStartIndex]
????}
??}
}

vue3--最長遞增子序列

那么相比vue2中的雙端對比，在vue3中的diff算法，又做了哪些優(yōu)化呢？

1. 從頭對比找到有相同的節(jié)點 patch ，發(fā)現(xiàn)不同，立即跳出。

2. 如果第一步?jīng)]有patch完，立即，從后往前開始patch ,如果發(fā)現(xiàn)不同立即跳出循環(huán)。

3. 如果新的節(jié)點大于老的節(jié)點數(shù) ，對于剩下的節(jié)點全部以新的vnode處理（這種情況說明已經(jīng)patch完相同的vnode）。

4. 對于老的節(jié)點大于新的節(jié)點的情況 ， 對于超出的節(jié)點全部卸載（這種情況說明已經(jīng)patch完相同的vnode）。

5. 不確定的元素（這種情況說明沒有patch完相同的vnode） 與 3 ，4對立關系。

前面的邏輯跟vue2還是比較像，逐漸向中間收縮，那么關鍵點就在判斷哪些節(jié)點是需要變動的。

在經(jīng)歷上述操作后，會出現(xiàn)以下節(jié)點需要判斷（即圖中圈起來的節(jié)點）：

這個source數(shù)組就是用來做新舊節(jié)點的對應關系的，我們將新節(jié)點在舊列表的位置存儲在該數(shù)組中，我們再根據(jù)source計算出它的最長遞增子序列用于移動DOM節(jié)點。

const?newVNodeMap?=?{
????c:?'1',?
????d:?'2',
????b:?'3',
????i:?'4'
}

在找節(jié)點時，如果舊節(jié)點在新列表中沒有的話，直接刪除就好。除此之外，我們還需要一個數(shù)量表示記錄我們已經(jīng)patch過的節(jié)點，如果數(shù)量已經(jīng)與新列表剩余的節(jié)點數(shù)量一樣，那么剩下的舊節(jié)點我們就直接刪除了就可以了。

Dom如何移動？

首先，我們需要定義一個Lis數(shù)組來存儲source中的最長連續(xù)遞增子序列的下標：- ? 然后從后往前遍歷 source 數(shù)組；這個過程中會發(fā)生三種情況：

• 當前數(shù)值為 -1 ，也就說明該節(jié)點是新增的，我們直接將其插入到隊尾就好了，同時 i--。
• 當前的索引和 Lis 中的值一致，即 i == Lis[j] ，同時 i --, j --。
• 當前的索引不是 Lis 中的值，那么該節(jié)點就需要進行移動，我們只需要將該節(jié)點插入到隊尾就可以了，因為隊尾是排好序的。

tips：沒看懂這三種情況？不要慌：

我們來一步一步拆解：

1. 首先，i = 3，即上圖中，值為 -1 為第一種情況，節(jié)點需要新增，i--；

2. i = 2，索引為 2 != Lis[j] ****為第三種情況，節(jié)點需要移動，直接在舊列表中，將b節(jié)點插入到尾部位置，i --

3. i = 1，此時索引 i == Lis[j] 為第二種情況，我們的節(jié)點不需要移動；

4. i = 0，此時索引 i == Lis[j] 為第二種情況，我們的節(jié)點也不需要移動；

至此 vue3的diff的對比過程就已經(jīng)完成了，相比于2中的首尾指針法，在這種非理想情況下的節(jié)點對比采用了最長遞增子序列的算法思想來做處理；

這三種情況對應在源碼中 ：

function?vue3Diff(prevChildren,?nextChildren,?parent)?{
??//...
??if?(move)?{
????//?需要移動
????const?seq?=?lis(source);?//?[0,?1]
????let?j?=?seq.length?-?1;??//?最長子序列的指針
????//?從后向前遍歷
????for?(let?i = nextLeft - 1；i >=?0; i--)?{
??????let?pos?=?nextStart?+?i,?//?對應新列表的index
????????nextNode?=?nextChildren[pos],?//?找到vnode
????????nextPos?=?pos?+?1，????//?下一個節(jié)點的位置，用于移動DOM
????????refNode?=?nextPos?>=?nextChildren.length???null?:?nextChildren[nextPos].el,?//DOM節(jié)點
????????cur?=?source[i];??????//?當前source的值，用來判斷節(jié)點是否需要移動
??????if?(cur?===?-1)?{
????????//?情況1，該節(jié)點是全新節(jié)點
????????mount(nextNode,?parent,?refNode)
??????}?else?if?(cur?===?seq[j])?{
????????//?情況2，是遞增子序列，該節(jié)點不需要移動
????????//?讓j指向下一個
????????j--
??????}?else?{
????????//?情況3，不是遞增子序列，該節(jié)點需要移動
????????parent.insetBefore(nextNode.el,?refNode)
??????}
????}
??}?else?{
??//?不需要移動
??for?(let?i = nextLeft - 1；i >=?0; i--)?{
??????let?cur?=?source[i];??????????????//?當前source的值，用來判斷節(jié)點是否需要移動
????
??????if?(cur?===?-1)?{
???????let?pos?=?nextStart?+?i,?????????//?對應新列表的index
??????????nextNode?=?nextChildren[pos],?//?找到vnode
??????????nextPos?=?pos?+?1，???????????//?下一個節(jié)點的位置，用于移動DOM
??????????refNode?=?nextPos?>=?nextChildren.length???null?:?nextChildren[nextPos].el,?//DOM節(jié)點
??????????mount(nextNode,?parent,?refNode)
??????}
????}
}

你可能會問，你這邊遞增的子序列需要連續(xù)嗎，那么這里給你將例子稍微變動一下：這時候你會發(fā)現(xiàn)連續(xù)遞增的節(jié)點是 c, d, e 他們不是緊密連續(xù)的，但是在整個list中卻是保持index遞增的，也不需要移動。

思考題

參考上面的圖解，結(jié)合源碼，看看下面例子中的虛擬dom節(jié)點是怎么移動的。

時間復雜度的優(yōu)化

這里我們只需要找出source中的最長連續(xù)遞增子序列 就ok了：

• 最長連續(xù)遞增子序列

• 直接放一道leetcode吧：最長遞增子序列^[2]

舉個例子：[10,5,6,7,4,1,2,8,9]

那么在該此例子中，連續(xù)遞增的子序列是 [5,6,7,8,9], 所以返回的個數(shù)是5；

可以參考該算法的基礎實現(xiàn)：

const?arr?=?[10,5,6,7,4,1,2,8,9]
function?lis(arr)?{
??let?len?=?arr.length,
????dp?=?new?Array(len).fill(1);?//?用于保存長度
??//?i?=?0?=>?O(n^2)?;??i?!=?0?=>??O(nlogn)
??for?(let?i?=?len?-?1;?i?>=?0;?i--)?{?
????let?cur?=?arr[i]
????for(let?j?=?i?+?1;?j???????let?next?=?arr[j]
??????//?如果是遞增?取更大的長度值
??????if?(cur?????}
??}
??return?Math.max(...dp)
}
lis(arr)?//?5

在vue2中關于的這種節(jié)點的查找和替換的時間復雜度穩(wěn)定為O(n^2)

在vue3中依賴于最長遞增子序列去做節(jié)點的移動和刪除/新增，時間復雜度為O(nlgn)～O(n^2)

• 至此vue3.0的diff算法大致理念以及概括完了，如果想要深入了解可以去閱讀以下源碼部分

• vue3 diff 源碼^[3]

四、key值的作用，為什么不能使用index作為key值？

key的作用--性能更高

• 在Vue中判斷節(jié)點是否可復用都是以key值作為判斷的前提條件，如果不使用key值判斷，會默認更新所有節(jié)點，而Vue中組件的更新過程也是極其復雜的，所以會造成一些不必要性能的成本；所以key可以更高效的幫助我們判斷節(jié)點的可復用性。

為什么不能使用index作為key？

很簡單，來看個例子：

??????????????????????

????a????????new??//?新增
????b????????a
????c????????b
??????????????????????????????c
???????????????????????????????????????????????

按理來說，我們應該會復用里面的 a、b、c 三個節(jié)點對吧；

解決辦法--唯一值

• 1、key值要選擇一個唯一值，通常用id來做key

• 2、不要做一些無謂的dom結(jié)構(gòu)修改或者跨層級去操作一些dom

總結(jié)

• 我們學習了虛擬dom和diff算法的基本概念，了解了為什么要存在虛擬dom和diff算法；
• 同時我們也了解了vue2和vue3中關于diff算法的處理過程，這可以更好的幫助我們理解vue的更新機制原理，同時也了解到了為什么diff可以如此高效的提升性能；
• 最后，我一直認為學習原理是為了讓我們更好的和更高效的去運用框架，可以避免一些不必要的bug問題，同時也是提升自我的一種方式途徑！

?另外，特別感謝本文審校的同學??（人名不分先后）：米澤，李世奇，胡元港

參考資料