一、是什么
diff 算法是一種通過同層的樹節(jié)點(diǎn)進(jìn)行比較的高效算法
其有兩個特點(diǎn)：
- 比較只會在同層級進(jìn)行, 不會跨層級比較
- 在diff比較的過程中，循環(huán)從兩邊向中間比較
diff 算法在很多場景下都有應(yīng)用，在 vue 中，作用于虛擬 dom 渲染成真實(shí) dom 的新舊 VNode 節(jié)點(diǎn)比較
二、比較方式
diff整體策略為：深度優(yōu)先，同層比較
- 比較只會在同層級進(jìn)行, 不會跨層級比較
- 比較的過程中，循環(huán)從兩邊向中間收攏
下面舉個vue通過diff算法更新的例子：
新舊VNode節(jié)點(diǎn)如下圖所示：
第一次循環(huán)后，發(fā)現(xiàn)舊節(jié)點(diǎn)D與新節(jié)點(diǎn)D相同，直接復(fù)用舊節(jié)點(diǎn)D作為diff后的第一個真實(shí)節(jié)點(diǎn)，同時舊節(jié)點(diǎn)endIndex移動到C，新節(jié)點(diǎn)的 startIndex 移動到了 C
第二次循環(huán)后，同樣是舊節(jié)點(diǎn)的末尾和新節(jié)點(diǎn)的開頭(都是 C)相同，同理，diff 后創(chuàng)建了 C 的真實(shí)節(jié)點(diǎn)插入到第一次創(chuàng)建的 B 節(jié)點(diǎn)后面。同時舊節(jié)點(diǎn)的 endIndex 移動到了 B，新節(jié)點(diǎn)的 startIndex 移動到了 E
第三次循環(huán)中，發(fā)現(xiàn)E沒有找到，這時候只能直接創(chuàng)建新的真實(shí)節(jié)點(diǎn) E，插入到第二次創(chuàng)建的 C 節(jié)點(diǎn)之后。同時新節(jié)點(diǎn)的 startIndex 移動到了 A。舊節(jié)點(diǎn)的 startIndex 和 endIndex 都保持不動
第四次循環(huán)中，發(fā)現(xiàn)了新舊節(jié)點(diǎn)的開頭(都是 A)相同，于是 diff 后創(chuàng)建了 A 的真實(shí)節(jié)點(diǎn)，插入到前一次創(chuàng)建的 E 節(jié)點(diǎn)后面。同時舊節(jié)點(diǎn)的 startIndex 移動到了 B，新節(jié)點(diǎn)的 startIndex 移動到了 B
第五次循環(huán)中，情形同第四次循環(huán)一樣，因此 diff 后創(chuàng)建了 B 真實(shí)節(jié)點(diǎn) 插入到前一次創(chuàng)建的 A 節(jié)點(diǎn)后面。同時舊節(jié)點(diǎn)的 startIndex 移動到了 C，新節(jié)點(diǎn)的 startIndex 移動到了 F
新節(jié)點(diǎn)的 startIndex 已經(jīng)大于 endIndex 了，需要創(chuàng)建 newStartIdx 和 newEndIdx 之間的所有節(jié)點(diǎn)，也就是節(jié)點(diǎn)F，直接創(chuàng)建 F 節(jié)點(diǎn)對應(yīng)的真實(shí)節(jié)點(diǎn)放到 B 節(jié)點(diǎn)后面
三、原理分析
當(dāng)數(shù)據(jù)發(fā)生改變時，set方法會調(diào)用Dep.notify通知所有訂閱者Watcher，訂閱者就會調(diào)用patch給真實(shí)的DOM打補(bǔ)丁，更新相應(yīng)的視圖
源碼位置：src/core/vdom/patch.js
function patch(oldVnode, vnode, hydrating, removeOnly) {
if (isUndef(vnode)) { // 沒有新節(jié)點(diǎn)，直接執(zhí)行destory鉤子函數(shù)
if (isDef(oldVnode)) invokeDestroyHook(oldVnode)
return
}
let isInitialPatch = false
const insertedVnodeQueue = []
if (isUndef(oldVnode)) {
isInitialPatch = true
createElm(vnode, insertedVnodeQueue) // 沒有舊節(jié)點(diǎn)，直接用新節(jié)點(diǎn)生成dom元素
} else {
const isRealElement = isDef(oldVnode.nodeType)
if (!isRealElement && sameVnode(oldVnode, vnode)) {
// 判斷舊節(jié)點(diǎn)和新節(jié)點(diǎn)自身一樣，一致執(zhí)行patchVnode
patchVnode(oldVnode, vnode, insertedVnodeQueue, null, null, removeOnly)
} else {
// 否則直接銷毀及舊節(jié)點(diǎn)，根據(jù)新節(jié)點(diǎn)生成dom元素
if (isRealElement) {
if (oldVnode.nodeType === 1 && oldVnode.hasAttribute(SSR_ATTR)) {
oldVnode.removeAttribute(SSR_ATTR)
hydrating = true
}
if (isTrue(hydrating)) {
if (hydrate(oldVnode, vnode, insertedVnodeQueue)) {
invokeInsertHook(vnode, insertedVnodeQueue, true)
return oldVnode
}
}
oldVnode = emptyNodeAt(oldVnode)
}
return vnode.elm
}
}
}
patch函數(shù)前兩個參數(shù)位為oldVnode 和 Vnode ，分別代表新的節(jié)點(diǎn)和之前的舊節(jié)點(diǎn)，主要做了四個判斷：
- 沒有新節(jié)點(diǎn)，直接觸發(fā)舊節(jié)點(diǎn)的
destory鉤子 - 沒有舊節(jié)點(diǎn)，說明是頁面剛開始初始化的時候，此時，根本不需要比較了，直接全是新建，所以只調(diào)用
createElm - 舊節(jié)點(diǎn)和新節(jié)點(diǎn)自身一樣，通過
sameVnode判斷節(jié)點(diǎn)是否一樣，一樣時，直接調(diào)用patchVnode去處理這兩個節(jié)點(diǎn) - 舊節(jié)點(diǎn)和新節(jié)點(diǎn)自身不一樣，當(dāng)兩個節(jié)點(diǎn)不一樣的時候，直接創(chuàng)建新節(jié)點(diǎn)，刪除舊節(jié)點(diǎn)
下面主要講的是patchVnode部分
function patchVnode (oldVnode, vnode, insertedVnodeQueue, removeOnly) {
// 如果新舊節(jié)點(diǎn)一致，什么都不做
if (oldVnode === vnode) {
return
}
// 讓vnode.el引用到現(xiàn)在的真實(shí)dom，當(dāng)el修改時，vnode.el會同步變化
const elm = vnode.elm = oldVnode.elm
// 異步占位符
if (isTrue(oldVnode.isAsyncPlaceholder)) {
if (isDef(vnode.asyncFactory.resolved)) {
hydrate(oldVnode.elm, vnode, insertedVnodeQueue)
} else {
vnode.isAsyncPlaceholder = true
}
return
}
// 如果新舊都是靜態(tài)節(jié)點(diǎn)，并且具有相同的key
// 當(dāng)vnode是克隆節(jié)點(diǎn)或是v-once指令控制的節(jié)點(diǎn)時，只需要把oldVnode.elm和oldVnode.child都復(fù)制到vnode上
// 也不用再有其他操作
if (isTrue(vnode.isStatic) &&
isTrue(oldVnode.isStatic) &&
vnode.key === oldVnode.key &&
(isTrue(vnode.isCloned) || isTrue(vnode.isOnce))
) {
vnode.componentInstance = oldVnode.componentInstance
return
}
let i
const data = vnode.data
if (isDef(data) && isDef(i = data.hook) && isDef(i = i.prepatch)) {
i(oldVnode, vnode)
}
const oldCh = oldVnode.children
const ch = vnode.children
if (isDef(data) && isPatchable(vnode)) {
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不是文本節(jié)點(diǎn)或者注釋節(jié)點(diǎn)
if (isUndef(vnode.text)) {
// 并且都有子節(jié)點(diǎn)
if (isDef(oldCh) && isDef(ch)) {
// 并且子節(jié)點(diǎn)不完全一致，則調(diào)用updateChildren
if (oldCh !== ch) updateChildren(elm, oldCh, ch, insertedVnodeQueue, removeOnly)
// 如果只有新的vnode有子節(jié)點(diǎn)
} else if (isDef(ch)) {
if (isDef(oldVnode.text)) nodeOps.setTextContent(elm, '')
// elm已經(jīng)引用了老的dom節(jié)點(diǎn)，在老的dom節(jié)點(diǎn)上添加子節(jié)點(diǎn)
addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue)
// 如果新vnode沒有子節(jié)點(diǎn)，而vnode有子節(jié)點(diǎn)，直接刪除老的oldCh
} else if (isDef(oldCh)) {
removeVnodes(elm, oldCh, 0, oldCh.length - 1)
// 如果老節(jié)點(diǎn)是文本節(jié)點(diǎn)
} else if (isDef(oldVnode.text)) {
nodeOps.setTextContent(elm, '')
}
// 如果新vnode和老vnode是文本節(jié)點(diǎn)或注釋節(jié)點(diǎn)
// 但是vnode.text != oldVnode.text時，只需要更新vnode.elm的文本內(nèi)容就可以
} else if (oldVnode.text !== vnode.text) {
nodeOps.setTextContent(elm, vnode.text)
}
if (isDef(data)) {
if (isDef(i = data.hook) && isDef(i = i.postpatch)) i(oldVnode, vnode)
}
}
patchVnode主要做了幾個判斷：
- 新節(jié)點(diǎn)是否是文本節(jié)點(diǎn)，如果是，則直接更新
dom的文本內(nèi)容為新節(jié)點(diǎn)的文本內(nèi)容 - 新節(jié)點(diǎn)和舊節(jié)點(diǎn)如果都有子節(jié)點(diǎn)，則處理比較更新子節(jié)點(diǎn)
- 只有新節(jié)點(diǎn)有子節(jié)點(diǎn)，舊節(jié)點(diǎn)沒有，那么不用比較了，所有節(jié)點(diǎn)都是全新的，所以直接全部新建就好了，新建是指創(chuàng)建出所有新
DOM，并且添加進(jìn)父節(jié)點(diǎn) - 只有舊節(jié)點(diǎn)有子節(jié)點(diǎn)而新節(jié)點(diǎn)沒有，說明更新后的頁面，舊節(jié)點(diǎn)全部都不見了，那么要做的，就是把所有的舊節(jié)點(diǎn)刪除，也就是直接把
DOM刪除
子節(jié)點(diǎn)不完全一致，則調(diào)用updateChildren
function updateChildren (parentElm, oldCh, newCh, insertedVnodeQueue, removeOnly) {
let oldStartIdx = 0 // 舊頭索引
let newStartIdx = 0 // 新頭索引
let oldEndIdx = oldCh.length - 1 // 舊尾索引
let newEndIdx = newCh.length - 1 // 新尾索引
let oldStartVnode = oldCh[0] // oldVnode的第一個child
let oldEndVnode = oldCh[oldEndIdx] // oldVnode的最后一個child
let newStartVnode = newCh[0] // newVnode的第一個child
let newEndVnode = newCh[newEndIdx] // newVnode的最后一個child
let 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
const canMove = !removeOnly
// 如果oldStartVnode和oldEndVnode重合，并且新的也都重合了，證明diff完了，循環(huán)結(jié)束
while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
// 如果oldVnode的第一個child不存在
if (isUndef(oldStartVnode)) {
// oldStart索引右移
oldStartVnode = oldCh[++oldStartIdx] // Vnode has been moved left
// 如果oldVnode的最后一個child不存在
} else if (isUndef(oldEndVnode)) {
// oldEnd索引左移
oldEndVnode = oldCh[--oldEndIdx]
// oldStartVnode和newStartVnode是同一個節(jié)點(diǎn)
} else if (sameVnode(oldStartVnode, newStartVnode)) {
// patch oldStartVnode和newStartVnode， 索引左移，繼續(xù)循環(huán)
patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue)
oldStartVnode = oldCh[++oldStartIdx]
newStartVnode = newCh[++newStartIdx]
// oldEndVnode和newEndVnode是同一個節(jié)點(diǎn)
} else if (sameVnode(oldEndVnode, newEndVnode)) {
// patch oldEndVnode和newEndVnode，索引右移，繼續(xù)循環(huán)
patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue)
oldEndVnode = oldCh[--oldEndIdx]
newEndVnode = newCh[--newEndIdx]
// oldStartVnode和newEndVnode是同一個節(jié)點(diǎn)
} else if (sameVnode(oldStartVnode, newEndVnode)) { // Vnode moved right
// patch oldStartVnode和newEndVnode
patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue)
// 如果removeOnly是false，則將oldStartVnode.eml移動到oldEndVnode.elm之后
canMove && nodeOps.insertBefore(parentElm, oldStartVnode.elm, nodeOps.nextSibling(oldEndVnode.elm))
// oldStart索引右移，newEnd索引左移
oldStartVnode = oldCh[++oldStartIdx]
newEndVnode = newCh[--newEndIdx]
// 如果oldEndVnode和newStartVnode是同一個節(jié)點(diǎn)
} else if (sameVnode(oldEndVnode, newStartVnode)) { // Vnode moved left
// patch oldEndVnode和newStartVnode
patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue)
// 如果removeOnly是false，則將oldEndVnode.elm移動到oldStartVnode.elm之前
canMove && nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm)
// oldEnd索引左移，newStart索引右移
oldEndVnode = oldCh[--oldEndIdx]
newStartVnode = newCh[++newStartIdx]
// 如果都不匹配
} else {
if (isUndef(oldKeyToIdx)) oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx)
// 嘗試在oldChildren中尋找和newStartVnode的具有相同的key的Vnode
idxInOld = isDef(newStartVnode.key)
? oldKeyToIdx[newStartVnode.key]
: findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx)
// 如果未找到，說明newStartVnode是一個新的節(jié)點(diǎn)
if (isUndef(idxInOld)) { // New element
// 創(chuàng)建一個新Vnode
createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm)
// 如果找到了和newStartVnodej具有相同的key的Vnode，叫vnodeToMove
} else {
vnodeToMove = oldCh[idxInOld]
/* istanbul ignore if */
if (process.env.NODE_ENV !== 'production' && !vnodeToMove) {
warn(
'It seems there are duplicate keys that is causing an update error. ' +
'Make sure each v-for item has a unique key.'
)
}
// 比較兩個具有相同的key的新節(jié)點(diǎn)是否是同一個節(jié)點(diǎn)
//不設(shè)key，newCh和oldCh只會進(jìn)行頭尾兩端的相互比較，設(shè)key后，除了頭尾兩端的比較外，還會從用key生成的對象oldKeyToIdx中查找匹配的節(jié)點(diǎn)，所以為節(jié)點(diǎn)設(shè)置key可以更高效的利用dom。
if (sameVnode(vnodeToMove, newStartVnode)) {
// patch vnodeToMove和newStartVnode
patchVnode(vnodeToMove, newStartVnode, insertedVnodeQueue)
// 清除
oldCh[idxInOld] = undefined
// 如果removeOnly是false，則將找到的和newStartVnodej具有相同的key的Vnode，叫vnodeToMove.elm
// 移動到oldStartVnode.elm之前
canMove && nodeOps.insertBefore(parentElm, vnodeToMove.elm, oldStartVnode.elm)
// 如果key相同，但是節(jié)點(diǎn)不相同，則創(chuàng)建一個新的節(jié)點(diǎn)
} else {
// same key but different element. treat as new element
createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm)
}
}
// 右移
newStartVnode = newCh[++newStartIdx]
}
}
while循環(huán)主要處理了以下五種情景：
- 當(dāng)新老
VNode節(jié)點(diǎn)的start相同時，直接patchVnode，同時新老VNode節(jié)點(diǎn)的開始索引都加 1 - 當(dāng)新老
VNode節(jié)點(diǎn)的end相同時，同樣直接patchVnode，同時新老VNode節(jié)點(diǎn)的結(jié)束索引都減 1 - 當(dāng)老
VNode節(jié)點(diǎn)的start和新VNode節(jié)點(diǎn)的end相同時，這時候在patchVnode后，還需要將當(dāng)前真實(shí)dom節(jié)點(diǎn)移動到oldEndVnode的后面，同時老VNode節(jié)點(diǎn)開始索引加 1，新VNode節(jié)點(diǎn)的結(jié)束索引減 1 - 當(dāng)老
VNode節(jié)點(diǎn)的end和新VNode節(jié)點(diǎn)的start相同時，這時候在patchVnode后，還需要將當(dāng)前真實(shí)dom節(jié)點(diǎn)移動到oldStartVnode的前面，同時老VNode節(jié)點(diǎn)結(jié)束索引減 1，新VNode節(jié)點(diǎn)的開始索引加 1 - 如果都不滿足以上四種情形，那說明沒有相同的節(jié)點(diǎn)可以復(fù)用，則會分為以下兩種情況：
- 從舊的
VNode為key值，對應(yīng)index序列為value值的哈希表中找到與newStartVnode一致key的舊的VNode節(jié)點(diǎn)，再進(jìn)行patchVnode，同時將這個真實(shí)dom移動到oldStartVnode對應(yīng)的真實(shí)dom的前面 - 調(diào)用
createElm創(chuàng)建一個新的dom節(jié)點(diǎn)放到當(dāng)前newStartIdx的位置
- 從舊的
小結(jié)
-
當(dāng)數(shù)據(jù)發(fā)生改變時，訂閱者
watcher就會調(diào)用patch給真實(shí)的DOM打補(bǔ)丁 -
通過
isSameVnode進(jìn)行判斷，相同則調(diào)用patchVnode方法 -
patchVnode做了以下操作：文章來源：http://www.zghlxwxcb.cn/news/detail-411586.html
- 找到對應(yīng)的真實(shí)
dom，稱為el - 如果都有都有文本節(jié)點(diǎn)且不相等，將
el文本節(jié)點(diǎn)設(shè)置為Vnode的文本節(jié)點(diǎn) - 如果
oldVnode有子節(jié)點(diǎn)而VNode沒有，則刪除el子節(jié)點(diǎn) - 如果
oldVnode沒有子節(jié)點(diǎn)而VNode有，則將VNode的子節(jié)點(diǎn)真實(shí)化后添加到el - 如果兩者都有子節(jié)點(diǎn)，則執(zhí)行
updateChildren函數(shù)比較子節(jié)點(diǎn)
- 找到對應(yīng)的真實(shí)
-
updateChildren主要做了以下操作：文章來源地址http://www.zghlxwxcb.cn/news/detail-411586.html
- 設(shè)置新舊
VNode的頭尾指針 - 新舊頭尾指針進(jìn)行比較，循環(huán)向中間靠攏，根據(jù)情況調(diào)用
patchVnode進(jìn)行patch重復(fù)流程、調(diào)用createElem創(chuàng)建一個新節(jié)點(diǎn)，從哈希表尋找key一致的VNode節(jié)點(diǎn)再分情況操作
- 設(shè)置新舊
參考文章
- https://juejin.cn/post/6881907432541552648#heading-1
- https://www.infoq.cn/article/udlcpkh4iqb0cr5wgy7f
到了這里，關(guān)于面試被問到vue的diff算法原理，我不允許你回答不上來的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
