吃透Diff算法核心原理（圖文并茂）
前言
在日常面試中，Diff算法都是繞不過(guò)去的一道坎，用最通俗的話，講最難的知識(shí)點(diǎn)一直是我寫文章的宗旨，今天我就用通俗的方式來(lái)講解一下Diff算法吧？Lets Go
什么是虛擬DOM
講Diff算法前，我先給大家講一講什么是虛擬DOM吧。這有利于后面大家對(duì)Diff算法的理解加深。
虛擬DOM是一個(gè)對(duì)象，一個(gè)什么樣的對(duì)象呢？一個(gè)用來(lái)表示真實(shí)DOM的對(duì)象，要記住這句話。我舉個(gè)例子，請(qǐng)看以下真實(shí)DOM：
"list">
????<li?class="item">哈哈li>
????<li?class="item">呵呵li>
????<li?class="item">嘿嘿li>
</ul>
對(duì)應(yīng)的虛擬DOM為：
let?oldVDOM?=?{?//?舊虛擬DOM
????????tagName:?'ul',?//?標(biāo)簽名
????????props:?{?//?標(biāo)簽屬性
????????????id:?'list'
????????},
????????children:?[?//?標(biāo)簽子節(jié)點(diǎn)
????????????{
????????????????tagName:?'li',?props:?{?class:?'item'?},?children:?['哈哈']
????????????},
????????????{
????????????????tagName:?'li',?props:?{?class:?'item'?},?children:?['呵呵']
????????????},
????????????{
????????????????tagName:?'li',?props:?{?class:?'item'?},?children:?['嘿嘿']
????????????},
????????]
????}
這時(shí)候，我修改一個(gè)li標(biāo)簽的文本：
"list">
????<li?class="item">哈哈li>
????<li?class="item">呵呵li>
????<li?class="item">林三心哈哈哈哈哈li>?//?修改
</ul>
這時(shí)候生成的新虛擬DOM為：
let?newVDOM?=?{?//?新虛擬DOM
????????tagName:?'ul',?//?標(biāo)簽名
????????props:?{?//?標(biāo)簽屬性
????????????id:?'list'
????????},
????????children:?[?//?標(biāo)簽子節(jié)點(diǎn)
????????????{
????????????????tagName:?'li',?props:?{?class:?'item'?},?children:?['哈哈']
????????????},
????????????{
????????????????tagName:?'li',?props:?{?class:?'item'?},?children:?['呵呵']
????????????},
????????????{
????????????????tagName:?'li',?props:?{?class:?'item'?},?children:?['林三心哈哈哈哈哈']
????????????},
????????]
????}
這就是咱們平常說(shuō)的新舊兩個(gè)虛擬DOM，這個(gè)時(shí)候的新虛擬DOM是數(shù)據(jù)的最新?tīng)顟B(tài)，那么我們直接拿新虛擬DOM去渲染成真實(shí)DOM的話，效率真的會(huì)比直接操作真實(shí)DOM高嗎？那肯定是不會(huì)的，看下圖：
由上圖，一看便知，肯定是第2種方式比較快，因?yàn)榈?種方式中間還夾著一個(gè)虛擬DOM的步驟，所以虛擬DOM比真實(shí)DOM快這句話其實(shí)是錯(cuò)的，或者說(shuō)是不嚴(yán)謹(jǐn)?shù)摹Ｄ钦_的說(shuō)法是什么呢？虛擬DOM算法操作真實(shí)DOM，性能高于直接操作真實(shí)DOM，虛擬DOM和虛擬DOM算法是兩種概念。虛擬DOM算法 = 虛擬DOM + Diff算法
什么是Diff算法
上面咱們說(shuō)了虛擬DOM，也知道了只有虛擬DOM + Diff算法才能真正的提高性能，那講完虛擬DOM，我們?cè)賮?lái)講講Diff算法吧，還是上面的例子(這張圖被壓縮的有點(diǎn)小，大家可以打開(kāi)看，比較清晰)：
上圖中，其實(shí)只有一個(gè)li標(biāo)簽修改了文本，其他都是不變的，所以沒(méi)必要所有的節(jié)點(diǎn)都要更新，只更新這個(gè)li標(biāo)簽就行，Diff算法就是查出這個(gè)li標(biāo)簽的算法。
總結(jié)：Diff算法是一種對(duì)比算法。對(duì)比兩者是舊虛擬DOM和新虛擬DOM，對(duì)比出是哪個(gè)虛擬節(jié)點(diǎn)更改了，找出這個(gè)虛擬節(jié)點(diǎn)，并只更新這個(gè)虛擬節(jié)點(diǎn)所對(duì)應(yīng)的真實(shí)節(jié)點(diǎn)，而不用更新其他數(shù)據(jù)沒(méi)發(fā)生改變的節(jié)點(diǎn)，實(shí)現(xiàn)精準(zhǔn)地更新真實(shí)DOM，進(jìn)而提高效率。
使用虛擬DOM算法的損耗計(jì)算：總損耗 = 虛擬DOM增刪改+（與Diff算法效率有關(guān)）真實(shí)DOM差異增刪改+（較少的節(jié)點(diǎn)）排版與重繪
直接操作真實(shí)DOM的損耗計(jì)算：總損耗 = 真實(shí)DOM完全增刪改+（可能較多的節(jié)點(diǎn)）排版與重繪
Diff算法的原理
Diff同層對(duì)比
新舊虛擬DOM對(duì)比的時(shí)候，Diff算法比較只會(huì)在同層級(jí)進(jìn)行, 不會(huì)跨層級(jí)比較。所以Diff算法是:廣度優(yōu)先算法。?時(shí)間復(fù)雜度:O(n)
Diff對(duì)比流程
當(dāng)數(shù)據(jù)改變時(shí)，會(huì)觸發(fā)setter，并且通過(guò)Dep.notify去通知所有訂閱者Watcher，訂閱者們就會(huì)調(diào)用patch方法，給真實(shí)DOM打補(bǔ)丁，更新相應(yīng)的視圖。對(duì)于這一步不太了解的可以看一下我之前寫Vue源碼系列
newVnode和oldVnode：同層的新舊虛擬節(jié)點(diǎn)
patch方法
這個(gè)方法作用就是，對(duì)比當(dāng)前同層的虛擬節(jié)點(diǎn)是否為同一種類型的標(biāo)簽(同一類型的標(biāo)準(zhǔn)，下面會(huì)講)：
是：繼續(xù)執(zhí)行 patchVnode方法進(jìn)行深層比對(duì)否：沒(méi)必要比對(duì)了，直接整個(gè)節(jié)點(diǎn)替換成 新虛擬節(jié)點(diǎn)
來(lái)看看patch的核心原理代碼
function?patch(oldVnode,?newVnode)?{
??//?比較是否為一個(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,?vnode.el,?api.nextSibling(oEl))?//?將新元素添加進(jìn)父元素
??????api.removeChild(parentEle,?oldVnode.el)??//?移除以前的舊元素節(jié)點(diǎn)
??????//?設(shè)置null，釋放內(nèi)存
??????oldVnode?=?null
????}
??}
??return?newVnode
}
sameVnode方法
patch關(guān)鍵的一步就是sameVnode方法判斷是否為同一類型節(jié)點(diǎn)，那問(wèn)題來(lái)了，怎么才算是同一類型節(jié)點(diǎn)呢？這個(gè)類型的標(biāo)準(zhǔn)是什么呢？
咱們來(lái)看看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方法
這個(gè)函數(shù)做了以下事情：
找到對(duì)應(yīng)的 真實(shí)DOM，稱為el判斷 newVnode和oldVnode是否指向同一個(gè)對(duì)象，如果是，那么直接return如果他們都有文本節(jié)點(diǎn)并且不相等，那么將 el的文本節(jié)點(diǎn)設(shè)置為newVnode的文本節(jié)點(diǎn)。如果 oldVnode有子節(jié)點(diǎn)而newVnode沒(méi)有，則刪除el的子節(jié)點(diǎn)如果 oldVnode沒(méi)有子節(jié)點(diǎn)而newVnode有，則將newVnode的子節(jié)點(diǎn)真實(shí)化之后添加到el如果兩者都有子節(jié)點(diǎn)，則執(zhí)行 updateChildren函數(shù)比較子節(jié)點(diǎn)，這一步很重要
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)，并更新
??????updateChildren(el,?oldCh,?newCh)
????}?else?if?(newCh)?{
??????//?新虛擬節(jié)點(diǎn)有子節(jié)點(diǎn)，舊虛擬節(jié)點(diǎn)沒(méi)有
??????//?創(chuàng)建新虛擬節(jié)點(diǎn)的子節(jié)點(diǎn)，并更新到真實(shí)DOM上去
??????createEle(newVnode)
????}?else?if?(oldCh)?{
??????//?舊虛擬節(jié)點(diǎn)有子節(jié)點(diǎn)，新虛擬節(jié)點(diǎn)沒(méi)有
??????//直接刪除真實(shí)DOM里對(duì)應(yīng)的子節(jié)點(diǎn)
??????api.removeChild(el)
????}
??}
}
其他幾個(gè)點(diǎn)都很好理解，我們?cè)敿?xì)來(lái)講一下updateChildren
updateChildren方法
這是patchVnode里最重要的一個(gè)方法，新舊虛擬節(jié)點(diǎn)的子節(jié)點(diǎn)對(duì)比，就是發(fā)生在updateChildren方法中，接下來(lái)就結(jié)合一些圖來(lái)講，讓大家更好理解吧
是怎么樣一個(gè)對(duì)比方法呢？就是首尾指針?lè)?/code>，新的子節(jié)點(diǎn)集合和舊的子節(jié)點(diǎn)集合，各有首尾兩個(gè)指針，舉個(gè)例子：
<ul>
????<li>ali>
????<li>bli>
????<li>cli>
ul>
修改數(shù)據(jù)后
<ul>
????<li>bli>
????<li>cli>
????<li>eli>
????<li>ali>
ul>
那么新舊兩個(gè)子節(jié)點(diǎn)集合以及其首尾指針為：
然后會(huì)進(jìn)行互相進(jìn)行比較，總共有五種比較情況：
1、 oldS 和 newS使用sameVnode方法進(jìn)行比較，sameVnode(oldS, newS)2、 oldS 和 newE使用sameVnode方法進(jìn)行比較，sameVnode(oldS, newE)3、 oldE 和 newS使用sameVnode方法進(jìn)行比較，sameVnode(oldE, newS)4、 oldE 和 newE使用sameVnode方法進(jìn)行比較，sameVnode(oldE, newE)5、如果以上邏輯都匹配不到，再把所有舊子節(jié)點(diǎn)的? key?做一個(gè)映射到舊節(jié)點(diǎn)下標(biāo)的?key -> index?表，然后用新?vnode?的?key?去找出在舊節(jié)點(diǎn)中可以復(fù)用的位置。
接下來(lái)就以上面代碼為例，分析一下比較的過(guò)程
分析之前，請(qǐng)大家記住一點(diǎn)，最終的渲染結(jié)果都要以newVDOM為準(zhǔn)，這也解釋了為什么之后的節(jié)點(diǎn)移動(dòng)需要移動(dòng)到newVDOM所對(duì)應(yīng)的位置
第一步
oldS?=?a,?oldE?=?c
newS?=?b,?newE?=?a
比較結(jié)果：oldS 和 newE?相等，需要把節(jié)點(diǎn)a移動(dòng)到newE所對(duì)應(yīng)的位置，也就是末尾，同時(shí)oldS++，newE--
第二步
oldS?=?b,?oldE?=?c
newS?=?b,?newE?=?e
比較結(jié)果：oldS 和 newS相等，需要把節(jié)點(diǎn)b移動(dòng)到newS所對(duì)應(yīng)的位置，同時(shí)oldS++,newS++
第三步
oldS?=?c,?oldE?=?c
newS?=?c,?newE?=?e
比較結(jié)果：oldS、oldE 和 newS相等，需要把節(jié)點(diǎn)c移動(dòng)到newS所對(duì)應(yīng)的位置，同時(shí)oldS++,oldE--,newS++
第四步? oldS > oldE，則oldCh先遍歷完成了，而newCh還沒(méi)遍歷完，說(shuō)明newCh比oldCh多，所以需要將多出來(lái)的節(jié)點(diǎn)，插入到真實(shí)DOM上對(duì)應(yīng)的位置上
思考題 我在這里給大家留一個(gè)思考題哈。上面的例子是 newCh比oldCh多，假如相反，是oldCh比newCh多的話，那就是newCh先走完循環(huán)，然后oldCh會(huì)有多出的節(jié)點(diǎn)，結(jié)果會(huì)在真實(shí)DOM里進(jìn)行刪除這些舊節(jié)點(diǎn)。大家可以自己思考一下，模擬一下這個(gè)過(guò)程，像我一樣，畫圖模擬，才能鞏固上面的知識(shí)。
附上updateChildren的核心原理代碼
function?updateChildren(parentElm,?oldCh,?newCh)?{
??let?oldStartIdx?=?0,?newStartIdx?=?0
??let?oldEndIdx?=?oldCh.length?-?1
??let?oldStartVnode?=?oldCh[0]
??let?oldEndVnode?=?oldCh[oldEndIdx]
??let?newEndIdx?=?newCh.length?-?1
??let?newStartVnode?=?newCh[0]
??let?newEndVnode?=?newCh[newEndIdx]
??let?oldKeyToIdx
??let?idxInOld
??let?elmToMove
??let?before
??while?(oldStartIdx?<=?oldEndIdx?&&?newStartIdx?<=?newEndIdx)?{
????if?(oldStartVnode?==?null)?{
??????oldStartVnode?=?oldCh[++oldStartIdx]
????}?else?if?(oldEndVnode?==?null)?{
??????oldEndVnode?=?oldCh[--oldEndIdx]
????}?else?if?(newStartVnode?==?null)?{
??????newStartVnode?=?newCh[++newStartIdx]
????}?else?if?(newEndVnode?==?null)?{
??????newEndVnode?=?newCh[--newEndIdx]
????}?else?if?(sameVnode(oldStartVnode,?newStartVnode))?{
??????patchVnode(oldStartVnode,?newStartVnode)
??????oldStartVnode?=?oldCh[++oldStartIdx]
??????newStartVnode?=?newCh[++newStartIdx]
????}?else?if?(sameVnode(oldEndVnode,?newEndVnode))?{
??????patchVnode(oldEndVnode,?newEndVnode)
??????oldEndVnode?=?oldCh[--oldEndIdx]
??????newEndVnode?=?newCh[--newEndIdx]
????}?else?if?(sameVnode(oldStartVnode,?newEndVnode))?{
??????patchVnode(oldStartVnode,?newEndVnode)
??????api.insertBefore(parentElm,?oldStartVnode.el,?api.nextSibling(oldEndVnode.el))
??????oldStartVnode?=?oldCh[++oldStartIdx]
??????newEndVnode?=?newCh[--newEndIdx]
????}?else?if?(sameVnode(oldEndVnode,?newStartVnode))?{
??????patchVnode(oldEndVnode,?newStartVnode)
??????api.insertBefore(parentElm,?oldEndVnode.el,?oldStartVnode.el)
??????oldEndVnode?=?oldCh[--oldEndIdx]
??????newStartVnode?=?newCh[++newStartIdx]
????}?else?{
??????//?使用key時(shí)的比較
??????if?(oldKeyToIdx?===?undefined)?{
????????oldKeyToIdx?=?createKeyToOldIdx(oldCh,?oldStartIdx,?oldEndIdx)?//?有key生成index表
??????}
??????idxInOld?=?oldKeyToIdx[newStartVnode.key]
??????if?(!idxInOld)?{
????????api.insertBefore(parentElm,?createEle(newStartVnode).el,?oldStartVnode.el)
????????newStartVnode?=?newCh[++newStartIdx]
??????}
??????else?{
????????elmToMove?=?oldCh[idxInOld]
????????if?(elmToMove.sel?!==?newStartVnode.sel)?{
??????????api.insertBefore(parentElm,?createEle(newStartVnode).el,?oldStartVnode.el)
????????}?else?{
??????????patchVnode(elmToMove,?newStartVnode)
??????????oldCh[idxInOld]?=?null
??????????api.insertBefore(parentElm,?elmToMove.el,?oldStartVnode.el)
????????}
????????newStartVnode?=?newCh[++newStartIdx]
??????}
????}
??}
??if?(oldStartIdx?>?oldEndIdx)?{
????before?=?newCh[newEndIdx?+?1]?==?null???null?:?newCh[newEndIdx?+?1].el
????addVnodes(parentElm,?before,?newCh,?newStartIdx,?newEndIdx)
??}?else?if?(newStartIdx?>?newEndIdx)?{
????removeVnodes(parentElm,?oldCh,?oldStartIdx,?oldEndIdx)
??}
}
用index做key
平常v-for循環(huán)渲染的時(shí)候，為什么不建議用index作為循環(huán)項(xiàng)的key呢？
我們舉個(gè)例子，左邊是初始數(shù)據(jù)，然后我在數(shù)據(jù)前插入一個(gè)新數(shù)據(jù)，變成右邊的列表
??????????????????????<ul>
????<li?key="0">ali>????????<li?key="0">林三心li>
????<li?key="1">bli>????????<li?key="1">ali>
????<li?key="2">cli>????????<li?key="2">bli>
??????????????????????????????<li?key="3">cli>
ul>?????????????????????</ul>
按理說(shuō)，最理想的結(jié)果是：只插入一個(gè)li標(biāo)簽新節(jié)點(diǎn)，其他都不動(dòng)，確保操作DOM效率最高。但是我們這里用了index來(lái)當(dāng)key的話，真的會(huì)實(shí)現(xiàn)我們的理想結(jié)果嗎？廢話不多說(shuō)，實(shí)踐一下：
???<li?v-for="(item,?index)?in?list"?:key="index">{{?item.title?}}li>
</ul>
增加button>
list:?[
????????{?title:?"a",?id:?"100"?},
????????{?title:?"b",?id:?"101"?},
????????{?title:?"c",?id:?"102"?},
??????]
??????
add()?{
??????this.list.unshift({?title:?"林三心",?id:?"99"?});
????}
點(diǎn)擊按鈕我們可以看到，并不是我們預(yù)想的結(jié)果，而是所有l(wèi)i標(biāo)簽都更新了
為什么會(huì)這樣呢？還是通過(guò)圖來(lái)解釋
按理說(shuō)，a，b，c三個(gè)li標(biāo)簽都是復(fù)用之前的，因?yàn)樗麄內(nèi)齻€(gè)根本沒(méi)改變，改變的只是前面新增了一個(gè)林三心
但是我們前面說(shuō)了，在進(jìn)行子節(jié)點(diǎn)的?diff算法?過(guò)程中，會(huì)進(jìn)行?舊首節(jié)點(diǎn)和新首節(jié)點(diǎn)的sameNode對(duì)比，這一步命中了邏輯，因?yàn)楝F(xiàn)在新舊兩次首部節(jié)點(diǎn)?的?key?都是?0了，同理，key為1和2的也是命中了邏輯，導(dǎo)致相同key的節(jié)點(diǎn)會(huì)去進(jìn)行patchVnode更新文本，而原本就有的c節(jié)點(diǎn)，卻因?yàn)橹皼](méi)有key為4的節(jié)點(diǎn)，而被當(dāng)做了新節(jié)點(diǎn)，所以很搞笑，使用index做key，最后新增的居然是本來(lái)就已有的c節(jié)點(diǎn)。所以前三個(gè)都進(jìn)行patchVnode更新文本，最后一個(gè)進(jìn)行了新增，那就解釋了為什么所有l(wèi)i標(biāo)簽都更新了。
那我們可以怎么解決呢？其實(shí)我們只要使用一個(gè)獨(dú)一無(wú)二的值來(lái)當(dāng)做key就行了
???<li?v-for="item?in?list"?:key="item.id">{{?item.title?}}li>
</ul>
現(xiàn)在再來(lái)看看效果
為什么用了id來(lái)當(dāng)做key就實(shí)現(xiàn)了我們的理想效果呢，因?yàn)檫@么做的話，a，b，c節(jié)點(diǎn)的key就會(huì)是永遠(yuǎn)不變的，更新前后key都是一樣的，并且又由于a，b，c節(jié)點(diǎn)的內(nèi)容本來(lái)就沒(méi)變，所以就算是進(jìn)行了patchVnode，也不會(huì)執(zhí)行里面復(fù)雜的更新操作，節(jié)省了性能，而林三心節(jié)點(diǎn)，由于更新前沒(méi)有他的key所對(duì)應(yīng)的節(jié)點(diǎn)，所以他被當(dāng)做新的節(jié)點(diǎn)，增加到真實(shí)DOM上去了。
結(jié)語(yǔ)
希望能幫到那些一直想了解虛擬DOM和Diff算法的同學(xué)
如果你覺(jué)得本文有幫到你一點(diǎn)點(diǎn)的話，請(qǐng)點(diǎn)個(gè)贊唄哈哈