为下个 offer 充电的前端er 🔋

Appearance

Vue Diff 算法核心笔记 ​

1. Diff 算法概述 ​

Diff (Difference) 算法是 Vue 中用于比较新旧两棵虚拟 DOM (Virtual DOM) 树的差异，并以最小的代价更新真实 DOM 的核心机制。这个过程也被称为 Patching。

核心思想：Diff 算法的目标不是改变虚拟 DOM，而是通过对比新旧虚拟 DOM 的差异，来决定如何最高效地操作真实 DOM。操作真实 DOM 的成本远高于操作 JavaScript 对象，因此 Diff 算法致力于最小化真实 DOM 的操作次数（包括创建、销毁、移动和属性更新）。

2. Diff 的触发时机 ​

Diff 过程并非在数据一变化就立即执行，而是嵌入在组件的更新流程中。

  1. 依赖收集：组件在创建时，会为其创建一个 Watcher。这个 Watcher 会执行一个包含 _render 和 _update 的函数。

    • 在执行 _render() 生成虚拟 DOM 的过程中，会读取组件的响应式数据（props 或 data）。
    • Watcher 会将自身作为依赖，被这些响应式数据收集起来。

  2. 触发更新：当响应式数据发生变化时，会通知其对应的 Watcher 重新执行。

  3. 执行更新函数：Watcher 的重新执行，会再次运行那个核心的更新函数。这个函数主要做两件事：

    • A. 生成新 VNode：调用 vm._render() 方法，根据最新的数据生成一棵新的虚拟 DOM 树。
    • B. 对比与更新：调用 vm._update() 方法，将新生成的 VNode 与组件上一次渲染时保存的旧 VNode (vm._vnode) 进行对比。Diff 算法就在 _update 方法中执行。
javascript
// 伪代码：理解 Watcher 与更新流程
// 每个组件实例都有一个渲染 Watcher
new Watcher(vm, () => {
  // 1. 生成新的虚拟 DOM 树
  const vnode = vm._render(); 
  
  // 2. 将新旧 vnode 传入，进行 patch/diff
  // vm._vnode 存储的是上一次渲染的旧 vnode
  vm._update(vnode); 
});

// vm._update 函数的核心逻辑
Vue.prototype._update = function (vnode) {
  const vm = this;
  const prevVnode = vm._vnode; // 获取旧 vnode
  vm._vnode = vnode; // 将当前 vnode 保存为下一次更新的“旧 vnode”

  // patch 函数是 diff 算法的真正实现
  vm.__patch__(prevVnode, vnode); 
}

3. Patch 核心流程 ​

patch 函数是 Diff 的具体实现。它遵循深度优先、同层比较的策略，不会进行跨层级的节点比较。

3.1 术语解释 ​

在深入流程之前，先理解几个关键术语：

  • <相同>：指两个虚拟节点可以被认为是同一个节点，可以进行就地复用和更新。判断标准：key 和 tag（标签名）都相同。对于 <input> 元素，还会额外比较 type 属性。
  • <新建元素>：根据一个 VNode 的信息（tag, data, children 等），创建一个全新的真实 DOM 元素，并将其挂载到 VNode 的 .elm 属性上。
  • <销毁元素>：从父节点中移除一个 VNode 对应的真实 DOM 元素（即 vnode.elm）。
  • <更新>：当两个 VNode <相同> 时，对它们进行详细对比，更新真实 DOM 的属性、事件、样式等，然后递归对比它们的子节点。
  • <对比子节点>：patch 流程中最复杂的部分，用于对比两组子节点数组。

3.2 对比根节点 ​

patch 函数接收新旧两个 VNode，首先对比根节点。

  • 旧 VNode 不存在：

    • 场景：组件首次渲染。
    • 操作：直接根据新 VNode 递归创建一整棵完整的真实 DOM 树，并挂载到指定位置。不涉及任何比较。

  • 旧 VNode 存在：

    • 情况一：根节点 <不相同>
      • 场景：根元素的 tag 或 key 发生了变化。
      • 操作：最直接的方式。销毁旧 VNode 对应的整个真实 DOM 树，然后根据新 VNode 创建全新的真实 DOM 树并替换。
    • 情况二：根节点 <相同>
      • 操作：进入 <更新> 流程。
        1. 将旧 VNode 的真实 DOM 元素 (oldVnode.elm) 引用赋给新 VNode (newVnode.elm = oldVnode.elm)，实现 DOM 复用。
        2. 对比新旧 VNode 的属性 (data)，将差异更新到复用的真实 DOM 元素上。
        3. 递归地 <对比子节点>。

3.3 对比子节点 (核心：双端比较算法) ​

这是 Vue Diff 算法的精髓，当两个节点的子节点都是数组时，通过高效的方式进行对比。

原则：尽可能复用 DOM 节点，尽量减少移动、创建和删除操作。

实现：使用四个指针，分别指向新旧两组子节点数组的头和尾。

  • oldStartIdx: 旧子节点数组的头部指针
  • oldEndIdx: 旧子节点数组的尾部指针
  • newStartIdx: 新子节点数组的头部指针
  • newEndIdx: 新子节点数组的尾部指针

