Diff算法的简单介绍

原生 DOM 更新

graph LR A[数据变化] –> B[手动查找DOM节点] B –> C[直接修改节点属性] C –> D[处理相关依赖节点]

Diff 算法更新

graph LR A[应用状态变更] –> B[生成新的虚拟 DOM 树] B –> C[Diff 算法比较新旧树] C –> D[计算最小变更集] D –> E[批量更新真实 DOM]

什么是 Diff 算法?

Diff 算法(差异算法) 是一种用于比较两个树形结构(通常是虚拟 DOM 树)之间的差异,并计算出最小变更集的高效算法。它是现代前端框架(如 React, Vue, Angular 等)实现高性能渲染的核心机制之一。

核心思想

  1. 比较对象:比较的是内存中表示 UI 结构的 JavaScript 对象(虚拟 DOM 树),而非直接操作浏览器中笨重的真实 DOM。
  2. 找出差异:精确找出新旧两棵虚拟 DOM 树中哪些节点发生了变化(增、删、改、移)。
  3. 最小化操作:只将必要的、最少的变更应用到真实 DOM 上,避免不必要的渲染开销。

Diff 算法的作用

  1. 性能优化(核心作用):

    • 减少 DOM 操作成本:直接操作真实 DOM(尤其是涉及布局重排和重绘)是浏览器中最昂贵的操作之一。Diff 算法确保只更新真正变化的部分。
    • 批量更新:框架可以将 Diff 计算出的多个变更集合并成一次批量的 DOM 操作,进一步提高效率。
    • 避免全量更新:无需在每次状态变化时都销毁整个旧 DOM 树并重建整个新 DOM 树。
  2. 简化开发逻辑:

    • 声明式编程:开发者只需关注“目标 UI 状态应该是什么样子”(描述新的虚拟 DOM),而无需手动编写繁琐的“如何从当前状态变过去”的命令式代码(如 document.getElementById(...).appendChild(...))。Diff 算法和渲染引擎自动处理更新过程。
    • 关注点分离:开发者聚焦于业务逻辑和状态管理,框架负责高效的 UI 更新。
  3. 跨平台能力的基础:

    • 虚拟 DOM 和 Diff 算法提供了一层抽象。计算出的最小变更集不仅可以应用于浏览器 DOM,也可以应用于 Native 组件(React Native)、Canvas、WebGL,甚至服务端渲染。

为什么需要实现 Diff 算法?

实现 Diff 算法是为了解决直接操作真实 DOM 带来的严重性能瓶颈和开发体验问题

  1. 直接操作 DOM 的代价高昂

    • 每次 DOM 操作(尤其是修改布局属性)都可能触发浏览器的 重排(Reflow)重绘(Repaint) ,这是非常消耗 CPU 和 GPU 资源的操作。
    • 频繁或低效的 DOM 更新会导致界面卡顿、响应迟缓,用户体验变差。
  2. 手动更新 DOM 复杂且易错

    • 在复杂的 Web 应用中,随着状态变化,需要精确计算出哪些 DOM 元素需要添加、删除、修改属性或移动位置。
    • 手动编写这些更新逻辑极其繁琐、容易出错,且代码难以维护。例如,在一个动态列表中插入一项,可能需要精确找到插入点、更新后续元素的索引、处理动画状态等。
  3. 全量更新不可行

    • 最简单粗暴的更新方式是:销毁整个旧的 DOM 树,然后用新的状态重建并插入整个新的 DOM 树。
    • 这种方法在简单静态页面上也许可行,但对于复杂动态应用:
      • 性能灾难:销毁和重建整个树的开销巨大,导致界面严重闪烁或卡死。
      • 状态丢失:输入框焦点、滚动条位置、组件内部状态(如视频播放进度)等都会被重置,破坏用户体验。

Diff 算法的优势解决方案

  1. 虚拟 DOM:轻量级的中间层

    • 在内存中创建真实 DOM 的轻量级 JavaScript 对象表示。创建和操作 JS 对象远比操作真实 DOM 快得多。
    • 状态变化时,先创建新的虚拟 DOM 树。
  2. Diff:计算最小变更

    • 使用优化过的 Diff 算法(通常是 O(n) 复杂度)对比新旧虚拟 DOM 树。
    • 精准找出节点级别的差异(元素类型变化?属性变化?子节点顺序变化?)。
  3. 高效更新

    • 将 Diff 计算出的 “补丁”(Patch) 应用到真实 DOM 上。
    • 只更新变化的部分,最大程度减少昂贵的 DOM 操作和重排/重绘。

原生 DOM 操作的”精确更新”假象(作用的补充说明)

