詳解vue的diff算法
1. 當數(shù)據(jù)發(fā)生變化時骨宠，vue是怎么更新節(jié)點的砚哗？
要知道渲染真實DOM的開銷是很大的滩报，比如有時候我們修改了某個數(shù)據(jù)，如果直接渲染到真實dom上會引起整個dom樹的重繪和重排植榕，有沒有可能我們只更新我們修改的那一小塊dom而不要更新整個dom呢？diff算法能夠幫助我們尼夺。
我們先根據(jù)真實DOM生成一顆virtual DOM尊残，當virtual DOM某個節(jié)點的數(shù)據(jù)改變后會生成一個新的Vnode，然后Vnode和oldVnode作對比淤堵，發(fā)現(xiàn)有不一樣的地方就直接修改在真實的DOM上寝衫，然后使oldVnode的值為Vnode。
diff的過程就是調(diào)用名為patch的函數(shù)拐邪，比較新舊節(jié)點慰毅，一邊比較一邊給真實的DOM打補丁。
2. virtual DOM和真實DOM的區(qū)別扎阶？
virtual DOM是將真實的DOM的數(shù)據(jù)抽取出來汹胃，以對象的形式模擬樹形結(jié)構(gòu)。比如dom是這樣的：
<div><p>123</p></div>
對應(yīng)的virtual DOM（偽代碼）：
varVnode = {
? ? tag: 'div',
? ? children: [
? ? ? ? { tag: 'p', text: '123' }
? ? ]
};
（溫馨提示：VNode和oldVNode都是對象东臀，一定要記鬃偶ⅰ）
3. diff的比較方式？
在采取diff算法比較新舊節(jié)點的時候惰赋，比較只會在同層級進行, 不會跨層級比較宰掉。
<div><p>123</p></div><div><span>456</span></div>
上面的代碼會分別比較同一層的兩個div以及第二層的p和span，但是不會拿div和span作比較赁濒。在別處看到的一張很形象的圖：
diff流程圖
當數(shù)據(jù)發(fā)生改變時贵扰，set方法會讓調(diào)用Dep.notify通知所有訂閱者Watcher，訂閱者就會調(diào)用patch給真實的DOM打補丁流部，更新相應(yīng)的視圖戚绕。
具體分析
patch
來看看patch是怎么打補丁的（代碼只保留核心部分）
function patch (oldVnode, vnode) {
? ? // some codeif (sameVnode(oldVnode, vnode)) {
? ? ? ? patchVnode(oldVnode, vnode)
? ? } else {
? ? ? ? const oEl = oldVnode.el// 當前oldVnode對應(yīng)的真實元素節(jié)點let parentEle = api.parentNode(oEl)// 父元素createEle(vnode)// 根據(jù)Vnode生成新元素if(parentEle !==null) {
? ? ? ? ? ? api.insertBefore(parentEle, vnode.el, api.nextSibling(oEl)) // 將新元素添加進父元素api.removeChild(parentEle, oldVnode.el)// 移除以前的舊元素節(jié)點oldVnode =null? ? ? ? }
? ? }
? ? // some code return vnode
}
patch函數(shù)接收兩個參數(shù)oldVnode和Vnode分別代表新的節(jié)點和之前的舊節(jié)點
判斷兩節(jié)點是否值得比較，值得比較則執(zhí)行patchVnode
function sameVnode (a, b) {
? return (
? ? a.key === b.key &&// key值a.tag === b.tag &&// 標簽名a.isComment === b.isComment &&// 是否為注釋節(jié)點// 是否都定義了data枝冀，data包含一些具體信息舞丛，例如onclick , styleisDef(a.data) === isDef(b.data) &&?
? ? sameInputType(a, b) // 當標簽是<input>的時候，type必須相同? )
}
不值得比較則用Vnode替換oldVnode
如果兩個節(jié)點都是一樣的果漾，那么就深入檢查他們的子節(jié)點球切。如果兩個節(jié)點不一樣那就說明Vnode完全被改變了，就可以直接替換oldVnode绒障。
雖然這兩個節(jié)點不一樣但是他們的子節(jié)點一樣怎么辦吨凑？別忘了，diff可是逐層比較的，如果第一層不一樣那么就不會繼續(xù)深入比較第二層了鸵钝。（我在想這算是一個缺點嗎糙臼？相同子節(jié)點不能重復利用了...）
patchVnode
當我們確定兩個節(jié)點值得比較之后我們會對兩個節(jié)點指定patchVnode方法。那么這個方法做了什么呢恩商？
patchVnode (oldVnode, vnode) {
? ? const el = vnode.el = oldVnode.el
? ? let i, oldCh = oldVnode.children, ch = vnode.children
? ? if(oldVnode === vnode)returnif(oldVnode.text !==null&& vnode.text !==null&& oldVnode.text !== vnode.text) {
? ? ? ? api.setTextContent(el, vnode.text)
? ? }else {
? ? ? ? updateEle(el, vnode, oldVnode)
? ? ? ? if(oldCh && ch && oldCh !== ch) {
? ? ? ? ? ? updateChildren(el, oldCh, ch)
? ? ? ? }elseif (ch){
? ? ? ? ? ? createEle(vnode) //create el's children dom}elseif (oldCh){
? ? ? ? ? ? api.removeChildren(el)
? ? ? ? }
? ? }
}
這個函數(shù)做了以下事情：
找到對應(yīng)的真實dom变逃，稱為el
判斷Vnode和oldVnode是否指向同一個對象，如果是怠堪，那么直接return
如果他們都有文本節(jié)點并且不相等揽乱，那么將el的文本節(jié)點設(shè)置為Vnode的文本節(jié)點。
如果oldVnode有子節(jié)點而Vnode沒有粟矿，則刪除el的子節(jié)點
如果oldVnode沒有子節(jié)點而Vnode有凰棉，則將Vnode的子節(jié)點真實化之后添加到el
如果兩者都有子節(jié)點，則執(zhí)行updateChildren函數(shù)比較子節(jié)點陌粹，這一步很重要
其他幾個點都很好理解渊啰，我們詳細來講一下updateChildren
updateChildren
代碼量很大，不方便一行一行的講解申屹，所以下面結(jié)合一些示例圖來描述一下绘证。
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) {// 對于vnode.key的比較，會把oldVnode = nulloldStartVnode = oldCh[++oldStartIdx]
? ? ? ? }elseif(oldEndVnode ==null) {
? ? ? ? ? ? oldEndVnode = oldCh[--oldEndIdx]
? ? ? ? }elseif(newStartVnode ==null) {
? ? ? ? ? ? newStartVnode = newCh[++newStartIdx]
? ? ? ? }elseif(newEndVnode ==null) {
? ? ? ? ? ? newEndVnode = newCh[--newEndIdx]
? ? ? ? }elseif (sameVnode(oldStartVnode, newStartVnode)) {
? ? ? ? ? ? patchVnode(oldStartVnode, newStartVnode)
? ? ? ? ? ? oldStartVnode = oldCh[++oldStartIdx]
? ? ? ? ? ? newStartVnode = newCh[++newStartIdx]
? ? ? ? }elseif (sameVnode(oldEndVnode, newEndVnode)) {
? ? ? ? ? ? patchVnode(oldEndVnode, newEndVnode)
? ? ? ? ? ? oldEndVnode = oldCh[--oldEndIdx]
? ? ? ? ? ? newEndVnode = newCh[--newEndIdx]
? ? ? ? }elseif (sameVnode(oldStartVnode, newEndVnode)) {
? ? ? ? ? ? patchVnode(oldStartVnode, newEndVnode)
? ? ? ? ? ? api.insertBefore(parentElm, oldStartVnode.el, api.nextSibling(oldEndVnode.el))
? ? ? ? ? ? oldStartVnode = oldCh[++oldStartIdx]
? ? ? ? ? ? newEndVnode = newCh[--newEndIdx]
? ? ? ? }elseif (sameVnode(oldEndVnode, newStartVnode)) {
? ? ? ? ? ? patchVnode(oldEndVnode, newStartVnode)
? ? ? ? ? ? api.insertBefore(parentElm, oldEndVnode.el, oldStartVnode.el)
? ? ? ? ? ? oldEndVnode = oldCh[--oldEndIdx]
? ? ? ? ? ? newStartVnode = newCh[++newStartIdx]
? ? ? ? }else {
? ? ? ? ? // 使用key時的比較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)
? ? }elseif(newStartIdx > newEndIdx) {
? ? ? ? removeVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx)
? ? }
}
先說一下這個函數(shù)做了什么
將Vnode的子節(jié)點Vch和oldVnode的子節(jié)點oldCh提取出來
oldCh和vCh各有兩個頭尾的變量StartIdx和EndIdx哗讥，它們的2個變量相互比較嚷那，一共有4種比較方式。如果4種比較都沒匹配杆煞，如果設(shè)置了key魏宽，就會用key進行比較，在比較的過程中决乎，變量會往中間靠队询，一旦StartIdx>EndIdx表明oldCh和vCh至少有一個已經(jīng)遍歷完了，就會結(jié)束比較构诚。
圖解updateChildren
終于來到了這一部分蚌斩，上面的總結(jié)相信很多人也看得一臉懵逼，下面我們好好說道說道范嘱。（這都是我自己畫的送膳，求推薦好用的畫圖工具...）
粉紅色的部分為oldCh和vCh
我們將它們?nèi)〕鰜聿⒎謩e用s和e指針指向它們的頭child和尾child
現(xiàn)在分別對oldS、oldE丑蛤、S叠聋、E兩兩做sameVnode比較，有四種比較方式受裹，當其中兩個能匹配上那么真實dom中的相應(yīng)節(jié)點會移到Vnode相應(yīng)的位置碌补，這句話有點繞，打個比方
如果是oldS和E匹配上了，那么真實dom中的第一個節(jié)點會移到最后
如果是oldE和S匹配上了厦章，那么真實dom中的最后一個節(jié)點會移到最前镇匀，匹配上的兩個指針向中間移動
如果四種匹配沒有一對是成功的，那么遍歷oldChild闷袒，S挨個和他們匹配，匹配成功就在真實dom中將成功的節(jié)點移到最前面岩梳，如果依舊沒有成功的囊骤，那么將S對應(yīng)的節(jié)點插入到dom中對應(yīng)的oldS位置，oldS和S指針向中間移動冀值。
再配個圖
第一步
oldS = a, oldE = d也物；
S = a, E = b;
oldS和S匹配，則將dom中的a節(jié)點放到第一個列疗，已經(jīng)是第一個了就不管了滑蚯，此時dom的位置為：a b d
第二步
oldS = b, oldE = d；
S = c, E = b;
oldS和E匹配抵栈，就將原本的b節(jié)點移動到最后告材，因為E是最后一個節(jié)點，他們位置要一致古劲，這就是上面說的：當其中兩個能匹配上那么真實dom中的相應(yīng)節(jié)點會移到Vnode相應(yīng)的位置斥赋，此時dom的位置為：a d b
第三步
oldS = d, oldE = d；
S = c, E = d;
oldE和E匹配产艾，位置不變此時dom的位置為：a d b
第四步
oldS++;
oldE--;
oldS > oldE;
遍歷結(jié)束疤剑，說明oldCh先遍歷完。就將剩余的vCh節(jié)點根據(jù)自己的的index插入到真實dom中去闷堡，此時dom位置為：a c d b
一次模擬完成隘膘。
這個匹配過程的結(jié)束有兩個條件：
oldS > oldE表示oldCh先遍歷完，那么就將多余的vCh根據(jù)index添加到dom中去（如上圖）
S > E表示vCh先遍歷完杠览，那么就在真實dom中將區(qū)間為[oldS, oldE]的多余節(jié)點刪掉
下面再舉一個例子弯菊，可以像上面那樣自己試著模擬一下
當這些節(jié)點sameVnode成功后就會緊接著執(zhí)行patchVnode了，可以看一下上面的代碼
if (sameVnode(oldStartVnode, newStartVnode)) {
? ? patchVnode(oldStartVnode, newStartVnode)
}
就這樣層層遞歸下去踱阿，直到將oldVnode和Vnode中的所有子節(jié)點比對完误续。也將dom的所有補丁都打好啦。那么現(xiàn)在再回過去看updateChildren的代碼會不會容易很多呢扫茅？
總結(jié)
以上為diff算法的全部過程蹋嵌，放上一張文章開始就發(fā)過的總結(jié)圖，可以試試看著這張圖回憶一下diff的過程葫隙。
以上內(nèi)容栽烂，來自于?_wind 先生