在循环中，指针不断向中间靠拢，进行以下 4 种核心比较，只要命中一种，就继续下一轮循环：

  1. oldStartVnode vs newStartVnode (头头比较)

    • 如果 <相同>，则 patch 这两个节点，然后头指针都向后移动 ++。

  2. oldEndVnode vs newEndVnode (尾尾比较)

    • 如果 <相同>，则 patch 这两个节点，然后尾指针都向前移动 --。

  3. oldStartVnode vs newEndVnode (旧头 vs 新尾)

    • 如果 <相同>，则 patch 这两个节点，然后将旧头对应的真实 DOM 移动到队尾，旧头指针 ++，新尾指针 --。

  4. oldEndVnode vs newStartVnode (旧尾 vs 新头)

    • 如果 <相同>，则 patch 这两个节点，然后将旧尾对应的真实 DOM 移动到队首，旧尾指针 --，新头指针 ++。

如果以上 4 种情况都不匹配：

  • 会为旧的子节点列表创建一个 key 到 index 的映射表 (Map)。
  • 用新节点的头部 newStartVnode 的 key 去映射表中查找。
    • 如果找到了：说明旧列表中存在这个节点。patch 这两个节点，并将找到的旧节点对应的真实 DOM 移动到当前新列表处理位置的前面。
    • 如果没找到：说明这是一个全新的节点。 <新建元素> 并插入到当前位置。

循环结束后的处理：

  • 如果旧节点列表的指针已经交错 (oldStartIdx > oldEndIdx)，但新列表还有剩余节点，说明这些都是需要批量新建的节点。
  • 如果新节点列表的指针已经交错 (newStartIdx > newEndIdx)，但旧列表还有剩余节点，说明这些都是多余的、需要批量销毁的节点。

4. key 的重要性与应用 ​

key 的主要作用是在 Diff 算法对比子节点时，作为一个唯一标识，帮助 Vue 准确地识别和追踪节点，从而实现高效的复用和移动。

场景一：v-for 循环 ​

不使用 key，或使用 index 作为 key，在列表发生反转、插入、删除等顺序变化时，会导致效率问题。

  • 无 key 的情况：Vue 会采用“就地复用”策略，即简单地按照索引顺序对比。例如，将列表 [A, B, C] 变为 [C, B, A]，Vue 会认为：

    • A -> C (修改内容)
    • B -> B (内容不变)
    • C -> A (修改内容)
    • 这会导致大量不必要的 DOM 内容更新，而不是更高效的 DOM 移动。如果节点是组件，还会导致组件状态错乱。

  • 有 key 的情况：Vue 会根据 key 识别出 A, B, C 仍然是它们自身，只是位置变了。于是，Diff 算法会执行移动操作，而不是更新内容，效率更高，且能保持组件内部状态。

html
<li v-for="(item, index) in items" :key="index"> {{ item.text }} </li>

<li v-for="item in items" :key="item.id"> {{ item.text }} </li>

场景二：强制重新渲染 ​

利用 key 的唯一性，可以强制一个元素或组件被销毁并重新创建，而不是就地复用。这在需要完全重置组件状态的场景中非常有用。

示例：切换登录方式时，希望清空输入框内容。

html
<template>
  <div>
    <input v-if="isUsernameLogin" key="username-input" placeholder="请输入用户名">
    <input v-else key="phone-input" placeholder="请输入手机号">
    
    <button @click="isUsernameLogin = !isUsernameLogin">切换登录方式</button>
  </div>
</template>

如果不加 key，Vue 会认为前后两个 input 是 <相同> 的节点（tag 和 type 都相同），只会更新 placeholder 的文本，而 input 的 value（用户输入）作为其内部状态会被保留下来。

5. 面试参考回答 ​

当被问到 Vue 的 Diff 算法时，可以这样组织回答：

  1. 触发时机：首先，Diff 算法发生在组件数据更新后。Vue 通过 Watcher 监听到数据变化，然后会调用一个更新函数，这个函数内部会先执行 render 函数生成新的 VNode，然后调用 patch 函数，将新旧 VNode 进行比较，这个 patch 的过程就是 Diff。

  2. 核心策略：Diff 算法的核心是同层比较和深度优先。它只对比同一层级的节点，不会跨层级比较，这样能将时间复杂度从 O(n^3) 优化到 O(n)。

  3. Patch 过程：

    • 首先对比新旧根节点。如果两个节点类型不同或 key 不同，就直接销毁旧的 DOM，用新的 VNode 创建全新的 DOM。
    • 如果根节点相同，就复用这个 DOM 元素，更新其属性，然后递归地对比它们的子节点。

  4. 子节点对比 (精髓)：对比子节点是 Diff 最复杂的部分，Vue 采用了双端比较的优化算法。它通过在新旧两组子节点的头和尾设置四个指针，进行头对头、尾对尾、头对尾、尾对头的四次比较，尽可能地复用和移动节点。如果这四种情况都不匹配，才会通过 key 创建一个映射表来查找对应的旧节点进行移动或复用。如果找不到，才会创建新节点。

  5. key 的作用：最后，强调 key 的重要性。在 v-for 中，key 作为一个唯一的标识，能帮助 Diff 算法准确地识别节点，从而在列表顺序变化时，执行高效的移动操作，而不是低效的内容更新，避免了性能问题和状态错乱。同时，key 也可以被用来强制触发组件或元素的销毁和重建。