在原生 JavaScript 中,开发者确实可以手动精确更新特定节点

// 原生 DOM 精确更新示例
const priceElement = document.getElementById("product-price");
priceElement.textContent = newPrice;

表面优势

  • 只更新一个节点
  • 没有额外开销
  • 性能看似高效

实际挑战

  1. 状态追踪复杂度:在大型应用中,需要手动维护数百个元素引用
  2. 依赖关系管理:当多个数据影响同一元素时,更新逻辑变得复杂
  3. 动态内容处理:列表渲染、条件渲染需要大量手动 DOM 操作
  4. 跨组件更新:深层嵌套组件更新需要穿透多层结构
特性 原生 DOM 操作 Vue 更新机制
更新范围 开发者手动控制 组件级渲染 + Diff 优化
状态管理 手动维护引用 响应式系统自动追踪
列表更新 手动操作每个元素 Key 优化 + 最小变更
条件渲染 手动添加/移除节点 自动 DOM 操作
性能开销 无框架开销 虚拟 DOM 比较开销
开发效率 低(代码量大) 高(声明式编程)
可维护性 随复杂度下降 始终保持良好
跨平台 需重写逻辑 同一套代码

Vue 中的 Diff 算法工作原理

组件级颗粒度

  1. 当响应式数据变化时,Vue 会:

    • 标记依赖该数据的组件为”待更新”
    • 触发这些组件的重新渲染
    // Vue 3 响应式更新伪代码
    effect(() => {
      if (state.dirty) {
        patchComponent(component); // 更新组件
      }
    });
    
  2. 未受影响的组件不会重新渲染,保持高性能

节点级颗粒度(Diff 核心)

在组件内部,Vue 使用优化后的 Diff 算法:

  1. 同级比较:只比较相同层级的节点

  2. 标签类型检查

    <!-- 标签不同 ⇒ 销毁重建 -->
    <div>
      →
      <section>
        <!-- 标签相同 ⇒ 更新属性 -->
        <div class="old">
          →
          <div class="new"></div>
        </div>
      </section>
    </div>
    
  3. Key 优化策略(列表渲染核心):

    <!-- 无 key ⇒ 顺序比较 -->
    <li v-for="item in items">{{ item }}</li>
    
    <!-- 有 key ⇒ 精确匹配 -->
    <li v-for="item in items" :key="item.id">{{ item.name }}</li>
    

Vue 3 的突破性优化

Vue 3 通过编译时优化解决颗粒度问题:

flowchart LR A[模板] –> B[编译优化] B –> C[静态提升] B –> D[Patch Flags] B –> E[Block Tree]

  1. 静态提升:将静态内容移出渲染函数
  2. Patch Flags:标记动态节点类型
    // 编译后的虚拟DOM节点
    {
      type: 'div',
      props: { class: 'active' },
      patchFlag: 1 // 1表示只有class是动态的
    }
    
  3. Block Tree:追踪动态节点树,跳过静态子树比较

Diff 算法的关键优化策略

1. 列表渲染与 key 的重要性

颗粒度问题最明显的场景

<!-- 问题:列表重新排序 -->
<ul>
  <li v-for="item in items">{{ item.text }}</li>
</ul>

<!-- 解决方案:key 提供节点标识 -->
<ul>
  <li v-for="item in items" :key="item.id">{{ item.text }}</li>
</ul>
  • 无 key:默认使用”就地复用”策略,可能导致状态错乱
  • 有 key:精确匹配节点,保持组件状态(如输入框内容)

2. 组件复用策略

Vue 通过组件签名决定是否复用:

// 决定组件复用的关键因素
function canPatch(oldVNode, newVNode) {
  return (
    oldVNode.type === newVNode.type && // 相同组件
    oldVNode.key === newVNode.key // 相同key
  );
}

3. 静态内容跳过

Vue 3 的突破性改进:

<!-- 静态内容只生成一次 -->
<div>
  <!-- 静态提升内容 -->
  <header>Site Title</header>

  <!-- 动态内容 -->
  <main>{{ dynamicContent }}</main>
</div>
  • Diff 算法完全跳过静态节点比较
  • 性能接近手动优化的 DOM 操作

为什么 Vue 需要 Diff 算法?

  1. 解决颗粒度鸿沟:弥合细粒度的数据变化与粗粒度的 UI 更新之间的差距
  2. 开发体验优先:让开发者专注于业务逻辑,无需手动优化 DOM 操作
  3. 平台抽象层:为 SSR、小程序等目标平台提供统一更新机制
  4. 性能与效率平衡:在框架开销与手动优化成本间取得最佳平衡点

