Vue2.0加入了Virtual Dom，Vue的Diff位于patch.js文件中狐血，該算法來源于snabbdom锁保，復雜度為O(n)

React的 Diff其實和Vue的 Diff 大同小異，只比較同層級節(jié)點，不會跨層級比較俊庇，目的就是最小變動

Diff 的過程就是調用 patch 函數(shù)咬扇，就像打補丁一樣修改真實DOM甲葬。

patch函數(shù)

// 只保留核心部分
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
}

(oldVnode, vnode) 也就是新舊兩個虛擬DOM節(jié)點，一個完整的 vnode 都有什么屬性：

// body下的 <div id="v" class="classA"><div> 對應的 oldVnode 就是
{
  el:  div  // 對真實節(jié)點的引用懈贺，document.querySelector('#id.classA')
  tagName: 'DIV',   // 節(jié)點的標簽
  sel: 'div#v.classA'  // 節(jié)點的選擇器
  data: null,   // 一個存儲節(jié)點屬性的對象经窖，對應節(jié)點的 el[prop] 屬性，如onclick, style
  children: [],  // 存儲子節(jié)點的數(shù)組梭灿，每個子節(jié)點也是 vnode 結構
  text: null,    // 如果是文本節(jié)點画侣，對應文本節(jié)點的textContent，否則為null
}

需要注意的是堡妒，屬性 el 引用的是此 Virtual DOM對應的真實DOM配乱，patch() 的參數(shù) vnode 中的 el 最初為 null，因為 patch() 之前它還沒有對應的真實DOM

1. patch(oldVnode, vnode) 的第一部分：

    if (sameVnode(oldVnode, vnode)) {
        patchVnode(oldVnode, vnode)
    }

sameVnode() 的作用是看這兩個節(jié)點是否值得比較皮迟，代碼很簡單：

    function sameVnode(oldVnode, vnode){
        // 只保留核心部分
        return vnode.key === oldVnode.key && vnode.sel === oldVnode.sel
    }

兩個 vnode 的 key 和 sel 相同才會去比較它們宪卿，比如 p和span、div.classA和div.classB 都被認為是不同結構而不去比較它們万栅。
不值得比較的節(jié)點會進入 else 中佑钾，過程如下：

else {
    // 1. 獲取 oldVnode.el 的父節(jié)點，parentEle 是真實DOM
    const oEl = oldVnode.el
    let parentEle = api.parentNode(oEl)
    // 2. 為 vnode 創(chuàng)建它的真實DOM烦粒，令 vnode.el = 真實DOM
    createEle(vnode)
    if (parentEle !== null) {
        // 3. parentEle 將新的DOM插入休溶，移除舊的DOM
        api.insertBefore(parentEle, vnode.el, api.nextSibling(oEl))
        api.removeChild(parentEle, oldVnode.el)
        oldVnode = null
    }
}

當不值得比較時，新節(jié)點直接把老節(jié)點整個替換掉了
最后執(zhí)行：return vnode扰她，返回的 vnode 與傳入時的 vnode 的區(qū)別就在于：vnode.el兽掰，之前 vnode.el=null，而現(xiàn)在 vnode.el=對應的真實DOM

    var oldVnode = patch (oldVnode, vnode)

至此完成一個patch過程徒役。

2. patchVnode(oldVnode, vnode)
   兩個節(jié)點值得比較時孽尽，會調用 patchVnode() 函數(shù)

patchVnode (oldVnode, vnode) {
    // 只保留核心部分
    const el = vnode.el = oldVnode.el    // 引用真實DOM
    let i, oldCh = oldVnode.children, ch = vnode.children
    if (oldVnode === vnode) return
    if (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)
        }else if (ch){
            createEle(vnode) //create el's children dom
        }else if (oldCh){
            api.removeChildren(el)
        }
    }
}

const el = vnode.el = oldVnode.el 這是很重要的一步，讓 vnode.el 引用到當前的真實DOM忧勿，當 el 變量修改時杉女，vnode.el 會同步變化。
節(jié)點比較的5種情況

