摘要：的算法是基于的實現，并在些基礎上作了很多的調整和改進。此時和之間的是新增的，調用，把這些虛擬全部插進的后邊，可以認為新節點先遍歷完。

為什么出現：

瀏覽器解析一個html大致分為五步：創建DOM tree –> 創建Style Rules -> 構建Render tree -> 布局Layout –> 繪制Painting。每次對真實dom進行操作的時候，瀏覽器都會從構建dom樹開始從頭到尾執行一遍流程。真實的dom操作代價昂貴，操作頻繁還會引起頁面卡頓影響用戶體驗，虛擬dom就是為了解決這個瀏覽器性能問題才被創造出來

虛擬dom在執行dom的更新操作后，虛擬dom不會直接操作真實dom，而是將更新的diff內容保存到本地js對象中，然后一次性attach到dom樹上，通知瀏覽器進行dom繪制避免大量無謂的計算。

如何實現：

js對象表示dom結構，對象記錄了dom節點的標簽、屬性和子節點

js對象的render函數通過對虛擬dom的屬性和子節點的遞歸構建出真實dom樹

虛擬DOM是一個純粹的JS對象，可以通過document.createDocumentFragment 創建，Vue中一個虛擬DOM包含以下屬性：

tag: 當前節點的標簽名
data: 當前節點的數據對象
children: 數組類型，包含了當前節點的子節點
text: 當前節點的文本，一般文本節點或注釋節點會有該屬性
elm: 當前虛擬節點對應的真實的dom節點
context: 編譯作用域
functionalContext: 函數化組件的作用域
key: 節點的key屬性，用于作為節點的標識，有利于patch的優化
sel: 節點的選擇器
componentOptions: 創建組件實例時會用到的選項信息
child: 當前節點對應的組件實例
parent: 組件的占位節點
raw: raw html
isStatic: 靜態節點的標識
isRootInsert: 是否作為根節點插入，被包裹的節點，該屬性的值為false
isComment: 當前節點是否是注釋節點
isCloned: 當前節點是否為克隆節點
isOnce: 當前節點是否有v-once指令

簡單總結：虛擬DOM是將真實的DOM節點用JavaScript模擬出來，將DOM變化的對比，放到 Js 層來做。

優勢：

跨平臺：Virtual DOM 是以 JavaScript 對象為基礎而不依賴真實平臺環境，所以使它具有了跨平臺的能力，比如說瀏覽器平臺、Weex、Node 等。

提高DOM操作效率：DOM操作的執行速度遠不如Javascript的運算速度快，因此，把大量的DOM操作搬運到Javascript中，運用patching算法來計算出真正需要更新的節點，最大限度地減少DOM操作，從而顯著提高性能。

提升渲染性能：在大量、頻繁的數據更新下，依托diff算法，能夠對視圖進行合理、高效的更新。

Vue.js通過編譯將template 模板轉換成渲染函數(render ) ，執行渲染函數就可以得到一個虛擬節點樹

在對 Model 進行操作的時候，會觸發對應 Dep 中的 Watcher 對象。Watcher 對象會調用對應的 update 來修改視圖。這個過程主要是將新舊虛擬節點進行差異對比（patch），然后根據對比結果進行DOM操作來更新視圖。

diff算法是一種優化手段，將前后兩個模塊進行差異對比，修補(更新)差異的過程叫做patch
patch：
虛擬DOM最核心的部分，它可以將vnode渲染成真實的DOM，這個過程是對比新舊虛擬節點之間有哪些不同，然后根據對比結果找出需要更新的的節點進行更新。
patch本身就有補丁、修補的意思，其實際作用是在現有DOM上進行修改來實現更新視圖的目的。Vue的Virtual DOM patching算法是基于Snabbdom的實現，并在些基礎上作了很多的調整和改進。

當數據發生改變時，set方法會讓調用Dep.notify通知所有訂閱者Watcher，訂閱者就會調用patch給真實的DOM打補丁，更新相應的視圖。

Vue的diff算法是僅在同級的vnode間做diff，遞歸地進行同級vnode的diff，最終實現整個DOM樹的更新。因為跨層級的操作是非常少的，忽略不計，這樣時間復雜度就從O(n3)變成O(n)。

diff算法的假設

Web UI 中 DOM 節點跨層級的移動操作特別少，可以忽略不計。

擁有相同類的兩個組件將會生成相似的樹形結構，擁有不同類的兩個組件將會生成不同的樹形結構。

對于同一層級的一組子節點，它們可以通過唯一 id 進行區分。

當新舊虛擬節點的key和sel都相同時，則進行節點的深度patch，若不相同則整個替換虛擬節點，同時創建真實DOM，實現視圖更新。

