在 Vue 3 的渲染系统中，patch 过程是虚拟 DOM (VNode) 更新的核心，其背后是高效的 diff 算法。该算法负责将新旧 VNode 树进行对比，找出最小的 DOM 操作集合，以实现高性能的视图更新。本节将深入剖析 patch 过程的核心逻辑，重点解析 key 的作用、双端对比（Dual-mode Diffing）策略以及快速路径优化（如 sameVNodeType）。

---

一、patch 过程概览

patch 函数是 Vue 渲染器的“大脑”，其主要职责是：

1. 比较新旧 VNode：判断它们是否代表同一个节点。
2. 更新节点：如果节点可复用，则更新其属性、子节点等。
3. 替换节点：如果节点不可复用，则销毁旧节点，创建并挂载新节点。

patch 是一个递归过程，从根节点开始，逐层对比子节点。

function patch(n1, n2, container) {
  if (n1 && !isSameVNodeType(n1, n2)) {
    // 节点类型不同，直接替换
    unmount(n1);
    n1 = null;
  }

  if (n1 === null) {
    // 挂载新节点
    mount(n2, container);
  } else {
    // 更新现有节点
    patchElement(n1, n2);
  }
}

---

二、key 的作用：节点的唯一标识

key 是 VNode 上一个至关重要的属性，它为 diff 算法提供了节点的身份标识。

1. 为什么需要 key？

考虑一个列表：

// 旧 VNode 数组
const oldChildren = [
  h('li', { key: 'a' }, 'A'),
  h('li', { key: 'b' }, 'B'),
  h('li', { key: 'c' }, 'C')
];

// 新 VNode 数组（顺序改变）
const newChildren = [
  h('li', { key: 'c' }, 'C'),
  h('li', { key: 'a' }, 'A'),
  h('li', { key: 'b' }, 'B')
];

如果没有 key，diff 算法只能基于索引进行对比：

• old[0] vs new[0]：'A' vs 'C' → 不同，更新文本。
• old[1] vs new[1]：'B' vs 'A' → 不同，更新文本。
• old[2] vs new[2]：'C' vs 'B' → 不同，更新文本。

结果是三次文本更新，效率低下。

2. 有 key 时的优化

当存在 key 时，算法可以基于 key 进行映射：

• key: 'a' 从索引 0 移动到 1。
• key: 'b' 从索引 1 移动到 2。
• key: 'c' 从索引 2 移动到 0。

算法只需执行三次移动操作（move），而无需更新文本内容，性能大幅提升。

3. key 的最佳实践

• 避免使用索引作为 key：当列表顺序改变时，索引会变，失去身份标识作用。
• 使用稳定、唯一的值：如数据库 ID、UUID。
• 不稳定的 key 会适得其反：频繁变化的 key 会导致节点无法复用，每次都重新创建。

---

三、双端对比（Dual-mode Diffing）

Vue 3 采用了一种称为“双端对比”的 diff 策略，它通过两个指针（头尾指针）从数组的两端同时进行对比，以最大化复用效率。

1. 算法步骤

设 oldChildren 和 newChildren 为两个子节点数组。

1. 初始化指针：

   • oldStartIndex = 0, oldEndIndex = oldChildren.length - 1
   • newStartIndex = 0, newEndIndex = newChildren.length - 1

2. 循环对比，直到任一数组遍历完毕：

   • 头头对比：oldStart vs newStart
   • 尾尾对比：oldEnd vs newEnd
   • 头尾对比：oldStart vs newEnd
   • 尾头对比：oldEnd vs newStart

3. 匹配成功：复用节点，移动指针。

4. 匹配失败：进入“复杂 diff”阶段，使用 key 建立映射表进行查找。

2. 代码示例（简化）

