Vue3 快速 Diff

oldChildren: [a, b, c, d, e, f, g]
newChildren: [a, h, i, c, d, e, b, g]

一、预处理：头尾双端匹配

初始化指针

当前处理的起始索引：i = 0（遍历起点）

旧列表的结束索引：oldEndIndex = oldChildren.length - 1 = 6

新列表的结束索引：newEndIndex = newChildren.length - 1 = 7

oldChildren: [a, b, c, d, e, f, g]
              ↑                 ↑
              i=0               oldEndIndex=6

newChildren: [a, h, i, c, d, e, b, g]
              ↑                    ↑
              i=0                  newEndIndex=7

头部预处理

1. i = 0
   oldChildren[i] === a, newChildren[i] === a
   相同 → 复用
   i++

2. i = 1
   oldChildren[i] === b, newChildren[i] === h
   不同 → 停止

前置匹配结束，i = 1

while (i <= oldEndIndex && i <= newEndIndex) {
    if (sameVNodeType(oldChildren[i], newChildren[i])) {
        // 节点可复用，执行更新操作（属性/文本等）
        patch(oldChildren[i], newChildren[i]);
        i++; // 继续匹配下一个
    } else {
        break; // 遇到不匹配节点，终止头部匹配
    }
}

尾部预处理

1. oldEndIndex = 6, newEndIndex = 7
   oldChildren[oldEndIndex] === g, newChildren[newEndIndex] === g
   相同 → 复用
   oldEndIndex--, newEndIndex--

2. oldEndIndex = 5, newEndIndex = 6
   oldChildren[oldEndIndex] === f, newChildren[newEndIndex] === b
   不同 → 停止

后置匹配结束，oldEndIndex = 5, newEndIndex = 6

while (oldEndIndex >= i && newEndIndex >= i) {
     if (sameVNodeType(oldChildren[oldEndIndex], newChildren[newEndIndex])) {
         // 节点可复用，执行更新操作
         patch(oldChildren[oldEndIndex], newChildren[newEndIndex]);
         oldEndIndex--;
         newEndIndex--;
     } else {
         break; // 遇到不匹配节点，终止尾部匹配
     }
 }

预处理后的序列变为：

oldChildren: [a, b, c, d, e, f, g]
                 ↑           ↑
                 i=1         oldEndIndex=5

newChildren: [a, h, i, c, d, e, b, g]
                 ↑              ↑
                 i=1            newEndIndex=6

二、处理剩余节点

情况 1：旧列表处理完，新列表有剩余（新增节点）

当 i > oldEndIndex && i <= newEndIndex 时，说明旧列表已处理完，但新列表还有剩余节点，这些节点都是新增的

if (i > oldEndIndex && i <= newEndIndex) {
    // 新增节点需要插入到正确位置：以新列表剩余节点的下一个节点为锚点（插入到锚点前）
    const anchor = newEndIndex + 1 < newChildren.length
        ? newChildren[newEndIndex + 1].el // 锚点为新列表剩余节点的下一个节点的DOM
        : null; // 若没有下一个节点，锚点为null（插入到容器末尾）
    while (i <= newEndIndex) {
        // 第一个参数为null表示创建新节点，anchor指定插入位置
        patch(null, newChildren[i], container, anchor);
        i++;
    }
    return;
}

情况 2：新列表处理完，旧列表有剩余（删除节点）

当 i > newEndIndex && i <= oldEndIndex 时，说明新列表已处理完，但旧列表还有剩余节点，这些节点需要删除

if (i> newEndIndex && i <= oldEndIndex) {
    while (i <= oldEndIndex) {
        unmount(oldChildren[i]); // 卸载剩余旧节点
        i++;
    }
    return;
}

情况 3：新旧列表都有剩余节点

这是最复杂的场景，需处理移动 / 新增 / 删除，需要通过 key 映射和 LIS 优化来处理。

下面定义几个变量方便理解：

  • oldMiddle：旧列表中间部分，未处理的旧节点

    • 取值范围：oldChildren[i...oldEndIndex]

    • 实际值：[b, c, d, e, f]

    • 实际索引：1 ~ 5

    • oldMiddleLength（长度）：oldEndIndex - i + 1

  • newMiddle：新列表中间部分，未处理的新节点

    • 取值范围：newChildren[i...newEndIndex]

    • 实际值：[h, i, c, d, e, b]

    • 实际索引 1 ~ 6

    • newMiddleLength（长度）：newEndIndex - i + 1

