Vue 3源码极客之：`Patch`函数的`diffing`算法：如何处理`VNode`的`key`变更和列表移动。

各位靓仔靓女，欢迎来到 Vue 3 源码极客修炼课堂！我是你们的讲师，人称“Bug终结者”的码农老王。今天咱要聊点硬核的，关于 Vue 3 的 patch 函数里，那个让人又爱又恨的 diffing 算法，特别是它怎么优雅地处理 VNode 的 key 变更和列表移动。准备好了吗？Let’s roll！

开场白：key 的重要性，以及 diffing 的目的

在 Vue 的世界里，key 就像是 VNode 的身份证，它让 Vue 能够高效地追踪和更新列表中的元素。想象一下，你有一堆照片，如果没有编号，你想重新排列它们，是不是得一张张比对，确定哪张是哪张？有了编号（key），Vue 就能直接根据 key 值来判断 VNode 是否相同，从而避免不必要的 DOM 操作。

diffing 算法的目的，说白了，就是找出新旧 VNode 之间的差异，然后只更新那些真正改变了的部分。这样就能大幅提升性能，避免直接暴力地重新渲染整个列表。这就像装修房子，如果只是墙面脏了，咱就刷墙，而不是把房子推倒重建。

patch 函数概览：diffing 的舞台

patch 函数是 Vue 更新 DOM 的核心，它负责将新的 VNode (Virtual Node，虚拟节点) 树与旧的 VNode 树进行比较，然后将差异应用到真实的 DOM 上。diffing 算法就藏在这个函数里，它决定了如何高效地找出这些差异。

在 Vue 3 中，patch 函数的基本流程大概是这样的：

1. 类型判断： 首先判断新旧 VNode 的类型是否相同。如果类型不同，那没啥好说的，直接替换整个节点。
2. Props 更新： 如果类型相同，就更新节点的属性 (props)。
3. 子节点更新： 这是 diffing 算法发挥作用的地方。它会比较新旧 VNode 的子节点，找出差异，并进行相应的更新操作。

今天咱们重点聊聊第三步，也就是子节点更新，特别是当子节点是列表，并且 key 发生变更或列表移动时，Vue 是怎么处理的。

diffing 算法的核心：新旧列表的比较

当 VNode 的子节点是列表时，diffing 算法会采用一种更复杂的策略来比较新旧列表。它会尽可能地复用现有的 DOM 节点，而不是简单地创建和销毁节点。

Vue 3 的 diffing 算法借鉴了 Snabbdom 的一些思想，它主要通过以下几个步骤来优化列表更新：

1. 简单情况处理： 首先处理一些简单的情况，比如新旧列表都为空，或者新列表为空，或者旧列表为空。这些情况可以直接进行相应的插入或删除操作。
2. 首尾节点比较： 从新旧列表的头部和尾部开始比较节点。如果头部节点相同，就直接更新；如果尾部节点相同，也直接更新。这样可以快速处理列表头部或尾部新增或删除节点的情况。
3. 中间节点比较： 如果头部和尾部节点都不同，就进入最复杂的中间节点比较阶段。Vue 会尝试在新旧列表中找到相同的节点，并进行移动或更新操作。

key 的作用：让 diffing 算法更聪明

key 在 diffing 算法中扮演着至关重要的角色。它让 Vue 能够更准确地识别哪些节点是相同的，哪些节点是新增的，哪些节点是被移动的。

如果没有 key，Vue 只能通过节点的类型和内容来判断是否相同。这样很容易出错，比如当列表中的节点内容相同，但顺序发生变化时，Vue 可能会错误地认为这些节点没有变化，从而导致不正确的更新。

有了 key，Vue 就可以直接根据 key 值来判断节点是否相同。即使节点的顺序发生变化，Vue 也能正确地识别出这些节点，并进行相应的移动操作。

代码示例：深入理解 diffing 过程

为了更好地理解 diffing 算法，咱们来看一个简单的代码示例。假设我们有以下的新旧两个列表：

• 旧列表： [A, B, C, D, E]，每个元素都有一个唯一的 key。
• 新列表： [A, C, B, E, F]，其中 B 和 C 的位置发生了互换，新增了 F。

下面是模拟 diffing 过程的关键步骤（简化版）：

