一文詳解Vue 的雙端 diff 算法
前言
Vue 和 React 都是基於 vdom 的前端框架，組件渲染會返回 vdom，渲染器再把 vdom 通過增刪改的 api 同步到 dom。
當再次渲染時，會產生新的 vdom，渲染器會對比兩棵 vdom 樹，對有差異的部分通過增刪改的 api 更新到 dom。
這裡對比兩棵 vdom 樹，找到有差異的部分的算法，就叫做 diff 算法。
diff 算法
我們知道，兩棵樹做 diff，復雜度是 O(n^3) 的，因為每個節點都要去和另一棵樹的全部節點對比一次，這就是 n 瞭，如果找到有變化的節點，執行插入、刪除、修改也是 n 的復雜度。所有的節點都是這樣，再乘以 n，所以是 O(n * n * n) 的復雜度。
這樣的復雜度對於前端框架來說是不可接受的，這意味著 1000 個節點，渲染一次就要處理 1000 * 1000 * 1000，一共 10 億次。
所以前端框架的 diff 約定瞭兩種處理原則：隻做同層的對比，type 變瞭就不再對比子節點。
因為 dom 節點做跨層級移動的情況還是比較少的，一般情況下都是同一層級的 dom 的增刪改。
這樣隻要遍歷一遍，對比一下 type 就行瞭，是 O(n) 的復雜度，而且 type 變瞭就不再對比子節點，能省下一大片節點的遍歷。另外，因為 vdom 中記錄瞭關聯的 dom 節點，執行 dom 的增刪改也不需要遍歷，是 O(1)的，整體的 diff 算法復雜度就是 O(n) 的復雜度。
1000 個節點渲染一次最多對比 1000 次，這樣的復雜度就是可接受的范圍瞭。但是這樣的算法雖然復雜度低瞭，卻還是存在問題的。
比如一組節點，假設有 5 個，類型是 ABCDE，下次渲染出來的是 EABCD，這時候逐一對比，發現 type 不一樣，就會重新渲染這 5 個節點。
而且根據 type 不同就不再對比子節點的原則，如果這些節點有子節點，也會重新渲染。dom 操作是比較慢的，這樣雖然 diff 的算法復雜度是低瞭，重新渲染的性能也不高。
所以，diff 算法除瞭考慮本身的時間復雜度之外，還要考慮一個因素：dom 操作的次數。
上面那個例子的 ABCDE 變為 EABCD，很明顯隻需要移動一下 E 就行瞭，根本不用創建新元素。
但是怎麼對比出是同個節點發生瞭移動呢？
判斷 type 麼？ 那不行，同 type 的節點可能很多，區分不出來的。最好每個節點都是有唯一的標識。
所以當渲染一組節點的時候，前端框架會讓開發者指定 key，通過 key 來判斷是不是有點節點隻是發生瞭移動，從而直接復用。這樣，diff 算法處理一組節點的對比的時候，就要根據 key 來再做一次算法的優化。我們會把基於 key 的兩組節點的 diff 算法叫做多節點 diff 算法，它是整個 vdom 的 diff 算法的一部分。
接下來我們來學習一下多節點 diff 算法：
簡單 diff
假設渲染 ABCD 一組節點，再次渲染是 DCAB，這時候怎麼處理呢？
多節點 diff 算法的目的是為瞭盡量復用節點，通過移動節點代替創建。
所以新 vnode 數組的每個節點我們都要找下在舊 vnode 數組中有沒有對應 key 的，有的話就移動到新的位置，沒有的話再創建新的。
也就是這樣的：
const oldChildren = n1.children
const newChildren = n2.children
let lastIndex = 0
// 遍歷新的 children
for (let i = 0; i < newChildren.length; i++) {
const newVNode = newChildren[i]
let j = 0
let find = false
// 遍歷舊的 children
for (j; j < oldChildren.length; j++) {
const oldVNode = oldChildren[j]
// 如果找到瞭具有相同 key 值的兩個節點，則調用 patch 函數更新
if (newVNode.key === oldVNode.key) {
find = true
patch(oldVNode, newVNode, container)
處理移動...
break //跳出循環，處理下一個節點
}
}
// 沒有找到就是新增瞭
if (!find) {
const prevVNode = newChildren[i - 1]
let anchor = null
if (prevVNode) {
anchor = prevVNode.el.nextSibling
} else {
anchor = container.firstChild
}
patch(null, newVNode, container, anchor)
}
}
這裡的 patch 函數的作用是更新節點的屬性，重新設置事件監聽器。如果沒有對應的舊節點的話，就是插入節點，需要傳入一個它之後的節點作為錨點 anchor。
我們遍歷處理新的 vnode：
先從舊的 vnode 數組中查找對應的節點，如果找到瞭就代表可以復用，接下來隻要移動就好瞭。如果沒找到，那就執行插入，錨點是上一個節點的 nextSibling。
那如果找到瞭可復用的節點之後，那移動到哪裡呢？其實新的 vnode 數組中記錄的順序就是目標的順序。所以把對應的節點按照新 vnode 數組的順序來移動就好瞭。
const prevVNode = newChildren[i - 1]
if (prevVNode) {
const anchor = prevVNode.el.nextSibling
insert(newVNode.el, container, anchor)
}
要插入到 i 的位置，那就要取 i-1 位置的節點的 nextSibling 做為錨點來插入當前節點。
但是並不是所有的節點都需要移動，比如處理到第二個新的 vnode，發現它在舊的 vnode 數組中的下標為 4，說明本來就是在後面瞭，那就不需要移動瞭。反之，如果是 vnode 查找到的對應的舊的 vnode 在當前 index 之前才需要移動。
也就是這樣：
let j = 0
let find = false
// 遍歷舊的 children
for (j; j < oldChildren.length; j++) {
const oldVNode = oldChildren[j]
// 如果找到瞭具有相同 key 值的兩個節點，則調用 patch 函數更新之
if (newVNode.key === oldVNode.key) {
find = true
patch(oldVNode, newVNode, container)
if (j < lastIndex) { // 舊的 vnode 數組的下標在上一個 index 之前，需要移動
const prevVNode = newChildren[i - 1]
if (prevVNode) {
const anchor = prevVNode.el.nextSibling
insert(newVNode.el, container, anchor)
}
} else {// 不需要移動
// 更新 lastIndex
lastIndex = j
}
break
}
}
查找新的 vnode 在舊的 vnode 數組中的下標，如果找到瞭的話，說明對應的 dom 就是可以復用的，先 patch 一下，然後移動。
移動的話判斷下下標是否在 lastIndex 之後，如果本來就在後面，那就不用移動，更新下 lastIndex 就行。如果下標在 lastIndex 之前，說明需要移動，移動到的位置前面分析過瞭，就是就是新 vnode 數組 i-1 的後面。這樣，我們就完成瞭 dom 節點的復用和移動。
新的 vnode 數組全部處理完後，舊的 vnode 數組可能還剩下一些不再需要的，那就刪除它們：
// 遍歷舊的節點
for (let i = 0; i < oldChildren.length; i++) {
const oldVNode = oldChildren[i]
// 拿著舊 VNode 去新 children 中尋找相同的節點
const has = newChildren.find(
vnode => vnode.key === oldVNode.key
)
if (!has) {
// 如果沒有找到相同的節點，則移除
unmount(oldVNode)
}
}
這樣，我們就完成瞭兩組 vnode 的 diff 和對應 dom 的增刪改。
小結一下：
diff 算法的目的是根據 key 復用 dom 節點，通過移動節點而不是創建新節點來減少 dom 操作。
對於每個新的 vnode，在舊的 vnode 中根據 key 查找一下，如果沒查找到，那就新增 dom 節點，如果查找到瞭，那就可以復用。
復用的話要不要移動要判斷下下標，如果下標在 lastIndex 之後，就不需要移動，因為本來就在後面，反之就需要移動。
最後，把舊的 vnode 中在新 vnode 中沒有的節點從 dom 樹中刪除。
這就是一個完整的 diff 算法的實現：
這個 diff 算法我們是從一端逐個處理的，叫做簡單 diff 算法。簡單 diff 算法其實性能不是最好的，比如舊的 vnode 數組是 ABCD，新的 vnode 數組是 DABC，按照簡單 diff 算法，A、B、C 都需要移動。
那怎麼優化這個算法呢？從一個方向順序處理會有這個問題，那從兩個方向同時對比呢？
這就是雙端 diff 算法：
雙端 diff
簡單 diff 算法能夠實現 dom 節點的復用，但有的時候會做一些沒必要的移動。雙端 diff 算法解決瞭這個問題，它是從兩端進行對比。
我們需要 4 個指針，分別指向新舊兩個 vnode 數組的頭尾：
頭和尾的指針向中間移動，直到 oldStartIdx <= oldEndIdx 並且 newStartIdx <= newEndIdx，說明就處理完瞭全部的節點。
每次對比下兩個頭指針指向的節點、兩個尾指針指向的節點，頭和尾指向的節點，是不是 key是一樣的，也就是可復用的。如果是可復用的話就直接用，調用 patch 更新一下，如果是頭尾這種，還要移動下位置。
也就是這樣的：
while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
if (oldStartVNode.key === newStartVNode.key) { // 頭頭
patch(oldStartVNode, newStartVNode, container)
oldStartVNode = oldChildren[++oldStartIdx]
newStartVNode = newChildren[++newStartIdx]
} else if (oldEndVNode.key === newEndVNode.key) {//尾尾
patch(oldEndVNode, newEndVNode, container)
oldEndVNode = oldChildren[--oldEndIdx]
newEndVNode = newChildren[--newEndIdx]
} else if (oldStartVNode.key === newEndVNode.key) {//頭尾，需要移動
patch(oldStartVNode, newEndVNode, container)
insert(oldStartVNode.el, container, oldEndVNode.el.nextSibling)
oldStartVNode = oldChildren[++oldStartIdx]
newEndVNode = newChildren[--newEndIdx]
} else if (oldEndVNode.key === newStartVNode.key) {//尾頭，需要移動
patch(oldEndVNode, newStartVNode, container)
insert(oldEndVNode.el, container, oldStartVNode.el)
oldEndVNode = oldChildren[--oldEndIdx]
newStartVNode = newChildren[++newStartIdx]
} else {
// 頭尾沒有找到可復用的節點
}
}
頭頭和尾尾的對比比較簡單，頭尾和尾頭的對比還要移動下節點。比如舊 vnode 的頭節點是新的 vnode 的尾節點，那就要把它移動到舊的 vnode 的尾節點的位置。
也就是：
insert(oldStartVNode.el, container, oldEndVNode.el.nextSibling)
插入節點的錨點節點是 oldEndVNode 對應的 dom 節點的 nextSibling。如果舊 vnode 的尾節點是新 vnode 的頭結點，那就要把它移動到舊 vnode 的頭結點的位置。
也就是：
insert(oldEndVNode.el, container, oldStartVNode.el)
插入節點的錨點節點是 oldStartVNode 對應的 dom 節點（因為要插在它之前）。從雙端進行對比，能盡可能的減少節點移動的次數。
當然，還要處理下如果雙端都沒有可復用節點的情況：
如果雙端都沒有可復用節點，那就在舊節點數組中找，找到瞭就把它移動過來，並且原位置置為 undefined。沒找到的話就插入一個新的節點。
也就是這樣：
const idxInOld = oldChildren.findIndex(
node => node.key === newStartVNode.key
)
if (idxInOld > 0) {
const vnodeToMove = oldChildren[idxInOld]
patch(vnodeToMove, newStartVNode, container)
insert(vnodeToMove.el, container, oldStartVNode.el)
oldChildren[idxInOld] = undefined
} else {
patch(null, newStartVNode, container, oldStartVNode.el)
}
因為有瞭一些 undefined 的節點，所以要加上空節點的處理邏輯：
if (!oldStartVNode) {
oldStartVNode = oldChildren[++oldStartIdx]
} else if (!oldEndVNode) {
oldEndVNode = newChildren[--oldEndIdx]
}
這樣就完成瞭節點的復用和移動的邏輯。那確實沒有可復用的節點的那些節點呢？
經過前面的移動之後，剩下的節點都被移動到瞭中間，如果新 vnode 有剩餘，那就批量的新增，如果舊 vnode 有剩餘那就批量的刪除。因為前面一個循環的判斷條件是 oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx，這樣如果 old vnode 多瞭，最後 newStartIdx 會小於 newEndIdx。如果 new vnode 多瞭，最後 oldStartIdx 會小於 oldEndIdx。
所以判斷條件是這樣的：
if (oldEndIdx < oldStartIdx && newStartIdx <= newEndIdx) {
// 添加新節點
for (let i = newStartIdx; i <= newEndIdx; i++) {
patch(null, newChildren[i], container, oldStartVNode.el)
}
} else if (newEndIdx < newStartIdx && oldStartIdx <= oldEndIdx) {
// 移除操作
for (let i = oldStartIdx; i <= oldEndIdx; i++) {
unmount(oldChildren[i])
}
}
這樣就是一個完整的 diff 算法瞭，包括查找可復用節點和移動節點、新增和刪除節點。而且因為從兩側查找節點，會比簡單 diff 算法性能更好一些。
比如 ABCD 到 DABC，簡單 diff 算法需要移動 ABC 三個節點，而雙端 diff 算法隻需要移動 D 一個節點。
小結一下：
雙端 diff 是頭尾指針向中間移動的同時，對比頭頭、尾尾、頭尾、尾頭是否可以復用，如果可以的話就移動對應的 dom 節點。
如果頭尾沒找到可復用節點就遍歷 vnode 數組來查找，然後移動對應下標的節點到頭部。最後還剩下舊的 vnode 就批量刪除，剩下新的 vnode 就批量新增。
雙端 diff 算法是 Vue2 采用的 diff 算法，性能還不錯。後來，Vue3 又對 diff 算法進行瞭一次升級，叫做快速 diff 算法。這個後面再講。
總結
React 和 Vue 都是基於 vdom 的前端框架，組件產生 vdom，渲染器再把 vdom 通過增刪改的 dom api 更新到 dom。
當再次渲染出 vdom 時，就要新舊兩棵 vdom 樹做 diff，隻更新變化的 dom 節點。兩棵樹的 diff 是 O(n^3) 的，時間復雜度太高，因此前端框架規定瞭隻做同層 diff，還有 type 不一樣就認為節點不一樣，不再對比子節點。這樣時間復雜度一下子就降到瞭 O(n)。但是對於多個子字節點的 diff 不能粗暴的刪除和新增，要盡量復用已有的節點，也就是通過移動代替新增。所以多節點的時候，要指定 key，然後 diff 算法根據 key 來查找和復用節點。
簡單 diff 算法是依次根據 key 查找舊節點的，移動的話通過 lastIndex 判斷，大於它就不用動，小於它才需要移動。剩下的節點再批量刪除和新增。但是簡單 diff 算法局限性還是比較大的，有些情況下性能並不好，所以 vue2 用的是雙端 diff 算法。
雙端 diff 算法是頭尾指針向中間移動，分別判斷頭尾節點是否可以復用，如果沒有找到可復用的節點再去遍歷查找對應節點的下標，然後移動。全部處理完之後也要對剩下的節點進行批量的新增和刪除。其實 diff 算法最重要的就是找到可復用的節點，然後移動到正確的位置。隻不過不同的算法查找順序不一樣。
到此這篇關於一文詳解Vue 的雙端 diff 算法的文章就介紹到這瞭,更多相關 Vue diff 算法內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！