Vue 中的三种 Diff 算法详解

📚 目录

  1. 什么是 Diff 算法
  2. Vue 2.x 双端 Diff 算法
  3. Vue 3.x 快速 Diff 算法
  4. 简单 Diff 算法
  5. 三种算法对比
  6. 实际应用场景

什么是 Diff 算法

简单理解

Diff 算法就像是"找不同"游戏，比较两个版本的列表（比如新旧 DOM 节点列表），找出哪些需要：

  • ✅ 新增：新列表有，旧列表没有
  • ❌ 删除：旧列表有，新列表没有
  • 🔄 移动：位置发生了变化
  • ✏️ 更新：内容发生了变化

为什么需要 Diff 算法？

想象一下，如果每次数据变化都完全重新渲染整个页面，就像把整栋楼拆了重建，非常浪费！

Diff 算法让我们能够：

  • 🚀 只更新变化的部分，提高性能
  • 💰 节省资源，减少不必要的 DOM 操作
  • ⚡ 提升用户体验，页面更新更快

Vue 2.x 双端 Diff 算法

核心思想

双端 Diff 就像两个人从两端同时开始比较，向中间靠拢。

算法步骤

  1. 四个指针：oldStartIdx、oldEndIdx、newStartIdx、newEndIdx
  2. 四种比较：
    • 旧头 vs 新头
    • 旧尾 vs 新尾
    • 旧头 vs 新尾
    • 旧尾 vs 新头

具体示例

示例 1：简单移动

旧列表：[A, B, C, D]
新列表：[D, A, B, C]

初始状态：
旧列表: [A, B, C, D]
         ↑        ↑
       oldStart oldEnd

新列表: [D, A, B, C]
         ↑        ↑
       newStart newEnd

步骤 1：比较 oldStart(A) 和 newStart(D) → 不匹配
步骤 2：比较 oldEnd(D) 和 newEnd(C) → 不匹配
步骤 3：比较 oldStart(A) 和 newEnd(C) → 不匹配
步骤 4：比较 oldEnd(D) 和 newStart(D) → ✅ 匹配！

结果：将 D 移动到最前面
操作：移动 D 到位置 0

继续比较：
旧列表: [A, B, C]
         ↑     ↑
       oldStart oldEnd

新列表: [A, B, C]
         ↑     ↑
       newStart newEnd

步骤 5：比较 oldStart(A) 和 newStart(A) → ✅ 匹配！
步骤 6：比较 oldEnd(C) 和 newEnd(C) → ✅ 匹配！

最终：只需要移动 1 个节点（D）
代码实现（简化版）
function diff(oldChildren, newChildren) {
  let oldStartIdx = 0;
  let oldEndIdx = oldChildren.length - 1;
  let newStartIdx = 0;
  let newEndIdx = newChildren.length - 1;
  
  while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
    const oldStartNode = oldChildren[oldStartIdx];
    const oldEndNode = oldChildren[oldEndIdx];
    const newStartNode = newChildren[newStartIdx];
    const newEndNode = newChildren[newEndIdx];
    
    // 情况 1：旧头 === 新头
    if (oldStartNode.key === newStartNode.key) {
      patch(oldStartNode, newStartNode);
      oldStartIdx++;
      newStartIdx++;
    }
    // 情况 2：旧尾 === 新尾
    else if (oldEndNode.key === newEndNode.key) {
      patch(oldEndNode, newEndNode);
      oldEndIdx--;
      newEndIdx--;
    }
    // 情况 3：旧头 === 新尾（需要移动）
    else if (oldStartNode.key === newEndNode.key) {
      patch(oldStartNode, newEndNode);
      moveNode(oldStartNode, oldEndIdx + 1);
      oldStartIdx++;
      newEndIdx--;
    }
    // 情况 4：旧尾 === 新头（需要移动）
    else if (oldEndNode.key === newStartNode.key) {
      patch(oldEndNode, newStartNode);
      moveNode(oldEndNode, oldStartIdx);
      oldEndIdx--;
      newStartIdx++;
    }
    // 情况 5：都不匹配，查找新头在旧列表中的位置
    else {
      const idxInOld = findIdxInOld(newStartNode.key, oldChildren);
      if (idxInOld === -1) {
        // 新节点，需要创建
        createNode(newStartNode);
      } else {
        // 找到节点，需要移动
        moveNode(oldChildren[idxInOld], oldStartIdx);
        patch(oldChildren[idxInOld], newStartNode);
      }
      newStartIdx++;
    }
  }
  
  // 处理剩余节点
  if (oldStartIdx > oldEndIdx) {
    // 新列表还有剩余，需要新增
    for (let i = newStartIdx; i <= newEndIdx; i++) {
      createNode(newChildren[i]);
    }
  } else if (newStartIdx > newEndIdx) {
    // 旧列表还有剩余，需要删除
    for (let i = oldStartIdx; i <= oldEndIdx; i++) {
      removeNode(oldChildren[i]);
    }
  }
}

