傳統(tǒng)diff

計(jì)算兩顆樹(shù)形結(jié)構(gòu)差異并進(jìn)行轉(zhuǎn)換稻轨，傳統(tǒng)diff算法是這樣做的：循環(huán)遞歸每一個(gè)節(jié)點(diǎn)

傳統(tǒng)diff.png

比如左側(cè)樹(shù)a節(jié)點(diǎn)依次進(jìn)行如下對(duì)比灵莲，左側(cè)樹(shù)節(jié)點(diǎn)b、c殴俱、d政冻、e亦是與右側(cè)樹(shù)每個(gè)節(jié)點(diǎn)對(duì)比
算法復(fù)雜度能達(dá)到O(n^2)，n代表節(jié)點(diǎn)的個(gè)數(shù)

a->e线欲、a->d明场、a->b、a->c李丰、a->a

查找完差異后還需計(jì)算最小轉(zhuǎn)換方式苦锨，這其中的原理我沒(méi)仔細(xì)去看，最終達(dá)到的算法復(fù)雜度是O(n^3)

react優(yōu)化的diff策略

傳統(tǒng)diff算法復(fù)雜度達(dá)到O(n^3 )這意味著1000個(gè)節(jié)點(diǎn)就要進(jìn)行數(shù)10億次的比較趴泌，這是非常消耗性能的舟舒。react大膽的將diff的復(fù)雜度從O(n^3)降到了O(n)，他是如何做到的呢

• 由于web UI中跨級(jí)移動(dòng)操作非常少嗜憔、可以忽略不計(jì)秃励，所以react實(shí)現(xiàn)的diff是同層級(jí)比較

  
  
  react的diff.png
• 擁有相同類型的兩個(gè)組件產(chǎn)生的DOM結(jié)構(gòu)也是相似的，不同類型的兩個(gè)組件產(chǎn)生的DOM結(jié)構(gòu)則不近相同
• 對(duì)于同一層級(jí)的一組子節(jié)點(diǎn)吉捶，通過(guò)分配唯一唯一id進(jìn)行區(qū)分（key值）

react虛擬節(jié)點(diǎn)

dom中沒(méi)有直接提供api讓我們獲取一棵樹(shù)結(jié)構(gòu)夺鲜，這里我們自己構(gòu)建一個(gè)虛擬的dom結(jié)構(gòu)，遍歷這樣的數(shù)據(jù)結(jié)構(gòu)是一件很輕松直觀的事情呐舔。
對(duì)于下面的dom谣旁，可以用js構(gòu)造出一個(gè)簡(jiǎn)單的虛擬dom

<div className="myDiv">
  <p>1</p>
  <div>2</div>
  <span>3</span>
</div>

{
  type: 'div',
  props: {
      className: 'myDiv',
  },
  chidren: [
      {type: 'p',props:{value:'1'}},
      {type: 'div',props:{value:'2'}},
      {type: 'span',props:{value:'3'}}
  ]
}

先序深度優(yōu)先遍歷

首先要遍歷新舊兩棵樹(shù)，采用深度優(yōu)先策略滋早，為樹(shù)的每個(gè)節(jié)點(diǎn)標(biāo)示唯一一個(gè)id

先序深度優(yōu)先遍歷

在遍歷過(guò)程中，對(duì)比新舊節(jié)點(diǎn)砌们，將差異記錄下來(lái)杆麸，記錄差異的方式后面會(huì)提到

//若新舊樹(shù)節(jié)點(diǎn)只是位置不同，移動(dòng)
//計(jì)算差異
//插入新樹(shù)中存在但舊樹(shù)中不存在的節(jié)點(diǎn)
//刪除新樹(shù)中沒(méi)有的節(jié)點(diǎn)

// diff 函數(shù)浪感，對(duì)比兩棵樹(shù)
function diff (oldTree, newTree) {
  // 當(dāng)前節(jié)點(diǎn)的標(biāo)志昔头，以后每遍歷到一個(gè)節(jié)點(diǎn)，加1
  var index = 0
  var patches = {} // 用來(lái)記錄每個(gè)節(jié)點(diǎn)差異的對(duì)象
  dfsWalk(oldTree, newTree, index, patches)
  return patches
}

// 對(duì)兩棵樹(shù)進(jìn)行深度優(yōu)先遍歷
function dfsWalk (oldNode, newNode, index, patches) {
  // 對(duì)比oldNode和newNode的不同影兽，記錄下來(lái)
  patches[index] = [...]

  diffChildren(oldNode.children, newNode.children, index, patches)
}

// 遍歷子節(jié)點(diǎn)
function diffChildren (oldChildren, newChildren, index, patches) {
  var leftNode = null
  var currentNodeIndex = index
  oldChildren.forEach(function (child, i) {
    var newChild = newChildren[i]
    currentNodeIndex = (leftNode && leftNode.count) // 計(jì)算節(jié)點(diǎn)的標(biāo)識(shí)
      ? currentNodeIndex + leftNode.count + 1
      : currentNodeIndex + 1
    dfsWalk(child, newChild, currentNodeIndex, patches) // 深度遍歷子節(jié)點(diǎn)
    leftNode = child
  })
}

