Diff算法基础：同层比较与key的作用

Diff算法基础：同层比较与key的作用

• 前言：从生活中的例子理解Diff
• 为什么需要 Diff 算法？
• • 没有 Diff 算法会怎样？
  • Diff 算法的目标
  • 传统 Diff 算法
• 同层比较的核心思想
• • 什么是同层比较？
  • 为什么不跨层级比较？
  • 同层比较的优势
• key在节点复用中的作用
• • 为什么需要key？
  • key的作用图解
• 手写实现：简单Diff算法
• 结语

在上一篇文章中，我们深入探讨了 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);

这种方式虽然可以解决问题，但存在很大的风险：

此时 Diff 算法的重要性就凸显出来了！

Diff 算法的目标

Diff 算法的核心目标可以概括为三点：

还是以上述 ul 结构为例，理想中的 Diff 操作应该是：

传统 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>

假设新旧两个列表是这样的，如果支持跨层级比较和移动，那么上述列表应该进行如下操作：

这种操作会让算法变得极其复杂，而且实际开发中，跨层级移动节点的情况非常罕见。所以 Vue 选择简化问题：如果节点跨层级了，就视为不同类型，直接替换。

function patch(oldVNode, newVNode) {
// 如果节点类型不同，直接替换
if (oldVNode.type !== newVNode.type) {
unmount(oldVNode);
mount(newVNode);
return;
}

// 同类型节点，进行深度比较
patchChildren(oldVNode, newVNode);
}

同层比较的优势

key在节点复用中的作用

为什么需要key？

我们来看一个简单的代办列表：

<!– 旧列表 –>
<li>学习Vue</li>
<li>写文章</li>
<li>休息一下</li>

<!– 新列表（删除了中间项 写文章） –>
<li>学习Vue</li>
<li>休息一下</li>

如果没有 key，Vue 会如何进行 diff 比较呢：

这样操作过程中，更新了一个 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 的"思维模式"。知道它如何思考、如何决策，才能写出与框架配合最好的代码。

对于文章中错误的地方或有任何疑问，欢迎在评论区留言讨论！