优缺点

优点：

  • ✅ 处理两端移动的场景效率高
  • ✅ 实现相对简单
  • ✅ 适合大多数常见场景

缺点：

  • ❌ 对于复杂乱序场景，需要多次查找
  • ❌ 可能产生不必要的移动操作

Vue 3.x 快速 Diff 算法

核心思想

快速 Diff 就像"找相同部分 + 找最长递增子序列"，先处理相同的前后缀，再处理中间乱序部分。

算法步骤

  1. 预处理：去除相同的前缀和后缀
  2. 构建映射：为新列表建立 key 到索引的映射
  3. 最长递增子序列（LIS）：找出不需要移动的节点
  4. 移动节点：只移动需要移动的节点

具体示例

示例 1：前缀后缀相同

旧列表：[A, B, C, D, E, F]
新列表：[A, B, D, C, E, F]

步骤 1：去除相同前缀
旧列表: [A, B, C, D, E, F]
         ✓  ✓  ↑
新列表: [A, B, D, C, E, F]
         ✓  ✓  ↑
前缀相同：A, B

步骤 2：去除相同后缀
旧列表: [C, D, E, F]
         ↑     ✓  ✓
新列表: [D, C, E, F]
         ↑     ✓  ✓
后缀相同：E, F

步骤 3：处理中间部分
旧列表: [C, D]
新列表: [D, C]

构建映射：
newKeyToIndex = { D: 0, C: 1 }

计算最长递增子序列（LIS）：
- 旧列表索引：[0(C), 1(D)]
- 在新列表中的位置：[1, 0]
- 递增序列：[1]（只有 C 不需要移动）

结果：只需要移动 D
示例 2：复杂乱序

旧列表：[A, B, C, D, E]
新列表：[E, A, B, C, D]

步骤 1：去除相同前缀
旧列表: [A, B, C, D, E]
         ↑
新列表: [E, A, B, C, D]
         ↑
前缀不同

步骤 2：去除相同后缀
旧列表: [A, B, C, D, E]
                     ↑
新列表: [E, A, B, C, D]
                     ↑
后缀不同

步骤 3：处理整个列表
构建映射：
newKeyToIndex = { E: 0, A: 1, B: 2, C: 3, D: 4 }

计算 LIS：
- 旧列表索引：[0(A), 1(B), 2(C), 3(D), 4(E)]
- 在新列表中的位置：[1, 2, 3, 4, 0]
- 递增序列：[1, 2, 3, 4]（A, B, C, D 不需要移动）