function patchKeyedChildren(
  c1, // 旧子节点列表
  c2, // 新子节点列表
  container, // 父节点
  anchor // 插入位置
) {
  let i = 0;
  const l2 = c2.length;
  let e1 = c1.length - 1; // 旧列表结束索引
  let e2 = l2 - 1; // 新列表结束索引

  // 1. 从头开始比较，找到相同的前缀
  while (i <= e1 && i <= e2) {
    const n1 = c1[i];
    const n2 = c2[i];
    if (isSameVNodeType(n1, n2)) {
      patch(n1, n2, container, anchor); // 递归 patch
    } else {
      break;
    }
    i++;
  }

  // 2. 从尾开始比较，找到相同的后缀
  while (i <= e1 && i <= e2) {
    const n1 = c1[e1];
    const n2 = c2[e2];
    if (isSameVNodeType(n1, n2)) {
      patch(n1, n2, container, anchor); // 递归 patch
    } else {
      break;
    }
    e1--;
    e2--;
  }

  // 3. 新增节点
  if (i > e1) {
    if (i <= e2) {
      const nextPos = e2 + 1;
      const anchor = nextPos < l2 ? c2[nextPos].el : null;
      while (i <= e2) {
        patch(null, c2[i], container, anchor); // 创建新节点并插入
        i++;
      }
    }
  }

  // 4. 删除节点
  else if (i > e2) {
    while (i <= e1) {
      unmount(c1[i]); // 移除旧节点
      i++;
    }
  }

  // 5. 处理未知序列，核心 diff 算法
  else {
    let s1 = i; // 旧列表开始索引
    let s2 = i; // 新列表开始索引

    // 5.1 构建 key -> index 的 map
    const keyToNewIndexMap = new Map();
    for (let j = s2; j <= e2; j++) {
      const nextChild = c2[j];
      if (nextChild.key != null) {
        keyToNewIndexMap.set(nextChild.key, j);
      }
    }

    // 5.2 遍历旧列表，寻找可复用的节点
    let patched = 0;
    const toBePatched = e2 - s2 + 1;
    const newIndexToOldIndexMap = new Array(toBePatched);
    for (let k = 0; k < toBePatched; k++) newIndexToOldIndexMap[k] = 0;

    for (let j = s1; j <= e1; j++) {
      const prevChild = c1[j];
      if (patched >= toBePatched) {
        // 所有新节点都处理过了，剩下的旧节点直接删除
        unmount(prevChild);
        continue;
      }

      let newIndex;
      if (prevChild.key != null) {
        newIndex = keyToNewIndexMap.get(prevChild.key);
      } else {
        // 没有 key 的节点，只能遍历新列表寻找
        for (let k = s2; k <= e2; k++) {
          if (
            newIndexToOldIndexMap[k - s2] === 0 &&
            isSameVNodeType(prevChild, c2[k])
          ) {
            newIndex = k;
            break;
          }
        }
      }

      if (newIndex === undefined) {
        // 旧节点在新列表中不存在，直接删除
        unmount(prevChild);
      } else {
        // 新旧节点都存在，进行 patch
        newIndexToOldIndexMap[newIndex - s2] = j + 1;
        patch(prevChild, c2[newIndex], container, null);
        patched++;
      }
    }

    // 5.3 移动和新增节点
    // 获取最长递增子序列
    const increasingNewIndexSequence = getSequence(newIndexToOldIndexMap);
    let j = increasingNewIndexSequence.length - 1;

    for (let k = toBePatched - 1; k >= 0; k--) {
      const index = s2 + k;
      const current = c2[index];
      const anchor = index + 1 < l2 ? c2[index + 1].el : null;

      if (newIndexToOldIndexMap[k] === 0) {
        // 新节点，创建并插入
        patch(null, current, container, anchor);
      } else if (increasingNewIndexSequence[j] === k) {
        // 是最长递增子序列中的节点，不需要移动
        j--;
      } else {
        // 需要移动的节点
        move(current, container, anchor);
      }
    }
  }
}

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

function unmount(vnode) {
  // 移除节点的逻辑
  console.log("unmount", vnode);
}

function patch(n1, n2, container, anchor) {
  // patch 节点的逻辑 (更新属性，递归子节点等)
  console.log("patch", n1, n2);
  if (!n1) {
    // 创建新节点
    console.log("create", n2);
  }
}

function move(vnode, container, anchor) {
  // 移动节点的逻辑
  console.log("move", vnode);
}

