前言：从生活中的例子理解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 = `
  
苹果
  
香蕉
  
橘子
`;
container.appendChild(newUl);

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

1. 性能极差：即使只改一个字，也要重建整个 DOM 树
2. 状态丢失：输入框内容、滚动位置都会丢失
3. 浪费资源：创建了大量不必要的 DOM 节点

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

Diff 算法的目标

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

1. 尽可能复用已有节点
2. 只更新变化的部分
3. 最小化 DOM 操作

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

1. 更新第三个 li 的文本内容：将
2. 橙子
替换成
3. 橘子
4. 其他节点完全复用，不作任何更改

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

1. 同层比较，即只比较同一层级的节点
2. 类型相同，即不同类型节点直接替换

什么是同层比较？

同层比较的意思是：只比较同一层级的节点，不跨层级移动。 我们来看一个简单的例子： 上图两个新旧 VNode 树中，对比过程是这样的：

为什么不跨层级比较？

我们可以再来一个更复杂的示例：

<ul>
  <li>li-1li>
  <li>li-2li>
  <li>
    <span>
      <a>
        li-3
      a>
    span>
  li>
ul>


<ul>
  <li>li-1li>
  <li>li-2li>
  <li>
    <a>
      li-3
    a>
  li>
ul>

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

1. 发现旧列表中 a 标签位于 span 标签下，新列表中直接位于 li 标签下；
2. 记录这个操作差异，保存 a 标签，删除 span 标签，再把 a 标签挂载到 li 标签下；
3. 更新父子节点关系。

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

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

同层比较的优势

key在节点复用中的作用

为什么需要key？

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

<li>学习Vueli>
<li>写文章li>
<li>休息一下li>


<li>学习Vueli>
<li>休息一下li>

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

1. 比较位置0：都是"学习Vue"，直接复用；
2. 比较位置1：旧的是"写文章"，新的是"休息一下" ，更新文本进行替换
3. 比较位置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="写文章" />  
  休息一下
li>

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 的"思维模式"。知道它如何思考、如何决策，才能写出与框架配合最好的代码。

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