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

Vue Diff 算法详解：双端与快速 Diff 对比 | 极客日志

初始状态：
旧列表：[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]);
    }
  }
}

步骤 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

步骤 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;
  }
}

步骤 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)	复杂场景	✅ 最优优化

算法	移动操作数	说明
简单 Diff	3 次	移动 E, C, D
双端 Diff	1 次	移动 E
快速 Diff	1 次	移动 E（利用前缀优化）

算法	移动操作数	说明
简单 Diff	4 次	移动所有节点
双端 Diff	2 次	利用双端比较
快速 Diff	2 次	利用 LIS 优化

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

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

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

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

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

Vue 中的三种 Diff 算法详解

什么是 Diff 算法

简单理解

为什么需要 Diff 算法？

Vue 2.x 双端 Diff 算法

核心思想

算法步骤

具体示例

示例 1：简单移动

代码实现（简化版）

优缺点

Vue 3.x 快速 Diff 算法

核心思想

算法步骤

具体示例

示例 1：前缀后缀相同

示例 2：复杂乱序

代码实现（简化版）

优缺点

简单 Diff 算法

核心思想

算法步骤

具体示例

示例 1：简单场景

代码实现（简化版）

优缺点

三种算法对比

性能对比表

场景对比示例

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

场景 2：完全乱序

场景 3：只改变顺序

选择建议

实际应用场景

场景 1：列表排序

场景 2：动态添加/删除

场景 3：过滤列表

总结

核心要点

学习建议

参考资料

微信扫一扫，关注极客日志

更多推荐文章

相关免费在线工具