• if (oldVnode === vnode) 它們的引用一致鸳吸，可以認為沒有變化熏挎，直接return
• if (oldVnode.text !== null && vnode.text !== null && oldVnode.text !== vnode.text) 文本節(jié)點的比較，需要修改時晌砾，則會調用 oldVnode.textContent = vnode.text
• if (oldCh && ch && oldCh !== ch) 兩個節(jié)點都有子節(jié)點坎拐，且它們不一樣，則調用 updateChildren() 函數(shù)去比較子節(jié)點，這是Diff的核心
• else if (ch) 只有新的節(jié)點有子節(jié)點哼勇，調用 createEle(vnode)都伪，vnode.el 已經引用了老的DOM幾點，createEle函數(shù)會在老的DOM節(jié)點上添加子節(jié)點积担。
• else if (oldCh) 新節(jié)點沒有子節(jié)點院溺，老節(jié)點有子節(jié)點，則直接刪除老節(jié)點磅轻。

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
    while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
        if (oldStartVnode == null) {   //對于vnode.key的比較，會把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)) {  // 比較方式一
            // 頭頭比較通過逐虚，patch不同之處聋溜，如class、style
            patchVnode(oldStartVnode, newStartVnode)
            // 向后移動指針
            oldStartVnode = oldCh[++oldStartIdx]
            newStartVnode = newCh[++newStartIdx]
        } else if (sameVnode(oldEndVnode, newEndVnode)) {  // 比較方式二
            // 尾尾比較通過叭爱，patch不同之處
            patchVnode(oldEndVnode, newEndVnode)
            // 向前移動指針
            oldEndVnode = oldCh[--oldEndIdx]
            newEndVnode = newCh[--newEndIdx]
        } else if (sameVnode(oldStartVnode, newEndVnode)) {  // 比較方式三
            // 舊頭與新尾比較通過撮躁，patch不同之處
            patchVnode(oldStartVnode, newEndVnode)
            // 移除這個舊節(jié)點，再添加到數(shù)組尾部
            api.insertBefore(parentElm, oldStartVnode.el, api.nextSibling(oldEndVnode.el))
            oldStartVnode = oldCh[++oldStartIdx]
            newEndVnode = newCh[--newEndIdx]
        } else if (sameVnode(oldEndVnode, newStartVnode)) {  // 比較方式四
            // 新頭與舊尾比較通過买雾，patch不同之處
            patchVnode(oldEndVnode, newStartVnode)
            // 移除這個舊節(jié)點把曼，再添加到數(shù)組頭部
            api.insertBefore(parentElm, oldEndVnode.el, oldStartVnode.el)
            oldEndVnode = oldCh[--oldEndIdx]
            newStartVnode = newCh[++newStartIdx]
        } else {
            // 四種比較方式都不滿足，如果設置了key漓穿，則使用 key 比較
            if (oldKeyToIdx === undefined) {
                // 由key生成index表嗤军，由此可見，應該給節(jié)點數(shù)組設置唯一key
                oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx)
            }
            idxInOld = oldKeyToIdx[newStartVnode.key]
            if (!idxInOld) {
                // 用新節(jié)點的key在 舊節(jié)點數(shù)組中查找晃危，沒有找到這個節(jié)點叙赚，則插入新節(jié)點
                api.insertBefore(parentElm, createEle(newStartVnode).el, oldStartVnode.el)
                newStartVnode = newCh[++newStartIdx]
            } else {
                elmToMove = oldCh[idxInOld]
                if (elmToMove.sel !== newStartVnode.sel) {
                    // key雖相同，但節(jié)點不同僚饭，把這個舊節(jié)點替換成新節(jié)點
                    api.insertBefore(parentElm, createEle(newStartVnode).el, oldStartVnode.el)
                } else {
                    // 兩個節(jié)點相同震叮，則patch不同之處
                    patchVnode(elmToMove, newStartVnode)
                    oldCh[idxInOld] = null
                    // 移除這個舊節(jié)點，重新插入更新后的節(jié)點
                    api.insertBefore(parentElm, elmToMove.el, oldStartVnode.el)
                }
                newStartVnode = newCh[++newStartIdx]
            }
        }
    }
    // 檢查新舊節(jié)點是否還有剩余
    if (oldStartIdx > oldEndIdx) {
        // 舊節(jié)點數(shù)組遍歷完了鳍鸵，則直接插入剩下的新節(jié)點
        before = newCh[newEndIdx + 1] == null ? null : newCh[newEndIdx + 1].el
        addVnodes(parentElm, before, newCh, newStartIdx, newEndIdx)
    } else if (newStartIdx > newEndIdx) {
        // 新節(jié)點遍歷完了苇瓣，那么直接移除剩下的舊節(jié)點
        removeVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx)
    }
}

代碼很密集，用圖描述這個過程：

updateChildren.png

只有在 oldCh和newCh 都存在的情況下才會執(zhí)行updateChildren()偿乖，可知updateChildren()進行的是同層級下的Children的更新比較击罪，也就是傳說中的Diff了。

一系列變量

• 舊節(jié)點數(shù)組oldCh贪薪，新節(jié)點數(shù)組newCh
• oldStartIdx外邓、oldEndIdx 分別指向oldCh頭部和尾部，對應元素oldStartVnode古掏、oldEndVnode
• newStartIdx损话、newEndIdx 分別指向newCh頭部和尾部，對應元素newStartVnode、newEndVnode
• oldKeyToIdx 是一個Map丧枪，其key就是v-bind:key的值光涂，value對應的就是當前vnode

