渲染篇(二)：解密Diff算法：如何用“最少的操作”更新UI
引子：从“推倒重来”到“精打细算”
在上一章《从零实现一个“微型React”》中，我们成功搭建了Virtual DOM体系的骨架。我们用createElement创建VNode（UI蓝图），用render函数将VNode渲染成真实DOM。但是，我们留下了一个尾巴：我们的render函数是“毁灭式”的，每次更新都清空所有内容然后重建。
function render(vnode, container) {
// 我们当前的实现方式
container.innerHTML = '';
container.appendChild(createDom(vnode));
}
这种“推倒重来”的策略，虽然简单，却完全没有发挥出Virtual DOM的真正威力。它依然在进行大规模的DOM操作，性能问题并未解决。
真正的目标，应该是“精打细算”地更新。当状态改变，我们生成一个新的VNode树时，我们要做的是：
- 将新的VNode树与旧的VNode树进行比较。
- 找出两棵树之间的最小差异。
- 生成一个**“补丁列表”（Patches）**，这个列表精确地描述了需要对真实DOM进行的最小化操作（比如，“给这个
<div>换个class”、“在那个<ul>里新增一个<li>”、“删除这个<p>”）。 - 将这些补丁一次性地应用到真实DOM上。
这个找出最小差异并生成补丁的过程，就是大名鼎鼎的Diff算法。今天，我们将亲手解密并实现它。这可能是本系列技术上最硬核的一章，但征服它，你将洞悉所有现代前端框架的渲染核心。
第一幕：Diff算法的“不可能”与“可能”
从理论上说，要找出两棵任意树之间的最小差异（即最小“树编辑距离”），这是一个复杂度极高的问题，时间复杂度高达 O(n³)，其中n是树中节点的数量。对于前端动辄成百上千个节点的DOM树来说，这个计算量是无法接受的。
幸运的是，前端领域的先驱们，特别是React团队，发现我们可以基于Web UI的几个特点，做出一些大胆但合理的假设，从而将算法的复杂度优化到 O(n) 级别。
Diff策略的三大核心假设
只在同层级进行比较，不跨层级移动节点。
- 假设：如果一个组件在DOM树中的层级发生了变化，比如从
<div>的子节点变成了<body>的直接子节点，我们不认为它是“移动”了，而是将其视为两个完全不同的节点，直接删除旧的，创建新的。 - 理由：在实际Web开发中，跨层级的DOM节点移动非常罕见。这个假设极大地简化了比对过程，我们只需要对树进行一次深度优先遍历，对每个层级的节点进行比较即可。
- 假设：如果一个组件在DOM树中的层级发生了变化，比如从
不同类型的元素会生成不同的树结构。
- 假设：如果一个元素的类型（
type）从div变成了p，或者从ComponentA变成了ComponentB，我们不尝试去比对它们内部的结构，而是直接认为这是一个“替换”操作：销毁旧的，创建新的。 - 理由：不同类型的元素，其渲染出的内容和结构通常是天差地别的，尝试复用它们的意义不大，反而会增加算法的复杂性。
- 假设：如果一个元素的类型（
可以通过
key属性来识别一组子元素中的相同个体。- 假设：在一组子元素（比如
<ul>下的多个<li>）中，我们可以通过给每个<li>一个唯一的、稳定的key属性，来帮助Diff算法在多次渲染之间识别出同一个节点。 - 理由：这是列表渲染性能优化的关键。如果没有
key，当你在列表开头插入一个元素时，算法可能会认为所有后续的<li>都发生了变化。而有了key，它能精确地知道，只是新增了一个节点，其他的节点只是“向后移动”了而已，甚至DOM节点本身可以完全复用。
- 假设：在一组子元素（比如
这三个假设，是我们将Diff算法从“不可能”变为“可能”的基石。接下来，我们将基于这些假设，一步步构建我们的diff函数。
第二幕：从零实现diff与patch
我们的目标是创建两个核心函数：
diff(oldVNode, newVNode): 接收新旧两个VNode，返回一个包含所有差异的patches对象。patch(dom, patches): 接收一个真实DOM节点和patches对象，将差异应用到该DOM节点上。
步骤一：定义“补丁”的类型
首先，我们需要定义“补丁”长什么样。一个补丁需要描述“在哪里”进行“什么样的”操作。我们可以定义几种补丁类型：
// patchTypes.js
const PatchType = {
REPLACE: 'REPLACE', // 替换整个节点
UPDATE: 'UPDATE', // 更新节点的属性或文本内容
REORDER: 'REORDER', // 对子节点进行重排序（移动、删除、新增）
};
module.exports = PatchType;
步骤二：diff函数的主体结构
diff函数将是整个过程的核心，它是一个递归函数。我们还需要一个全局变量patches来收集所有节点的补丁，以及一个walk函数来启动整个Diff过程。
diff.js
// CSDN @ 你的用户名
// 系列: 前端内功修炼：从零构建一个“看不见”的应用
//
// 文件: /src/v4/diff.js
// 描述: 实现核心的Diff算法。
const PatchType = require('./patchTypes');
let patches;
let currentPatch;
function diff(oldVNode, newVNode) {
patches = {}; // 初始化补丁对象
walk(oldVNode, newVNode, 0); // 启动递归遍历，初始索引为0
return patches;
}
/**
* 递归遍历新旧VNode树，找出差异并记录到patches中。
* @param {object} oldNode - 旧的VNode。
* @param {object} newNode - 新的VNode。
* @param {number} index - 当前节点在DOM树中的“一维”索引。
*/
function walk(oldNode, newNode, index) {
currentPatch = []; // 每个节点都可能有自己的补丁数组
// 场景1：新节点不存在，直接认为是删除
if (!newNode) {
// 在reorder类型的补丁中处理
}
// 场景2：都是文本节点，但内容不同
else if (oldNode.type === 'TEXT_ELEMENT' && newNode.type === 'TEXT_ELEMENT') {
if (oldNode.props.nodeValue !== newNode.props.nodeValue) {
currentPatch.push({ type: PatchType.UPDATE, payload: { text: newNode.props.nodeValue } });
}
}
// 场景3：节点类型相同
else if (oldNode.type === newNode.type) {
// 比较props的差异
const propsPatches = diffProps(oldNode.props, newNode.props);
if (Object.keys(propsPatches).length > 0) {
currentPatch.push({ type: PatchType.UPDATE, payload: { props: propsPatches } });
}
// 比较子节点
diffChildren(oldNode.children, newNode.children, index);
}
// 场景4：节点类型不同，直接替换
else {
currentPatch.push({ type: PatchType.REPLACE, payload: { newNode } });
}
// 如果当前节点有补丁，就记录下来
if (currentPatch.length > 0) {
patches[index] = currentPatch;
}
}
// 导出diff函数
module.exports = { diff };
这个walk函数勾勒出了Diff算法的主体逻辑。它首先处理几种最基本的场景：节点被删除、文本节点更新、节点被替换。最复杂的部分在于diffProps和diffChildren。
步骤三：diffProps - 比较属性差异
比较属性相对简单，我们只需遍历新旧props对象，找出增加、修改和删除的属性即可。
diffProps.js (在 diff.js 文件内)
// ... diff.js 上下文 ...
function diffProps(oldProps, newProps) {
const propsPatches = {};
// 遍历新props，找出新增和修改的
for (const key in newProps) {
if (oldProps[key] !== newProps[key]) {
propsPatches[key] = newProps[key]; // 新增或修改
}
}
// 遍历旧props，找出被删除的
for (const key in oldProps) {
if (!(key in newProps)) {
propsPatches[key] = null; // 值为null表示删除
}
}
return propsPatches;
}
步骤四：diffChildren - 列表比对的精髓
这是Diff算法中最核心、最复杂的部分。我们将采用一种基于key的策略来高效地进行比对。
- 将旧的子节点列表转换成一个以
key为键的Map，这样可以快速查找。 - 遍历新的子节点列表，在旧的Map中查找是否存在相同
key的节点。 - 根据查找结果，确定是移动、新增还是删除。
diffChildren.js (在 diff.js 文件内)
// ... diff.js 上下文 ...
// 全局变量，用于追踪子节点的遍历
let globalIndex;
function diffChildren(oldChildren, newChildren, parentIndex) {
globalIndex = parentIndex; // 当前父节点的索引
// 使用key进行列表比对
const keyedPatches = diffKeyedChildren(oldChildren, newChildren);
// 将keyed比对的结果应用到patches对象
if (keyedPatches.length > 0) {
currentPatch.push({ type: PatchType.REORDER, payload: { moves: keyedPatches } });
}
}
function diffKeyedChildren(oldChildren, newChildren) {
const moves = []; // 存储移动/删除/新增操作
const oldKeyedMap = {};
const free = []; // 存储旧列表中没有key的节点索引
// 1. 将旧列表转换为keyed map和free list
oldChildren.forEach((child, index) => {
const key = child.props.key;
if (key) {
oldKeyedMap[key] = { node: child, index };
} else {
free.push(index);
}
});
let lastPlacedIndex = 0; // 用于判断是否需要移动
let freeIndex = 0;
// 2. 遍历新列表
newChildren.forEach((child, index) => {
const key = child.props.key;
if (key) {
const oldMatch = oldKeyedMap[key];
if (oldMatch) {
// 在旧列表中找到了匹配的key
const oldNode = oldMatch.node;
const oldIndex = oldMatch.index;
// 递归diff子节点
walk(oldNode, child, globalIndex + 1 + oldIndex);
// 判断是否需要移动
if (oldIndex < lastPlacedIndex) {
moves.push({ type: 'MOVE', from: oldIndex, to: index });
}
lastPlacedIndex = Math.max(oldIndex, lastPlacedIndex);
delete oldKeyedMap[key]; // 标记为已处理
} else {
// 在旧列表中没找到，是新增节点
moves.push({ type: 'INSERT', node: child, to: index });
}
} else {
// 新节点没有key，尝试从free列表中找一个匹配
if (freeIndex < free.length) {
const oldIndex = free[freeIndex];
const oldNode = oldChildren[oldIndex];
// 递归diff子节点
walk(oldNode, child, globalIndex + 1 + oldIndex);
freeIndex++;
} else {
// free列表也用完了，是新增节点
moves.push({ type: 'INSERT', node: child, to: index });
}
}
});
// 3. 处理删除
// 旧keyed map里剩下的都是被删除的
Object.keys(oldKeyedMap).forEach(key => {
moves.push({ type: 'REMOVE', from: oldKeyedMap[key].index });
});
// free列表里剩下的也是被删除的
for (let i = freeIndex; i < free.length; i++) {
moves.push({ type: 'REMOVE', from: free[i] });
}
return moves;
}
// 注意：walk函数需要做一点小修改，以正确地增加globalIndex
function walk(oldNode, newNode, index) {
// ... walk函数内容 ...
// 在比较子节点之前，更新globalIndex
if (oldNode.children) {
globalIndex += oldNode.children.length;
}
}
（注意：为了简化，上述diffKeyedChildren的实现是一个核心逻辑的展示，实际生产环境的实现会更复杂，需要处理更多边缘情况。但它已经抓住了key比对的核心思想。）
现在，我们的diff函数已经完成了！它能接收两个VNode树，返回一个结构如下的patches对象：
patches = {
0: [ // 补丁应用在索引为0的DOM节点上
{ type: 'UPDATE', payload: { props: { class: 'new-class' } } }
],
2: [ // 补丁应用在索引为2的DOM节点上
{ type: 'REPLACE', payload: { newNode: ... } }
],
3: [ // 补丁应用在索引为3的DOM节点上
{ type: 'REORDER', payload: { moves: [...] } }
]
}
步骤五：patch函数 - 将补丁应用于真实DOM
patch函数的工作就是解析patches对象，并将这些操作应用到真实DOM上。它同样需要一个递归的辅助函数。
patch.js
// CSDN @ 你的用户名
// 系列: 前端内功修炼：从零构建一个“看不见”的应用
//
// 文件: /src/v4/patch.js
// 描述: 实现patch函数，将补丁应用到真实DOM。
const PatchType = require('./patchTypes');
const { createDom, applyProps } = require('../v3/render'); // 复用上一章的工具函数
let allPatches;
let domIndex;
function patch(rootNode, patches) {
allPatches = patches;
domIndex = 0;
walkPatch(rootNode);
}
function walkPatch(node) {
const currentPatches = allPatches[domIndex++];
const childNodes = node.childNodes;
// 递归遍历子节点
childNodes.forEach(child => walkPatch(child));
// 应用当前节点的补丁
if (currentPatches) {
applyPatches(node, currentPatches);
}
}
function applyPatches(domNode, patchesToApply) {
patchesToApply.forEach(patch => {
switch (patch.type) {
case PatchType.REPLACE:
domNode.parentNode.replaceChild(createDom(patch.payload.newNode), domNode);
break;
case PatchType.UPDATE:
applyUpdate(domNode, patch.payload);
break;
case PatchType.REORDER:
applyReorder(domNode, patch.payload.moves);
break;
default:
throw new Error(`Unknown patch type: ${patch.type}`);
}
});
}
function applyUpdate(domNode, payload) {
if (payload.props) {
// 更新属性
applyProps(domNode, payload.props);
}
if (payload.text) {
// 更新文本内容
domNode.textContent = payload.text;
}
}
function applyReorder(domNode, moves) {
const staticNodeList = Array.from(domNode.childNodes);
const newChildren = [];
// 处理新增和移动
moves.forEach(move => {
if (move.type === 'INSERT') {
newChildren[move.to] = createDom(move.node);
} else if (move.type === 'MOVE') {
newChildren[move.to] = staticNodeList[move.from];
}
});
// 处理删除
moves.filter(m => m.type === 'REMOVE').forEach(move => {
staticNodeList[move.from] = null;
});
// 将未被删除的节点放入新列表
staticNodeList.forEach(node => {
if (node) {
let i = 0;
while (newChildren[i]) i++;
newChildren[i] = node;
}
});
// 清空并重新插入
domNode.innerHTML = '';
newChildren.forEach(child => {
if (child) domNode.appendChild(child);
});
}
module.exports = { patch };
步骤六：串联一切
我们现在有了diff和patch。为了在Node.js中演示，我们将继续使用renderToString来“模拟”DOM操作。我们会打印出旧的HTML、新的HTML以及计算出的patches。
main.js
// CSDN @ 你的用户名
// 系列: 前端内功修炼：从零构建一个“看不见”的应用
//
// 文件: /src/v4/main.js
// 描述: 演示Diff和Patch的核心流程。
const { createElement } = require('../v3/createElement');
const { renderToString } = require('../v3/render');
const { diff } = require('./diff');
// --- 旧的VNode ---
const oldState = {
items: [
{ id: 'a', value: 'A' },
{ id: 'b', value: 'B' },
{ id: 'c', value: 'C' },
{ id: 'd', value: 'D' },
]
};
function OldApp(state) {
return createElement('ul', { class: 'list-old' },
...state.items.map(item =>
createElement('li', { key: item.id }, item.value)
)
);
}
const oldVNode = OldApp(oldState);
// --- 新的VNode (模拟状态更新) ---
const newState = {
items: [
{ id: 'd', value: 'D-updated' }, // D移动到最前，并更新了内容
{ id: 'a', value: 'A' }, // A
{ id: 'e', value: 'E' }, // 新增E
{ id: 'b', value: 'B' }, // B
// C被删除了
]
};
function NewApp(state) {
return createElement('ul', { class: 'list-new' }, // ul的class也变了
...state.items.map(item =>
createElement('li', { key: item.id }, item.value)
)
);
}
const newVNode = NewApp(newState);
// --- 执行Diff ---
console.log('--- Old VNode Tree ---');
console.log(renderToString(oldVNode));
/*
<ul class="list-old">
<li key="a">A</li>
<li key="b">B</li>
<li key="c">C</li>
<li key="d">D</li>
</ul>
*/
console.log('\n--- New VNode Tree ---');
console.log(renderToString(newVNode));
/*
<ul class="list-new">
<li key="d">D-updated</li>
<li key="a">A</li>
<li key="e">E</li>
<li key="b">B</li>
</ul>
*/
console.log('\n--- Calculating Patches ---');
const patches = diff(oldVNode, newVNode);
console.log(JSON.stringify(patches, null, 2));
/*
--- 预期的Patches输出 (结构可能略有不同，但反映了核心差异) ---
{
"0": [
{ "type": "UPDATE", "payload": { "props": { "class": "list-new" } } },
{ "type": "REORDER", "payload": { "moves": [
{ "type": "MOVE", "from": 3, "to": 0 },
{ "type": "INSERT", "node": { ... E ... }, "to": 2 },
{ "type": "REMOVE", "from": 2 }
] } }
],
"4": [ // 对应旧VNode中的D节点
{ "type": "UPDATE", "payload": { "text": "D-updated" } }
]
}
*/
第四章总结：我们征服了性能优化的“珠峰”
这一章无疑是硬核的。我们从理论出发，理解了Diff算法得以实现的三大假设，然后一步步地实现了diff和patch的核心逻辑。
我们完成了一个完整的、从“状态变更”到“最小化DOM更新”的闭环：
- VDOM生成：
state->createElement->VNode - 差异比对：
diff(oldVNode, newVNode)->patches - 应用补丁：
patch(rootDomNode, patches)-> UI更新！
虽然我们的实现是简化的，但它蕴含了所有现代框架（React, Vue, Svelte等）渲染引擎的共同智慧。理解了它，你就理解了这些框架是如何在保证开发效率的同时，实现极致的渲染性能的。
核心要点：
- 完整的树Diff算法复杂度过高，不适用于前端。
- 现代前端框架的Diff算法基于三个核心假设：同层比对、不同类型替换、使用key识别。这使得算法复杂度优化到O(n)。
- Diff算法的核心是递归地遍历新旧VNode树，找出替换（REPLACE）、**更新（UPDATE）和重排序（REORDER）**等差异。
key在列表比对中至关重要，它能帮助算法最大程度地复用已有DOM节点，减少新增和删除操作。patch函数是Diff结果的执行者，它负责将生成的“补丁”精确地应用到真实DOM上。
至此，我们“看不见”的应用已经拥有了自己高效的“渲染引擎”。在下一章**《状态管理(一)：Redux已死？从发布订阅模式徒手打造一个“迷你状态机”》**中，我们将回到数据层面。当应用变得复杂，组件层级变深，状态如何在不同组件间高效、可预测地流动？我们将从最基础的发布订阅模式出发，亲手构建一个属于我们自己的“Redux”，来解决状态管理的难题。敬请期待！