vue.js diff算法原理詳細解析
diff算法的概念
diff算法可以看作是一種對比算法，對比的對象是新舊虛擬Dom。顧名思義，diff算法可以找到新舊虛擬Dom之間的差異，但diff算法中其實並不是隻有對比虛擬Dom，還有根據對比後的結果更新真實Dom。
虛擬Dom
上面的概念我們提到瞭虛擬Dom，相信大傢對這個名詞並不陌生，下面為大傢解釋一下虛擬Dom的概念，以及diff算法中為什麼要對比虛擬Dom，而不是直接去操作真實Dom。
虛擬Dom，其實很簡單，就是一個用來描述真實Dom的對象
它有六個屬性，sel表示當前節點標簽名，data內是節點的屬性，children表示當前節點的其他子標簽節點，elm表示當前虛擬節點對應的真實節點（這裡暫時沒有），key即為當前節點的key，text表示當前節點下的文本，結構類似這樣。
let vnode = {
sel: 'ul',
data: {},
children: [
{
sel: 'li', data: { class: 'item' }, text: 'son1'
},
{
sel: 'li', data: { class: 'item' }, text: 'son2'
},
],
elm: undefined,
key: undefined,
text: undefined
}
那麼虛擬Dom有什麼用呢。我們其實可以把虛擬Dom理解成對應真實Dom的一種狀態。當真實Dom發生變化後，虛擬Dom可以為我們提供這個真實Dom變化之前和變化之後的狀態，我們通過對比這兩個狀態，即可得出真實Dom真正需要更新的部分，即可實現最小量更新。在一些比較復雜的Dom變化場景中，通過對比虛擬Dom後更新真實Dom會比直接更新真實Dom的效率高，這也就是虛擬Dom和diff算法真正存在的意義。
h函數
在介紹diff算法原理之前還需要簡單讓大傢瞭解一下h函數，因為我們要靠它為我們生成虛擬Dom。這個h函數大傢應該也比較熟悉，就是render函數裡面傳入的那個h函數。
h函數可以接受多種類型的參數，但其實它內部隻幹瞭一件事，就是執行vnode函數。根據傳入h函數的參數來決定執行vnode函數時傳入的參數。那麼vnode函數又是幹什麼的呢？vnode函數其實也隻幹瞭一件事，就是把傳入h函數的參數轉化為一個對象，即虛擬Dom。
// vnode.js
export default function (sel, data, children, text, elm) {
const key = data.key
return {sel, data, children, text, elm, key}
}
執行h函數後，內部會通過vnode函數生成虛擬Dom，h函數把這個虛擬在return出去。
diff對比規則
明確瞭h函數是幹什麼的，我們可以簡單用h函數生成兩個不同的虛擬節點，我們將通過一個簡易版的diff算法代碼介紹diff對比的具體流程。
// 第一個參數是sel 第二個參數是data 第三個參數是children
const myVnode1 = h("h1", {}, [
h("p", {key: "a"}, "a"),
h("p", {key: "b"}, "b"),
]);
const myVnode2 = h("h1", {}, [
h("p", {key: "c"}, "c"),
h("p", {key: "d"}, "d"),
]);
patch
比較的第一步就是執行patch，它相當於對比的入口。既然是對比兩個虛擬Dom，那麼就將兩個虛擬Dom作為參數傳入patch中。patch的主要作用是對比兩個虛擬Dom的根節點，並根據對比結果操作真實Dom。
patch函數的核心代碼如下，註意註釋。
// patch.js
import vnode from "./vnode"
import patchDetails from "./patchVnode"
import createEle from "./createEle"
/**
* @description 用來對比兩個虛擬dom的根節點，並根據對比結果操作真實Dom
* @param {*} oldVnode
* @param {*} newVnode
*/
export function patch(oldVnode, newVnode) {
// 1.判斷oldVnode是否為虛擬節點，不是的話轉化為虛擬節點
if(!oldVnode.sel) {
// 轉化為虛擬節點
oldVnode = vnode(oldVnode.tagName.toLowerCase(), {}, [], undefined, oldVnode)
}
// 2.判斷oldVnode和newVnode是否為同一個節點
if(oldVnode.key == newVnode.key && oldVnode.sel == newVnode.sel) {
console.log('是同一個節點')
// 比較子節點
patchDetails(oldVnode, newVnode)
}else {
console.log('不是同一個節點')
// 插入newVnode
const newNode = createEle(newVnode) // 插入之前需要先將newVnode轉化為dom
oldVnode.elm.parentNode.insertBefore(newNode, oldVnode.elm) // 插入操作
// 刪除oldVnode
oldVnode.elm.parentNode.removeChild(oldVnode.elm)
}
}
// createEle.js
/**
* @description 根據傳入的虛擬Dom生成真實Dom
* @param {*} vnode
* @returns real node
*/
export default function createEle (vnode) {
const realNode = document.createElement(vnode.sel)
// 子節點轉換
if(vnode.text && (vnode.children == undefined || (vnode.children && vnode.children.length == 0)) ) {
// 子節點隻含有文本
realNode.innerText = vnode.text
}else if(Array.isArray(vnode.children) && vnode.children.length > 0) {
// 子節點為其他虛擬節點 遞歸添加node
for(let i = 0; i < vnode.children.length; i++) {
const childNode = createEle(vnode.children[i])
realNode.appendChild(childNode)
}
}
// 補充vnode的elm屬性
vnode.elm = realNode
return vnode.elm
}
patchVnode
patchVnode用來比較兩個虛擬節點的子節點並更新其子節點對應的真實Dom節點
// patchVnode.js
import updateChildren from "./updateChildren"
import createEle from "./createEle"
/**
* @description 比較兩個虛擬節點的子節點（children or text） 並更新其子節點對應的真實dom節點
* @param {*} oldVnode
* @param {*} newVnode
* @returns
*/
export function patchDetails(oldVnode, newVnode) {
// 判斷oldVnode和newVnode是否為同一個對象, 是的話直接不用比瞭
if(oldVnode == newVnode) return
// 默認newVnode和oldVnode隻有text和children其中之一，真實的源碼這裡的情況會更多一些，不過大同小異。
if(hasText(newVnode)) {
// newVnode有text但沒有children
/**
* newVnode.text !== oldVnode.text 直接囊括瞭兩種情況
* 1.oldVnode有text無children 但是text和newVnode的text內容不同
* 2.oldVnode無text有children 此時oldVnode.text為undefined
* 兩種情況都可以通過innerText屬性直接完成dom更新
* 情況1直接更新text 情況2相當於去掉瞭children後加瞭新的text
*/
if(newVnode.text !== oldVnode.text) {
oldVnode.elm.innerText = newVnode.text
}
}else if(hasChildren(newVnode)) {
// newVnode有children但是沒有text
if(hasText(oldVnode)) {
// oldVnode有text但是沒有children
oldVnode.elm.innerText = '' // 刪除oldVnode的text
// 添加newVnode的children
for(let i = 0; i < newVnode.children.length; i++) {
oldVnode.elm.appendChild(createEle(newVnode.children[i]))
}
}else if(hasChildren(oldVnode)) {
// oldVnode有children但是沒有text
// 對比兩個節點的children 並更新對應的真實dom節點
updateChildren(oldVnode.children, newVnode.children, oldVnode.elm)
}
}
}
// 有children沒有text
function hasChildren(node) {
return !node.text && (node.children && node.children.length > 0)
}
// 有text沒有children
function hasText(node) {
return node.text && (node.children == undefined || (node.children && node.children.length == 0))
}
updateChildren
該方法是diff算法中最復雜的方法（大的要來瞭）。對應上面patchVnode中oldVnode和newVnode都有children的情況。
首先我們需要介紹一下這裡的對比規則。
對比過程中會引入四個指針，分別指向oldVnode子節點列表中的第一個節點和最後一個節點（後面我們簡稱為舊前和舊後）以及指向newVnode子節點列表中的第一個節點和最後一個節點（後面我們簡稱為新前和新後）
對比時，每一次對比按照以下順序進行命中查找
- 舊前與新前節點對比（1）
- 舊後與新後節點對比（2）
- 舊前與新後節點對比（3）
- 舊後與新前節點對比（4）
上述四種情況，如果某一種情況兩個指針對應的虛擬Dom相同，那麼我們稱之為命中。命中後就不會接著查找瞭，指針會移動，（還有可能會操作真實Dom，3或者4命中時會操作真實Dom移動節點）之後開始下一次對比。如果都沒有命中，則去oldVnode子節點列表循環查找當前新前指針所指向的節點，如果查到瞭，那麼操作真實Dom移動節點，沒查到則新增真實Dom節點插入。
這種模式的對比會一直進行，直到滿足瞭終止條件。即舊前指針移動到瞭舊後指針的後面或者新前指針移動到瞭新後指針的後面，我們可以理解為舊子節點先處理完畢和新子節點處理完畢。那麼我們可以預想到新舊子節點中總會有其一先處理完，對比結束後，我們會根據沒有處理完子節點的那一對前後指針決定是要插入真實Dom還是刪除真實Dom。
- 如果舊子節點先處理完瞭，新子節點有剩餘，說明有要新增的節點。將根據最終新前和新後之間的虛擬節點執行插入操作
- 如果新子節點先處理完瞭，舊子節點有剩餘，說明有要刪除的節點。將根據最終舊前和舊後之間的虛擬節點執行刪除操作
下面將呈現代碼，註意註釋：
// updateChildren.js
import patchDetails from "./patchVnode"
import createEle from "./createEle";
/**
* @description 對比子節點列表並更新真實Dom
* @param {*} oldCh 舊虛擬Dom子節點列表
* @param {*} newCh 新虛擬Dom子節點列表
* @param {*} parent 新舊虛擬節點對應的真實Dom
* @returns
*/
export default function updateChildren(oldCh, newCh, parent) {
// 定義四個指針 舊前 舊後 新前 新後 （四個指針兩兩一對，每一對前後指針所指向的節點以及其之間的節點為未處理的子節點）
let oldStartIndex = 0;
let oldEndIndex = oldCh.length - 1;
let newStartIndex = 0;
let newEndIndex = newCh.length - 1;
// 四個指針對應的節點
let oldStartNode = oldCh[oldStartIndex];
let oldEndNode = oldCh[oldEndIndex];
let newStartNode = newCh[newStartIndex];
let newEndNode = newCh[newEndIndex];
// oldCh中每個子節點 key 與 index的哈希表 用於四種對比規則都不匹配的情況下在oldCh中尋找節點
const keyMap = new Map();
/**
* 開始遍歷兩個children數組進行細節對比
* 對比規則：舊前-新前 舊後-新後 舊前-新後 舊後-新前
* 對比之後指針進行移動
* 直到指針不滿足以下條件 意味著有一對前後指針之間再無未處理的子節點 則停止對比 直接操作DOM
*/
while (oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex) {
// 這四種情況是為瞭讓指針在移動的過程中跳過空節點
if (oldStartNode == undefined) {
oldStartNode = oldCh[++oldStartIndex];
} else if (oldEndNode == undefined) {
oldEndNode = oldCh[--oldEndIndex];
} else if (newStartNode == undefined) {
newStartNode = newCh[++newStartIndex];
} else if (newEndNode == undefined) {
newEndNode = newCh[--newEndIndex];
} else if (isSame(oldStartNode, newStartNode)) {
console.log("method1");
// 舊前-新前是同一個虛擬節點
// 兩個子節點再對比他們的子節點並更新dom （遞歸切入點）
patchDetails(oldStartNode, newStartNode);
// 指針移動
oldStartNode = oldCh[++oldStartIndex];
newStartNode = newCh[++newStartIndex];
} else if (isSame(oldEndNode, newEndNode)) {
console.log("method2");
// 舊後-新後是同一個虛擬節點
// 兩個子節點再對比他們的子節點並更新dom （遞歸切入點）
patchDetails(oldEndNode, newEndNode);
// 指針移動
oldEndNode = oldCh[--oldEndIndex];
newEndNode = newCh[--newEndIndex];
} else if (isSame(oldStartNode, newEndNode)) {
console.log("method3");
// 舊前-新後是同一個虛擬節點
// 兩個子節點再對比他們的子節點並更新dom （遞歸切入點）
patchDetails(oldStartNode, newEndNode);
/**
* 這一步多一個移動(真實)節點的操作
* 需要把當前指針所指向的子節點 移動到 oldEndIndex所對應真實節點之後（也就是未處理真實節點的尾部）
* 註意：這一步是在操作真實節點
*/
parent.insertBefore(oldStartNode.elm, oldEndNode.elm.nextSibling);
// 指針移動
oldStartNode = oldCh[++oldStartIndex];
newEndNode = newCh[--newEndIndex];
} else if (isSame(oldEndNode, newStartNode)) {
console.log("method4");
// 舊後-新前 是同一個虛擬節點
// 兩個子節點再對比他們的子節點並更新dom （遞歸切入點）
patchDetails(oldEndNode, newStartNode);
/**
* 這一步多一個移動(真實)節點的操作
* 與method3不同在移動位置
* 需要把當前指針所指向的子節點 移動到 oldStartIndex所對應真實節點之前（也就是未處理真實節點的頂部）
* 註意：這一步是在操作真實節點
*/
parent.insertBefore(oldEndNode.elm, oldCh[oldStartIndex].elm);
// 指針移動
oldEndNode = oldCh[--oldEndIndex];
newStartNode = newCh[++newStartIndex];
} else {
console.log("does not match");
// 四種規則都不匹配
// 生成keyMap
if (keyMap.size == 0) {
for (let i = oldStartIndex; i <= oldEndIndex; i++) {
if (oldCh[i].key) keyMap.set(oldCh[i].key, i);
}
}
// 在oldCh中搜索當前newStartIndex所指向的節點
if (keyMap.has(newStartNode.key)) {
// 搜索到瞭
// 先獲取oldCh中該虛擬節點
const oldMoveNode = oldCh[keyMap.get(newStartNode.key)];
// 兩個子節點再對比他們的子節點並更新dom （遞歸切入點）
patchDetails(oldMoveNode, newStartNode);
// 移動這個節點（移動的是真實節點）
parent.insertBefore(oldMoveNode.elm, oldStartNode.elm);
// 該虛擬節點設置為undefined（還記得最開始的四個條件嗎，因為這裡會將子節點制空，所以加瞭那四個條件）
oldCh[keyMap.get(newStartNode.key)] = undefined;
} else {
// 沒搜索到 直接插入
parent.insertBefore(createEle(newStartNode), oldStartNode.elm);
}
// 指針移動
newStartNode = newCh[++newStartIndex];
}
}
/**
* 插入和刪除節點
* while結束後 有一對前後指針之間仍然有未處理的子節點，那麼就會進行插入或者刪除操作
* oldCh的雙指針中有未處理的子節點，進行刪除操作
* newCh的雙指針中有未處理的子節點，進行插入操作
*/
if (oldStartIndex <= oldEndIndex) {
// 刪除
for (let i = oldStartIndex; i <= oldEndIndex; i++) {
// 加判斷是因為oldCh[i]有可能為undefined
if(oldCh[i]) parent.removeChild(oldCh[i].elm);
}
} else if (newStartIndex <= newEndIndex) {
/**
* 插入
* 這裡需要註意的點是從哪裡插入，也就是appendChild的第二個參數
* 應該從oldStartIndex對應的位置插入
*/
for (let i = newStartIndex; i <= newEndIndex; i++) {
// oldCh[oldStartIndex]存在是從頭部插入
parent.insertBefore(createEle(newCh[i]), oldCh[oldStartIndex] ? oldCh[oldStartIndex].elm : undefined);
}
}
}
// 判斷兩個虛擬節點是否為同一個虛擬節點
function isSame(a, b) {
return a.sel == b.sel && a.key == b.key;
}
這裡的邏輯稍微比較復雜，需要大傢多理幾遍，必要的話，自己手畫一張圖自己移動一下指針。著重需要註意的地方是操作真實Dom時，插入、移動節點應該將節點從哪裡插入或者移動到哪裡，其實基本插入到oldStartIndex對應的真實Dom的前面，除瞭第三種命中後的移動節點操作，是移動到oldEndIndex所對應真實節點之後
總結
由於diff算法對比的是虛擬Dom，而虛擬Dom是呈樹狀的，所以我們可以發現，diff算法中充滿瞭遞歸。總結起來，其實diff算法就是一個 patch —> patchVnode —> updateChildren —> patchVnode —> updateChildren —> patchVnode這樣的一個循環遞歸的過程。
這裡再提一嘴key，我們面試中經常會被問到vue中key的作用。根據上面我們分析的，key的主要作用其實就是對比兩個虛擬節點時，判斷其是否為相同節點。加瞭key以後，我們可以更為明確的判斷兩個節點是否為同一個虛擬節點，是的話判斷子節點是否有變更（有變更更新真實Dom），不是的話繼續比。如果不加key的話，如果兩個不同節點的標簽名恰好相同，那麼就會被判定為同一個節點（key都為undefined），結果一對比這兩個節點的子節點發現不一樣，這樣會憑空增加很多對真實Dom的操作，從而導致頁面更頻繁地重繪和回流。
所以我認為合理利用key可以有效減少真實Dom的變動，從而減少頁面重繪和回流的頻率，進而提高頁面更新的效率。
到此這篇關於vue.js diff算法原理詳細解析的文章就介紹到這瞭,更多相關vue.js diff算法內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！