结果：只需要移动 E 到最前面
代码实现（简化版）
function quickDiff(oldChildren, newChildren) {
  // 步骤 1：去除相同前缀
  let j = 0;
  let oldVNode = oldChildren[j];
  let newVNode = newChildren[j];
  
  while (oldVNode && newVNode && oldVNode.key === newVNode.key) {
    patch(oldVNode, newVNode);
    j++;
    oldVNode = oldChildren[j];
    newVNode = newChildren[j];
  }
  
  // 步骤 2：去除相同后缀
  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);
    oldEnd--;
    newEnd--;
    oldVNode = oldChildren[oldEnd];
    newVNode = newChildren[newEnd];
  }
  
  // 步骤 3：处理中间部分
  if (j > oldEnd && j <= newEnd) {
    // 只有新增
    for (let i = j; i <= newEnd; i++) {
      createNode(newChildren[i]);
    }
  } else if (j > newEnd) {
    // 只有删除
    for (let i = j; i <= oldEnd; i++) {
      removeNode(oldChildren[i]);
    }
  } else {
    // 有移动和更新
    const count = newEnd - j + 1;
    const source = new Array(count).fill(-1);
    const oldStart = j;
    const newStart = j;
    let moved = false;
    let pos = 0;
    
    // 构建 key 到索引的映射
    const keyIndex = {};
    for (let i = newStart; i <= newEnd; i++) {
      keyIndex[newChildren[i].key] = i;
    }
    
    // 填充 source 数组
    for (let i = oldStart; i <= oldEnd; i++) {
      const oldVNode = oldChildren[i];
      const k = keyIndex[oldVNode.key];
      
      if (k !== undefined) {
        newVNode = newChildren[k];
        patch(oldVNode, newVNode);
        source[k - newStart] = i;
        
        if (k < pos) {
          moved = true;
        } else {
          pos = k;
        }
      } else {
        removeNode(oldVNode);
      }
    }
    
    if (moved) {
      // 计算最长递增子序列
      const seq = getSequence(source);
      let s = seq.length - 1;
      let i = count - 1;
      
      for (i; i >= 0; i--) {
        if (source[i] === -1) {
          // 新节点，需要插入
          createNode(newChildren[i + newStart]);
        } else if (i !== seq[s]) {
          // 需要移动
          moveNode(oldChildren[source[i]], newChildren[i + newStart]);
        } else {
          // 不需要移动
          s--;
        }
      }
    }
  }
}

// 最长递增子序列算法（简化版）
function getSequence(arr) {
  const result = [0];
  const p = arr.slice();
  let len = arr.length;
  let i, j, u, v, c;
  
  for (i = 0; i < len; i++) {
    const arrI = arr[i];
    if (arrI !== -1) {
      j = result[result.length - 1];
      if (arr[j] < arrI) {
        p[i] = j;
        result.push(i);
        continue;
      }
      u = 0;
      v = result.length - 1;
      while (u < v) {
        c = (u + v) >> 1;
        if (arr[result[c]] < arrI) {
          u = c + 1;
        } else {
          v = c;
        }
      }
      if (arrI < arr[result[u]]) {
        if (u > 0) {
          p[i] = result[u - 1];
        }
        result[u] = i;
      }
    }
  }
  
  u = result.length;
  v = result[u - 1];
  while (u-- > 0) {
    result[u] = v;
    v = p[v];
  }
  
  return result;
}

优缺点

优点：

  • ✅ 处理前缀后缀相同的场景效率极高
  • ✅ 通过 LIS 算法最小化移动操作
  • ✅ 整体性能优于双端 Diff

缺点：

  • ❌ 实现复杂度较高
  • ❌ LIS 算法本身有一定开销

简单 Diff 算法

核心思想

简单 Diff 就像"暴力比较"，逐个比较每个节点，找到就更新，找不到就删除或新增。

算法步骤

  1. 遍历新列表
  2. 在旧列表中查找相同 key 的节点
  3. 找到就更新，找不到就新增
  4. 最后删除旧列表中多余的节点

具体示例

示例 1：简单场景

旧列表：[A, B, C]
新列表：[C, A, B]

步骤 1：处理新列表的第一个节点 C
  在旧列表中查找 C → 找到（索引 2）
  更新节点 C
  移动 C 到位置 0

步骤 2：处理新列表的第二个节点 A
  在旧列表中查找 A → 找到（索引 0）
  更新节点 A
  移动 A 到位置 1

步骤 3：处理新列表的第三个节点 B
  在旧列表中查找 B → 找到（索引 1）
  更新节点 B
  移动 B 到位置 2

