diff 算法
约 5346 字大约 18 分钟
2026-03-29
在子节点更新中,如果新旧子节点都是数组,最简单的做法是先把旧子节点全部卸载,再把新子节点全部挂载
oldVNode.children.forEach((child) => unmount(child));
newVNode.children.forEach((child) => patch(null, child, container));这当然能得到正确结果,但代价很高。因为很多时候新旧两组子节点只是内容变化、顺序变化,或者局部新增删除,并不需要把所有真实 DOM 都销毁再重建。如果节点数量较少,性能差异可能不明显,但如果节点数量较多,这种 "全量替换" 的方式就会导致明显的性能问题。Diff 算法就是为了解决这个问题而设计的
重要
Diff 算法要解决的问题就是:在保证最终 DOM 顺序正确的前提下,尽可能复用旧节点对应的真实 DOM,并减少移动、挂载和卸载操作
Key 的作用
如果两个节点的 type 不同,一般可以直接认为不是同一个节点。但如果一组子节点都是同一种标签,比如都是 p,仅靠 type 就无法判断它们之间的对应关系
const oldChildren = [
{ type: 'p', children: '1' },
{ type: 'p', children: '2' },
{ type: 'p', children: '3' },
];
const newChildren = [
{ type: 'p', children: '3' },
{ type: 'p', children: '1' },
{ type: 'p', children: '2' },
];上面这组节点里,所有节点的 type 都是 p。如果没有额外标识,渲染器无法知道新的第一个 p 到底对应旧的哪一个 p。所以需要引入 key
const oldChildren = [
{ type: 'p', key: 1, children: '1' },
{ type: 'p', key: 2, children: '2' },
{ type: 'p', key: 3, children: '3' },
];
const newChildren = [
{ type: 'p', key: 3, children: '3' },
{ type: 'p', key: 1, children: '1' },
{ type: 'p', key: 2, children: '2' },
];有了 key 之后,渲染器就可以判断:
- 新节点
key: 3对应旧节点key: 3 - 新节点
key: 1对应旧节点key: 1 - 新节点
key: 2对应旧节点key: 2
这时更新就不再是 "按位置替换",而是可以进入 "按身份复用"。这也是 keyed diff 的基础
Diff
简单 Diff
简单 Diff 将更动作拆成三个基本动作:
- 找到可复用节点并调用
patch - 新节点在旧节点中不存在时挂载
- 旧节点在新节点中不存在时卸载
先处理相同位置的节点
如果新旧两组子节点长度相同,而且顺序也没有变化,那么可以直接按索引逐个
patch思路
先取新旧两组子节点的公共长度
commonLength,公共部分逐个更新。新列表更长时,多出来的部分挂载;旧列表更长时,多出来的部分卸载代码
function patchKeyedChildren(oldChildren, newChildren, container) { const oldLen = oldChildren.length; const newLen = newChildren.length; const commonLength = Math.min(oldLen, newLen); for (let i = 0; i < commonLength; i++) { patch(oldChildren[i], newChildren[i], container); } if (newLen > oldLen) { for (let i = commonLength; i < newLen; i++) { patch(null, newChildren[i], container); } } else if (oldLen > newLen) { for (let i = commonLength; i < oldLen; i++) { unmount(oldChildren[i]); } } }通过
key找到可复用节点只按索引更新有一个问题:一旦顺序发生变化,就会把本来可以复用的节点当成不同节点处理
思路
遍历新子节点,再到旧子节点中寻找相同
key的节点。只要找到了,就说明这两个虚拟节点对应同一个真实 DOM,可以调用patch更新代码
function patchKeyedChildren(oldChildren, newChildren, container) { for (let i = 0; i < newChildren.length; i++) { const newVNode = newChildren[i]; for (let j = 0; j < oldChildren.length; j++) { const oldVNode = oldChildren[j]; if (newVNode.key === oldVNode.key) { patch(oldVNode, newVNode, container); break; } } } }判断节点是否需要移动
找到可复用节点之后,还要判断它对应的真实 DOM 是否需要移动
这里有一个关键点:新子节点的顺序,就是最终真实 DOM 应该呈现的顺序。遍历新子节点时,如果在旧子节点中找到的索引不是递增的,就说明当前节点需要移动
思路
用
lastIndex记录遍历过程中遇到的最大旧索引。如果当前找到的旧索引j小于lastIndex,说明这个节点在旧列表中的位置靠前,但在新列表中被放到了后面,此时需要移动代码
function patchKeyedChildren(oldChildren, newChildren, container) { let lastIndex = 0; for (let i = 0; i < newChildren.length; i++) { const newVNode = newChildren[i]; for (let j = 0; j < oldChildren.length; j++) { const oldVNode = oldChildren[j]; if (newVNode.key === oldVNode.key) { patch(oldVNode, newVNode, container); if (j < lastIndex) { const prevVNode = newChildren[i - 1]; if (prevVNode) { const anchor = prevVNode.el.nextSibling; insert(newVNode.el, container, anchor); } } else { lastIndex = j; } break; } } } }处理新增节点
如果新节点在旧节点中找不到相同
key,说明它是新增节点,需要挂载思路
新节点的插入位置由它前一个新节点决定。如果前一个新节点存在,就把当前节点插入到前一个节点真实 DOM 的下一个兄弟节点前面;如果前一个新节点不存在,说明它是第一个节点,锚点就是容器的第一个子节点
代码
if (!matched) { const prevVNode = newChildren[i - 1]; let anchor = null; if (prevVNode) { anchor = prevVNode.el.nextSibling; } else { anchor = container.firstChild; } patch(null, newVNode, container, anchor); }处理需要卸载的旧节点
遍历新节点只能发现哪些新节点需要更新或挂载,但无法发现哪些旧节点已经不存在
思路
更新完成后,再遍历旧子节点。只要某个旧节点的
key在新子节点中不存在,就说明它应该被卸载代码
for (let i = 0; i < oldChildren.length; i++) { const oldVNode = oldChildren[i]; const has = newChildren.find((newVNode) => newVNode.key === oldVNode.key); if (!has) { unmount(oldVNode); } }简单 Diff 的问题
简单 Diff 可以复用 DOM,也可以处理新增、删除和移动。但它判断移动的方式比较粗糙,容易产生不必要的移动
例如旧序列是
[1, 2, 3],新序列是[3, 1, 2]。简单 Diff 会认为1和2都需要移动,但更优的做法其实是只把3移动到最前面这就是双端 Diff 要解决的问题
双端 Diff
双端 Diff 的核心是:同时从新旧两组子节点的两端开始比较
这样做的原因是,真实场景中节点移动经常发生在头尾附近。如果只从左到右扫描,很容易错过更少移动次数的方案;而双端比较可以更快发现 "旧头到新尾"、"旧尾到新头" 这类移动
准备四个端点
思路
分别用四个索引指向旧列表头部、旧列表尾部、新列表头部、新列表尾部。每轮循环只处理这四个端点中的匹配情况
代码
let oldStartIdx = 0; let oldEndIdx = oldChildren.length - 1; let newStartIdx = 0; let newEndIdx = newChildren.length - 1; let oldStartVNode = oldChildren[oldStartIdx]; let oldEndVNode = oldChildren[oldEndIdx]; let newStartVNode = newChildren[newStartIdx]; let newEndVNode = newChildren[newEndIdx];旧头和新头比较
如果旧头和新头的
key相同,说明这个节点本来就在头部,不需要移动,只需要更新,然后两个头部索引同时向后移动if (oldStartVNode.key === newStartVNode.key) { patch(oldStartVNode, newStartVNode, container); oldStartVNode = oldChildren[++oldStartIdx]; newStartVNode = newChildren[++newStartIdx]; }旧尾和新尾比较
如果旧尾和新尾的
key相同,说明这个节点本来就在尾部,也不需要移动,只需要更新,然后两个尾部索引同时向前移动else if (oldEndVNode.key === newEndVNode.key) { patch(oldEndVNode, newEndVNode, container); oldEndVNode = oldChildren[--oldEndIdx]; newEndVNode = newChildren[--newEndIdx]; }旧头和新尾比较
如果旧头和新尾相同,说明旧头节点在新列表中移动到了尾部。更新后,需要把旧头对应的真实 DOM 移动到当前旧尾的后面
else if (oldStartVNode.key === newEndVNode.key) { patch(oldStartVNode, newEndVNode, container); insert(oldStartVNode.el, container, oldEndVNode.el.nextSibling); oldStartVNode = oldChildren[++oldStartIdx]; newEndVNode = newChildren[--newEndIdx]; }旧尾和新头比较
如果旧尾和新头相同,说明旧尾节点在新列表中移动到了头部。更新后,需要把旧尾对应的真实 DOM 移动到当前旧头的前面
else if (oldEndVNode.key === newStartVNode.key) { patch(oldEndVNode, newStartVNode, container); insert(oldEndVNode.el, container, oldStartVNode.el); oldEndVNode = oldChildren[--oldEndIdx]; newStartVNode = newChildren[++newStartIdx]; }四个端点都没有命中
如果四种端点比较都没有命中,就退回到旧列表中查找新头节点
思路
如果找到了,就说明该旧节点可以复用,先
patch,再把它移动到旧头前面,并把旧数组当前位置置为undefined,避免后续重复处理。如果找不到,说明新头是新增节点,直接挂载到旧头前面代码
else { const indexInOld = oldChildren.findIndex( (node) => node && node.key === newStartVNode.key, ); if (indexInOld > 0) { const vnodeToMove = oldChildren[indexInOld]; patch(vnodeToMove, newStartVNode, container); insert(vnodeToMove.el, container, oldStartVNode.el); oldChildren[indexInOld] = undefined; } else { patch(null, newStartVNode, container, oldStartVNode.el); } newStartVNode = newChildren[++newStartIdx]; }循环结束后的补充处理
双端循环结束后,还可能剩余新节点或旧节点
思路
如果旧节点先处理完,新列表中剩下的节点就是新增节点;如果新节点先处理完,旧列表中剩下的节点就是需要卸载的节点
代码
if (oldEndIdx < oldStartIdx && newStartIdx <= newEndIdx) { for (let i = newStartIdx; i <= newEndIdx; i++) { patch(null, newChildren[i], container, oldStartVNode?.el ?? null); } } else if (newEndIdx < newStartIdx && oldStartIdx <= oldEndIdx) { for (let i = oldStartIdx; i <= oldEndIdx; i++) { if (oldChildren[i]) { unmount(oldChildren[i]); } } }双端 Diff 的问题
双端 Diff 相比简单 Diff,已经能减少不少不必要的移动。但它仍然有一个明显问题:端点比较失败后,仍然需要在旧列表里查找节点
更重要的是,它不能很好地识别中间区域中 "相对顺序没有变化" 的节点。比如某些节点虽然整体位置发生了偏移,但它们之间的相对顺序仍然稳定,这些节点其实不需要移动
快速 Diff 会通过预处理和最长递增子序列 来处理这个问题
快速 Diff
Vue 3 中的 keyed children 更新,核心思想更接近快速 Diff:
- 先从头部处理相同的前置节点
- 再从尾部处理相同的后置节点
- 如果剩余部分只是新增,直接挂载
- 如果剩余部分只是删除,直接卸载
- 如果剩余部分既有新增、删除,也有移动,就进入复杂区间处理
- 复杂区间中,用索引表定位可复用节点,用最长递增子序列减少 DOM 移动
预处理相同的前置节点
前置节点指新旧两组子节点从头部开始连续相同的部分。这部分节点在最终顺序中位置不变,只需要更新,不需要移动
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]; }预处理相同的后置节点
后置节点指新旧两组子节点从尾部开始连续相同的部分。这部分同样只需要更新,不需要移动
let oldEnd = oldChildren.length - 1; let newEnd = newChildren.length - 1; oldVNode = oldChildren[oldEnd]; newVNode = newChildren[newEnd]; while (oldVNode.key === newVNode.key) { patch(oldVNode, newVNode, container); oldEnd--; newEnd--; oldVNode = oldChildren[oldEnd]; newVNode = newChildren[newEnd]; }简单情况:只需要新增
如果旧列表已经处理完,但新列表中还有未处理节点,说明剩下的都是新增节点
思路
新增节点要插入到正确位置。锚点可以通过
newEnd + 1找到,如果后面还有节点,就插到它前面;如果后面没有节点,就插入到末尾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) { while (j <= oldEnd) { unmount(oldChildren[j++]); } }复杂区间:建立新节点索引表
如果前面两个简单分支都不满足,说明剩余区间中同时存在复用、移动、新增或卸载
思路
先把新子节点剩余区间的
key -> index做成索引表。这样遍历旧子节点时,就可以用key快速判断它是否还存在于新列表中代码
const oldStart = j; const newStart = j; const count = newEnd - newStart + 1; const source = new Array(count).fill(-1); const keyIndex = new Map(); for (let i = newStart; i <= newEnd; i++) { keyIndex.set(newChildren[i].key, i); }复杂区间:填充
sourcesource数组用来记录新子节点剩余区间中的每个节点,在旧子节点中的位置for (let i = oldStart; i <= oldEnd; i++) { const oldVNode = oldChildren[i]; const k = keyIndex.get(oldVNode.key); if (k !== undefined) { const newVNode = newChildren[k]; patch(oldVNode, newVNode, container); source[k - newStart] = i; } else { unmount(oldVNode); } }如何理解
source如果
source[i]是-1,说明新列表中的这个节点在旧列表中不存在,需要挂载如果
source[i]不是-1,它的值就是该节点在旧列表中的位置。这个位置序列可以用来判断哪些节点需要移动判断是否需要移动
遍历旧节点并填充
source时,可以顺手判断新索引是否递增思路
用
pos记录遍历过程中遇到的最大新索引。如果后续遇到的k小于pos,说明顺序发生了倒退,需要移动let moved = false; let pos = 0; if (k < pos) { moved = true; } else { pos = k; }使用最长递增子序列减少移动
最长递增子序列(Longest Increasing Subsequence,LIS),它解决的问题是:从一个数组里,找出一组保持原有先后顺序、并且数值递增的最长序列
什么是子序列
子序列不是子数组。子数组必须连续,子序列不要求连续,但顺序不能乱
例如:
原数组: [2, 1, 5, 3, 6, 4, 8, 9, 7] 子序列: [2, 5, 6, 8] 或 [1, 3, 4, 9] 等等它们不一定连续,但在原数组里的相对顺序没有变
什么是递增
递增就是后一个数比前一个数大
例如:
[1, 3, 4, 8, 9] 是递增的 [1, 5, 3, 6] 不是递增的,因为 3 < 5什么是最长
在所有递增子序列里,长度最长的那个,就是最长递增子序列
例如:
[2, 1, 5, 3, 6, 4, 8, 9, 7] 它的最长递增子序列可以是: [1, 3, 4, 8, 9] [2, 3, 4, 8, 9]Diff 当中使用最长递增子序列是用于判断哪些节点可以不移动
旧节点顺序: A B C D 新节点顺序: B C A D先把节点映射成它们在旧节点中的位置
新节点:B C A D 旧索引: 1 2 0 3所以得到数组:
[1, 2, 0, 3]找这个数组的最长递增子序列是[1, 2, 3],对应的节点是B C D,它们在新旧列表中的相对顺序没有变,可以保持不动;而A不在最长递增子序列里,说明它需要移动思路
从后往前遍历新子节点剩余区间。如果当前位置是
-1,说明是新增节点,挂载;如果当前位置不在最长递增子序列里,说明需要移动;如果在最长递增子序列里,说明可以保持原位代码
if (moved) { const seq = getSequence(source); let s = seq.length - 1; for (let i = count - 1; i >= 0; i--) { const pos = i + newStart; const newVNode = newChildren[pos]; const nextPos = pos + 1; const anchor = nextPos < newChildren.length ? newChildren[nextPos].el : null; if (source[i] === -1) { patch(null, newVNode, container, anchor); } else if (i !== seq[s]) { insert(newVNode.el, container, anchor); } else { s--; } } }
本质说明
Diff 算法就在说一件事:当一组子节点从旧状态变为新状态时,怎么用最少的 DOM 操作,把页面更新成新状态
比如旧的是:
A B C新的变成
C A B最笨的做法就是删掉 A B C,然后再重新创建 C A B 这可定可以实现,但代价很大。Diff 想做的是:发现了 A B C 都还在,只是顺序变了,所以根本不需要删掉重建,只需只移动 DOM
重要
所以最核心的问题只有三个:
- 哪些节点可以复用
- 哪些节点是新增的
- 哪些节点需要删除或移动
这个就是 key 的作用,没有 key 时,Vue 只能猜:旧的第 1 个节点对应新的第 1 个节点。有了 key Vue 就可以确定旧的 key: 3 对应新的 key: 3。所以 Diff 本质上就不是在比较 DOM,而是比较两组虚拟节点的身份和顺序
简单 Diff 说的是:先遍历新节点,然后去旧的节点里找有没有相同的 key,如果找到了就复用节点 patch 一下;如果没找到就说明是新节点,需要挂载;最后在反过来检查旧节点,如果旧节点的 key 在新节点里找不到,说明它被删除了,需要卸载。这种 Diff 的问题是:它没有利用新旧两组节点的顺序信息,导致很多不必要的移动
然后就是双端 Diff,在 Vue2 中主要使用的双端 Diff。双端 Diff 说的是:先从两端开始比较,它每次只比较四种情况
新头 vs 旧头
新尾 vs 旧尾
新头 vs 旧尾
新尾 vs 旧头因为很多移动都是发生在头尾附近的,比如
旧: A B C
新: C A B那么简单 Diff 可能会移动 A 和 B,而双端 Diff 就能发现 C 在旧列表的尾部,直接把 C 移到头部就好了。但双端 Diff 的问题是:如果四种情况都没有命中,它就只能退回到旧列表里查找新头节点,这时就没什么优化了
最后就是快速 Diff,在 Vue3 中使用的是双端 Diff。快速 Diff 说的是:先预处理两端相同的节点,剩下的就是中间区间了
旧: A B C D E
新: A B X D E这个时候头和尾都没有变化,A B 是相同前缀,D E 是相同后缀,真正需要处理的只有中间,所以快速 Diff 的第一步就是跳过相同的头,在跳过相同的尾,只处理不同的部分,如果中间只是新增,则挂载;只是删除,则卸载;如果既有新增、删除、移动就进入复杂处理。这个时候就可以通过索引表快速定位可复用节点,并用最长递增子序列来减少移动次数
先把新子节点剩余区间的 key -> index 做成 Map 索引表。这样遍历旧子节点时,就可以用 key 快速判断它是否还存在于新列表中
现阶段完整代码
src
renderer.ts
sequence.ts
import { getSequence } from './sequence';
function createRenderer(options) {
const {
insert,
setElementText,
} = options;
function render(vnode, container) {
if (vnode) {
patch(container._vnode, vnode, container);
} else if (container._vnode) {
unmount(container._vnode);
}
container._vnode = vnode;
}
function patch(oldVNode, newVNode, container, anchor = null) {
if (oldVNode && oldVNode.type !== newVNode.type) {
unmount(oldVNode);
oldVNode = null;
}
if (!oldVNode) {
mountElement(newVNode, container, anchor);
} else {
patchElement(oldVNode, newVNode);
}
}
function patchElement(oldVNode, newVNode) {
const el = newVNode.el = oldVNode.el;
patchProps(oldVNode, newVNode, el);
patchChildren(oldVNode, newVNode, el);
}
function patchChildren(oldVNode, newVNode, container) {
const oldChildren = oldVNode.children;
const newChildren = newVNode.children;
if (typeof newChildren === 'string') {
if (Array.isArray(oldChildren)) {
oldChildren.forEach((child) => unmount(child));
}
setElementText(container, newChildren);
} else if (Array.isArray(newChildren)) {
if (Array.isArray(oldChildren)) {
patchKeyedChildren(oldChildren, newChildren, container);
} else {
setElementText(container, '');
newChildren.forEach((child) => patch(null, child, container));
}
} else {
if (Array.isArray(oldChildren)) {
oldChildren.forEach((child) => unmount(child));
} else if (typeof oldChildren === 'string') {
setElementText(container, '');
}
}
}
function patchKeyedChildren(oldChildren, newChildren, container) {
let j = 0;
let oldVNode = oldChildren[j];
let newVNode = newChildren[j];
while (
oldVNode &&
newVNode &&
oldVNode.key === newVNode.key
) {
patch(oldVNode, newVNode, container);
j++;
oldVNode = oldChildren[j];
newVNode = newChildren[j];
}
let oldEnd = oldChildren.length - 1;
let newEnd = newChildren.length - 1;
oldVNode = oldChildren[oldEnd];
newVNode = newChildren[newEnd];
while (
oldVNode &&
newVNode &&
oldVNode.key === newVNode.key
) {
patch(oldVNode, newVNode, container);
oldEnd--;
newEnd--;
oldVNode = oldChildren[oldEnd];
newVNode = newChildren[newEnd];
}
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) {
while (j <= oldEnd) {
unmount(oldChildren[j++]);
}
} else {
const oldStart = j;
const newStart = j;
const count = newEnd - newStart + 1;
const source = new Array(count).fill(-1);
const keyIndex = new Map();
let moved = false;
let pos = 0;
let patched = 0;
for (let i = newStart; i <= newEnd; i++) {
keyIndex.set(newChildren[i].key, i);
}
for (let i = oldStart; i <= oldEnd; i++) {
const oldVNode = oldChildren[i];
if (patched >= count) {
unmount(oldVNode);
continue;
}
const k = keyIndex.get(oldVNode.key);
if (k !== undefined) {
const newVNode = newChildren[k];
patch(oldVNode, newVNode, container);
patched++;
source[k - newStart] = i;
if (k < pos) {
moved = true;
} else {
pos = k;
}
} else {
unmount(oldVNode);
}
}
const seq = moved ? getSequence(source) : [];
let s = seq.length - 1;
for (let i = count - 1; i >= 0; i--) {
const pos = i + newStart;
const newVNode = newChildren[pos];
const nextPos = pos + 1;
const anchor = nextPos < newChildren.length
? newChildren[nextPos].el
: null;
if (source[i] === -1) {
patch(null, newVNode, container, anchor);
} else if (moved) {
if (i !== seq[s]) {
insert(newVNode.el, container, anchor);
} else {
s--;
}
}
}
}
}
function mountElement(vnode, container, anchor = null) {
// 挂载元素逻辑在前文已经实现
}
function patchProps(oldVNode, newVNode, el) {
// 更新 props 逻辑在前文已经实现
}
function unmount(vnode) {
const parent = vnode.el.parentNode;
if (parent) {
parent.removeChild(vnode.el);
}
}
return {
patch,
render,
};
}export function getSequence(source: number[]): number[] {
const length = source.length;
const dp = new Array(length).fill(1);
const prev = new Array(length).fill(-1);
let maxIndex = -1;
for (let i = 0; i < length; i++) {
if (source[i] === -1) {
dp[i] = 0;
continue;
}
for (let j = 0; j < i; j++) {
if (
source[j] !== -1 &&
source[j] < source[i] &&
dp[j] + 1 > dp[i]
) {
dp[i] = dp[j] + 1;
prev[i] = j;
}
}
if (maxIndex === -1 || dp[i] > dp[maxIndex]) {
maxIndex = i;
}
}
const result: number[] = [];
let current = maxIndex;
while (current !== -1) {
result.unshift(current);
current = prev[current];
}
return result;
}