如何判定新舊節點是否為同一節點：
當兩個VNode的tag、key、isComment都相同，并且同時定義或未定義data的時候，且如果標簽為input則type必須相同。這時候這兩個VNode則算sameVnode，可以直接進行patchVnode操作。

function patch (oldVnode, vnode) {
    if (sameVnode(oldVnode, vnode)) { // 有必要進行patch, key和sel都相同時才進行patch
        patchVnode(oldVnode, vnode)
    } else {  // 沒有必要進行patch, 整個替換
        const oEl = oldVnode.el
        let parentEle = api.parentNode(oEl)
        createEle(vnode) // vnode創建它的真實dom，令vnode.el =真實dom
        if (parentEle !== null) {
            api.insertBefore(parentEle, vnode.el, api.nextSibling(oEl)) // 插入整個新節點樹
            api.removeChild(parentEle, oldVnode.el) // 移出整個舊的虛擬DOM
            oldVnode = null
        }
    }
    return vnode
}

深度patch：

 function patchVnode (oldVnode, vnode, insertedVnodeQueue, removeOnly) {
    /*兩個VNode節點相同則直接返回*/
    if (oldVnode === vnode) {
      return
    }
    // reuse element for static trees.
    // note we only do this if the vnode is cloned -
    // if the new node is not cloned it means the render functions have been
    // reset by the hot-reload-api and we need to do a proper re-render.
    /*
      如果新舊VNode都是靜態的，同時它們的key相同（代表同一節點），
      并且新的VNode是clone或者是標記了once（標記v-once屬性，只渲染一次），
      那么只需要替換elm以及componentInstance即可。
    */
    if (isTrue(vnode.isStatic) &&
        isTrue(oldVnode.isStatic) &&
        vnode.key === oldVnode.key &&
        (isTrue(vnode.isCloned) || isTrue(vnode.isOnce))) {
      vnode.elm = oldVnode.elm
      vnode.componentInstance = oldVnode.componentInstance
      return
    }
    let i
    const data = vnode.data
    if (isDef(data) && isDef(i = data.hook) && isDef(i = i.prepatch)) {
      /*i = data.hook.prepatch，如果存在的話，見"./create-component componentVNodeHooks"。*/
      i(oldVnode, vnode)
    }
    const elm = vnode.elm = oldVnode.elm
    const oldCh = oldVnode.children
    const ch = vnode.children
    if (isDef(data) && isPatchable(vnode)) {
      /*調用update回調以及update鉤子*/
      for (i = 0; i < cbs.update.length; ++i) cbs.update[i](oldVnode, vnode)
      if (isDef(i = data.hook) && isDef(i = i.update)) i(oldVnode, vnode)
    }
    /*如果這個VNode節點沒有text文本時*/
    if (isUndef(vnode.text)) {
      if (isDef(oldCh) && isDef(ch)) {
        /*新老節點均有children子節點，則對子節點進行diff操作，調用updateChildren*/
        if (oldCh !== ch) updateChildren(elm, oldCh, ch, insertedVnodeQueue, removeOnly)
      } else if (isDef(ch)) {
        /*如果老節點沒有子節點而新節點存在子節點，先清空elm的文本內容，然后為當前節點加入子節點*/
        if (isDef(oldVnode.text)) nodeOps.setTextContent(elm, "")
        addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue)
      } else if (isDef(oldCh)) {
        /*當新節點沒有子節點而老節點有子節點的時候，則移除所有ele的子節點*/
        removeVnodes(elm, oldCh, 0, oldCh.length - 1)
      } else if (isDef(oldVnode.text)) {
        /*當新老節點都無子節點的時候，只是文本的替換，因為這個邏輯中新節點text不存在，所以直接去除ele的文本*/
        nodeOps.setTextContent(elm, "")
      }
    } else if (oldVnode.text !== vnode.text) {
      /*當新老節點text不一樣時，直接替換這段文本*/
      nodeOps.setTextContent(elm, vnode.text)
    }
    /*調用postpatch鉤子*/
    if (isDef(data)) {
      if (isDef(i = data.hook) && isDef(i = i.postpatch)) i(oldVnode, vnode)
    }
  }

patchVnode的規則

1.如果新舊VNode都是靜態的，同時它們的key相同（代表同一節點），那么只需要替換elm以及componentInstance即可（原地復用）。

2.新老節點均有children子節點且不同，則對子節點進行diff操作，調用updateChildren，這個updateChildren也是diff的核心。

3.如果只有新節點存在子節點，先清空老節點DOM的文本內容，然后為當前DOM節點加入子節點。

4.如果只有老節點有子節點，直接刪除老節點的子節點。

5.當新老節點都無子節點的時候，只是文本的替換。

接下來就是最復雜的diff算法的理解

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 = 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時的比較
            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)
    }
}

將Vnode的子節點Vch和oldVnode的子節點oldCh提取出來

