登录
Diff算法基础：同层比较与key的作用
2026年2月27日 09:37
在上一篇文章中，我们深入探讨了 patch 算法的完整实现。今天，我们将聚焦于 Diff 算法的核心思想——为什么需要它？它如何工作？key 又为什么如此重要？通过这篇文章，我们将彻底理解 Diff 算法的基础原理。
前言：从生活中的例子理解Diff
想象一下，假如我们有一排积木：
A B C D
然后我们想把它变成这样：
A C D B
这时，我们应该怎么做呢？
-
方式一：全部推倒重来：移除所有，按照我们想要的顺序重新摆放
-
方式二：只调整变化的部分：移动位置，替换积木，即：我们只需要调整
B C D三块积木的位置即可。
很显然，方式二的做法更高效。这就是 Diff 算法的本质——找出最小化的更新方案。
为什么需要 Diff 算法？
没有 Diff 算法会怎样？
假设我们有一个简单的列表：
<!-- 旧列表 -->
<ul>
<li>苹果</li>
<li>香蕉</li>
<li>橙子</li>
</ul>
<!-- 新列表（只改了最后一个） -->
<ul>
<li>苹果</li>
<li>香蕉</li>
<li>橘子</li>
</ul>
上述两个列表中，新列表只改了最后一项数据，如果没有 Diff 算法，我们只能按照 前言 中的方式一处理：删除整个 ul，重新创建：
const oldUl = document.querySelector('ul');
oldUl.remove();
const newUl = document.createElement('ul');
newUl.innerHTML = `
<li>苹果</li>
<li>香蕉</li>
<li>橘子</li>
`;
container.appendChild(newUl);
这种方式虽然可以解决问题，但存在很大的风险：
- 性能极差：即使只改一个字，也要重建整个 DOM 树
- 状态丢失：输入框内容、滚动位置都会丢失
- 浪费资源：创建了大量不必要的 DOM 节点
此时 Diff 算法的重要性就凸显出来了！
Diff 算法的目标
Diff 算法的核心目标可以概括为三点：
- 尽可能复用已有节点
- 只更新变化的部分
- 最小化 DOM 操作
还是以上述 ul 结构为例，理想中的 Diff 操作应该是：
- 更新第三个
li的文本内容：将<li>橙子</li>替换成<li>橘子</li> - 其他节点完全复用，不作任何更改
传统 Diff 算法
function diff(oldList, newList){
for(let i = 0; i < oldList.length; i++){
for(let j = 0; j < newList.length; j++){
if(oldList[i] === newList[j]){
// 找到相同的节点，进行复用
console.log('找到了相同的节点', oldList[i]);
break;
} else {
// 没找到相同的节点，进行新增
console.log('需要新增节点', newList[j]);
}
}
}
}
上述代码的时间复杂度为：O(n²)；如果再考虑到移动、删除、新增等操作，其时间复杂度可以达到：O(n³)。这显然是不合理的。
同层比较的核心思想
为了解决传统 Diff 算法的时间复杂度问题，Vue 团队通过两个关键思想，将 Diff 算法的时间复杂降低到了：O(n)：
- 同层比较，即只比较同一层级的节点
- 类型相同，即不同类型节点直接替换
什么是同层比较？
同层比较的意思是：只比较同一层级的节点，不跨层级移动。
我们来看一个简单的例子：
上图两个新旧 VNode 树中，对比过程是这样的：
为什么不跨层级比较？
我们可以再来一个更复杂的示例：
<!-- 旧列表 -->
<ul>
<li>li-1</li>
<li>li-2</li>
<li>
<span>
<a>
li-3
</a>
</span>
</li>
</ul>
<!-- 新列表 -->
<ul>
<li>li-1</li>
<li>li-2</li>
<li>
<a>
li-3
</a>
</li>
</ul>
假设新旧两个列表是这样的，如果支持跨层级比较和移动，那么上述列表应该进行如下操作：
- 发现旧列表中
a标签位于span标签下，新列表中直接位于li标签下； - 记录这个操作差异，保存
a标签，删除span标签，再把a标签挂载到li标签下； - 更新父子节点关系。
这种操作会让算法变得极其复杂，而且实际开发中，跨层级移动节点的情况非常罕见。所以 Vue 选择简化问题：如果节点跨层级了，就视为不同类型，直接替换。
function patch(oldVNode, newVNode) {
// 如果节点类型不同，直接替换
if (oldVNode.type !== newVNode.type) {
unmount(oldVNode);
mount(newVNode);
return;
}
// 同类型节点，进行深度比较
patchChildren(oldVNode, newVNode);
}
同层比较的优势
| 优势 | 说明 | 示例 |
|---|---|---|
| 算法简单 | 只需要比较同一层 | 树形结构简化为线性比较 |
| 性能可控 | 复杂度O(n) | 1000个节点只需比较1000次 |
| 实现可靠 | 边界情况少 | 不需要处理复杂移动 |
key在节点复用中的作用
为什么需要key？
我们来看一个简单的代办列表：
<!-- 旧列表 -->
<li>学习Vue</li>
<li>写文章</li>
<li>休息一下</li>
<!-- 新列表（删除了中间项 写文章） -->
<li>学习Vue</li>
<li>休息一下</li>
如果没有 key，Vue 会如何进行 diff 比较呢：
- 比较位置0：都是"学习Vue"，直接复用；
- 比较位置1：旧的是"写文章"，新的是"休息一下" ，更新文本进行替换
- 比较位置2：旧的有"休息一下"，新的没有，则删除
这样操作过程中，更新了一个 li 的文本，删除了一个 li 。
这个过程看起来是没有问题的，但是如果上述列表有状态呢？
<!-- 带输入框的列表 -->
<li>
<input value="学习Vue" />
学习Vue
</li>
<li>
<input value="写文章" />
写文章
</li>
<li>
<input value="休息一下" />
休息一下
</li>
<!-- 删除中间项后 -->
<li>
<input value="学习Vue" /> <!-- 输入框内容被保留了 -->
学习Vue
</li>
<li>
<input value="休息一下" /> <!-- 这里会是"休息一下"吗？ -->
休息一下
</li>
这时候问题就出现了：输入框的内容被错误地复用了！由于没有 key 的情况下，Vue 只按位置比较，最后的实际结果是：
<li>
<input value="学习Vue" /> <!-- 输入框内容被保留了 -->
学习Vue
</li>
<li>
<input value="写文章" /> <!-- label变成了"写文章" -->
休息一下
</li>
这个例子也同样解释了为什么不推荐，或者说不能用 index 作为 key 的原因。正确的做法是使用唯一的、稳定的标识作为 key。
key的作用图解
key的作用可以这样理解：
手写实现：简单Diff算法
class SimpleDiff {
constructor(options) {
this.options = options;
}
/**
* 执行diff更新
* @param {Array} oldChildren 旧子节点数组
* @param {Array} newChildren 新子节点数组
* @param {HTMLElement} container 父容器
*/
diff(oldChildren, newChildren, container) {
// 1. 创建key到索引的映射（如果有key）
const oldKeyMap = this.createKeyMap(oldChildren);
const newKeyMap = this.createKeyMap(newChildren);
// 2. 记录已处理的节点
const processed = new Set();
// 3. 第一轮：尝试复用有key的节点
this.patchKeyedNodes(oldChildren, newChildren, oldKeyMap, newKeyMap, processed, container);
// 4. 第二轮：处理剩余节点
this.processRemainingNodes(oldChildren, newChildren, processed, container);
}
/**
* 创建key到索引的映射
*/
createKeyMap(children) {
const map = new Map();
for (let i = 0; i < children.length; i++) {
const child = children[i];
if (child.key != null) {
map.set(child.key, i);
}
}
return map;
}
/**
* 处理有key的节点
*/
patchKeyedNodes(oldChildren, newChildren, oldKeyMap, newKeyMap, processed, container) {
// 遍历新节点
for (let i = 0; i < newChildren.length; i++) {
const newVNode = newChildren[i];
// 如果新节点没有key，跳过第一轮处理
if (newVNode.key == null) continue;
// 尝试在旧节点中找相同key的节点
const oldIndex = oldKeyMap.get(newVNode.key);
if (oldIndex !== undefined) {
const oldVNode = oldChildren[oldIndex];
// 标记为已处理
processed.add(oldIndex);
// 执行patch更新
this.patchVNode(oldVNode, newVNode, container);
} else {
// 没有找到对应key，说明是新增节点
this.mountVNode(newVNode, container);
}
}
}
/**
* 处理剩余节点
*/
processRemainingNodes(oldChildren, newChildren, processed, container) {
// 1. 卸载未处理的旧节点
for (let i = 0; i < oldChildren.length; i++) {
if (!processed.has(i)) {
this.unmountVNode(oldChildren[i]);
}
}
// 2. 挂载新节点中未处理的节点
for (let i = 0; i < newChildren.length; i++) {
const newVNode = newChildren[i];
// 如果没有key或者key不在旧节点中，需要挂载
if (newVNode.key == null) {
this.mountVNode(newVNode, container);
} else {
const oldIndex = oldChildren.findIndex(old => old.key === newVNode.key);
if (oldIndex === -1) {
this.mountVNode(newVNode, container);
}
}
}
}
/**
* 更新节点
*/
patchVNode(oldVNode, newVNode, container) {
console.log(`更新节点: ${oldVNode.key || '无key'}`);
// 复用DOM元素
newVNode.el = oldVNode.el;
// 更新属性
this.updateProps(newVNode.el, oldVNode.props, newVNode.props);
// 更新子节点
if (newVNode.children !== oldVNode.children) {
newVNode.el.textContent = newVNode.children;
}
}
/**
* 挂载新节点
*/
mountVNode(vnode, container) {
console.log(`挂载新节点: ${vnode.key || '无key'}`);
// 创建DOM元素
const el = document.createElement(vnode.type);
vnode.el = el;
// 设置属性
this.updateProps(el, {}, vnode.props);
// 设置内容
if (vnode.children) {
el.textContent = vnode.children;
}
// 插入到容器
container.appendChild(el);
}
/**
* 卸载节点
*/
unmountVNode(vnode) {
console.log(`卸载节点: ${vnode.key || '无key'}`);
if (vnode.el && vnode.el.parentNode) {
vnode.el.parentNode.removeChild(vnode.el);
}
}
/**
* 更新属性
*/
updateProps(el, oldProps = {}, newProps = {}) {
// 移除不存在的属性
for (const key in oldProps) {
if (!(key in newProps)) {
el.removeAttribute(key);
}
}
// 设置新属性
for (const key in newProps) {
if (oldProps[key] !== newProps[key]) {
el.setAttribute(key, newProps[key]);
}
}
}
}
// 创建VNode的辅助函数
function h(type, props = {}, children = '') {
return {
type,
props,
key: props.key,
children,
el: null
};
}
结语
理解 Diff 算法的基础原理，就像掌握了Vue 更新 DOM 的"思维模式"。知道它如何思考、如何决策，才能写出与框架配合最好的代码。
对于文章中错误的地方或有任何疑问，欢迎在评论区留言讨论！