步骤 1：遍历 newMiddle，构建 keyToNewIndexMap

遍历 newMiddle，构建 keyToNewIndexMap: Map<key, index>，其键为新节点的 key，值为新节点的索引，用于快速查找旧节点在新列表中的位置。

const keyToNewIndexMap = new Map()
for (let j = i; j <= newEndIndex; j++) {
  keyToNewIndexMap.set(newChildren[j].key, j)
}

console.log(keyToNewIndexMap)
// {h: 1, i: 2, c: 3, d: 4, e: 5, b: 6}

步骤 2：根据 newMiddle 长度，创建 newIndexToOldIndexMap

根据 newMiddle 的长度，创建一个数组，初始全为 0，用于记录 新列表中间部分每个节点 是否能在旧列表中找到对应项，并记录其在旧列表中的位置。

const newIndexToOldIndexMap = new Array(newMiddleLength)
for (let j = 0; j < newMiddleLength; j++) newIndexToOldIndexMap[j] = 0
// [0, 0, 0, 0, 0, 0] 6个

步骤 3：遍历 oldMiddle，填充 newIndexToOldIndexMap

然后遍历 oldMiddle，填充 newIndexToOldIndexMap，用于记录新列表中间各节点在旧列表中的位置：

for (let j = i; j <= oldEndIndex; j++) {
    const oldChild = oldChildren[j];
    // 查找旧节点在新列表中的索引（通过key映射）
    const newIndex = keyToNewIndexMap.get(oldChild.key);

    if (newIndex == null) {
        // 旧节点在新列表中无对应节点 → 卸载
        unmount(oldChild);
    } else {
        // 找到对应新节点 → 可复用，执行更新
        patch(oldChild, newChildren[newIndex]);
        // 记录：新列表中位置 newIndex 的节点，对应旧列表中 j 位置的节点
        // 注意：newIndexToOldIndexMap 的索引是 (newIndex - i)
        newIndexToOldIndexMap[newIndex - i] = j + 1; // j + 1 是为了区分“未匹配”（0 表示新增）
    }
}

关键点解释：

  • newIndex - i：将新列表索引转换为 newIndexToOldIndexMap 的局部索引。

  • j + 1：为什么加 1？因为我们要用 0 来表示“这个新节点在旧列表中没有对应项”，所以存储的是 “旧索引 + 1”。这是 Vue 源码中的技巧。

回顾一下数据：

oldChildren: [a, b, c, d, e, f, g]
                 ↑           ↑
                 i=1         oldEndIndex=5

newChildren: [a, h, i, c, d, e, b, g]
                 ↑              ↑
                 i=1            newEndIndex=6

keyToNewIndexMap：{h: 1, i: 2, c: 3, d: 4, e: 5, b: 6}
oldChildoldIndexnewIndex动作记录
b16patch(b, b)newIndexToOldIndexMap[6-1=5] = 1 + 1 = 2
c23patch(c, c)newIndexToOldIndexMap[3-1=2] = 2 + 1 = 3
d34patch(d, d)newIndexToOldIndexMap[4-1=3] = 3 + 1 = 4
e45patch(e, e)newIndexToOldIndexMap[5-1=4] = 4 + 1 = 5
f5undefinedunmount(f)不记录

执行后：

newChild index:       1, 2, 3, 4, 5, 6
newMiddle index：     0, 1, 2, 3, 4, 5
newMiddle：          [h, i, c, d, e, b]
oldChild index:       ?, ?, 2, 3, 4, 1
oldChild index + 1:   0, 0, 3, 4, 5, 2

所以：newIndexToOldIndexMap = [0, 0, 3, 4, 5, 2]

  • 该数组的第一个数据 “0” 表示：新列表中间部分的第一个节点（h）在旧列表中不存在，需要新增

  • 第二个数据 “0” 表示：新列表中间部分的第二个节点（i）在旧列表中不存在，需要新增

  • 第三个数据 “3” 表示：新列表中间部分的第三个节点（c）与旧列表索引为 “3-1=2” 的节点相同（相同的节点就可以被复用，至于复用的方式是移动位置还是保持原来位置不变？这个先不管，后面再说）

  • 第四个数据 “4” 表示：新列表中间部分的第四个节点（d）与旧列表索引为 “4-1=3” 的节点相同…

  • …以此类推