oldCh和vCh各有兩個頭尾的變量StartIdx和EndIdx，它們的2個變量相互比較，一共有4種比較方式，，當其中兩個能匹配上那么真實dom中的相應節點會移到Vnode相應的位置。如果4種比較都沒匹配，如果設置了key，就會用key進行比較，在比較的過程中，變量會往中間靠，一旦StartIdx>EndIdx表明oldCh和vCh至少有一個已經遍歷完了，就會結束比較。

在新老兩個VNode節點的左右頭尾兩側都有一個變量標記，在遍歷過程中這幾個變量都會向中間靠攏。當oldStartIdx <= oldEndIdx或者newStartIdx <= newEndIdx時結束循環。

我們通過一個例子來理解整個對比過程：

真實節點：a，b，d

舊節點：a，b，d

新節點：a，c，d，b

第一步：

oldS = a, oldE = d；
S = a, E = b;

oldS和S，E比較；oldE和S，E比較，得出oldS和S匹配的結論，于是a節點應該按照新節點的順序放置在第一個。此時舊節點的a節點也在第一個，故而位置不動；

第一輪對比結束oldS和S為同一節點，向后移動，oldE和E不動；

第二步：

舊節點：a，b，d

新節點：a，c，d，b

oldS = b, oldE = d；
S = c, E = b;

四個變量兩輛對比可得oldS和E匹配，將原本的b節點移動到最后，因為E是最后一個節點，他們位置要一致，這就是上面說的：當其中兩個能匹配上那么真實dom中的相應節點會移到Vnode相應的位置；

第二輪對比結束，oldE和E為同一節點，向前移動，oldS和S位置不動；

第三步：

舊節點：a，d，b

新節點：a，c，d，b

oldS = d, oldE = d；
S = c, E = d;

oldE和E匹配，位置不變;

第四步：

舊節點：a，d，b

新節點：a，c，d，b

oldS++;
oldE--;
oldS > oldE;

遍歷結束，說明舊節點先遍歷完。就將剩余的新節點c根據自己的的index插入到真實dom中去

舊節點：a，c，d，b

新節點：a，c，d，b

對比完成。

當然也會存在四個變量無法互相匹配，分為兩種情況

如果新舊子節點都存在key，那么會根據舊節點的key生成一張hash表，用S的key與hash表做匹配，匹配成功就判斷S和匹配節點是否為sameNode，如果是，就在真實dom中將成功的節點移到最前面，否則，將S生成對應的節點插入到dom中對應的oldS位置，oldS和S指針向中間移動。

如果沒有key,則直接將S生成新的節點插入真實DOM （這里可以解釋為什么設置key會讓diff更高效

結束時存在兩種具體的情況：

oldS > oldE，可以認為舊節點先遍歷完。當然也有可能新節點此時也正好完成了遍歷，統一都歸為此類。此時S和E之間的vnode是新增的，調用addVnodes，把這些虛擬node.elm全部插進before的后邊.

S> E，可以認為新節點先遍歷完。此時oldS和oldE之間的節點在新的子節點里已經不存在了，直接刪除

在模擬兩個例子體會一下

eg.1
O b,a,d,f,e
N a,b,e
1. 
oldS = b, oldE = e；
S = a, E = e;
O b,a,d,f,e
N a,b,e
2.
oldS = b, oldE = f；
S = a, E = b;
O a,d,f,b,e
N a,b,e
3.
s>e d,f 刪除
O a,b,e
N a,b,e

eg.2
O b,d,c,a
N a,e,b,f
1. 
oldS = b, oldE = a；
S = a, E = f;
O a,b,d,c
N a,e,b,f
2.
oldS = d, oldE = c；
S = e, E = f;
此時四個參數無法匹配，根據key來對比O中是否有S對應的節點，沒有，則在O的S位置插入對應節點
O a,e,d,b,c
N a,e,b,f
3.
oldS = d, oldE = c；
S = b, E = f;
此時四個參數無法匹配,根據key查找是否有S對應的B節點，有，移動到S當前的位置
O a,e,b,d,c
N a,e,b,f
4.
oldS = d, oldE = c；
S = f, E = f;
此時四個參數無法匹配,根據key查找是否有S對應的f節點,沒有，則在O的S位置插入對應節點
O a,e,b,d,c,f
N a,e,b,f
5.
oldS = d, oldE = c；
s>f
循環結束，oldS與oldE之間的節點刪除

總結：

盡量不要跨層級的修改dom

在開發組件時，保持穩定的 DOM 結構會有助于性能的提升

設置key可以讓diff更高效

參考：

詳解Vue中的虛擬DOM

VirtualDOM與diff(Vue實現)

虛擬DOM介紹

數據更新到視圖更新，Vue做了什么

詳解vue的diff算法