重构人生

外观

Diff 算法详解 Vue 2

约 4250 字大约 14 分钟

2025-06-24

Vue 2 的虚拟 DOM Diff 算法是其高效渲染的核心，它通过精细的比较策略最小化 DOM 操作。

一、Diff 算法的基本概念

Diff 算法是用于比较两棵虚拟 DOM 树的差异，并计算出最小更新操作的算法。Vue 2 采用的是同级比较、深度优先的策略。

核心特点

  1. 同级比较：不会跨层级比较，大幅减少复杂度
  2. 双端比较：同时从新旧节点的两端向中间比较
  3. 深度优先：对有子节点的节点，优先进行子节点的比较和更新。
  4. key 的重要性：key 是识别节点的唯一标识，帮助算法高效复用节点。如果没有 key，就调用 sameVnode() 方法进行简单的比较。

触发起点

在 Vue 中，Vue 通过收集 data() 对象的依赖，观察其变化，并执行相应的副作用函数，来完成相应的处理和页面的刷新。diff 算法中会执行一系列的操作：DOM 更新、钩子函数执行等，然后调用 updated() 钩子函数，执行更新后的回调处理。

其触发的入口可能有两种：

  • 节点本身：修改元素本身的属性;页面第一次初始化;显示、隐藏、移除某个元素（v-if / v-show），
  • 父节点：列表中出现元素的新增、删除、移动(v-for)

在这个过程中，元素本身或者父元素对应的 虚拟节点，就是触发 diff 算法的起点，其前后状态就是触发 patch() 函数的参数： oldVnode 和 newVnode。

文字总结整个流程

文字总结整个流程

对外暴露的方法：patch(oldVnode, vnode)，进入 diff 流程

  1. 旧节点不存在：直接创建新节点
  2. 新节点不存在：直接移除旧节点
  3. 新旧节点都存在：进行比较
    1. 比较两个节点是否是相同节点：sameVnode(oldVnode, vnode)
      1. 不同节点：直接移除旧节点，创建新节点
      2. 相同节点：继续比较节点的属性和子节点，patchVnode(oldVnode, vnode)
        1. 比较属性是否有变化，有变化则更新属性
        2. 比较子节点是否有变化：
          1. 旧节点有子节点，新节点没有子节点：直接移除旧节点的子节点
          2. 旧节点没有子节点，新节点有子节点：直接将新节点的子节点添加到旧节点
          3. 新旧节点都有子节点：进行同层子节点的比较和更新 updateChildren()
            1. 新首 == 旧首
              1. 从 3.2 开始递归比较两个节点的属性和子节点
              2. 移动新首、旧首指针
            2. 新尾 == 旧尾
              1. 从 3.2 开始递归比较两个节点的属性和子节点
              2. 移动新尾、旧尾指针
            3. 新尾 == 旧首
              1. 从 3.2 开始递归比较两个节点的属性和子节点
              2. 移动旧首节点到旧尾节点的前边
              3. 移动旧首、新尾的指针
            4. 新首 == 旧尾
              1. 从 3.2 开始递归比较两个节点的属性和子节点
              2. 将旧尾节点移动到旧首节点的前面
              3. 移动新首、旧尾指针
            5. 都不相同，尝试在旧节点列表里，能不能找到新首
              1. 能找到：
                1. 从 3.2 开始递归比较两个节点的属性和子节点
                2. 将可复用的旧节点移动到旧首节点的前面
                3. 移动旧首指针
              2. 不能找到：
                1. 创建新节点，插入到旧首节点的前面
                2. 移动新首指针
            6. 一直移动到旧队列或者新队列完成遍历
              1. 旧队列有剩余节点：移除旧队列的节点
              2. 新队列有剩余节点：在旧队列的末尾创建新队列的节点

流程图

二、Diff 算法的具体流程

代码位置：node_modules\vue\src\core\vdom\patch.js

1、patch() 入口

patch() 方法是最终的 Diff 算法的入口，它负责新旧节点的比较和更新。该方法会被挂载到 Vue.prototype.__patch__ 上

Vue.prototype.__patch__ = inBrowser ? patch : noop;

调用场景有两种：

  1. 初始渲染：当 Vue 实例首次渲染时，调用 patch() 进行初始挂载
  2. 更新渲染：当数据发生变化，触发视图更新时，也会调用 patch() 进行比较和更新