性能对比基准

更新方式 1000 节点更新时间 内存开销 开发成本
直接 DOM 操作 10ms 极高
全量虚拟 DOM 50ms
Vue 3 优化 Diff 15ms

总结

  1. 在内存中(虚拟 DOM)进行高效的差异计算
  2. 找出新旧 UI 表示之间的最小变更集
  3. 只将必要的更新应用到昂贵的真实 DOM 上

vue2 双端比较算法(双指针 diff)简单示例,主要是处理 v-for 关键之一:

function sameVNode(a, b) {
  return a.key === b.key && a.tag === b.tag;
}

function updateChildren(parentEl, 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];

  // 创建旧节点 key 映射
  const keyMap = {};
  for (let i = oldStartIdx; i <= oldEndIdx; i++) {
    const key = oldCh[i].key;
    if (key) keyMap[key] = i;
  }

  // 可视化步骤
  const steps = [];

  while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
    // 1. 头头比较
    if (sameVNode(oldStartVnode, newStartVnode)) {
      steps.push(`头头比较: ${oldStartVnode.key} 和 ${newStartVnode.key} 匹配`);
      oldStartVnode = oldCh[++oldStartIdx];
      newStartVnode = newCh[++newStartIdx];
    }
    // 2. 尾尾比较
    else if (sameVNode(oldEndVnode, newEndVnode)) {
      steps.push(`尾尾比较: ${oldEndVnode.key} 和 ${newEndVnode.key} 匹配`);
      oldEndVnode = oldCh[--oldEndIdx];
      newEndVnode = newCh[--newEndIdx];
    }
    // 3. 头尾比较
    else if (sameVNode(oldStartVnode, newEndVnode)) {
      steps.push(`头尾比较: ${oldStartVnode.key} 移动到末尾`);
      parentEl.insertBefore(oldStartVnode.el, oldEndVnode.el.nextSibling);
      oldStartVnode = oldCh[++oldStartIdx];
      newEndVnode = newCh[--newEndIdx];
    }
    // 4. 尾头比较
    else if (sameVNode(oldEndVnode, newStartVnode)) {
      steps.push(`尾头比较: ${oldEndVnode.key} 移动到开头`);
      parentEl.insertBefore(oldEndVnode.el, oldStartVnode.el);
      oldEndVnode = oldCh[--oldEndIdx];
      newStartVnode = newCh[++newStartIdx];
    }
    // 5. key 匹配
    else {
      const idxInOld = keyMap[newStartVnode.key];

      if (idxInOld !== undefined) {
        const vnodeToMove = oldCh[idxInOld];
        steps.push(
          `Key匹配: 找到 ${newStartVnode.key} 并移动到位置 ${newStartIdx}`
        );
        parentEl.insertBefore(vnodeToMove.el, oldStartVnode.el);
        oldCh[idxInOld] = undefined;
      } else {
        steps.push(`创建节点: ${newStartVnode.key} 是新增节点`);
        parentEl.insertBefore(createElm(newStartVnode), oldStartVnode.el);
      }

      newStartVnode = newCh[++newStartIdx];
    }
  }

  // 添加新节点
  if (oldStartIdx > oldEndIdx) {
    for (let i = newStartIdx; i <= newEndIdx; i++) {
      steps.push(`添加节点: ${newCh[i].key}`);
      parentEl.appendChild(createElm(newCh[i]));
    }
  }
  // 删除旧节点
  else {
    for (let i = oldStartIdx; i <= oldEndIdx; i++) {
      if (oldCh[i]) {
        steps.push(`删除节点: ${oldCh[i].key}`);
        parentEl.removeChild(oldCh[i].el);
      }
    }
  }

  return steps;
}

function createElm(vnode) {
  const el = document.createElement("div");
  el.className = "node";
  el.textContent = vnode.key + (vnode.key === "E" ? " (新增节点)" : "");
  el.dataset.key = vnode.key;
  vnode.el = el;
  return el;
}

vue3 的简化 patchKeyedChildren 示例(伪代码):

// --------------- 工具函数 ---------------
function isSameVNode(n1, n2) {
  return n1.key === n2.key && n1.type === n2.type;
}
function createElement(vnode) {
  const el = document.createElement(vnode.type);
  if (typeof vnode.children === "string") el.textContent = vnode.children;
  vnode.el = el;
  return el;
}
function mountElement(vnode, container, anchor = null) {
  const el = createElement(vnode);
  container.insertBefore(el, anchor);
}
function unmount(vnode) {
  vnode.el && vnode.el.parentNode.removeChild(vnode.el);
}

