diff演算法是一種透過同層的樹節點進行比較的高效演算法，避免了對樹進行逐層搜尋遍歷。那麼大家對diff演算法嗎有多少了解呢？以下這篇文章就來帶大家深入解析下vue2的diff演算法，希望對大家有幫助！
看Vue 2 的源代碼已經很久了，從用flow 到如今使用TypeScript，我每次都會打開它的源代碼看一看，但是每次都只看到了資料初始化 部分，也就是beforeMount 的階段，對於如何產生VNode（Visual Dom Node， 也可以直接稱為vdom） 以及元件更新時如何比較VNode（diff ）始終沒有仔細研究，只知道採用了雙端diff 演算法，至於這個雙端是怎麼開始怎麼結束的也一直沒有去看過，所以這次趁寫文章的機會仔細研究一下。如果內容有誤，希望大家能幫我指出，非常感謝~
在我的理解中，diff 指代的是differences，即新舊內容之間的區別計算；Vue 中的diff 演算法，則是透過一種簡單且高效 的手段快速對比出新舊VNode 節點數組之間的差異 以便以最少的dom 操作來更新頁面內容。 【相關推薦：vuejs影片教學、web前端開發】
#此時這裡有兩個必須的前提：
比較的是VNode 陣列
同時存在新舊兩組VNode 陣列
所以它一般只會發生在資料更新造成頁面內容需要更新時執行，即renderWatcher.run()。
上面說了，diff 中比較的是VNode，而不是真實的dom 節點，相信為什麼會用VNode 大部分人都比較清楚，筆者就簡單帶過吧?~
在Vue 中使用VNode 的原因大致有兩個面向：
VNode 作為框架設計者根據框架需求設計的JavaScript 對象，本身屬性相對真實的dom 節點要簡單，且操作時不需要進行dom 查詢，可以大幅優化計算時的效能消耗
在VNode 到真實dom 的這個渲染過程，可以根據不同平台（web、微信小程式）進行不同的處理，產生適配各平台的真實dom 元素
在diff 過程中會遍歷新舊節點資料進行對比，所以使用VNode 能帶來很大的效能提升。
在網頁中，真實的dom 節點都是以樹 的形式存在的，根節點都是 ，為了確保虛擬節點能與真實dom 節點一致，VNode 也一樣採用的是樹狀結構。
如果在元件更新時，需要比較全部VNode 節點的話，新舊兩組節點都需要進行深度遍歷 和比較，會產生很大的效能開銷；所以，Vue 中默認同層級節點比較，也就是如果新舊VNode 樹的層級不同的話，多餘層級的內容會直接新建或捨棄，只在同層級進行diff 操作。
一般來說，diff 操作一般發生在v-for 迴圈或有v-if/v-else 、component 這類動態產生 的節點物件上（靜態節點一般不會改變，對比起來很快），而這個過程是為了更新dom，所以在原始碼中，這個過程對應的方法名稱是updateChildren ，位於src/core/vdom/patch.ts 中。如下圖：
這裡回顧Vue 元件實例的建立與更新過程：
首先是
beforeCreate到created階段，主要進行資料和狀態以及一些基礎事件、方法的處理然後，會呼叫
$mount(vm .$options.el)方法進入Vnode與dom 的建立與掛載階段，也就是beforeMount到mounted之間（元件更新時與這裡類似）原型上的
$mount會在platforms/web/runtime-with-compiler.ts中進行一次重寫，原始實作在platforms/web/runtime/index.ts中；在原始實作方法中，其實就是呼叫mountComponent方法執行render；而在web下的runtime-with-compiler則是增加了模板字串編譯 模組，會對options中的的template# 進行一次解析和編譯，轉換成一個函數綁定到options.render中
mountComponent函數內部就是定義了渲染方法updateComponent = () => (vm._update(vm._render())，實例化一個具有before配置的watcher實例（即renderWatcher），透過定義watch觀察物件為剛剛定義的updateComponent方法來執行首次元件渲染與觸發依賴收集，其中的before配置僅配置了觸發beforeMount/beforeUpdate鉤子函數的方法；這也是為什麼在beforeMount階段取不到真實dom 節點與beforeUpdate階段獲取的是舊dom 節點的原因
_update方法的定義與mountComponent在同一檔案下，其核心就是讀取元件實例中的$el（舊dom 節點）與_vnode（舊VNode）與_render()函數產生的vnode進行patch運算
patch函式先比較是否有舊節點，沒有的話一定是新建的元件，直接進行創建和渲染；如果具有舊節點的話，則透過patchVnode進行新舊節點的對比，並且如果新舊節點一致並且都具有children子節點，則進入diff的核心邏輯—updateChildren子節點比較更新，這個方法也是我們常說的diff演算法
既然是比較新舊VNode 數組，那麼首先肯定有對比 的判斷方法：sameNode (a, b)、新增節點的方法addVnodes、移除節點的方法removeVnodes，當然，即使sameNode 判斷了VNode 一致之後，仍會使用patchVnode 對單一新舊VNode 的內容進行深度比較，確認內部資料是否需要更新。
這個方法就一個目的：比較新舊節點是否相同。
在這個方法中，首先比較的是a 和b 的key 是否相同，這也是為什麼Vue 在文件中註明了v-for、v-if、 v-else 等動態節點必須設定key 來標識節點唯一性，如果key 存在且相同，則只需要比較內部是否發生了改變，一般情況下可以減少很多dom 操作；而如果沒有設定的話，則會直接銷毀重建對應的節點元素。
然後會比較是不是非同步元件，這裡會比較他們的建構子是不是一致。
然後會進入兩種不同的情況比較：
undefined
#函數整體過程如下
顧名思義，新增新的VNode 節點。
此函數接收6 個參數：parentElm 目前節點陣列父元素、refElm 指定位置的元素、vnodes 新的虛擬節點陣列、startIdx 新節點陣列的插入元素開始位置、endIdx 新節點陣列的插入元素結束索引、insertedVnodeQueue 需要插入的虛擬節點隊列。
函數內部會從startIdx 開始遍歷vnodes 陣列直到endIdx 位置，然後呼叫createElm 依序在refElm 之前建立和插入vnodes[idx] 對應的元素。
當然，在這個vnodes[idx] 中有可能會有Component 元件，此時也會呼叫createComponent 來建立對應的組件實例。
因為整個
VNode和dom 都是一個樹結構，所以在同層級的比較之後，還需要處理目前層級下更深層的VNode和dom 處理。
與 addVnodes 相反，此方法就是用來移除 VNode 節點的。
由於這個方法只是移除，所以只需要三個參數：vnodes 舊虛擬節點陣列、startIdx 開始索引、endIdx 結束索引。
函數內部會從startIdx 開始遍歷vnodes 陣列直到endIdx 位置，如果vnodes[idx ] 不為undefined 的話，則會根據tag 屬性來區分處理：
tag，說明是一個元素或元件，需要遞歸處理vnodes[idx] 的內容，觸發remove hooks 與destroy hooks
tag，說明是一個純文字節點，直接從dom 移除該節點即可節點比較的實際完整比較與dom 更新 方法。
在這個方法中，主要包含九個 主要的參數判斷，並對應不同的處理邏輯：
新舊VNode 全等，則說明沒有變化，直接退出
如果新的VNode 具有真實的dom 綁定，並且需要更新的節點集合是一個數組的話，則拷貝當前的VNode 到集合的指定位置
如果舊節點是一個非同步元件並且還沒有載入結束的話就直接退出，否則透過hydrate 函數將新的VNode 轉換為真實的dom 進行渲染；兩種情況都會退出函數
如果新舊節點都是 靜態節點 且key 相等，或是isOnce 指定的不更新節點，也會直接重複使用舊節點的元件實例 並退出函數
如果新的VNode 節點具有data 屬性並且有配置prepatch 鉤子函數，則執行prepatch(oldVnode, vnode) 通知進入節點的比較階段，一般這一步驟會配置效能最佳化
如果新的VNode 具有data 屬性並且遞歸改節點的子元件實例的vnode，還是可用標籤的話，cbs 回呼函數物件中配置的update 鉤子函數以及data 中配置的update 鉤子函數
如果新的VNode 不是文字節點的話，會進入核心對比階段：
children 子節點，則進入updateChildren 方法對比子節點text 文字如果新的VNode 具有text 文字（是文字節點），則比較新舊節點的文字內容是否一致，否則進行文字內容的更新
最後呼叫新節點的data 中配置的postpatch 鉤子函數，通知節點更新完畢
#簡單來說，patchVnode 就是在同一個節點更新階段進行新內容與舊內容的對比，如果發生改變則更新對應的內容；如果有子節點，則「遞歸」執行每個子節點的比較和更新。
而 子節點陣列的比較和更新，則是 diff 的核心邏輯，也是面試時常被提及的問題之一。
下面，就進入updateChildren 方法的解析吧~
updateChildren diff 核心解析#首先，我們先思考一下以新陣列為準比較兩個物件陣列元素差異 有哪些方法？
一般來說，我們可以透過 暴力手段直接遍歷兩個陣列 來找出陣列中每個元素的順序和差異，也就是 簡單 diff 演算法。
即遍歷新節點數組，在每次循環中再次遍歷舊節點數組對比兩個節點是否一致，透過對比結果確定新節點是新增還是移除還是移動，整個過程中需要進行m*n 次比較，所以預設時間複雜度是On。
這種比較方式在大量節點更新過程中是非常消耗性能的，所以Vue 2 對其進行了優化，改為雙端對比演算法，也就是雙端diff。
顧名思義，雙端 就是從兩端開始分別向中間進行遍歷對比 的演算法.
在雙端diff 中，分成五個比較情況：
新舊頭相等
新舊尾相等
舊頭等於新尾
舊尾等於新頭
四者互不相等
其中，前四種屬於比較理想的情況，而第五種才是最複雜的對比情況。
判斷相等即
sameVnode(a, b)等於true
下面我們透過一種預設情況來進行分析。
為了盡量同時示範出以上五種情況，我預設了以下的新舊節點陣列：
oldChildren，包含1 - 7 共7 個節點newChildren，也有7 個節點，但是相比舊節點減少了一個vnode 3 並增加了一個vnode 8
在進行比較之前，首先需要定義兩組節點的雙端索引：
let oldStartIdx = 0 let oldEndIdx = oldCh.length - 1 let oldStartVnode = oldCh[0] let oldEndVnode = oldCh[oldEndIdx] let newStartIdx = 0 let newEndIdx = newCh.length - 1 let newStartVnode = newCh[0] let newEndVnode = newCh[newEndIdx]
複製的原始程式碼，其中
oldCh在圖中為oldChildren，newCh為newChildren
然後，我們定義遍歷對比操作的停止條件：
while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx)
這裡的停止條件是只要新舊節點數組任一個遍歷結束，則立即停止遍歷。
此時節點狀態如下：
為了保證新舊節點數組在對比時不會進行無效對比，會先排除掉舊節點數組起始部分與末尾部分連續且值為Undefined 的資料。
if (isUndef(oldStartVnode)) {
oldStartVnode = oldCh[++oldStartIdx]
} else if (isUndef(oldEndVnode)) {
oldEndVnode = oldCh[--oldEndIdx]
當然我們的例子中沒有這種情況，可以忽略。
此時相當於新舊節點陣列的兩個起始索引 指向的節點是基本上一致的，那麼此時會呼叫patchVnode 對兩個vnode 進行深層比較和dom 更新，並且將兩個起始索引向後移動。即：
if (sameVnode(oldStartVnode, newStartVnode)) {
patchVnode(
oldStartVnode,
newStartVnode,
insertedVnodeQueue,
newCh,
newStartIdx
)
oldStartVnode = oldCh[++oldStartIdx]
newStartVnode = newCh[++newStartIdx]
}這時的節點和索引變化如圖所示：
與頭結點相等類似，這種情況代表新舊節點數組的最後一個節點基本上一致，此時一樣調用patchVnode 比較兩個尾結點和更新dom，然後將兩個末尾索引向前移動。
if (sameVnode(oldEndVnode, newEndVnode)) {
patchVnode(
oldEndVnode,
newEndVnode,
insertedVnodeQueue,
newCh,
newEndIdx
)
oldEndVnode = oldCh[--oldEndIdx]
newEndVnode = newCh[--newEndIdx]
}這時的節點和索引變化如圖所示：
#這裡表示的是舊節點數組目前起始索引指向的vnode 與新節點數組目前末尾索引指向的vnode 基本上一致，一樣調用patchVnode 對兩個節點進行處理。
但與上述兩種有差別的地方在於：這種情況會造成節點的移動，所以此時也會在patchVnode 結束之後 透過nodeOps.insertBefore 將舊的頭節點 重新插入到目前舊的尾結點之後。
然後，會將 舊節點的起始索引後移、新節點的結尾索引前移。
看到這裡大家可能會有一個疑問，為什麼這裡移動的是舊的節點數組，這裡因為vnode 節點中有一個屬性
elm，會指向該vnode 對應的實際dom 節點，所以這裡移動舊節點數組其實就是側面去移動實際的dom 節點順序；並且注意這裡是當前的尾結點，在索引改變之後，這裡不一定就是原始舊節點數組的最末尾。
即：
if (sameVnode(oldStartVnode, newEndVnode)) {
patchVnode(
oldStartVnode,
newEndVnode,
insertedVnodeQueue,
newCh,
newEndIdx
)
canMove && nodeOps.insertBefore(parentElm, oldStartVnode.elm, nodeOps.nextSibling(oldEndVnode.elm))
oldStartVnode = oldCh[++oldStartIdx]
newEndVnode = newCh[--newEndIdx]
}此时状态如下：
这里与上面的 旧头等于新尾 类似，一样要涉及到节点对比和移动，只是调整的索引不同。此时 旧节点的 末尾索引 前移、新节点的 起始索引 后移，当然了，这里的 dom 移动对应的 vnode 操作是 将旧节点数组的末尾索引对应的 vnode 插入到旧节点数组 起始索引对应的 vnode 之前。
if (sameVnode(oldEndVnode, newStartVnode)) {
patchVnode(
oldEndVnode,
newStartVnode,
insertedVnodeQueue,
newCh,
newStartIdx
)
canMove && nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm)
oldEndVnode = oldCh[--oldEndIdx]
newStartVnode = newCh[++newStartIdx]
}此时状态如下：
在以上情况都处理之后，就来到了四个节点互相都不相等的情况，这种情况也是 最复杂的情况。
当经过了上面几种处理之后，此时的 索引与对应的 vnode 状态如下：
可以看到四个索引对应的 vnode 分别是：vnode 3、vnode 5、 vnode 4、vnode 8，这几个肯定是不一样的。
此时也就意味着 双端对比结束。
后面的节点对比则是 将旧节点数组剩余的 vnode （oldStartIdx 到 oldEndIdx 之间的节点）进行一次遍历，生成由 vnode.key 作为键，idx 索引作为值的对象 oldKeyToIdx，然后 遍历新节点数组的剩余 vnode（newStartIdx 到 newEndIdx 之间的节点），根据新的节点的 key 在 oldKeyToIdx 进行查找。此时的每个新节点的查找结果只有两种情况：
找到了对应的索引，那么会通过 sameVNode 对两个节点进行对比：
patchVnode 进行深层对比和 dom 更新，将 oldKeyToIdx 中对应的索引 idxInOld 对应的节点插入到 oldStartIdx 对应的 vnode 之前；并且，这里会将 旧节点数组中 idxInOld 对应的元素设置为 undefinedcreateElm 重新创建一个新的 dom 节点并将 新的 vnode 插入到对应的位置没有找到对应的索引，则直接 createElm 创建新的 dom 节点并将新的 vnode 插入到对应位置
注：这里 只有找到了旧节点并且新旧节点一样才会将旧节点数组中
idxInOld中的元素置为undefined。
最后，会将 新节点数组的 起始索引 向后移动。
if (isUndef(oldKeyToIdx)) {
oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx)
}
idxInOld = isDef(newStartVnode.key)
? oldKeyToIdx[newStartVnode.key]
: findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx)
if (isUndef(idxInOld)) {
// New element
createElm(
newStartVnode,
insertedVnodeQueue,
parentElm,
oldStartVnode.elm,
false,
newCh,
newStartIdx
)
} else {
vnodeToMove = oldCh[idxInOld]
if (sameVnode(vnodeToMove, newStartVnode)) {
patchVnode(
vnodeToMove,
newStartVnode,
insertedVnodeQueue,
newCh,
newStartIdx
)
oldCh[idxInOld] = undefined
canMove &&
nodeOps.insertBefore(
parentElm,
vnodeToMove.elm,
oldStartVnode.elm
)
} else {
// same key but different element. treat as new element
createElm(
newStartVnode,
insertedVnodeQueue,
parentElm,
oldStartVnode.elm,
false,
newCh,
newStartIdx
)
}
}
newStartVnode = newCh[++newStartIdx]
}大致逻辑如下图：
经过上面的处理之后，根据判断条件也不难看出，遍历结束之后 新旧节点数组都刚好没有剩余元素 是很难出现的，当且仅当遍历过程中每次新头尾节点总能和旧头尾节点中总能有两个新旧节点相同时才会发生，只要有一个节点发生改变或者顺序发生大幅调整，最后 都会有一个节点数组起始索引和末尾索引无法闭合。
那么此时就需要对剩余元素进行处理：
即：
Vue 2 的 diff 算法相对于简单 diff 算法来说，通过 双端对比与生成索引 map 两种方式 减少了简单算法中的多次循环操作，新旧数组均只需要进行一次遍历即可将所有节点进行对比。
其中雙端對比會分別進行四次對比和移動，性能不算最優解，所以Vue 3 中引入了最長遞增子序列 的方式來替代雙端對比，而其餘部分則依然透過轉換為索引map 的形式利用空間擴展來減少時間複雜度，從而更高的提升計算效能。
當然本文的圖表中沒有給出 vnode 對應的 elm 真實 dom 節點，兩者的移動關係可能會給大家帶來誤解，建議配合 《Vue.js 設計與實現》一起閱讀。
整體流程如下：
以上是快速搞懂Vue2 diff演算法（圖文詳解）的詳細內容。更多資訊請關注PHP中文網其他相關文章！