三、LIS（最长递增子序列）优化移动

Vue3 会基于 newIndexToOldIndexMap 计算一个 最长递增子序列（LIS），表示哪些节点原本就是按顺序的，不需要移动。这是一种优化手段，可以减少 DOM 操作。

// 根据 newIndexToOldIndexMap 计算出最长递增子序列
const increasingNewIndexSequence = getSequence(newIndexToOldIndexMap);
// increasingNewIndexSequence[j] 表示 LIS 的最后一个索引
let j = increasingNewIndexSequence.length - 1;

getSequence() 就是计算 LIS 的函数，知道就行，有时间再完善这一部分。

四、逆序遍历 newMiddle，创建和移动节点

什么是逆序遍历？

Vue3 采用 从后往前遍历 newMiddle，是为了利用 DOM 插入特性：parent.insertBefore(newNode, referenceNode) ，如果 referenceNode 是 null，就插到最后；否则插在它前面。

从后往前处理，那么每次插入的新节点或移动的节点，其参考节点（锚点）已经就位，可以正确插入。

// 逆序遍历新列表中间部分，从后往前，处理新增和移动
for (let k = newMiddleLength - 1; k >= 0; k--) {
    // 因为要插入到锚点节点之前
    // 例如当遍历到 newMiddle 的最后一个节点时，锚点其实是 newMiddle 再后面的一个节点
    // 所以要 + 1
    const anchorIndex = k + i + 1;
    // 如果锚点的索引 >= newChildren 的长度，
    // 说明 newMiddle 的最后一个节点就是 newChildren 的最后一个节点
    // 所以 newEndIndex + 1 才会 >= newChildren.length
    // 这时候就要把锚点置空，因为 referenceNode 是 null，就会插到最后
    const anchor = anchorIndex < newChildren.length ? newChildren[anchorIndex].el : null;

    // 当前遍历到的新节点
    const nextChild = newChildren[k + i];

    if (newIndexToOldIndexMap[k] === 0) {
        // 没有对应的 oldChild → 创建新节点
        // container 是 父级 DOM 容器，也就是这些子节点（children）所挂载的 父元素。
        patch(null, nextChild, container, anchor);
    } else if (moved) {
        // 不等于 0，表示有对应的 oldChild，则只需要移动
        // 因为在"遍历旧列表中间部分，填充 newIndexToOldIndexMap" 阶段已经 patch 过，所以不需要再重复 patch 了
        if (j < 0 || k !== increasingNewIndexSequence[j]) {
            // 不在 LIS 中 → 需要移动
            move(nextChild, container, anchor);
        } else {
            // 在 LIS 中，不需要动
            j--; // j 是 LIS 的最后一个索引
        }
    }
}

moved 的作用是什么？

moved 它是一个“顺序是否被打乱”的检测器。如果新旧列表中节点的相对顺序保持得很好，就可以用更简单的方式处理直接 patch，避免不必要的计算；如果顺序乱了，就需要启用更复杂的 LIS 算法来找出最优的移动方案。

旧列表：[a, b, c, d, e, f, g]

新列表：[a, h, i, c, d, e, b, g]

在我们的例子中，旧列表中关键节点的相对顺序是：

  • e 前面是 d，d 前面是 c，c 前面是 b

但是在新列表中：

  • e 前面是 d，d 前面是 c，b 后面是 b，相对顺序有变化，则 moved = true

为什么要逆序？如果是正序会怎样

oldMiddle：[b, c, d, e, f]

newMiddle：[h, i, c, d, e, b]

正序

先看正序：

  1. h 插入：anchor = i.el，但 i 还没创建 → anchor = null → 插到末尾 ❌

  2. i 插入：anchor = c.el，但 c 还没处理 → anchor = null → 插到末尾 ❌

  3. c,d,e：已在位，跳过

  4. b 插入：anchor = g.el，g 是后置节点，el 存在 → 插入到 g 前面 ✅

h 和 i 被插到末尾，顺序错乱！

逆序

再来看逆序：

  1. b：anchor = g.el → 存在 → 插入到 g 前面 ✅

  2. e：已在位，跳过

  3. d：跳过

  4. c：跳过

  5. i：anchor = c.el → 已就位 → 插入到 c 前面 ✅

  6. h：anchor = i.el → 已创建 → 插入到 i 前面 ✅

