Vue Diff 算法详解：双端与快速 Diff 对比

代码实现（简化版）

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);
    }
  }
}

优缺点

优点：

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

缺点：

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

三种算法对比

性能对比表

场景对比示例

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

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

场景 2：完全乱序

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

场景 3：只改变顺序

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

选择建议

• 简单 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. 选择原则：根据场景复杂度选择合适算法

学习建议

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 题