本文我們總結(jié)一下有關(guān)diff算法的相關(guān)內(nèi)容和實(shí)現(xiàn)原理

開門見山，直接先給出大家diff算法的概念

diff算法可以看作是一種對(duì)比算法，對(duì)比的對(duì)象是新舊虛擬Dom。顧名思義，diff算法可以找到新舊虛擬Dom之間的差異，但diff算法中其實(shí)并不是只有對(duì)比虛擬Dom，還有根據(jù)對(duì)比后的結(jié)果更新真實(shí)Dom。

虛擬Dom

上面的概念我們提到了虛擬Dom，相信大家對(duì)這個(gè)名詞并不陌生，下面為大家解釋一下虛擬Dom的概念，以及diff算法中為什么要對(duì)比虛擬Dom，而不是直接去操作真實(shí)Dom。

虛擬Dom，其實(shí)很簡單，就是一個(gè)用來描述真實(shí)Dom的對(duì)象

它有六個(gè)屬性，sel表示當(dāng)前節(jié)點(diǎn)標(biāo)簽名，data內(nèi)是節(jié)點(diǎn)的屬性，children表示當(dāng)前節(jié)點(diǎn)的其他子標(biāo)簽節(jié)點(diǎn)，elm表示當(dāng)前虛擬節(jié)點(diǎn)對(duì)應(yīng)的真實(shí)節(jié)點(diǎn)（這里暫時(shí)沒有），key即為當(dāng)前節(jié)點(diǎn)的key，text表示當(dāng)前節(jié)點(diǎn)下的文本，結(jié)構(gòu)類似這樣。

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有什么用呢。我們其實(shí)可以把虛擬Dom理解成對(duì)應(yīng)真實(shí)Dom的一種狀態(tài)。當(dāng)真實(shí)Dom發(fā)生變化后，虛擬Dom可以為我們提供這個(gè)真實(shí)Dom變化之前和變化之后的狀態(tài)，我們通過對(duì)比這兩個(gè)狀態(tài)，即可得出真實(shí)Dom真正需要更新的部分，即可實(shí)現(xiàn)最小量更新。在一些比較復(fù)雜的Dom變化場景中，通過對(duì)比虛擬Dom后更新真實(shí)Dom會(huì)比直接更新真實(shí)Dom的效率高，這也就是虛擬Dom和diff算法真正存在的意義。

h函數(shù)

在介紹diff算法原理之前還需要簡單讓大家了解一下h函數(shù)，因?yàn)槲覀円克鼮槲覀兩商摂MDom。這個(gè)h函數(shù)大家應(yīng)該也比較熟悉，就是render函數(shù)里面?zhèn)魅氲哪莻€(gè)h函數(shù)。

h函數(shù)可以接受多種類型的參數(shù)，但其實(shí)它內(nèi)部只干了一件事，就是執(zhí)行vnode函數(shù)。根據(jù)傳入h函數(shù)的參數(shù)來決定執(zhí)行vnode函數(shù)時(shí)傳入的參數(shù)。那么vnode函數(shù)又是干什么的呢？vnode函數(shù)其實(shí)也只干了一件事，就是把傳入h函數(shù)的參數(shù)轉(zhuǎn)化為一個(gè)對(duì)象，即虛擬Dom。

// vnode.js export default function (sel, data, children, text, elm) {const key = data.key return {sel, data, children, text, elm, key} }

執(zhí)行h函數(shù)后，內(nèi)部會(huì)通過vnode函數(shù)生成虛擬Dom，h函數(shù)把這個(gè)虛擬在return出去。

diff對(duì)比規(guī)則

明確了h函數(shù)是干什么的，我們可以簡單用h函數(shù)生成兩個(gè)不同的虛擬節(jié)點(diǎn)，我們將通過一個(gè)簡易版的diff算法代碼介紹diff對(duì)比的具體流程。

// 第一個(gè)參數(shù)是sel 第二個(gè)參數(shù)是data 第三個(gè)參數(shù)是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

比較的第一步就是執(zhí)行patch，它相當(dāng)于對(duì)比的入口。既然是對(duì)比兩個(gè)虛擬Dom，那么就將兩個(gè)虛擬Dom作為參數(shù)傳入patch中。patch的主要作用是對(duì)比兩個(gè)虛擬Dom的根節(jié)點(diǎn)，并根據(jù)對(duì)比結(jié)果操作真實(shí)Dom。

patch函數(shù)的核心代碼如下，注意注釋。

