圖解Diff算法——Vue篇

一、虛擬dom

1. 虛擬 dom 是什么？

//?真實(shí)的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',?//?標(biāo)簽名
?????props:?{??//?標(biāo)簽屬性
????????id:?'list'?
?????},
?????children:?[?//?標(biāo)簽子節(jié)點(diǎn)
????????{?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',?//?標(biāo)簽名
?????props:?{??//?標(biāo)簽屬性
????????id:?'list'?
?????},
?????children:?[?//?標(biāo)簽子節(jié)點(diǎn)
?????????//?在diff中，會(huì)通過patch發(fā)現(xiàn)此處兩個(gè)節(jié)點(diǎn)沒有變化，并將其復(fù)用
????????{?tagName:?'li',?props:?{?class:?'item1'?},?children:?['111']?},
????????{?tagName:?'li',?props:?{?class:?'item2'?},?children:?['222']?},
????????//?在diff的過程中，會(huì)通過patch來找出此處發(fā)生了更改，并將其替換
????????{?tagName:?'li',?props:?{?class:?'item3'?},?children:?['three-three']},
?????]
}

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

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

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

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

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

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

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

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

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

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

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

• 虛擬dom的缺點(diǎn)？

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

1. 首屏加載時(shí)間更長

由于我們需要根據(jù)當(dāng)前的節(jié)點(diǎn)，來生成對(duì)應(yīng)的虛擬dom，我們都知道虛擬dom是一個(gè)JS對(duì)象，所以在項(xiàng)目初始化的時(shí)候去生成對(duì)應(yīng)的虛擬節(jié)點(diǎn)也是一筆時(shí)間上的開銷；因此項(xiàng)目的首次加載可能耗費(fèi)更多時(shí)間

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

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

二、Diff算法

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

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

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

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

同層比較

為什么要同層比較？

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

可以看到圖中每一層的節(jié)點(diǎn)，都是同層在進(jìn)行對(duì)比，這樣的好處就是，不會(huì)每一層的對(duì)比都是相對(duì)獨(dú)立的，不會(huì)影響到下一層的對(duì)比；同時(shí)同層對(duì)比的時(shí)間復(fù)雜度也是 O(n)；

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

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

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

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

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

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

4. 文本變化

三、vue中的diff算法

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

vue2--雙端比較

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

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

patch ()

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

sameVNode ()

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

patchVNode ()

• 拿到真實(shí)的dom節(jié)點(diǎn)el（即oldVnode）

• 判斷當(dāng)前newVnode和oldVnode是否指向同一個(gè)對(duì)象，如果是則直接return

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

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

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

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

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

updateChildren ()

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

• 主要是通過 首尾指針法 ： 通過在新舊子節(jié)點(diǎn)的首尾定義四個(gè)指針，然后不斷的對(duì)比找到可復(fù)用的節(jié)點(diǎn)，同時(shí)判斷需要移動(dòng)的節(jié)點(diǎn)。

????
a

????
b

????
c

????
b

?

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

????
d

????
b

????
a

????
c

1、理想情況下

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

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

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

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

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

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

function?vue2Diff(prevChildren,?nextChildren,?parent)?{
??//?在新舊首尾，分別定義四個(gè)指針
??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é)點(diǎn)原本在舊列表末尾的節(jié)點(diǎn)，卻是新列表中的開頭節(jié)點(diǎn)，沒有人比它更靠前，因?yàn)樗堑谝粋€(gè)，所以我們只需要把當(dāng)前的節(jié)點(diǎn)移動(dòng)到原本舊列表中的第一個(gè)節(jié)點(diǎn)之前，讓它成為第一個(gè)節(jié)點(diǎn)即可。

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

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

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

那么我們就以 newCh 的首節(jié)點(diǎn)的key值，去到 oldCh 的 key - index 的映射表中，去根據(jù)key值找到對(duì)應(yīng)的節(jié)點(diǎn)，同時(shí)將 b 節(jié)點(diǎn)移動(dòng)到首部去，因?yàn)樵谛铝斜碇?b 就屬于首部，所以在oldCh中也需要移動(dòng)到首部 ；同時(shí)，還需要將 oldCh 中的 b 節(jié)點(diǎn)設(shè)為 undefined , 因?yàn)橐呀?jīng)復(fù)用過了，就可以跳過比較了。

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é)點(diǎn)key?相同的節(jié)點(diǎn)
??????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)
????????//?復(fù)用后，設(shè)置為?undefined?
????????prevChildren[oldIndex]?=?undefined
??????}
??????newStartNode?=?nextChildren[++newStartIndex]
????}
??}
}

vue3--最長遞增子序列

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

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

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

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

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

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

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

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

這個(gè)source數(shù)組就是用來做新舊節(jié)點(diǎn)的對(duì)應(yīng)關(guān)系的，我們將新節(jié)點(diǎn)在舊列表的位置存儲(chǔ)在該數(shù)組中，我們?cè)俑鶕?jù)source計(jì)算出它的最長遞增子序列用于移動(dòng)DOM節(jié)點(diǎn)。

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

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

Dom如何移動(dòng)？

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

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

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

我們來一步一步拆解：

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

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

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

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

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

這三種情況對(duì)應(yīng)在源碼中 ：

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

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

思考題

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

時(shí)間復(fù)雜度的優(yōu)化

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

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

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

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

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

可以參考該算法的基礎(chǔ)實(shí)現(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中關(guān)于的這種節(jié)點(diǎn)的查找和替換的時(shí)間復(fù)雜度穩(wěn)定為O(n^2)

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

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

• vue3 diff 源碼^[3]

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

key的作用--性能更高

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

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

很簡單，來看個(gè)例子：

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

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

按理來說，我們應(yīng)該會(huì)復(fù)用里面的 a、b、c 三個(gè)節(jié)點(diǎn)對(duì)吧；

解決辦法--唯一值

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

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

總結(jié)

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

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

參考資料