差異類型

上面代碼中揭斧，將所有的差異保存在了patches對(duì)象中，會(huì)有如下幾種差異類型：

1. 插入：patches[0]:{type:'INSERT_MARKUP',node: newNode }
2. 移動(dòng)：patches[0]: {type: 'MOVE_EXISTING'}
3. 刪除：patches[0]: {type: 'REMOVE_NODE'}
4. 文本內(nèi)容改變：patches[0]: {type: 'TEXT_CONTENT',content: 'virtual DOM2'}
5. 屬性改變：patches[0]: {type: 'SET_MARKUP',props: {className:''}}

列表對(duì)比

節(jié)點(diǎn)兩兩進(jìn)行對(duì)比時(shí)，我們知道新節(jié)點(diǎn)較舊節(jié)點(diǎn)有什么不同讹开。如果同一層的多個(gè)子節(jié)點(diǎn)進(jìn)行對(duì)比盅视，他們只是順序不同，按照上面的算法旦万，會(huì)先刪除舊節(jié)點(diǎn)闹击，再新增一個(gè)相同的節(jié)點(diǎn)，這可不是我們想看到的結(jié)果
實(shí)際上成艘，react在同級(jí)節(jié)點(diǎn)對(duì)比時(shí)赏半，提供了更優(yōu)的算法：

同級(jí)比較

首先對(duì)新集合的節(jié)點(diǎn)(nextChildren)進(jìn)行in循環(huán)遍歷，通過(guò)唯一的key(這里是變量name)可以取得新老集合中相同的節(jié)點(diǎn)淆两，如果不存在断箫，prevChildren即為undefined。如果存在相同節(jié)點(diǎn)秋冰，也即prevChild === nextChild仲义，則進(jìn)行移動(dòng)操作，但在移動(dòng)前需要將當(dāng)前節(jié)點(diǎn)在老集合中的位置與 lastIndex 進(jìn)行比較丹莲，見(jiàn)moveChild函數(shù)光坝，如下圖

moveChild

if (child._mountIndex < lastIndex)，則進(jìn)行節(jié)點(diǎn)移動(dòng)操作甥材，否則不執(zhí)行該操作盯另。這是一種順序優(yōu)化手段，lastIndex一直在更新洲赵，表示訪問(wèn)過(guò)的節(jié)點(diǎn)在老集合中最右的位置（即最大的位置）鸳惯，如果新集合中當(dāng)前訪問(wèn)的節(jié)點(diǎn)比lastIndex大，說(shuō)明當(dāng)前訪問(wèn)節(jié)點(diǎn)在老集合中就比上一個(gè)節(jié)點(diǎn)位置靠后叠萍，則該節(jié)點(diǎn)不會(huì)影響其他節(jié)點(diǎn)的位置芝发，因此不用添加到差異隊(duì)列中，即不執(zhí)行移動(dòng)操作苛谷，只有當(dāng)訪問(wèn)的節(jié)點(diǎn)比lastIndex小時(shí)辅鲸，才需要進(jìn)行移動(dòng)操作。

所以下圖中只需要移動(dòng)A腹殿、C

移動(dòng)

Vue優(yōu)化的diff策略

既然傳統(tǒng)diff算法性能開(kāi)銷如此之大独悴，Vue做了什么優(yōu)化呢？

• 跟react一樣锣尉，只進(jìn)行同層級(jí)比較刻炒，忽略跨級(jí)操作

react以及Vue在diff時(shí)，都是在對(duì)比虛擬dom節(jié)點(diǎn)自沧，下文提到的節(jié)點(diǎn)都指虛擬節(jié)點(diǎn)坟奥。Vue是怎樣描述一個(gè)節(jié)點(diǎn)的呢？

Vue虛擬節(jié)點(diǎn)

// body下的 <div id="v" class="classA"><div> 對(duì)應(yīng)的 oldVnode 就是

{
  el:  div  //對(duì)真實(shí)的節(jié)點(diǎn)的引用，本例中就是document.querySelector('#id.classA')
  tagName: 'DIV',   //節(jié)點(diǎn)的標(biāo)簽
  sel: 'div#v.classA'  //節(jié)點(diǎn)的選擇器
  data: null,       // 一個(gè)存儲(chǔ)節(jié)點(diǎn)屬性的對(duì)象爱谁，對(duì)應(yīng)節(jié)點(diǎn)的el[prop]屬性晒喷，例如onclick , style
  children: [], //存儲(chǔ)子節(jié)點(diǎn)的數(shù)組，每個(gè)子節(jié)點(diǎn)也是vnode結(jié)構(gòu)
  text: null,    //如果是文本節(jié)點(diǎn)管行，對(duì)應(yīng)文本節(jié)點(diǎn)的textContent厨埋，否則為null
}

patch

diff時(shí)調(diào)用patch函數(shù)，patch接收兩個(gè)參數(shù)vnode捐顷，oldVnode荡陷，分別代表新舊節(jié)點(diǎn)。