/**
 * 核心的 patch 函数，负责新旧节点的比较和更新
 * @param {VNode} oldVnode - 旧的虚拟节点树
 * @param {VNode} vnode - 新的虚拟节点
 * @param {boolean} hydrating - 是否服务端渲染
 * @param {boolean} removeOnly - 是否只移除节点
 */
function patch(oldVnode, vnode, hydrating, removeOnly) {
  // 如果新节点不存在
  if (isUndef(vnode)) {
    // 如果存在旧节点，直接调用 Destroy 钩子移除旧节点
    if (isDef(oldVnode)) invokeDestroyHook(oldVnode);
    return;
  }
  // 是否初始化挂载
  let isInitialPatch = false;
  // 定义插入队列，用于收集需要插入的节点
  const insertedVnodeQueue: any[] = [];
  // 老节点不存在，说明是节点初始化时挂载
  if (isUndef(oldVnode)) {
    isInitialPatch = true;
    // 空挂载、类似组件、创建新的根元素
    createElm(vnode, insertedVnodeQueue);
  } else {
    // 是否为真实的 DOM 元素，为 true 走 SSR 的Diff
    const isRealElement = isDef(oldVnode.nodeType);
    if (!isRealElement && sameVnode(oldVnode, vnode)) {
      // 如果是虚拟节点，并且新老元素相同，进行内容的详细比较
      patchVnode(oldVnode, vnode, insertedVnodeQueue, null, null, removeOnly);
    } else {
      // 省略了一些 SSR Diff 处理代码
      // ....................
      const oldElm = oldVnode.elm;
      const parentElm = nodeOps.parentNode(oldElm);
      // 创建新节点
      createElm(
        vnode,
        insertedVnodeQueue,
        // extremely rare edge case: do not insert if old element is in a
        // leaving transition. Only happens when combining transition +
        // keep-alive + HOCs. (#4590)
        oldElm._leaveCb ? null : parentElm,
        nodeOps.nextSibling(oldElm)
      );

      // 处理父节点的一些状态

      // 销毁旧节点
      if (isDef(parentElm)) {
        // 情况1：存在父节点
        removeVnodes([oldVnode], 0, 0); // 从DOM中移除旧节点
      } else if (isDef(oldVnode.tag)) {
        // 情况2：无父节点但旧节点是有效标签
        invokeDestroyHook(oldVnode); // 只触发销毁钩子不操作DOM
      }
    }
  }
  // 执行插入钩子
  invokeInsertHook(vnode, insertedVnodeQueue, isInitialPatch);
  return vnode.elm;
}

2、sameVnode() 判断当前节点是否相同

sameVnode() 用于判断两个虚拟节点是否是相同节点，即具有相同的 key、asyncFactory、tag、isComment 等属性。

主要是通过 key 和 选择器类型来比较

/**
 * 判断两个VNode是否是相同节点
 * 比较key、asyncFactory、tag、isComment等属性
 * 如果是输入框，还需要比较类型、属性、状态等
 */
function sameVnode(a, b) {
  return (
    a.key === b.key && // key 节点的key，用于diff算法优化
    a.asyncFactory === b.asyncFactory && // asyncFactory 异步组件工厂函数
    ((a.tag === b.tag && // tag 节点标签名
      a.isComment === b.isComment && // isComment 是否是注释节点
      isDef(a.data) === isDef(b.data) && // data 节点数据，包含属性、事件等
      sameInputType(a, b)) || // 比较二者是否为相同的input。类型、属性、状态是否相同
      // 如果是异步组件的占位符，则检查错误状态
      (isTrue(a.isAsyncPlaceholder) && isUndef(b.asyncFactory.error)))
  );
}

3、patchVnode() 节点内容比较

当确定是相同节点后，进入 patchVnode 流程：

  1. 依次调用自身组件 prepatch 钩子
  2. 依次调用自身组件和模块的 update 钩子
  3. 处理节点本身
  4. 处理子节点