顺序正确！

原因

insertBefore(newNode, referenceNode) 依赖 referenceNode 存在，如果 referenceNode 不存在就会插入到末尾。

逆序可以保证 referenceNode 已就位，后面的节点已经处理完，el 存在。

正序时 referenceNode 可能不存在或位置错，就会导致插入位置错误。

五、完整流程

/**
 * Vue3 风格的 Diff 算法（修正并贴合源码）
 * @param {VNode[]} oldChildren - 旧的子节点列表
 * @param {VNode[]} newChildren - 新的子节点列表
 * @param {Element} container - 父容器 DOM 元素
 * @param {VNode} parentAnchor - 锚点（用于 insertBefore），通常是父级的 anchor 或 null
 */
function diff(oldChildren, newChildren, container) {
    let i = 0;
    let oldEndIndex = oldChildren.length - 1;
    let newEndIndex = newChildren.length - 1;

    // 1. 头尾预处理
    // 相同节点指key和类型均相同（由sameVNodeType判断）
    // 1.1 头部预处理：从头开始匹配相同节点（减少比对范围）
    while (i <= oldEndIndex && i <= newEndIndex) {
        if (sameVNodeType(oldChildren[i], newChildren[i])) {
            // 节点可复用，执行更新操作（属性/文本等）
            patch(oldChildren[i], newChildren[i]);
            i++; // 继续匹配下一个
        } else {
            break; // 遇到不匹配节点，终止头部匹配
        }
    }

    // 1.2. 尾部预处理：从尾开始匹配相同节点（进一步减少比对范围）
    while (oldEndIndex >= i && newEndIndex >= i) {
        if (sameVNodeType(oldChildren[oldEndIndex], newChildren[newEndIndex])) {
            // 节点可复用，执行更新操作
            patch(oldChildren[oldEndIndex], newChildren[newEndIndex]);
            oldEndIndex--;
            newEndIndex--;
        } else {
            break; // 遇到不匹配节点，终止尾部匹配
        }
    }

    // 2. 剩余节点处理：根据头尾预处理后的索引关系判断场景
    // 2.1 旧列表已处理完，新列表仍有剩余节点 → 全部新增
    if (i > oldEndIndex && i <= newEndIndex) {
        // 新增节点需要插入到正确位置：以新列表剩余节点的下一个节点为锚点（插入到锚点前）
        const anchor = newEndIndex + 1 < newChildren.length
            ? newChildren[newEndIndex + 1].el // 锚点为新列表剩余节点的下一个节点的DOM
            : null; // 若没有下一个节点，锚点为null（插入到容器末尾）
        while (i <= newEndIndex) {
            // 第一个参数为null表示创建新节点，anchor指定插入位置
            patch(null, newChildren[i], container, anchor);
            i++;
        }
        return;
    }

    // 2.2 新列表已处理完，旧列表仍有剩余节点 → 全部卸载
    if (i > newEndIndex && i <= oldEndIndex) {
        while (i <= oldEndIndex) {
            unmount(oldChildren[i]); // 卸载剩余旧节点
            i++;
        }
        return;
    }

    // 2.3 新旧列表均有剩余节点 → 处理中间乱序部分
    // 计算中间部分长度（相对于起始索引i的偏移）
    const oldMiddleLength = oldEndIndex - i + 1;
    const newMiddleLength = newEndIndex - i + 1;

    // 2.3.1 构建新列表中间部分的key→索引映射（用于快速查找旧节点在新列表中的位置）
    const keyToNewIndexMap = new Map();
    for (let j = i; j <= newEndIndex; j++) {
        keyToNewIndexMap.set(newChildren[j].key, j);
    }

    // 2.3.2 newIndexToOldIndexMap：用于记录新列表中间部分每个节点在旧列表中的索引（用于计算LIS）
    // 长度为新列表中间部分长度，初始值0表示该新节点在旧列表中无对应节点（需新增）
    const newIndexToOldIndexMap = new Array(newMiddleLength).fill(0);

    // 2.3.3 遍历旧列表中间部分，标记可复用节点并卸载无用节点
    for (let j = i; j <= oldEndIndex; j++) {
        const oldChild = oldChildren[j];
        // 查找旧节点在新列表中的索引（通过key映射）
        const newIndex = keyToNewIndexMap.get(oldChild.key);

        if (newIndex == null) {
            // 旧节点在新列表中无对应节点 → 卸载
            unmount(oldChild);
        } else {
            // 找到对应新节点 → 可复用，执行更新
            patch(oldChild, newChildren[newIndex]);
            // 记录：新列表中位置 newIndex 的节点，对应旧列表中 j 位置的节点
            // 注意：newIndexToOldIndexMap 的索引是 (newIndex - i)
            newIndexToOldIndexMap[newIndex - i] = j + 1; // j + 1 是为了区分“未匹配”（0 表示新增）
        }
    }

    // 3. 根据 newIndexToOldIndexMap 计算出最长递增子序列
    const increasingNewIndexSequence = getSequence(newIndexToOldIndexMap);
    // increasingNewIndexSequence[j] 表示 LIS 的最后一个索引
    let j = increasingNewIndexSequence.length - 1;

    // 4. 逆序遍历新列表中间部分，从后往前，处理新增和移动
    for (let k = newMiddleLength - 1; k >= 0; k--) {
        // 因为要插入到锚点节点之前
        // 例如当遍历到 newMiddle 的最后一个节点时，锚点其实是 newMiddle 再后面的一个节点
        // 所以要 + 1
        const anchorIndex = k + i + 1;
        // 如果锚点的索引 >= newChildren 的长度，
        // 说明 newMiddle 的最后一个节点就是 newChildren 的最后一个节点
        // 所以 newEndIndex + 1 才会 >= newChildren.length
        // 这时候就要把锚点置空，因为 referenceNode 是 null，就会插到最后
        const anchor = anchorIndex < newChildren.length ? newChildren[anchorIndex].el : null;

        // 当前遍历到的新节点
        const nextChild = newChildren[k + i];

        if (newIndexToOldIndexMap[k] === 0) {
            // 没有对应的 oldChild → 创建新节点
            // container 是 父级 DOM 容器，也就是这些子节点（children）所挂载的 父元素。
            patch(null, nextChild, container, anchor);
        } else if (moved) {
            // 不等于 0，表示有对应的 oldChild，则只需要移动
            // 因为在"遍历旧列表中间部分，填充 newIndexToOldIndexMap" 阶段已经 patch 过，所以不需要再重复 patch 了
            if (j < 0 || k !== increasingNewIndexSequence[j]) {
                // 不在 LIS 中 → 需要移动
                move(nextChild, container, anchor);
            } else {
                // 在 LIS 中，不需要动
                j--; // j 是 LIS 的最后一个索引
            }
        }
    }
}