结果：移动了 3 个节点（效率较低）
代码实现（简化版）
function simpleDiff(oldChildren, newChildren) {
  // 构建旧列表的 key 到索引映射
  const oldKeyToIndex = {};
  for (let i = 0; i < oldChildren.length; i++) {
    oldKeyToIndex[oldChildren[i].key] = i;
  }
  
  let lastIndex = 0;
  
  // 遍历新列表
  for (let i = 0; i < newChildren.length; i++) {
    const newVNode = newChildren[i];
    const j = oldKeyToIndex[newVNode.key];
    
    if (j !== undefined) {
      // 找到节点，更新
      patch(oldChildren[j], newVNode);
      
      if (j < lastIndex) {
        // 需要移动
        moveNode(oldChildren[j], i);
      } else {
        lastIndex = j;
      }
    } else {
      // 新节点，需要创建
      createNode(newVNode);
    }
  }
  
  // 删除旧列表中多余的节点
  for (let i = 0; i < oldChildren.length; i++) {
    const oldVNode = oldChildren[i];
    const has = newChildren.some(vnode => vnode.key === oldVNode.key);
    if (!has) {
      removeNode(oldVNode);
    }
  }
}

优缺点

优点：

  • ✅ 实现最简单
  • ✅ 容易理解和维护

缺点：

  • ❌ 效率最低，可能产生大量不必要的移动
  • ❌ 不适合复杂场景

三种算法对比

性能对比表

算法 时间复杂度 空间复杂度 适用场景 移动操作优化
简单 Diff O(n²) O(n) 简单列表 ❌ 无优化
双端 Diff O(n) O(n) 常见场景 ⚠️ 部分优化
快速 Diff O(n) O(n) 复杂场景 ✅ 最优优化

场景对比示例

场景 1：前缀相同，中间乱序

旧列表：[A, B, C, D, E]
新列表：[A, B, E, C, D]

算法 移动操作数 说明
简单 Diff 3 次 移动 E, C, D
双端 Diff 1 次 移动 E
快速 Diff 1 次 移动 E（利用前缀优化）
场景 2：完全乱序

旧列表：[A, B, C, D]
新列表：[D, C, B, A]

算法 移动操作数 说明
简单 Diff 4 次 移动所有节点
双端 Diff 2 次 利用双端比较
快速 Diff 2 次 利用 LIS 优化
场景 3：只改变顺序

旧列表：[A, B, C]
新列表：[C, A, B]

算法 移动操作数 说明
简单 Diff 3 次 移动所有节点
双端 Diff 1 次 移动 C
快速 Diff 1 次 移动 C

选择建议

  • 简单 Diff：仅用于学习或极简单场景
  • 双端 Diff：Vue 2.x 使用，适合大多数场景
  • 快速 Diff：Vue 3.x 使用，性能最优

实际应用场景

场景 1：列表排序

<template>
  <div>
    <button @click="sortAsc">升序</button>
    <button @click="sortDesc">降序</button>
    <ul>
      <li v-for="item in list" :key="item.id">{{ item.name }}</li>
    </ul>
  </div>
</template>

<script>
export default {
  data() {
    return {
      list: [
        { id: 1, name: 'A' },
        { id: 2, name: 'B' },
        { id: 3, name: 'C' }
      ]
    };
  },
  methods: {
    sortAsc() {
      this.list.sort((a, b) => a.id - b.id);
      // Vue 会使用 Diff 算法高效更新 DOM
    },
    sortDesc() {
      this.list.sort((a, b) => b.id - a.id);
      // 只需要移动节点，不需要重新创建
    }
  }
};
</script>

场景 2：动态添加/删除

<template>
  <div>
    <button @click="addItem">添加</button>
    <button @click="removeItem">删除</button>
    <ul>
      <li v-for="item in list" :key="item.id">
        {{ item.name }}
        <button @click="remove(item.id)">删除</button>
      </li>
    </ul>
  </div>
</template>

<script>
export default {
  data() {
    return {
      list: [
        { id: 1, name: 'Item 1' },
        { id: 2, name: 'Item 2' }
      ],
      nextId: 3
    };
  },
  methods: {
    addItem() {
      this.list.push({ id: this.nextId++, name: `Item ${this.nextId - 1}` });
      // Diff 算法只会在末尾添加新节点
    },
    removeItem() {
      this.list.pop();
      // Diff 算法只删除最后一个节点
    },
    remove(id) {
      const index = this.list.findIndex(item => item.id === id);
      if (index > -1) {
        this.list.splice(index, 1);
        // Diff 算法会高效处理删除操作
      }
    }
  }
};
</script>