過程可以概況為：
頭頭比較、尾尾比較拧烦，頭尾比較忘闻，尾頭比較，如果 4 種比較都不匹配恋博，但設置了key齐佳，則會用key進行比較。

具體的Diff分析

Vue2在比較過程中會直接操作DOM债沮，相比之下炼吴，React把Diff和DOM操作分為兩個階段，DOM操作在提交階段疫衩。
Diff的遍歷過程中硅蹦，只要是對DOM的操作都會調用 api.insertBefore()，api.insertBefore()只是原生insertBefore()的簡單封裝闷煤。

官方文檔：parentElement.insertBefore(newElement, referenceElement)童芹，如果referenceElement為null，則newElement將被插入到子節(jié)點的末尾鲤拿；如果newElement已經存在于DOM樹中假褪，則首先會從DOM樹中移除。

1. 對于頭頭比較sameVnode(oldStartVnode, newStartVnode)和尾尾比較sameVnode(oldEndVnode, newEndVnode) 近顷，為true時是不需要對移動DOM的嗜价，只是更新節(jié)點(patchVnode)。
2. 設置 key (v-bind:key="xxx") 與不設置 key 的區(qū)別：
   • 不設key(undefined)幕庐，newCh和oldCh只會進行頭尾兩端的相互比較久锥；而且 sameVnode() 在判斷兩個節(jié)點是否值得比較時，無法比較key是否相同异剥。
     在特定情況下瑟由，比如v-for的列表是10個多選框，選中哪一個則刪除哪一個冤寿，那么會發(fā)現(xiàn)：刪除第一個checkbox歹苦，新的第一個checkbox會處于選中狀態(tài)！
   • 設置key督怜，如果頭尾兩端的比較都不匹配殴瘦，還會從用 key 生成的Map對象 oldKeyToIdx 中查找匹配的節(jié)點，最大化的復用節(jié)點号杠，提高性能蚪腋。
   • 不建議直接用 index 作為 key丰歌，其實就相當于不加key。當刪除/插入元素時屉凯，因為后續(xù)元素的key="index"都會發(fā)生變化立帖，導致它們重新渲染，無法復用悠砚，浪費性能晓勇。
     key="index"只適用于比較穩(wěn)定的狀態(tài)。
3. 當sameVnode(oldStartVnode, newEndVnode) 值得比較時灌旧，說明 oldStartVnode.el 跑到 oldEndVnode.el 的后邊了绑咱。

假設startIdx遍歷到1.png

4. 當 sameVnode(oldEndVnode, newStartVnode) 值得比較，oldEndVnode.el 跑到了 oldStartVnode.el 的前邊枢泰。
   準確的說應該是 oldEndVnode.el 需要移動到 oldStartVnode.el的前邊描融。
   而實際操作是，先插入宗苍，后移除。

2038.png

5. 4種頭尾方式比較完后薄榛，就會去檢查舊節(jié)點的Map表讳窟。根據(jù)新節(jié)點的key，到表中查找是否有這樣一個節(jié)點敞恋。
   • 找不到丽啡，說明這個新節(jié)點不存在與舊節(jié)點樹中，將新節(jié)點插入到 oldStartVnode.el 的前邊硬猫。

createEle.png

• 找到了，也要去檢查兩個節(jié)點是否還是同一節(jié)點elmToMove.sel !== newStartVnode.sel
  如果是同一節(jié)點啸蜜，則更新節(jié)點坑雅，移動到新的位置；否則衬横，替換這個舊節(jié)點裹粤。

6. while循環(huán)結束后（新、舊有一個發(fā)生了交叉）蜂林，也分為兩種情況：
   • oldStartIdx > oldEndIdx 表示舊節(jié)點先遍歷完遥诉。當然有可能 newCh 也剛好遍歷完，但都歸為此類噪叙。
     那么矮锈，直接插入剩下的新節(jié)點即可。

before.png

• newStartIdx > newEndIdx 表示新節(jié)點遍歷結束睁蕾，那么就移除剩下的舊節(jié)點苞笨。

remove.png

小結

• 盡量不要跨層級的修改DOM
• 設置 Key 可以最大化的利用節(jié)點
• 不要盲目相信 Diff 的效率，在必要時可以手工優(yōu)化

舉個例子.png

原有的 oldCh 的順序是 A 、B猫缭、C男娄、D、E奉狈、F央渣、G，更新后成 ch 的順序 F射窒、D藏杖、A、H脉顿、E蝌麸、C、B艾疟、G

初始狀態(tài).png

為了更好理解后續(xù)的 STEP来吩，先看下相關符合標記的說明：

圖解說明.png