通过这样的 Diff 算法，Vue3 能够以最小的 DOM 操作成本完成列表的更新，特别是通过 LIS 优化，大大减少了节点移动的次数。

源码地址：
https://github.com/vuejs/core/blob/main/packages/runtime-core/src/renderer.ts#L1763

# vue.js
Logo
AI Agent技术社区

Agent 垂直技术社区，欢迎活跃、内容共建。

更多推荐

cover

90%的人认为RAG和Agent分开做都不难，合在一起就废？可写简历:RAG+Agent合体全链路方案

avatar AI Agent技术社区

AI Agent编排：复杂工作流的自动化实现

在深入探讨Agent编排之前，我们首先需要明确什么是AI Agent。AI Agent是一个能够感知环境、做出决策并采取行动的自主实体。感知模块：接收和处理环境信息推理/决策模块：基于感知信息进行思考和决策行动模块：执行具体的操作（如调用工具、生成文本）记忆模块：存储历史信息和知识通信模块：与其他Agent或系统进行交互Agent编排（Agent Orchestration）是指对多个Agent的

avatar AI Agent技术社区

看病总是记不住医生说的？从“听完就忘”到“医嘱随时查”的完整解决方案

医疗信息的准确性直接关系到健康甚至生命。在问诊时，患者天然处于“弱势”——时间紧、信息多、情绪乱。过去我们只能靠脑子记、靠手写，结果就是“听时明白，出门就忘”。现在，随着AI语音技术和智能整理技术的成熟，我们已经有了一个非常成熟的解决方案。智在记录这套工具，本质上是一个“医疗信息伴侣”——它帮你把医生的每一句话变成可读、可查、可分享的结构化内容，让你从“害怕遗忘”的焦虑中解放出来。进诊室前打开录音

avatar AI Agent技术社区