概念
DIFF 算法即兩顆虛擬 DOM 樹做 DIFF，比較兩顆樹的差異性，只更新產(chǎn)生變化的節(jié)點(diǎn)，渲染更新后的節(jié)點(diǎn)到真實(shí)的 DOM，以節(jié)約資源。
用戶每次修改數(shù)據(jù)后都會引起頁面元素重排和重繪，渲染真實(shí)的 DOM 開銷較大，非常消耗性能。相對于真實(shí) DOM 對象，js對象（即虛擬DOM）處理起來更快，而且更簡單。 通過 DIFF 算法對比新舊 virtual DOM 之間的差異，可以批量的、最小化的執(zhí)行 DOM 操作，從而提高性能。
我們先根據(jù)真實(shí) DOM 生成一顆 virtual DOM，當(dāng) virtual DOM 某個節(jié)點(diǎn)的數(shù)據(jù)改變后會生成一個新的Vnode，然后 Vnode 和 oldVnode 作對比，發(fā)現(xiàn)有不一樣的地方就直接修改在真實(shí)的 DOM 上，然后使 oldVnode 的值更新為 Vnode。
DIFF 的過程就是調(diào)用名為 patch 的函數(shù)，比較新舊節(jié)點(diǎn)，一邊比較一邊給真實(shí)的 DOM 打補(bǔ)丁。
比較的方式
diff時間復(fù)雜度分析：
常規(guī)：O(n^3) 遍歷樹1； 遍歷樹2； 排序； 1000個節(jié)點(diǎn)，十億的量級。
優(yōu)化：O(n) 只比較同一層級 ；tag不相同，直接刪掉重建； 通過key來標(biāo)識區(qū)分相同節(jié)點(diǎn)。
在采取diff算法比較新舊節(jié)點(diǎn)的時候，比較只會在同層級進(jìn)行, 不會跨層級比較。若對 DOM 樹進(jìn)行跨層比較，即進(jìn)行完全遍歷，算法的時間復(fù)雜度與節(jié)點(diǎn)個數(shù)呈指數(shù)級增長。
同時Web UI 中 DOM 節(jié)點(diǎn)跨層級的移動操作特別少，可以忽略不計，所以diff的算法只做同層比較，若 Vnode 做了跨層移動，則直接刪除 oldVnode, 再新建一個 new Vnode。
DIFF流程圖
當(dāng)用戶操作數(shù)據(jù)發(fā)生改變的時候，set方法會讓調(diào)用Dep.notify通知所有訂閱者Watcher，訂閱者就會調(diào)用patch給真實(shí)的DOM打補(bǔ)丁，更新相應(yīng)的視圖。
具體分析
在 Vue 中，diff 算法主要聚焦于 vDOM 更新過程中的三個關(guān)鍵函數(shù)，分別是 patch、patchVNode、updateChildren。
patch
patch：比對兩個虛擬dom時會有三種操作：刪除、新增、更新
入?yún)榕f節(jié)點(diǎn)和新節(jié)點(diǎn)，首先判斷新老節(jié)點(diǎn)是否為同一個節(jié)點(diǎn)，判斷方法即比較他們的 key 值、tag 值（標(biāo)簽類型）是否相同，若為同一個節(jié)點(diǎn)則執(zhí)行 patchVnode 方法進(jìn)行打補(bǔ)丁更新。
以下的代碼是 Vue 源碼中相關(guān)函數(shù)的精簡偽代碼，api 指的是原生的DOM操作函數(shù)集合。
function patch (oldVnode, vnode) {
// some code
if (sameVnode(oldVnode, vnode)) {
patchVnode(oldVnode, vnode)
} else {
const oEl = oldVnode.el // 當(dāng)前oldVnode對應(yīng)的真實(shí)元素節(jié)點(diǎn)
let parentEle = api.parentNode(oEl) // 父元素
createEle(vnode) // 根據(jù)Vnode生成新元素
if (parentEle !== null) {
api.insertBefore(parentEle, vnode.el, api.nextSibling(oEl)) // 將新元素添加進(jìn)父元素
api.removeChild(parentEle, oldVnode.el) // 移除以前的舊元素節(jié)點(diǎn)
oldVnode = null
}
}
// some code
return vnode
}
function sameVnode (a, b) {
return (
a.key === b.key && // key值
a.tag === b.tag && // 標(biāo)簽名
a.isComment === b.isComment && // 是否為注釋節(jié)點(diǎn)
// 是否都定義了data，data包含一些具體信息，例如onclick , style
isDef(a.data) === isDef(b.data) &&
sameInputType(a, b) // 當(dāng)標(biāo)簽是<input>的時候，type必須相同
)
}
patchVnode
patchVnode：比較兩個VNode三種類型操作 屬性更新、文本更新、子節(jié)點(diǎn)更新
patchVnode (oldVnode, vnode) {
const el = vnode.el = oldVnode.el
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)
}
}
}
updateChildren
updateChildren：用一種較高效的方式對比新舊兩個VNode的children，得出最小操作補(bǔ)丁。四指針雙循環(huán)執(zhí)行方式。
function updateChildren (parentElm, oldCh, newCh, insertedVnodeQueue, removeOnly) {
var oldStartIdx = 0;
var newStartIdx = 0;
var oldEndIdx = oldCh.length - 1;
var oldStartVnode = oldCh[0];
var oldEndVnode = oldCh[oldEndIdx];
var newEndIdx = newCh.length - 1;
var newStartVnode = newCh[0];
var newEndVnode = newCh[newEndIdx];
var oldKeyToIdx, idxInOld, vnodeToMove, refElm;
// removeOnly is a special flag used only by <transition-group>
// to ensure removed elements stay in correct relative positions
// during leaving transitions
var canMove = !removeOnly;
if (process.env.NODE_ENV !== 'production') {
checkDuplicateKeys(newCh);
}
while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
if (isUndef(oldStartVnode)) {
oldStartVnode = oldCh[++oldStartIdx]; // Vnode has been moved left
} else if (isUndef(oldEndVnode)) {
oldEndVnode = oldCh[--oldEndIdx];
} else if (sameVnode(oldStartVnode, newStartVnode)) {
patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue);
oldStartVnode = oldCh[++oldStartIdx];
newStartVnode = newCh[++newStartIdx];
} else if (sameVnode(oldEndVnode, newEndVnode)) {
patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue);
oldEndVnode = oldCh[--oldEndIdx];
newEndVnode = newCh[--newEndIdx];
} else if (sameVnode(oldStartVnode, newEndVnode)) { // Vnode moved right
patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue);
canMove && nodeOps.insertBefore(parentElm, oldStartVnode.elm, nodeOps.nextSibling(oldEndVnode.elm));
oldStartVnode = oldCh[++oldStartIdx];
newEndVnode = newCh[--newEndIdx];
} else if (sameVnode(oldEndVnode, newStartVnode)) { // Vnode moved left
patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue);
canMove && nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm);
oldEndVnode = oldCh[--oldEndIdx];
newStartVnode = newCh[++newStartIdx];
} else {
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);
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];
}
}
if (oldStartIdx > oldEndIdx) {
refElm = isUndef(newCh[newEndIdx + 1]) ? null : newCh[newEndIdx + 1].elm;
addVnodes(parentElm, refElm, newCh, newStartIdx, newEndIdx, insertedVnodeQueue);
} else if (newStartIdx > newEndIdx) {
removeVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx);
}
}
四指針雙循環(huán)：
保證 oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx 前提下，執(zhí)行如下循環(huán)算法：
- oldStartVNode 和 newStartVnode 滿足 sameVnode 的條件，進(jìn)行 patchVnode， 兩個頭指針右移。
- oldEndVnode 和 newEndVnode 滿足 sameVnode，進(jìn)行 patchVnode，兩個尾指針左移。
- oldStartVnode 和 newEndVnode 滿足 sameVnode, 進(jìn)行 patchVnode，同時把頭元素插入到 children nodes 尾部。++oldStartIdx，--newEndIdx。
- sameVnode(oldEndVnode, newStartVnode)。--oldStartIdx，++newEndIdx。
不符合以上四種情況，則直接尋找 oldCh 中是否存在和 newStartVnode 相同的節(jié)點(diǎn)，并移動到最前。
找不到和 newStartVnode 一致的節(jié)點(diǎn)，則調(diào)用 createElm 創(chuàng)建一個新的 DOM 節(jié)點(diǎn)。
循環(huán)結(jié)束后，處理剩余節(jié)點(diǎn)，
若 oldStartIdx > oldEndIdx 此時舊的 Vnode 節(jié)點(diǎn)已經(jīng)遍歷結(jié)束，但是新的節(jié)點(diǎn)還沒遍歷結(jié)束，則將剩余的 Vnode（>=0） 按照對應(yīng)的下標(biāo)插入到真實(shí)的DOM中去。
若 newStartIdx > newEndIdx, 此時新的 Vnode 已經(jīng)遍歷完成，但是老的節(jié)點(diǎn)還未遍歷結(jié)束，說明需要在真實(shí)的 DOM 中把多余的老的Vnode節(jié)點(diǎn)刪除。
圖解直接看文檔吧，配合源碼食用更佳：https://www.cnblogs.com/lilicat/p/13448827.html