function patchVnode(oldVnode, vnode) {
  const elm = (vnode.elm = oldVnode.elm);
  const oldCh = oldVnode.children;
  const ch = vnode.children;
  const data = vnode.data;
  let i;
  // 执行 prepatch 钩子
  if (isDef(data) && isDef((i = data.hook)) && isDef((i = i.prepatch))) {
    i(oldVnode, vnode);
  }
  // 1. 依次调用自身组件和模块的 update 钩子
  if (isDef(data) && isPatchable(vnode)) {
    for (i = 0; i < cbs.update.length; ++i) {
      cbs.update[i](oldVnode, vnode);
      if (isDef((i = data.hook)) && isDef((i = i.update))) {
        i(oldVnode, vnode);
      }
    }
  }
  // 2. 处理本节点
  if (isUndef(vnode.text)) {
    // 新节点是否存在文本
    if (isDef(oldCh) && isDef(ch)) {
      if (oldCh !== ch) {
        // 新旧都有子节点，进入子节点比较 updateChildren
        updateChildren(elm, oldCh, ch);
      }
    } else if (isDef(ch)) {
      // 新节点是否存在子节点
      if (__DEV__) {
        checkDuplicateKeys(ch); // 检查是否有重复的key
      }
      // 只有新节点有子节点，添加新子节点
      addVnodes(elm, null, ch, 0, ch.length - 1); // 将ch 列表里的所有节点添加到 elm 下
    } else if (isDef(oldCh)) {
      // 只有旧节点有子节点，移除全部旧子节点
      // 移除的同时需要执行Rmover、Destroy钩子
      removeVnodes(oldCh, 0, oldCh.length - 1);
    }
  } else if (oldVnode.text !== vnode.text) {
    elm.textContent = vnode.text; // 文本节点内容不同，直接更新文本
  }
  // 执行 postpatch 钩子
  if (isDef(data)) {
    if (isDef((i = data.hook)) && isDef((i = i.postpatch))) i(oldVnode, vnode);
  }
}

上述代码中 cbs 是 Vue 实例化时创建的钩子函数集合，用于在节点更新时执行相应的钩子函数。

//
import platformModules from 'web/runtime/modules/index'
import baseModules from 'core/vdom/modules/index'
const modules = baseModules.concat(platformModules) as any[]
// 合并后的模块
// const modules = [attrs, klass, events, domProps, style, transition, ref, directives]

const hooks = ['create', 'activate', 'update', 'remove', 'destroy']
const cbs: any = {}

for (i = 0; i < hooks.length; ++i) {
  let hook = hooks[i];
  cbs[hook] = []
  for (j = 0; j < modules.length; ++j) {
    let fn = modules[j][hook]; // 例如：attrs.create，klass.remove
    if (isDef(fn)) { // 如果模块上绑定了钩子函数
      cbs[hook].push(fn)
    }
  }
}
// 实例相当于把同类的钩子都放到一起
cbs = {
  create: [fn1, fn2, ...],   // 创建时的钩子
  activate: [fn...],         // 激活keep-alive组件时的钩子
  update: [fn...],           // 更新时的钩子
  remove: [fn...],           // 移除时的钩子
  destroy: [fn...]           // 销毁时的钩子
};

4、updateChildren() 双端比较算法详解

这是 Vue 2 Diff 算法的核心部分，对子节点列表采用双端交叉对比策略：

在对比节点内容的 patchVnode() 方法中，完成比较本层节点，和递归调用 updateChildren() 方法，完成下一层子节点的比较。