// patch.js ? import vnode from "./vnode" import patchDetails from "./patchVnode" import createEle from "./createEle" ? /*** @description 用來對(duì)比兩個(gè)虛擬dom的根節(jié)點(diǎn)，并根據(jù)對(duì)比結(jié)果操作真實(shí)Dom* @param {*} oldVnode * @param {*} newVnode */ export function patch(oldVnode, newVnode) {// 1.判斷oldVnode是否為虛擬節(jié)點(diǎn)，不是的話轉(zhuǎn)化為虛擬節(jié)點(diǎn)if(!oldVnode.sel) {// 轉(zhuǎn)化為虛擬節(jié)點(diǎn)oldVnode = vnode(oldVnode.tagName.toLowerCase(), {}, [], undefined, oldVnode)} ?// 2.判斷oldVnode和newVnode是否為同一個(gè)節(jié)點(diǎn)if(oldVnode.key == newVnode.key && oldVnode.sel == newVnode.sel) {console.log('是同一個(gè)節(jié)點(diǎn)')// 比較子節(jié)點(diǎn)patchDetails(oldVnode, newVnode)}else {console.log('不是同一個(gè)節(jié)點(diǎn)')// 插入newVnode const newNode = createEle(newVnode) // 插入之前需要先將newVnode轉(zhuǎn)化為domoldVnode.elm.parentNode.insertBefore(newNode, oldVnode.elm) // 插入操作// 刪除oldVnodeoldVnode.elm.parentNode.removeChild(oldVnode.elm)} } ? // createEle.js ? /*** @description 根據(jù)傳入的虛擬Dom生成真實(shí)Dom* @param {*} vnode * @returns real node*/ export default function createEle (vnode) {const realNode = document.createElement(vnode.sel) ?// 子節(jié)點(diǎn)轉(zhuǎn)換if(vnode.text && (vnode.children == undefined || (vnode.children && vnode.children.length == 0)) ) {// 子節(jié)點(diǎn)只含有文本realNode.innerText = vnode.text }else if(Array.isArray(vnode.children) && vnode.children.length > 0) {// 子節(jié)點(diǎn)為其他虛擬節(jié)點(diǎn) 遞歸添加nodefor(let i = 0; i < vnode.children.length; i++) {const childNode = createEle(vnode.children[i])realNode.appendChild(childNode)}} ?// 補(bǔ)充vnode的elm屬性vnode.elm = realNode ?return vnode.elm }

patchVnode

patchVnode用來比較兩個(gè)虛擬節(jié)點(diǎn)的子節(jié)點(diǎn)并更新其子節(jié)點(diǎn)對(duì)應(yīng)的真實(shí)Dom節(jié)點(diǎn)

// patchVnode.js ? import updateChildren from "./updateChildren" import createEle from "./createEle" ? /*** @description 比較兩個(gè)虛擬節(jié)點(diǎn)的子節(jié)點(diǎn)（children or text） 并更新其子節(jié)點(diǎn)對(duì)應(yīng)的真實(shí)dom節(jié)點(diǎn)* @param {*} oldVnode * @param {*} newVnode * @returns */ export function patchDetails(oldVnode, newVnode) {// 判斷oldVnode和newVnode是否為同一個(gè)對(duì)象, 是的話直接不用比了if(oldVnode == newVnode) return ?// 默認(rèn)newVnode和oldVnode只有text和children其中之一，真實(shí)的源碼這里的情況會(huì)更多一些，不過大同小異。 ?if(hasText(newVnode)) {// newVnode有text但沒有children ?/*** newVnode.text !== oldVnode.text 直接囊括了兩種情況* 1.oldVnode有text無children 但是text和newVnode的text內(nèi)容不同* 2.oldVnode無text有children 此時(shí)oldVnode.text為undefined * 兩種情況都可以通過innerText屬性直接完成dom更新 * 情況1直接更新text 情況2相當(dāng)于去掉了children后加了新的text*/if(newVnode.text !== oldVnode.text) {oldVnode.elm.innerText = newVnode.text} ?}else if(hasChildren(newVnode)) {// newVnode有children但是沒有textif(hasText(oldVnode)) {// oldVnode有text但是沒有childrenoldVnode.elm.innerText = '' // 刪除oldVnode的text// 添加newVnode的childrenfor(let i = 0; i < newVnode.children.length; i++) {oldVnode.elm.appendChild(createEle(newVnode.children[i]))} ?}else if(hasChildren(oldVnode)) {// oldVnode有children但是沒有text ?// 對(duì)比兩個(gè)節(jié)點(diǎn)的children 并更新對(duì)應(yīng)的真實(shí)dom節(jié)點(diǎn)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算法中最復(fù)雜的方法（大的要來了）。對(duì)應(yīng)上面patchVnode中oldVnode和newVnode都有children的情況。