场景 3：过滤列表

<template>
  <div>
    <input v-model="filterText" placeholder="搜索...">
    <ul>
      <li v-for="item in filteredList" :key="item.id">
        {{ item.name }}
      </li>
    </ul>
  </div>
</template>

<script>
export default {
  data() {
    return {
      filterText: '',
      list: [
        { id: 1, name: 'Apple' },
        { id: 2, name: 'Banana' },
        { id: 3, name: 'Cherry' }
      ]
    };
  },
  computed: {
    filteredList() {
      return this.list.filter(item => 
        item.name.toLowerCase().includes(this.filterText.toLowerCase())
      );
      // Diff 算法会智能地只更新变化的节点
    }
  }
};
</script>

总结

核心要点

  1. Diff 算法的目的：高效更新 DOM，只改变需要改变的部分
  2. 三种算法特点：
    • 简单 Diff：最基础，效率低
    • 双端 Diff：Vue 2.x，平衡性能和复杂度
    • 快速 Diff：Vue 3.x，性能最优
  3. 选择原则：根据场景复杂度选择合适算法

总结

简单Diff算法

Diff算法用来计算两组子节点的差异，并试图最大程度地复用DOM元素。一种简单的方式来更新子节点，即卸载所有旧子节点，再挂载所有新子节点，然而这种更新方式无法对DOM元素进行复用，需要大量的DOM操作能完成更新，非常消耗性能。

于是，我们对他进行了改进，改进后的方案是，遍历新旧两组子节点中数量较少的那一组，并逐个调用patch函数进行打补丁，然后比较新旧两组子节点的数量，如果新的一组子节点数量更多，说明有新子节点需要挂载；否则说明在旧的一组子节点中，有节点需要卸载。

然后，虚拟节点中key的作用，他就像虚拟节点的“身份证号”。在更新时，渲染器通过key属性找到可复用的节点，然后尽可能地通过DOM移动操作来完成更新，避免过多地对DOM元素进行销毁和重建。

接着，讨论了简单Diff算法是如何寻找需要移动的节点的，简单Diff算法的核心逻辑是，拿新的一组子节点中的节点去旧的一组子节点中寻找可复用的节点，如果找到了，则记录该节点的位置索引。我们把这个位置索引称为最大索引，在整个更新过程中，如果一个节点的索引值小于最大索引，则说明该节点对应的真实DOM元素需要移动。

双端Diff算法

双端Diff算法指的是，在新旧两组子节点的四个端点之间分别进行比较，并试图找到可复用的节点。相比简单Diff算法，双端Diff双发的优势在于，对于同样的更新场景，执行的DOM移动操作次数更少

快速Diff算法

快速Diff算法在实测中性能最优，它借鉴了文本Diff中的预处理思路，先处理新旧两组子节点中相同的前置节点和相同的后置节点，当前置节点和后置节点全部处理完毕后，如果无法简单的通过挂载新节点或卸载已经不存在的节点来完成更新，则需要根据节点的索引关系，构造出一个最长递增子序列，最长递增子序列所指向的节点即为不需要移动的节点。

学习建议

  1. 先理解简单 Diff，掌握基本概念
  2. 再学习双端 Diff，理解优化思路
  3. 最后学习快速 Diff，了解高级优化
  4. 通过实际项目加深理解

参考资料

  • Vue 2.x 源码：src/core/vdom/patch.js
  • Vue 3.x 源码：packages/runtime-core/src/renderer.ts
  • 最长递增子序列算法：LeetCode 300 题

希望这份文档能帮助你理解 Vue 中的 Diff 算法！ 🎉

# vue.js # 算法 # 前端
Logo
AI Agent技术社区

Agent 垂直技术社区，欢迎活跃、内容共建。

更多推荐

cover

从一张商品图到正式上架：实测店匠 Shoplazza Athena，AI Agent 不只是聊天框

avatar AI Agent技术社区
cover

我测试了一个0.9B模型，它竟然能自动区分多人讲话）

avatar AI Agent技术社区
cover

【AI Agent】《2026年9月 AI Agent全栈开发技术选型专项面试宝典》

avatar AI Agent技术社区