while (oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex) {
  const oldStart = oldChildren[oldStartIndex];
  const oldEnd = oldChildren[oldEndIndex];
  const newStart = newChildren[newStartIndex];
  const newEnd = newChildren[newEndIndex];

  if (isSameVNodeType(oldStart, newStart)) {
    // 头头匹配
    patch(oldStart, newStart);
    oldStartIndex++;
    newStartIndex++;
  } else if (isSameVNodeType(oldEnd, newEnd)) {
    // 尾尾匹配
    patch(oldEnd, newEnd);
    oldEndIndex--;
    newEndIndex--;
  } else if (isSameVNodeType(oldStart, newEnd)) {
    // 头尾匹配：oldStart 移动到末尾
    patch(oldStart, newEnd);
    move(oldStart.el, parent, getNextSibling(oldEnd.el));
    oldStartIndex++;
    newEndIndex--;
  } else if (isSameVNodeType(oldEnd, newStart)) {
    // 尾头匹配：oldEnd 移动到开头
    patch(oldEnd, newStart);
    move(oldEnd.el, parent, oldStart.el);
    oldEndIndex--;
    newStartIndex++;
  } else {
    // 复杂情况，使用 key 查找
    break;
  }
}

3. 优势

双端对比能高效处理以下常见场景：

• 列表末尾添加/删除元素。
• 列表开头添加/删除元素。
• 列表整体反转。
• 列表部分元素移动。

---

四、快速路径优化：sameVNodeType

Vue 3 的 diff 算法包含多个“快速路径”优化，sameVNodeType 是最核心的一个。

1. sameVNodeType 函数

function isSameVNodeType(n1, n2) {
  return n1.type === n2.type && n1.key === n2.key;
}

它通过比较 type 和 key 来判断两个 VNode 是否代表同一个节点。

• type 相同：确保是同一类节点（如都是 div 或都是 MyComponent）。
• key 相同：确保是同一个实例。

2. 快速路径的执行

如果 isSameVNodeType(n1, n2) 为 true，算法会进入快速更新流程：

if (isSameVNodeType(n1, n2)) {
  // 节点可复用，直接 patch
  patchElement(n1, n2);
  // 更新引用
  n2.el = n1.el;
  n2.component = n1.component;
}

patchElement 会进一步比较 props、children 等，并应用 patchFlag 进行细粒度更新。

3. 避免不必要的操作

快速路径优化避免了：

• 销毁和重建 DOM 节点。
• 重新创建组件实例。
• 重新绑定事件监听器。

这些操作开销巨大，快速路径能显著提升性能。

---

五、复杂 diff 与 key 映射表

当双端对比无法继续时，算法进入复杂 diff 阶段：

1. 创建 key 映射表：

   const keyToNewIndexMap = new Map();
   for (let i = newStartIndex; i <= newEndIndex; i++) {
     const child = newChildren[i];
     if (child.key != null) {
       keyToNewIndexMap.set(child.key, i);
     }
   }

2. 遍历 oldChildren：

   • 对每个 oldChild，在 keyToNewIndexMap 中查找其 key。
   • 如果找到，说明节点可复用，执行 patch 并标记为已处理。
   • 如果未找到，说明节点被删除，执行 unmount。

3. 处理新增节点：

   • 遍历 keyToNewIndexMap，找出未被复用的新节点，执行 mount。

---

六、总结

Vue 3 的 patch 过程和 diff 算法通过一系列精巧的设计实现了高性能更新：

• key：为节点提供唯一身份标识，使算法能基于身份而非位置进行对比，是高效更新的基础。
• 双端对比：通过头尾指针从两端同时对比，高效处理列表的常见变更模式（添加、删除、移动）。
• 快速路径优化 (sameVNodeType)：通过 type 和 key 快速判断节点可复用性，避免昂贵的销毁和重建操作。
• patchFlag：编译时生成的优化标志，指导运行时只更新动态部分，实现细粒度更新。

这些机制协同工作，使得 Vue 能够以最小的 DOM 操作代价，将虚拟 DOM 的变化高效地同步到真实 DOM，为开发者提供了流畅的用户体验。理解这些底层逻辑，有助于编写更高效的 Vue 应用，尤其是在处理大型列表或复杂 UI 时。