首先我們需要介紹一下這里的對(duì)比規(guī)則。

對(duì)比過程中會(huì)引入四個(gè)指針，分別指向oldVnode子節(jié)點(diǎn)列表中的第一個(gè)節(jié)點(diǎn)和最后一個(gè)節(jié)點(diǎn)（后面我們簡稱為舊前和舊后）以及指向newVnode子節(jié)點(diǎn)列表中的第一個(gè)節(jié)點(diǎn)和最后一個(gè)節(jié)點(diǎn)（后面我們簡稱為新前和新后）

對(duì)比時(shí)，每一次對(duì)比按照以下順序進(jìn)行命中查找

• 舊前與新前節(jié)點(diǎn)對(duì)比（1）
• 舊后與新后節(jié)點(diǎn)對(duì)比（2）
• 舊前與新后節(jié)點(diǎn)對(duì)比（3）
• 舊后與新前節(jié)點(diǎn)對(duì)比（4）

上述四種情況，如果某一種情況兩個(gè)指針對(duì)應(yīng)的虛擬Dom相同，那么我們稱之為命中。命中后就不會(huì)接著查找了，指針會(huì)移動(dòng)，（還有可能會(huì)操作真實(shí)Dom，3或者4命中時(shí)會(huì)操作真實(shí)Dom移動(dòng)節(jié)點(diǎn)）之后開始下一次對(duì)比。如果都沒有命中，則去oldVnode子節(jié)點(diǎn)列表循環(huán)查找當(dāng)前新前指針?biāo)赶虻墓?jié)點(diǎn)，如果查到了，那么操作真實(shí)Dom移動(dòng)節(jié)點(diǎn)，沒查到則新增真實(shí)Dom節(jié)點(diǎn)插入。

這種模式的對(duì)比會(huì)一直進(jìn)行，直到滿足了終止條件。即舊前指針移動(dòng)到了舊后指針的后面或者新前指針移動(dòng)到了新后指針的后面，我們可以理解為舊子節(jié)點(diǎn)先處理完畢和新子節(jié)點(diǎn)處理完畢。那么我們可以預(yù)想到新舊子節(jié)點(diǎn)中總會(huì)有其一先處理完，對(duì)比結(jié)束后，我們會(huì)根據(jù)沒有處理完子節(jié)點(diǎn)的那一對(duì)前后指針決定是要插入真實(shí)Dom還是刪除真實(shí)Dom。

• 如果舊子節(jié)點(diǎn)先處理完了，新子節(jié)點(diǎn)有剩余，說明有要新增的節(jié)點(diǎn)。將根據(jù)最終新前和新后之間的虛擬節(jié)點(diǎn)執(zhí)行插入操作
• 如果新子節(jié)點(diǎn)先處理完了，舊子節(jié)點(diǎn)有剩余，說明有要?jiǎng)h除的節(jié)點(diǎn)。將根據(jù)最終舊前和舊后之間的虛擬節(jié)點(diǎn)執(zhí)行刪除操作

下面將呈現(xiàn)代碼，注意注釋