STEP-1
對比 A-F --> G-G，sameVnode(oldEndVnode, newEndVnode)值得比較蔽莱，DOM順序不變

• 對 G 進行patchVnode()弟疆，更新oldG.el
• 移動指針：--oldEndIdx，--newEndIdx

step-1.png

STEP-2
對比 A-F --> F-B --> A-B --> F-F盗冷，sameVnode(oldEndVnode, newStartVnode)值得比較

• 對 F 進行patchVnode()怠苔，更新oldF.el
• 找到 oldStartVnode 在DOM中的位置A，在其前面插入更新后的F
• 移動指針：--oldEndIdx仪糖，++newStartIdx

step-2.png

STEP-3
對比 A-D --> E-B --> A-B --> E-D柑司，sameVnode(old, new)都不匹配，則取newStartVnode的key锅劝，即D.key攒驰， 在 oldKeyToIdx 中查找，并成功找到對應的D

• 將 D 賦值給 elmToMove故爵，圖示中為vnodeToMove
• 對 D 進行patchVnode()讼育，更新oldD.el
• 將 oldCh 中對應D的vnode置空：oldCh[idxInOld] = null
• 找到 oldStartVnode 在DOM中的位置A，在其前面插入更新后的D
• 移動指針：++newStartIdx

step-3.png

STEP-4
對比 A-A稠集，sameVnode(oldStartVnode, newStartVnode)匹配成功奶段，進行比較，DOM順序不變

• 將 A 進行patchVnode()剥纷，更新oldA.el
• 移動指針：++oldStartIdx痹籍，++newStartIdx

step-4.png

STEP-5
對比 B-H --> E-B --> B-B，sameVnode(oldStartVnode, newEndVnode)值得比較

• 將 B 進行patchVnode()晦鞋，更新oldB.el
• 找到 oldEndVnode - E 的下一個兄弟節(jié)點 G蹲缠，在其前面（G前面棺克、E后面）插入更新后的B
• 移動指針：++oldStartIdx，--newEndIdx

step-5.png

STEP-6
對比 C-H --> E-C --> C-C线定，sameVnode(oldStartVnode, newEndVnode)值得比較（同STEP-5）

• 將 C 進行patchVnode()娜谊，更新oldC.el
• 找到 oldEndVnode - E 的下一個兄弟節(jié)點 B，在其前面（B前面斤讥、E后面）插入更新后的C
• 移動指針：++oldStartIdx纱皆，--newEndIdx

step-6.png

STEP-7
因為 STEP-3 中的 oldCh[idxInOld] = null，當前獲取的 oldStartVnode = null

• 移動指針：++oldStartIdx

step-7.png

STEP-8
對比 E-H --> E-E芭商，sameVnode(oldEndVnode, newEndVnode)值得比較派草，DOM順序不變

• 將 E 進行patchVnode()，更新oldE.el
• 移動指針：--oldEndIdx铛楣，--newEndIdx

step-8.png

last
此時的 oldStartIdx > oldEndIdx近迁，有一方發(fā)生了交叉，則退出循環(huán)簸州。

        if (oldStartIdx > oldEndIdx) {
            before = newCh[newEndIdx + 1] == null ? null : newCh[newEndIdx + 1].el
            addVnodes(parentElm, before, newCh, newStartIdx, newEndIdx)
        }

舊VirtualDOM 首先發(fā)生交叉鉴竭，所以把新VirtualDOM中剩余的節(jié)點直接插入到oldCh中

• 找到 newEndIdx + 1 位置E --> before
• 剩余的待處理部分：newStartIdx -- newEndIdx 之間的 vnode 視為新增的部分 -- [ H ]
• 插入到 before 位置E 的前面

last.png

注意點

• 在Diff過程中，oldCh 和 newCh 的位置并不會發(fā)生變化岸浑，真正進行操作的是傳入的parentElm -- 父vnode的elm
• 插入操作使用的 insertBefore(newElement, referenceElement)搏存，在指定節(jié)點前插入。
• patch() 中其實還有一個數(shù)組insertedVnodeQueue助琐，涉及到組件的patch過程：組件的 $mount 函數(shù)之后之后并不會立即觸發(fā)組件實例的mounted鉤子祭埂，而是把當前實例push到insertedVnodeQueue中面氓，然后在patch的倒數(shù)第二行執(zhí)行invokeInsertHook -- 觸發(fā)所有組件實例的insert鉤子兵钮，而組件的insert鉤子函數(shù)中才會觸發(fā)組件實例的mounted鉤子。比如舌界，在patch的過程中掘譬，patch了多個組件vnode，它們都進行了$mount即生成DOM呻拌，但沒有立即觸發(fā)mounted葱轩，而是等整個patch完成，再逐一觸發(fā)藐握。