function updateChildren(parentElm, oldCh, newCh) {
  let oldStartIdx = 0;
  let newStartIdx = 0;
  let oldEndIdx = oldCh.length - 1;
  let newEndIdx = newCh.length - 1;
  let oldStartVnode = oldCh[0];
  let oldEndVnode = oldCh[oldEndIdx];
  let newStartVnode = newCh[0];
  let newEndVnode = newCh[newEndIdx];
  let oldKeyToIdx; // oldCh下元素的 key 和 id 的映射关系

  // 进行双端对比
  while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
    if (isUndef(oldStartVnode)) {
      oldStartVnode = oldCh[++oldStartIdx]; // Vnode has been moved left
    } else if (isUndef(oldEndVnode)) {
      oldEndVnode = oldCh[--oldEndIdx];
    }
    // 1. 旧首 vs 新首
    else if (sameVnode(oldStartVnode, newStartVnode)) {
      // 二者相同，意味着不需要移动，可以直接对比内容进行更新
      patchVnode(oldStartVnode, newStartVnode);
      // 移动旧首、新首的指针
      oldStartVnode = oldCh[++oldStartIdx];
      newStartVnode = newCh[++newStartIdx];
    }
    // 2. 旧尾 vs 新尾
    else if (sameVnode(oldEndVnode, newEndVnode)) {
      // 二者相同，同样意味着不需要移动，可以直接对比内容进行更新
      patchVnode(oldEndVnode, newEndVnode);
      // 移动旧尾、新尾的指针
      oldEndVnode = oldCh[--oldEndIdx];
      newEndVnode = newCh[--newEndIdx];
    }
    // 3. 旧首 vs 新尾
    else if (sameVnode(oldStartVnode, newEndVnode)) {
      // 进行对比更新
      patchVnode(oldStartVnode, newEndVnode);
      // 需要将旧首节点移动到旧尾节点的前面
      parentElm.insertBefore(oldStartVnode.elm, oldEndVnode.elm.nextSibling);
      // 移动旧首、新尾的指针
      oldStartVnode = oldCh[++oldStartIdx];
      newEndVnode = newCh[--newEndIdx];
    }
    // 4. 旧尾 vs 新首
    else if (sameVnode(oldEndVnode, newStartVnode)) {
      // 进行对比更新
      patchVnode(oldEndVnode, newStartVnode);
      // 需要将旧尾节点移动到旧首节点的前面
      parentElm.insertBefore(oldEndVnode.elm, oldStartVnode.elm);
      // 移动旧尾、新首的指针
      oldEndVnode = oldCh[--oldEndIdx];
      newStartVnode = newCh[++newStartIdx];
    }
    // 5. 以上都不匹配，尝试用key查找
    else {
      // 创建旧节点key到index的映射表
      if (isUndef(oldKeyToIdx)) {
        oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx);
      }
      // 找到新首节点在旧子节点列表中的位置
      // 需要判断节点有没有设置 key 属性的值
      idxInOld = isDef(newStartVnode.key)
        ? oldKeyToIdx[newStartVnode.key]
        : findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx);
      if (isUndef(idxInOld)) {
        // 没找到，说明新首没有对应的节点，需要创建新节点
        createElm(newStartVnode, parentElm, oldStartVnode.elm);
      } else {
        // 新首在旧节点序列中存在，为可复用节点
        vnodeToMove = oldCh[idxInOld];
        // 再次判断，确保节点相同
        if (sameVnode(vnodeToMove, newStartVnode)) {
          // 对比更新可复用节点
          patchVnode(vnodeToMove, newStartVnode);
          oldCh[idxInOld] = undefined;
          // 复用节点位置更新，将可复用节点移动到旧首节点的前面
          parentElm.insertBefore(vnodeToMove.elm, oldStartVnode.elm);
        } else {
          // key相同但节点不同，创建新节点
          createElm(newStartVnode, parentElm, oldStartVnode.elm);
        }
      }
      // 移动新首
      newStartVnode = newCh[++newStartIdx];
    }
  }
  // 双端对比结束
  // 旧列表遍历完了，说明新列表有剩，需要添加新列表中剩余的节点
  if (oldStartIdx > oldEndIdx) {
    // 旧节点先遍历完，添加剩余新节点
    addVnodes(parentElm, null, newCh, newStartIdx, newEndIdx);
    // 旧列表遍历完了，说明旧列表有剩，需要删除旧列表中剩余的节点
  } else if (newStartIdx > newEndIdx) {
    // 新节点先遍历完，删除剩余旧节点
    removeVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx);
  }
}
/**
 * 创建key到索引的映射表
 * 用于快速查找具有key的子节点在旧子节点列表中的位置
 */
function createKeyToOldIdx(children, beginIdx, endIdx) {
  let i, key;
  const map = {};
  for (i = beginIdx; i <= endIdx; ++i) {
    key = children[i].key;
    if (isDef(key)) map[key] = i;
  }
  return map;
}
/**
 * 在旧子节点列表中查找匹配的节点索引
 * 用于没有key的子节点比较
 */
function findIdxInOld(node, oldCh, start, end) {
  for (let i = start; i < end; i++) {
    const c = oldCh[i];
    if (isDef(c) && sameVnode(node, c)) return i;
  }
}

三、为什么选用双端比较算法？

首先我们来看如果使用传统的比较方式，应该怎么实现：