// updateChildren.js ? import patchDetails from "./patchVnode" import createEle from "./createEle"; ? /*** @description 對(duì)比子節(jié)點(diǎn)列表并更新真實(shí)Dom* @param {*} oldCh 舊虛擬Dom子節(jié)點(diǎn)列表 * @param {*} newCh 新虛擬Dom子節(jié)點(diǎn)列表 * @param {*} parent 新舊虛擬節(jié)點(diǎn)對(duì)應(yīng)的真實(shí)Dom* @returns */ ? export default function updateChildren(oldCh, newCh, parent) {// 定義四個(gè)指針 舊前 舊后 新前 新后 （四個(gè)指針兩兩一對(duì)，每一對(duì)前后指針?biāo)赶虻墓?jié)點(diǎn)以及其之間的節(jié)點(diǎn)為未處理的子節(jié)點(diǎn)）let oldStartIndex = 0;let oldEndIndex = oldCh.length - 1;let newStartIndex = 0;let newEndIndex = newCh.length - 1; ?// 四個(gè)指針對(duì)應(yīng)的節(jié)點(diǎn)let oldStartNode = oldCh[oldStartIndex];let oldEndNode = oldCh[oldEndIndex];let newStartNode = newCh[newStartIndex];let newEndNode = newCh[newEndIndex]; ?// oldCh中每個(gè)子節(jié)點(diǎn) key 與 index的哈希表 用于四種對(duì)比規(guī)則都不匹配的情況下在oldCh中尋找節(jié)點(diǎn)const keyMap = new Map(); ?/*** 開始遍歷兩個(gè)children數(shù)組進(jìn)行細(xì)節(jié)對(duì)比* 對(duì)比規(guī)則：舊前-新前 舊后-新后 舊前-新后 舊后-新前* 對(duì)比之后指針進(jìn)行移動(dòng)* 直到指針不滿足以下條件 意味著有一對(duì)前后指針之間再無未處理的子節(jié)點(diǎn) 則停止對(duì)比 直接操作DOM*/ ?while (oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex) {// 這四種情況是為了讓指針在移動(dòng)的過程中跳過空節(jié)點(diǎn)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");// 舊前-新前是同一個(gè)虛擬節(jié)點(diǎn) ?// 兩個(gè)子節(jié)點(diǎn)再對(duì)比他們的子節(jié)點(diǎn)并更新dom （遞歸切入點(diǎn)）patchDetails(oldStartNode, newStartNode);// 指針移動(dòng)oldStartNode = oldCh[++oldStartIndex];newStartNode = newCh[++newStartIndex];} else if (isSame(oldEndNode, newEndNode)) {console.log("method2");// 舊后-新后是同一個(gè)虛擬節(jié)點(diǎn) ?// 兩個(gè)子節(jié)點(diǎn)再對(duì)比他們的子節(jié)點(diǎn)并更新dom （遞歸切入點(diǎn)）patchDetails(oldEndNode, newEndNode);// 指針移動(dòng)oldEndNode = oldCh[--oldEndIndex];newEndNode = newCh[--newEndIndex];} else if (isSame(oldStartNode, newEndNode)) {console.log("method3");// 舊前-新后是同一個(gè)虛擬節(jié)點(diǎn) ?// 兩個(gè)子節(jié)點(diǎn)再對(duì)比他們的子節(jié)點(diǎn)并更新dom （遞歸切入點(diǎn)）patchDetails(oldStartNode, newEndNode); ?/*** 這一步多一個(gè)移動(dòng)(真實(shí))節(jié)點(diǎn)的操作* 需要把當(dāng)前指針?biāo)赶虻淖庸?jié)點(diǎn) 移動(dòng)到 oldEndIndex所對(duì)應(yīng)真實(shí)節(jié)點(diǎn)之后（也就是未處理真實(shí)節(jié)點(diǎn)的尾部）* 注意：這一步是在操作真實(shí)節(jié)點(diǎn)*/parent.insertBefore(oldStartNode.elm, oldEndNode.elm.nextSibling); ?// 指針移動(dòng)oldStartNode = oldCh[++oldStartIndex];newEndNode = newCh[--newEndIndex];} else if (isSame(oldEndNode, newStartNode)) {console.log("method4");// 舊后-新前 是同一個(gè)虛擬節(jié)點(diǎn) ?// 兩個(gè)子節(jié)點(diǎn)再對(duì)比他們的子節(jié)點(diǎn)并更新dom （遞歸切入點(diǎn)）patchDetails(oldEndNode, newStartNode);/*** 這一步多一個(gè)移動(dòng)(真實(shí))節(jié)點(diǎn)的操作* 與method3不同在移動(dòng)位置* 需要把當(dāng)前指針?biāo)赶虻淖庸?jié)點(diǎn) 移動(dòng)到 oldStartIndex所對(duì)應(yīng)真實(shí)節(jié)點(diǎn)之前（也就是未處理真實(shí)節(jié)點(diǎn)的頂部）* 注意：這一步是在操作真實(shí)節(jié)點(diǎn)*/parent.insertBefore(oldEndNode.elm, oldCh[oldStartIndex].elm); ?// 指針移動(dòng)oldEndNode = oldCh[--oldEndIndex];newStartNode = newCh[++newStartIndex];} else {console.log("does not match");// 四種規(guī)則都不匹配 ?// 生成keyMapif (keyMap.size == 0) {for (let i = oldStartIndex; i <= oldEndIndex; i++) {if (oldCh[i].key) keyMap.set(oldCh[i].key, i);}} ?// 在oldCh中搜索當(dāng)前newStartIndex所指向的節(jié)點(diǎn)if (keyMap.has(newStartNode.key)) {// 搜索到了 ?// 先獲取oldCh中該虛擬節(jié)點(diǎn)const oldMoveNode = oldCh[keyMap.get(newStartNode.key)];// 兩個(gè)子節(jié)點(diǎn)再對(duì)比他們的子節(jié)點(diǎn)并更新dom （遞歸切入點(diǎn)）patchDetails(oldMoveNode, newStartNode); ?// 移動(dòng)這個(gè)節(jié)點(diǎn)（移動(dòng)的是真實(shí)節(jié)點(diǎn)）parent.insertBefore(oldMoveNode.elm, oldStartNode.elm); ?// 該虛擬節(jié)點(diǎn)設(shè)置為undefined（還記得最開始的四個(gè)條件嗎，因?yàn)檫@里會(huì)將子節(jié)點(diǎn)制空，所以加了那四個(gè)條件）oldCh[keyMap.get(newStartNode.key)] = undefined;} else {// 沒搜索到 直接插入parent.insertBefore(createEle(newStartNode), oldStartNode.elm);} ?// 指針移動(dòng)newStartNode = newCh[++newStartIndex];}} ?/*** 插入和刪除節(jié)點(diǎn)* while結(jié)束后 有一對(duì)前后指針之間仍然有未處理的子節(jié)點(diǎn)，那么就會(huì)進(jìn)行插入或者刪除操作* oldCh的雙指針中有未處理的子節(jié)點(diǎn)，進(jìn)行刪除操作* newCh的雙指針中有未處理的子節(jié)點(diǎn)，進(jìn)行插入操作*/if (oldStartIndex <= oldEndIndex) {// 刪除for (let i = oldStartIndex; i <= oldEndIndex; i++) {// 加判斷是因?yàn)閛ldCh[i]有可能為undefinedif(oldCh[i]) parent.removeChild(oldCh[i].elm);}} else if (newStartIndex <= newEndIndex) {/*** 插入* 這里需要注意的點(diǎn)是從哪里插入，也就是appendChild的第二個(gè)參數(shù)* 應(yīng)該從oldStartIndex對(duì)應(yīng)的位置插入*/for (let i = newStartIndex; i <= newEndIndex; i++) {// oldCh[oldStartIndex]存在是從頭部插入parent.insertBefore(createEle(newCh[i]), oldCh[oldStartIndex] ? oldCh[oldStartIndex].elm : undefined);}} } ? // 判斷兩個(gè)虛擬節(jié)點(diǎn)是否為同一個(gè)虛擬節(jié)點(diǎn) function isSame(a, b) {return a.sel == b.sel && a.key == b.key; }

