Diff算法有大概有簡單Diff算法，雙端Diff算法和快速Diff算法三種咨察，而快速Diff算法中又借鑒了簡單Diff算法的思路，所以下面會介紹分析三種算法。
Vue2.0使用的是雙端Diff算法巫糙。Vue3.0使用的是快速Diff算法。
Diff算法的作用
Vue是提供了聲明式的方法方便開發(fā)人員編寫出響應(yīng)式的代碼颊乘，框架內(nèi)部封裝了指令式的查找修改DOM的過程参淹，對于數(shù)據(jù)變化后更新視圖這一過程，判斷哪里需要修改疲牵，執(zhí)行修改更新的過程承二，就是Diff算法要處理的問題，主要目的是精確查到需要更新的虛擬DOM纲爸，優(yōu)化DOM更新消耗的性能亥鸠。
Diff算法的簡潔流程
- 找到key值匹配的oldVNode 和newVNode ，更新他們的內(nèi)容
- 判斷是否要移動DOM识啦，三種diff有不同的判斷方案
- 判斷是否有新增節(jié)點(diǎn)要掛載负蚊，或者有節(jié)點(diǎn)要被移除
1. 簡單Diff 算法
簡單Diff算法核心是與當(dāng)前節(jié)點(diǎn)的(舊)索引與最大索引值比較，如果小于颓哮，要移動節(jié)點(diǎn)（簡單來說就是原先在前面的節(jié)點(diǎn)家妆，被移動到后面）。
對于前后節(jié)點(diǎn)數(shù)量都一樣的情況冕茅，核心流程如下：
核心流程.png
特殊情況處理：
- 遍歷完oldVNodeChildren伤极，沒有找到匹配的VNode, 說明當(dāng)前newVNode是新增的，需要掛載姨伤。
- 上面的更新步驟結(jié)束后哨坪，遍歷oldVNodeChildren，如果有節(jié)點(diǎn)在新的數(shù)組中找不到對應(yīng)的元素乍楚，說明該節(jié)點(diǎn)需要卸載当编。
2. 雙端Diff算法
雙端Diff算法會采用newStartIdx，newEndIdx, oldStartIdx, oldEndIdx四個指針徒溪，從首尾指針兩兩對比找可以復(fù)用節(jié)點(diǎn)忿偷，如果首尾都找不到金顿，直接用數(shù)組的findIndex方法用新數(shù)組的頭元素去舊數(shù)組里找，進(jìn)行更新鲤桥，移動后揍拆，把oldVNode置為undefined.
2.雙端diff.png
function patchKeyedChildren (n1, n2, container) {
const oldChildren = n1.children;
const newChildren = n2.children;
// 定義四個索引值
let oldStartIdx = 0;
let oldEndIdx = oldChildren.length - 1;
let newStartIdx = 0;
let newEndIdx = newChildren.length - 1;
// 四個索引指向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)被處理過了，直接跳到下一個位置
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比對（尾部節(jié)點(diǎn)比較）
// 節(jié)點(diǎn)在新的順序中依舊處于尾部礁凡，不需要移動，但是依舊需要打補(bǔ)丁
patch(oldEndVNode, newEndVNode, container);
// 更新尾部的節(jié)點(diǎn)和指針
oldEndVNode = oldChildren[--oldEndIdx];
newEndVNode = newChildren[--newEndIdx];
} else if (oldStartVNode.key == newEndVNode.key) {
// 第三步慧妄，oldStartVNode與newEndVNode對比
patch(oldEndVNode, newEndVNode, container);
// oldStartVNode 插入到oldEndVNode后面(也就是他的下一個兄弟節(jié)點(diǎn)的前面)
insert(oldStartVNode.el, oldEndVNode.el.nextSibling, container);
// 更新索引到下一個位置
oldStartVNode = oldChildren[++oldStartIdx];
newEndVNode = newChildren[--newEndIdx];
} else if (oldEndVNode.key == newStartVNode.key) {
// 依然要調(diào)用patch函數(shù)進(jìn)行打補(bǔ)丁
patch(oldEndVNode, newStartVNode, container);
// 移動DOM操作
//oldEndVNode.el 移動到 oldStartVNode.el前面
insert(oldEndVNode.el, container, oldStartVNode.el);
// 移動DOM完成后顷牌，更新索引值，并指向下一個位置
oldEndVNode = oldChildren[--oldEndIdx];
newStartVNode = newChildren[++newStartIdx];
} else {
// 四個首尾節(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)對應(yīng)真實的DOM已經(jīng)移動到了別處塞淹，因此可以設(shè)置為undefined;
oldChildren[idxOnOld] = undefined;
// 更新newStartIdx到下一個位置
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)容（即只更新，不需要移動）套耕。
預(yù)處理之后谁帕，判斷是否需要新增或者刪除節(jié)點(diǎn)。剩下的節(jié)點(diǎn)需要判斷是否需要移動位置冯袍。這時候會利用這些節(jié)點(diǎn)在oldChlidren中的索引匈挖，求出最長遞增子序列，索引（oldChildren中的）在最長遞增子序列里的不需要移動康愤，否則就需要移動儡循。
快速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ù)處理之后還需要移動中間的元素的情況
const count = newEnd - j + 1;
const source = new Array(count).fill(-1); // 用來存儲新的一組子節(jié)點(diǎn)在舊一組子節(jié)點(diǎn)中的位置索引择膝，后面會用它來計算出一個最長的遞增子序列，并用于輔助完成DOM移動的操作
const oldStart = j;
const newStart = j;
// 時間復(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;
// }
// }
// }
// 新增兩個變量检激，moved 和 pos
let moved = false; // 節(jié)點(diǎn)是否需要移動
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; // 有一個元素需要移動就是需要移動
} else {
pos = k;
}
} else {
// 舊節(jié)點(diǎn)不存在新數(shù)組中
unmount(oldVNode);
}
} else {
// 更新過的節(jié)點(diǎn)值大于需要更新的節(jié)點(diǎn)值肴捉，卸載多余的節(jié)點(diǎn)
unmount(oldVNode);
}
}
if (moved) {
// 計算最長遞增子序列，子序列在更新前后順序沒有變化
const seq = getSequence(source);// 返回的是索引值
// s指向最長遞增子序列的最后一個元素
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]) {
// 索引值不在最長遞增子序列里每庆，需要移動
const pos = i + newStart;
const newVNode = newChildren[pos];
// 該節(jié)點(diǎn)的一個節(jié)點(diǎn)的位置索引
const nextPos = pos + 1;
//
const anchor = nextPos < newChildren.length ? newChildren[nextPos].el : null;
// 移動節(jié)點(diǎn)是通過insert函數(shù)實現(xiàn)的
insert(newVNode, container, anchor);
} else {
s--;
}
}
}
}
}