function getSequence(arr) {
  const p = arr.slice();
  const result = [0];
  let i, j, u, v, c;
  const len = arr.length;
  for (i = 0; i < len; i++) {
    const arrI = arr[i];
    if (arrI !== 0) {
      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;
}

// 模拟 VNode
function createVNode(type, key) {
  return { type, key };
}

// 模拟数据
const oldChildren = [
  createVNode("div", "A"),
  createVNode("div", "B"),
  createVNode("div", "C"),
  createVNode("div", "D"),
  createVNode("div", "E"),
];
const newChildren = [
  createVNode("div", "A"),
  createVNode("div", "C"),
  createVNode("div", "B"),
  createVNode("div", "E"),
  createVNode("div", "F"),
];

const container = document.createElement("div"); // 假设这是父节点
patchKeyedChildren(oldChildren, newChildren, container, null);

在这个例子中，patchKeyedChildren 函数模拟了 diffing 算法的核心逻辑。它首先比较新旧列表的头部和尾部，然后构建 keyToNewIndexMap 来快速查找节点在新列表中的位置。接着，它遍历旧列表，尝试在新列表中找到相同的节点。如果找到了，就进行 patch 操作；如果没有找到，就删除旧节点。最后，它遍历新列表，将新增的节点插入到正确的位置。

其中，getSequence函数用于计算最长递增子序列，其目的是为了尽可能减少DOM的移动次数。只有不在最长递增子序列中的节点才需要移动。

流程图：更直观地理解 diffing 过程

为了更直观地理解 diffing 过程，咱们可以画一个简单的流程图：

graph LR
    A[开始] --> B{新旧列表是否为空？};
    B -- 是 --> C{插入或删除节点};
    B -- 否 --> D{从头开始比较};
    D --> E{头部节点相同？};
    E -- 是 --> F{更新头部节点};
    E -- 否 --> G{从尾开始比较};
    G --> H{尾部节点相同？};
    H -- 是 --> I{更新尾部节点};
    H -- 否 --> J{构建 key -> index 的 map};
    J --> K{遍历旧列表，寻找可复用的节点};
    K --> L{找到可复用的节点？};
    L -- 是 --> M{更新节点};
    L -- 否 --> N{删除旧节点};
    M --> O{遍历新列表，插入新增的节点};
    N --> O;
    O --> P[结束];
    F --> D;
    I --> G;

表格总结：各种情况的处理方式

为了更清晰地总结 diffing 算法的处理方式，咱们可以用一个表格来概括：

情况	处理方式
新旧列表都为空	不做任何操作
新列表为空	删除旧列表中的所有节点
旧列表为空	将新列表中的所有节点插入到 DOM 中
头部节点相同	更新头部节点，并继续比较下一个节点
尾部节点相同	更新尾部节点，并继续比较前一个节点
节点 key 相同	更新节点，并比较其子节点
节点 key 不同	如果旧节点在新列表中存在，则移动旧节点到新位置；如果旧节点在新列表中不存在，则删除旧节点；如果新节点在旧列表中不存在，则创建新节点

注意事项：key 的使用规范

在使用 key 时，需要注意以下几点：

• 唯一性： key 必须是唯一的，否则 Vue 无法正确地识别节点。
• 稳定性： key 应该尽量保持稳定，不要频繁地改变。如果 key 经常变化，Vue 可能会错误地认为节点发生了变化，从而导致不必要的 DOM 操作。
• 避免使用 index： 尽量避免使用 index 作为 key，除非列表是静态的，不会发生变化。因为当列表发生移动或删除操作时，index 可能会发生变化，从而导致 Vue 无法正确地识别节点。

总结：diffing 算法的精髓

diffing 算法是 Vue 性能优化的关键。它通过比较新旧 VNode 树，找出差异，并只更新那些真正改变了的部分，从而避免不必要的 DOM 操作。key 在 diffing 算法中扮演着至关重要的角色，它让 Vue 能够更准确地识别节点，并进行相应的移动或更新操作。

结束语：成为 diffing 大师的秘诀

要成为 diffing 大师，光靠听讲是不够的，还需要多看源码，多写代码，多思考。只有真正理解了 diffing 算法的原理，才能在实际开发中灵活运用，写出高性能的 Vue 应用。

今天的课程就到这里，希望大家有所收获！下次再见！

(悄悄告诉你：理解了 diffing 算法，面试 Vue 高级岗位的时候，腰杆都能挺得更直！)