這里的邏輯稍微比較復(fù)雜，需要大家多理幾遍，必要的話，自己手畫一張圖自己移動(dòng)一下指針。著重需要注意的地方是操作真實(shí)Dom時(shí)，插入、移動(dòng)節(jié)點(diǎn)應(yīng)該將節(jié)點(diǎn)從哪里插入或者移動(dòng)到哪里，其實(shí)基本插入到oldStartIndex對(duì)應(yīng)的真實(shí)Dom的前面，除了第三種命中后的移動(dòng)節(jié)點(diǎn)操作，是移動(dòng)到oldEndIndex所對(duì)應(yīng)真實(shí)節(jié)點(diǎn)之后

總結(jié)

由于diff算法對(duì)比的是虛擬Dom，而虛擬Dom是呈樹狀的，所以我們可以發(fā)現(xiàn)，diff算法中充滿了遞歸。總結(jié)起來，其實(shí)diff算法就是一個(gè) patch —> patchVnode —> updateChildren —> patchVnode —> updateChildren —> patchVnode這樣的一個(gè)循環(huán)遞歸的過程。

這里再提一嘴key，我們面試中經(jīng)常會(huì)被問到vue中key的作用。根據(jù)上面我們分析的，key的主要作用其實(shí)就是對(duì)比兩個(gè)虛擬節(jié)點(diǎn)時(shí)，判斷其是否為相同節(jié)點(diǎn)。加了key以后，我們可以更為明確的判斷兩個(gè)節(jié)點(diǎn)是否為同一個(gè)虛擬節(jié)點(diǎn)，是的話判斷子節(jié)點(diǎn)是否有變更（有變更更新真實(shí)Dom），不是的話繼續(xù)比。如果不加key的話，如果兩個(gè)不同節(jié)點(diǎn)的標(biāo)簽名恰好相同，那么就會(huì)被判定為同一個(gè)節(jié)點(diǎn)（key都為undefined），結(jié)果一對(duì)比這兩個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)發(fā)現(xiàn)不一樣，這樣會(huì)憑空增加很多對(duì)真實(shí)Dom的操作，從而導(dǎo)致頁面更頻繁得進(jìn)行重繪和回流。

所以我認(rèn)為合理利用key可以有效減少真實(shí)Dom的變動(dòng)，從而減少頁面重繪和回流的頻率，進(jìn)而提高頁面更新的效率。

總結(jié)

以上是生活随笔為你收集整理的十分详细的diff算法原理解析的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。