Diff算法有大概有簡(jiǎn)單Diff算法，雙端Diff算法和快速Diff算法三種，而快速Diff算法中又借鑒了簡(jiǎn)單Diff算法的思路，所以下面會(huì)介紹分析三種算法。
Vue2.0使用的是雙端Diff算法。Vue3.0使用的是快速Diff算法。
Diff算法的作用
Vue是提供了聲明式的方法方便開發(fā)人員編寫出響應(yīng)式的代碼，框架內(nèi)部封裝了指令式的查找修改DOM的過程，對(duì)于數(shù)據(jù)變化后更新視圖這一過程，判斷哪里需要修改，執(zhí)行修改更新的過程，就是Diff算法要處理的問題，主要目的是精確查到需要更新的虛擬DOM，優(yōu)化DOM更新消耗的性能。
Diff算法的簡(jiǎn)潔流程
- 找到key值匹配的oldVNode 和newVNode ，更新他們的內(nèi)容
- 判斷是否要移動(dòng)DOM，三種diff有不同的判斷方案
- 判斷是否有新增節(jié)點(diǎn)要掛載，或者有節(jié)點(diǎn)要被移除
1. 簡(jiǎn)單Diff 算法
簡(jiǎn)單Diff算法核心是與當(dāng)前節(jié)點(diǎn)的(舊)索引與最大索引值比較，如果小于，要移動(dòng)節(jié)點(diǎn)（簡(jiǎn)單來說就是原先在前面的節(jié)點(diǎn)，被移動(dòng)到后面）。
對(duì)于前后節(jié)點(diǎn)數(shù)量都一樣的情況，核心流程如下：
核心流程.png
特殊情況處理：
- 遍歷完oldVNodeChildren，沒有找到匹配的VNode, 說明當(dāng)前newVNode是新增的，需要掛載。
- 上面的更新步驟結(jié)束后，遍歷oldVNodeChildren，如果有節(jié)點(diǎn)在新的數(shù)組中找不到對(duì)應(yīng)的元素，說明該節(jié)點(diǎn)需要卸載。
2. 雙端Diff算法
雙端Diff算法會(huì)采用newStartIdx，newEndIdx, oldStartIdx, oldEndIdx四個(gè)指針，從首尾指針兩兩對(duì)比找可以復(fù)用節(jié)點(diǎn)，如果首尾都找不到，直接用數(shù)組的findIndex方法用新數(shù)組的頭元素去舊數(shù)組里找，進(jìn)行更新，移動(dòng)后，把oldVNode置為undefined.
2.雙端diff.png
function patchKeyedChildren (n1, n2, container) {
const oldChildren = n1.children;
const newChildren = n2.children;
// 定義四個(gè)索引值
let oldStartIdx = 0;
let oldEndIdx = oldChildren.length - 1;
let newStartIdx = 0;
let newEndIdx = newChildren.length - 1;
// 四個(gè)索引指向vnode節(jié)點(diǎn)
let oldStartVNode = oldChildren[oldStartIdx];
let oldEndVNode = oldChildren[oldEndIdx];
let newStartVNode = newChildren[newStartIdx];
let newEndVNode = newChildren[newEndIdx];
while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
// 如果舊數(shù)組的首尾節(jié)點(diǎn)被處理過了，直接跳到下一個(gè)位置
if (!oldStartVNode) {
oldStartVNode = oldChildren[++oldStartIdx]
} else if (!oldEndVNode) {
oldEndVNode = oldChildren[--oldEndIdx];
} else if (oldStartVNode.key == newStartVNode.key) {
// 第一步，oldStartVNode 和 newStartVNode比較（頭部節(jié)點(diǎn)比較）
patch(oldStartVNode, newStartVNode, container);
oldStartVNode = oldChildren[++oldStartIdx];
newStartVNode = newChildren[++newStartIdx];
} else if (oldEndVNode.key == newEndVNode.key) {
// 第二步,oldEndVNode 與newEndVNode比對(duì)（尾部節(jié)點(diǎn)比較）
// 節(jié)點(diǎn)在新的順序中依舊處于尾部，不需要移動(dòng)，但是依舊需要打補(bǔ)丁
patch(oldEndVNode, newEndVNode, container);
// 更新尾部的節(jié)點(diǎn)和指針
oldEndVNode = oldChildren[--oldEndIdx];
newEndVNode = newChildren[--newEndIdx];
} else if (oldStartVNode.key == newEndVNode.key) {
// 第三步，oldStartVNode與newEndVNode對(duì)比
patch(oldEndVNode, newEndVNode, container);
// oldStartVNode 插入到oldEndVNode后面(也就是他的下一個(gè)兄弟節(jié)點(diǎn)的前面)
insert(oldStartVNode.el, oldEndVNode.el.nextSibling, container);
// 更新索引到下一個(gè)位置
oldStartVNode = oldChildren[++oldStartIdx];
newEndVNode = newChildren[--newEndIdx];
} else if (oldEndVNode.key == newStartVNode.key) {
// 依然要調(diào)用patch函數(shù)進(jìn)行打補(bǔ)丁
patch(oldEndVNode, newStartVNode, container);
// 移動(dòng)DOM操作
//oldEndVNode.el 移動(dòng)到 oldStartVNode.el前面
insert(oldEndVNode.el, container, oldStartVNode.el);
// 移動(dòng)DOM完成后，更新索引值，并指向下一個(gè)位置
oldEndVNode = oldChildren[--oldEndIdx];
newStartVNode = newChildren[++newStartIdx];
} else {
// 四個(gè)首尾節(jié)點(diǎn)都沒有匹配上
// 拿新的一組子節(jié)點(diǎn)中的頭部節(jié)點(diǎn)去舊的一組節(jié)點(diǎn)重查找
const idxOnOld = oldChildren.findIndex(node => node.key == newStartVNode.key);
if (idxOnOld > 0) { // 說明非頭節(jié)點(diǎn)的元素變成了頭節(jié)點(diǎn)
const vnodeToMove = oldChildren[idxOnOld];
patch(vnodeToMove, newStartVNode, container);
insert(vnodeToMove.el, container, oldStartVNode.el);
// 由于位置idxInOld處的節(jié)點(diǎn)對(duì)應(yīng)真實(shí)的DOM已經(jīng)移動(dòng)到了別處，因此可以設(shè)置為undefined;
oldChildren[idxOnOld] = undefined;
// 更新newStartIdx到下一個(gè)位置
newStartVNode = newChildren[++newStartIdx];
} else { // 說明是新增的節(jié)點(diǎn)，當(dāng)前在新數(shù)組中是newStartIdx
patch(undefined, newStartVNode, container, oldStartVNode.el)
newStartVNode = newChildren[++newStartIdx];
}
}
}
// 循環(huán)結(jié)束后檢查索引值的情況
if (oldEndIdx < oldStartIdx && newStartIdx <= newEndIdx) {
// 說明有新的節(jié)點(diǎn)遺漏，需要掛載
for (let i = newStartIdx; i <= newEndIdx; i++) {
patch(null, newChildren[i], container, oldEndVNode.el);
}
} else if (newEndIdx < newStartIdx && newStartIdx <= newEndIdx) {
// 移除操作
for (let i = oldStartIdx; i <= oldEndIdx; i++) {
unmount(oldChildren[i]);
}
}
}
3. 快速Diff算法
快速diff算法增加了預(yù)處理。首先在首尾遍歷更新key值匹配上的節(jié)點(diǎn)，更新他們的內(nèi)容（即只更新，不需要移動(dòng)）。
預(yù)處理之后，判斷是否需要新增或者刪除節(jié)點(diǎn)。剩下的節(jié)點(diǎn)需要判斷是否需要移動(dòng)位置。這時(shí)候會(huì)利用這些節(jié)點(diǎn)在oldChlidren中的索引，求出最長(zhǎng)遞增子序列，索引（oldChildren中的）在最長(zhǎng)遞增子序列里的不需要移動(dòng)，否則就需要移動(dòng)。
快速diff.png
function patchKeyedChildren(n1, n2, container) {
const newChildren = n2.children;
const oldChildren = n1.children;
// 處理相同的前置節(jié)點(diǎn)
let j = 0;
let oldVNode = oldChildren[j];
let newVNode = newChildren[j];
while (oldVNode.key == newVNode.key) {
patch(oldVNode, newVNode, container);
j++;
oldVNode = oldChildren[j];
newVNode = newChildren[j];
}
// 更新相同的后置節(jié)點(diǎn)
let oldEnd = oldChildren[oldChildren.length] - 1;
let newEnd = newChildren[newChildren.length] - 1;
oldVNode = oldChildren[oldEnd];
newVNode = newChildren[newEnd];
while (oldVNode.key == newVNode.key) {
//調(diào)用patch函數(shù)進(jìn)行更新
patch(oldVNode, newVNode, container);
// 遞減oldEnd 和 nextEnd
oldEnd--;
newEnd--;
oldVNode = oldChildren[oldEnd];
newVNode = newChildren[newEnd];
}
// 新增節(jié)點(diǎn)的情況
// 預(yù)處理完畢，如果滿足以下條件，說明j到newEnd之間的節(jié)點(diǎn)應(yīng)該作為新節(jié)點(diǎn)插入
if (j > oldEnd && j <= newEnd) {
const anchorIndex = newEnd + 1;
const anchor =
anchorIndex < newChildren.length ? newChildren[anchorIndex].el : null;
while (j <= newEnd) {
patch(null, newChildren[j++], container, anchor);
}
} else if (j > newEnd && j <= oldEnd) {
// 刪除節(jié)點(diǎn)的情況oldEnd >= j
while (j <= oldEnd) {
unmount(oldChildren[j++]);
}
} else {
// 預(yù)處理之后還需要移動(dòng)中間的元素的情況
const count = newEnd - j + 1;
const source = new Array(count).fill(-1); // 用來存儲(chǔ)新的一組子節(jié)點(diǎn)在舊一組子節(jié)點(diǎn)中的位置索引，后面會(huì)用它來計(jì)算出一個(gè)最長(zhǎng)的遞增子序列，并用于輔助完成DOM移動(dòng)的操作
const oldStart = j;
const newStart = j;
// 時(shí)間復(fù)雜度太高,不能這么寫
// // 遍歷舊的一組子節(jié)點(diǎn)
// for (let i = oldStart; i <= oldEnd; i++){
// const oldVNode = oldChildren[i];
// // 遍歷新的一組節(jié)點(diǎn)
// for (let k = newStart; k <= newEnd; k++){
// const newVNode = newChildren[i];
// if (oldVNode.key == newVNode.key) {
// // 調(diào)用patch進(jìn)行更新
// patch(oldVNode, newVNode, container);
// // 最后填充source數(shù)組
// source[k - newStart] = i;
// }
// }
// }
// 新增兩個(gè)變量，moved 和 pos
let moved = false; // 節(jié)點(diǎn)是否需要移動(dòng)
let pos = 0; // 最大索引值
const keyIndex = {}; // key:VNode.key, value: 節(jié)點(diǎn)在newVNode中的索引
for (let i = newStart; i <= newEnd; i++) {
keyIndex[newChildren[i].key] = i;
}
let patched = 0; // 更新過的節(jié)點(diǎn)數(shù)量
for (let i = oldStart; i <= oldEnd; i++) {
oldVNode = oldChildren[i];
if (patched <= count) {
const k = keyIndex[oldVNode.key];
if (typeof k !== 'undefined') {
newVNode = newChildren[k];
patch(oldVNode, newVNode, container);
patched++;
// 填充source數(shù)組
source[k - newStart] = i;
if (k < pos) {
moved = true; // 有一個(gè)元素需要移動(dòng)就是需要移動(dòng)
} else {
pos = k;
}
} else {
// 舊節(jié)點(diǎn)不存在新數(shù)組中
unmount(oldVNode);
}
} else {
// 更新過的節(jié)點(diǎn)值大于需要更新的節(jié)點(diǎn)值，卸載多余的節(jié)點(diǎn)
unmount(oldVNode);
}
}
if (moved) {
// 計(jì)算最長(zhǎng)遞增子序列，子序列在更新前后順序沒有變化
const seq = getSequence(source);// 返回的是索引值
// s指向最長(zhǎng)遞增子序列的最后一個(gè)元素
let s = seq.length - 1;
let i = count - 1;
for (i; i >= 0; i--){
if (source[i] == -1) {// 在舊數(shù)組中不存在，需要掛載
const pos = i + newStart;
const newVNode = newChildren[pos];
const nextPos = pos + 1;
// 錨點(diǎn)
const anchor = nextPos < newChildren.length ? newChildren[nextPos].el : null;
patch(null, newVNode, container, anchor);
}
if (i != seg[s]) {
// 索引值不在最長(zhǎng)遞增子序列里，需要移動(dòng)
const pos = i + newStart;
const newVNode = newChildren[pos];
// 該節(jié)點(diǎn)的一個(gè)節(jié)點(diǎn)的位置索引
const nextPos = pos + 1;
//
const anchor = nextPos < newChildren.length ? newChildren[nextPos].el : null;
// 移動(dòng)節(jié)點(diǎn)是通過insert函數(shù)實(shí)現(xiàn)的
insert(newVNode, container, anchor);
} else {
s--;
}
}
}
}
}