function patch (oldVnode, vnode) {
    if (sameVnode(oldVnode, vnode)) {
        patchVnode(oldVnode, vnode)
    } else {
        const oEl = oldVnode.el
        let parentEle = api.parentNode(oEl)
        createEle(vnode)
        if (parentEle !== null) {
            api.insertBefore(parentEle, vnode.el, api.nextSibling(oEl))
            api.removeChild(parentEle, oldVnode.el)
            oldVnode = null
        }
    }
    return vnode
}

patch函數(shù)內(nèi)第一個(gè)if判斷sameVnode(oldVnode, vnode)就是判斷這兩個(gè)節(jié)點(diǎn)是否為同一類型節(jié)點(diǎn)迅涮，以下是它的實(shí)現(xiàn)：

function sameVnode(oldVnode, vnode){
  //兩節(jié)點(diǎn)key值相同废赞，并且sel屬性值相同，即認(rèn)為兩節(jié)點(diǎn)屬同一類型叮姑，可進(jìn)行下一步比較
    return vnode.key === oldVnode.key && vnode.sel === oldVnode.sel
}

也就是說(shuō)唉地，即便同一個(gè)節(jié)點(diǎn)元素比如div，他的className不同传透，Vue就認(rèn)為是兩個(gè)不同類型的節(jié)點(diǎn)耘沼，執(zhí)行刪除舊節(jié)點(diǎn)、插入新節(jié)點(diǎn)操作朱盐。這與react diff實(shí)現(xiàn)是不同的群嗤，react對(duì)于同一個(gè)節(jié)點(diǎn)元素認(rèn)為是同一類型節(jié)點(diǎn)，只更新其節(jié)點(diǎn)上的屬性兵琳。

patchVnode

對(duì)于同類型節(jié)點(diǎn)調(diào)用patchVnode(oldVnode, vnode)進(jìn)一步比較:

patchVnode (oldVnode, vnode) {
    const el = vnode.el = oldVnode.el  //讓vnode.el引用到現(xiàn)在的真實(shí)dom狂秘，當(dāng)el修改時(shí)，vnode.el會(huì)同步變化躯肌。
    let i, oldCh = oldVnode.children, ch = vnode.children
    if (oldVnode === vnode) return  //新舊節(jié)點(diǎn)引用一致者春，認(rèn)為沒(méi)有變化
    //文本節(jié)點(diǎn)的比較
    if (oldVnode.text !== null && vnode.text !== null && oldVnode.text !== vnode.text) {
        api.setTextContent(el, vnode.text)
    }else {
        updateEle(el, vnode, oldVnode)
        //對(duì)于擁有子節(jié)點(diǎn)(兩者的子節(jié)點(diǎn)不同)的兩個(gè)節(jié)點(diǎn)，調(diào)用updateChildren
        if (oldCh && ch && oldCh !== ch) {
            updateChildren(el, oldCh, ch)
        }else if (ch){  //只有新節(jié)點(diǎn)有子節(jié)點(diǎn)清女，添加新的子節(jié)點(diǎn)
            createEle(vnode) //create el's children dom
        }else if (oldCh){  //只有舊節(jié)點(diǎn)內(nèi)存在子節(jié)點(diǎn)钱烟，執(zhí)行刪除子節(jié)點(diǎn)操作
            api.removeChildren(el)
        }
    }
}

updateChildren

patchVnode中有一個(gè)重要的概念updateChildren，這是Vue diff實(shí)現(xiàn)的核心：

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) {   //對(duì)于vnode.key的比較嫡丙，會(huì)把oldVnode = 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)
        }
}

代碼很長(zhǎng)忠售，解讀參照文章下面提到的大神文章。原理示意圖如下：

image.png

過(guò)程可以概括為：oldCh和newCh各有兩個(gè)頭尾的變量StartIdx和EndIdx迄沫，它們的2個(gè)變量相互比較，一共有4種比較方式卦方。如果4種比較都沒(méi)匹配羊瘩，如果設(shè)置了key，就會(huì)用key進(jìn)行比較，在比較的過(guò)程中尘吗，變量會(huì)往中間靠逝她，一旦StartIdx>EndIdx表明oldCh和newCh至少有一個(gè)已經(jīng)遍歷完了，就會(huì)結(jié)束比較睬捶。

這種由兩端至中間的對(duì)比方法與react的updateChildren實(shí)現(xiàn)也是不同黔宛，后者是從左至右依次進(jìn)行對(duì)比，各有優(yōu)點(diǎn)擒贸。
比如一個(gè)集合臀晃，只是把最后一個(gè)節(jié)點(diǎn)移到了第一個(gè)，react實(shí)現(xiàn)就出現(xiàn)了短板介劫，react會(huì)依次移動(dòng)前三個(gè)節(jié)點(diǎn)到對(duì)應(yīng)的位置：

image.png

詳細(xì)解析有大神已經(jīng)寫了：解析vue2.0的diff算法