let repeatNum = 0; // 可复用节点的数量
// 按照新节点去遍历
newCh.forEach((newItem, index) => {
  // 在旧节点里寻找可复用的节点
  let oldIndex = oldCh.findIndex((oldItem) => sameNode(oldItem, newItem));
  if (oldIndex >= 0) {
    // 找到可复用的节点，先深度优先进行精细对比和子节点对比。
    patchVnode(oldItem, oldCh[oldIndex]);
    // 对比结束后，将可复用节点移动到指定位置
    parentElm.insertBefore(oldItem.elm, parentElm.children[index]);
    repeatNum++; // 可复用节点数量加1
  } else {
    // 节点不存在，创建该节点，并插入到指定位置
    chElm = createElm(newItem);
    parentElm.insertBefore(chElm, parentElm.children[index]);
  }
});

上边的代码执行完以后，此时的 DOM 节点的前半部分与 newCh 保持一致，后半部分为旧节点中待删除的部分。经过分析，我们可以得到待删除的节点数据应该为 ：旧节点的数量 - 可复用节点的数量。

因此我们可以执行代码，完成多余节点的删除：

let len = oldCh.length - repeatNum; // 待删除节点的数量
if (len > 0) {
  for (let i = 0; i < len; i++) {
    // 逐个删除最末尾的元素
    parentElm.removeChild(parentElm.lastChild);
  }
}

此时我们发现，传统对比的算法复杂度是 O(mn) 或者 O(n^2)，而双端对比的算法复杂度最优情况下是最优情况下为 O(n)，最差情况下为 O(n^2)。

因此双端比较算法的复杂度是优于传统对比算法的。

四、深度优先 vs 广度优先

为什么 Vue 要选择深度优先作为比较策略？

深度优先的算法复杂度是优于广度优先的。

我们在进行双端对比时，遇到相同节点直接递归调用 patchVnode() 函数，如果节点相同且被判定为不需要更新，就不再进行子树的比较了。而广度优先，首先需要完成同层比较，然后再双层循环调用 patchVnode() 函数，对比相同节点。很明显，深度优先的算法复杂度是比广度优先低的。并且代码高更易读，更简洁。

与虚拟组件树的递归结构、更新顺序匹配

Vue 的模板和组件是嵌套的树形结构（例如父子组件、嵌套的 v-if/v-for 等）。深度优先遍历天然适合递归处理这种结构，可以自然地遍历到最深层级的子节点，再回溯处理父节点。

Vue 的渲染和补丁（patch）过程是递归的。深度优先遍历保证在更新 DOM 时，子节点的更新优先于父节点，避免父节点更新导致子节点重复渲染（例如父节点的 class 变化不应触发子节点的重新渲染）。

四、Diff 算法的优化策略

  1. 双端交叉对比：同时从新旧子节点的首尾向中间比较，共进行 4 种尝试：

    • 旧首 vs 新首
    • 旧尾 vs 新尾
    • 旧首 vs 新尾
    • 旧尾 vs 新首

  2. key 的重要性：

    • 没有 key 时，只能按顺序比较，复用率低
    • 有 key 时，可以建立映射表直接查找可复用节点
    • 错误使用 key（如 index）会导致性能下降

  3. 原地复用：

    • 对于相同节点，直接复用 DOM 元素，仅更新变化的部分
    • 减少 DOM 创建和销毁的开销

五、Vue 2 Diff 的局限性

  1. 同级比较：不会跨层级移动节点，导致某些情况下无法最优复用
  2. 静态树优化不足：Vue 3 在这方面做了改进
  3. 全量 Diff：即使只有小部分变化，也要比较整个子树

六、与 Vue 3 Diff 的对比

特性Vue 2Vue 3
算法类型双端比较快速路径+双端比较
静态提升无有
事件缓存无有
Patch Flag无有
最长递增子序列无用于优化移动

七、最佳实践

  1. 合理使用 key：

    • 使用唯一且稳定的值作为 key
    • 避免使用 index 作为 key（除非列表是纯静态的）

  2. 减少动态节点层级：

    • 扁平化 DOM 结构有助于提高 Diff 效率

  3. 合理拆分组件：

    • 组件的边界会阻断 Diff 过程，合理拆分可以减少比较范围

Vue 2 的 Diff 算法通过这种精细的比较策略，在大多数情况下都能提供高效的 DOM 更新，理解其原理有助于我们编写更高效的 Vue 代码。

更新日志

2025/8/24 08:17
查看所有更新日志
  • e7112-1于