// --------------- 核心 patch ---------------
function patch(n1, n2, container) {
  if (!n1) {
    // mount
    mountElement(n2, container);
  } else if (!isSameVNode(n1, n2)) {
    // 替换
    unmount(n1);
    mountElement(n2, container);
  } else {
    // 同类型节点 → 复用 el
    const el = (n2.el = n1.el);
    if (typeof n2.children === "string") {
      if (n2.children !== n1.children) el.textContent = n2.children;
    } else {
      patchKeyedChildren(n1.children, n2.children, el);
    }
  }
}

// --------------- Vue3 风格列表 Diff ---------------
function patchKeyedChildren(c1 = [], c2 = [], container) {
  let i = 0;
  let e1 = c1.length - 1;
  let e2 = c2.length - 1;

  // 1️⃣ 从头同步
  while (i <= e1 && i <= e2 && isSameVNode(c1[i], c2[i])) {
    patch(c1[i], c2[i], container);
    i++;
  }

  // 2️⃣ 从尾同步
  while (i <= e1 && i <= e2 && isSameVNode(c1[e1], c2[e2])) {
    patch(c1[e1], c2[e2], container);
    e1--;
    e2--;
  }

  // 3️⃣ 新列表更长 → 挂载
  if (i > e1) {
    const anchor = c2[e2 + 1]?.el || null;
    while (i <= e2) mountElement(c2[i++], container, anchor);
    return;
  }

  // 4️⃣ 旧列表更长 → 卸载
  if (i > e2) {
    while (i <= e1) unmount(c1[i++]);
    return;
  }

  // 5️⃣ 处理中间乱序区间
  const s1 = i,
    s2 = i;
  const keyToNewIdx = new Map();
  for (let j = s2; j <= e2; j++) keyToNewIdx.set(c2[j].key, j);

  const toBePatched = e2 - s2 + 1;
  const newIdxToOldIdx = new Array(toBePatched).fill(0);

  // 5.1 先遍历旧节点,找到可复用的并 patch
  for (let j = s1; j <= e1; j++) {
    const oldVNode = c1[j];
    const newIdx = keyToNewIdx.get(oldVNode.key);
    if (newIdx === undefined) {
      unmount(oldVNode); // 不存在 → 删除
    } else {
      newIdxToOldIdx[newIdx - s2] = j + 1; // 记录旧索引(+1 防 0)
      patch(oldVNode, c2[newIdx], container); // 复用并递归 patch
    }
  }

  // 5.2 计算 LIS,确定哪些节点可以不动
  const increasingSeq = getLIS(newIdxToOldIdx);
  let seqIdx = increasingSeq.length - 1;

  // 5.3 倒序遍历新列表,边插入边移动
  for (let j = toBePatched - 1; j >= 0; j--) {
    const newIdx = j + s2;
    const newVNode = c2[newIdx];
    const anchor = c2[newIdx + 1]?.el || null;

    if (newIdxToOldIdx[j] === 0) {
      // 新节点
      mountElement(newVNode, container, anchor);
    } else if (j !== increasingSeq[seqIdx]) {
      // 需要移动
      container.insertBefore(newVNode.el, anchor);
    } else {
      // 在 LIS 中,保持不动
      seqIdx--;
    }
  }
}

// --------------- 最长递增子序列 (O(n log n)) ---------------
function getLIS(arr) {
  const p = arr.slice();
  const result = [];
  for (let i = 0; i < arr.length; i++) {
    const n = arr[i];
    if (n === 0) continue; // 0 表示新节点,占位
    let last = result[result.length - 1];
    if (last === undefined || n > arr[last]) {
      p[i] = last;
      result.push(i);
      continue;
    }
    // 二分替换
    let l = 0,
      r = result.length - 1;
    while (l < r) {
      const mid = (l + r) >> 1;
      if (arr[result[mid]] < n) l = mid + 1;
      else r = mid;
    }
    if (n < arr[result[l]]) {
      if (l > 0) p[i] = result[l - 1];
      result[l] = i;
    }
  }
  // 反向回溯出索引序列
  let u = result.length,
    v = result[result.length - 1];
  const lis = Array(u);
  while (u--) {
    lis[u] = v;
    v = p[v];
  }
  return lis;
}
逻辑点 Vue 2 Vue 3
Patch 函数名 updateChildren patchKeyedChildren
Diff 方法 双端比较 + keyMap 双端比较 + keyMap + LIS(更优)
是否支持 Fragment (需要虚拟根) 支持
DOM 操作 insertBefore, removeChild 等 同上

注:以上主要是个人学习使用,各位大佬自行辨别,有错误请指正会进行修改更新。