15_第_10_章_双端_Diff_算法

约 8864 字大约 30 分钟

2026-10-05

这一章要反复用到一批词。它们在前面章节里都已经集中解释过，这里先用一张表一句话回顾，后面再出现时就不再重复解释：

词	一句话回顾
DOM（Document Object Model，文档对象模型）	浏览器里真实存在的一棵节点树，你打开开发者工具就能看到它。比喻：它就是已经交付的房子，看得见、摸得着
虚拟 DOM（virtual DOM，一个 vnode 就是它的一个片段）	用普通 JavaScript 对象（形如 `{ type, props, children }`）把“这个位置应该显示什么”描述出来的一份草稿。比喻：装修开工前画在纸上的施工草图——纸上画的房子
真实 DOM	真正挂在页面上的那棵节点树。比喻：按草图盖出来的毛坯真房子
`key`	你写在虚拟节点上的一个“身份证号”，用来告诉框架“这个节点和上次的那个是同一个东西”。比喻：给每件行李贴行李条号，箱子换来换去也认得出
`patch`（打补丁）	拿新的 vnode 去更新旧的 vnode 对应的真实 DOM，把有差异的地方补上。比喻：旧毛衣改小一码——毛线还是那团毛线，只改要改的地方
`el`	vnode 上的一个属性，指向这个 vnode 对应的真实 DOM 节点。比喻：设计图上标着“这一格对应真房子的哪一间”
复用（reuse）	新旧两个 vnode 的 `key` 相同，就认定它们是“同一个东西”，直接沿用原来的真实 DOM，不重新创建。比喻：还是那个同事，只是换了工位，工位不用重新布置
移动（move）	真实 DOM 节点本身不变，只改变它在父节点里的位置。比喻：书架上的《Vue.js 入门》从第 1 格挪到第 3 格——书没重印，只是换了格子
锚点（anchor）	一次插入 / 移动的参照物，语义是“插到这个节点的前面”。比喻：排队插队得有个参照点——“我插在老王前面”，老王就是锚点
挂载（mount）	创建一个全新的节点并插进页面。比喻：搬进来一件家里从来没有过的新家具
卸载（unmount）	把已经不需要的真实 DOM 节点从页面里删掉。比喻：把搬走后剩下的空位收拾干净
Diff	diff = difference（差异）。这里指“比较新旧两份描述，算出该改哪里”。比喻：两份菜谱对一下，只重做不一样的工序

上一章我们学了简单 Diff，它有个明显缺点：DOM 移动操作不是最优的。有时候本来只需 1 次移动就能搞定，简单 Diff 却要做 2 次。

这一章要讲的 双端 Diff，能用更少的移动次数完成同样的更新。

打个比方来理解两种 Diff 的差别：

简单 Diff 像是在一排队伍里一个一个挨着找：从头到尾找一遍，看看哪个老员工应该被调到新位置上。
双端 Diff 像是在一排队伍里从两头往中间夹：先比头、再比尾、再交叉比，比一次就能确定两端。

这一章我们会一步步拆解双端 Diff 怎么工作、为什么更优、以及它自己也有搞不定的时候。

10.1　双端比较的原理

什么是双端

双端（two-ended）：

顾名思义，“两个端点”。意思是同时看两组子节点的开头和结尾。

上一章的简单 Diff 对 DOM 的移动操作并不是最优的。我们拿上一章的例子来看，如图 10-1 所示。

图 10-1　新旧两组子节点及索引

在这个例子里：

旧子节点：p-1、p-2、p-3
新子节点：p-3、p-1、p-2

如果用简单 Diff 算法，要发生 2 次 DOM 移动：

图 10-2　两次 DOM 移动操作完成更新

第 1 次：把 p-1 移动到 p-3 后面
第 2 次：把 p-2 移动到 p-1 后面

但其实只需要 1 次 DOM 移动就够：把 p-3 直接挪到 p-1 前面。简单 Diff 做不到这一点，但本章的双端 Diff 可以做到。

图 10-3　把真实 DOM 节点 p-3 移动到真实 DOM 节点 p-1 前面

接下来我们就来讨论双端 Diff 算法的原理。

4 个索引指向两端

4 个索引（start/end index）：

双端 Diff 同时比较新旧两组子节点的两个端点，所以需要 4 个索引值，分别指向头尾。

oldStartIdx / newStartIdx：指向新旧两组子节点的头
oldEndIdx / newEndIdx：指向新旧两组子节点的尾

图 10-4　四个索引值，分别指向新旧两组子节点的端点

用代码来表达就是：

function patchChildren(n1, n2, container) {
  if (typeof n2.children === 'string') {
    // 省略部分代码
  } else if (Array.isArray(n2.children)) {
    // 封装 patchKeyedChildren 函数处理两组子节点
    patchKeyedChildren(n1, n2, container)
  } else {
    // 省略部分代码
  }
}

function patchKeyedChildren(n1, n2, container) {
  const oldChildren = n1.children
  const newChildren = n2.children
  // 四个索引值
  let oldStartIdx = 0
  let oldEndIdx = oldChildren.length - 1
  let newStartIdx = 0
  let newEndIdx = newChildren.length - 1
}

我们逐行看：

function patchChildren(n1, n2, container)：上一章就有的“打补丁”总入口。如果新 vnode 的 children 是数组，就把“两组子节点”的更新工作全部委托给 patchKeyedChildren。
const oldChildren = n1.children：拿到旧的一组子节点（旧数组）。
const newChildren = n2.children：拿到新的一组子节点（新数组）。
let oldStartIdx = 0：旧数组的“头指针”，一开始指向第 0 个。
let oldEndIdx = oldChildren.length - 1：旧数组的“尾指针”，一开始指向最后一个。
let newStartIdx = 0：新数组的头指针。
let newEndIdx = newChildren.length - 1：新数组的尾指针。

有了索引，还得有“索引指向的虚拟节点”才好比较。再加 4 个变量：

function patchKeyedChildren(n1, n2, container) {
  const oldChildren = n1.children
  const newChildren = n2.children
  let oldStartIdx = 0
  let oldEndIdx = oldChildren.length - 1
  let newStartIdx = 0
  let newEndIdx = newChildren.length - 1
  // 四个索引指向的 vnode 节点
  let oldStartVNode = oldChildren[oldStartIdx]
  let oldEndVNode = oldChildren[oldEndIdx]
  let newStartVNode = newChildren[newStartIdx]
  let newEndVNode = newChildren[newEndIdx]
}

oldStartVNode / oldEndVNode：旧子节点中的“头节点”和“尾节点”。
newStartVNode / newEndVNode：新子节点中的“头节点”和“尾节点”。

4 步比较循环

4 步比较循环（four-step loop）：

有了这 4 个节点，双端比较就开始了。每一轮比较都分成 4 个步骤，按顺序尝试。

如图 10-5 所示。

图 10-5　双端比较的方式

图 10-5 的简化示意（4 步比较）：

⚠️ 对着图 10-5 数一数：旧的一组子节点是 p-1、p-2、p-3、p-4，新的一组子节点是 p-4、p-2、p-1、p-3。这 4 个节点只是位置换了个样子，谁也没多谁也没少——所以有旧可循、可以复用。真实 DOM 此刻的顺序还是 p-1、p-2、p-3、p-4，等着被改成新顺序。

拿图 10-5 那个例子来说，4 步比较分别会这样：

步骤	比较的两个节点	`key`	结果
步骤 1	旧头 `p-1` vs 新头 `p-4`	不同	跳过
步骤 2	旧尾 `p-4` vs 新尾 `p-3`	不同	跳过
步骤 3	旧头 `p-1` vs 新尾 `p-3`	不同	跳过
步骤 4	旧尾 `p-4` vs 新头 `p-4`	相同	命中！

步骤 4 命中意味着：原本在尾部的节点 p-4，在新顺序里要排到头部去。所以需要把 p-4 对应的真实 DOM 挪到当前头部节点 p-1 的真实 DOM 前面。

用代码实现 4 步比较：

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
  if (oldStartVNode.key === newStartVNode.key) {
    // 第一步：oldStartVNode 和 newStartVNode 比较
  } else if (oldEndVNode.key === newEndVNode.key) {
    // 第二步：oldEndVNode 和 newEndVNode 比较
  } else if (oldStartVNode.key === newEndVNode.key) {
    // 第三步：oldStartVNode 和 newEndVNode 比较
  } else if (oldEndVNode.key === newStartVNode.key) {
    // 第四步：oldEndVNode 和 newStartVNode 比较
    // 仍然需要调用 patch 函数进行打补丁
    patch(oldEndVNode, newStartVNode, container)
    // 移动 DOM 操作：oldEndVNode.el 移动到 oldStartVNode.el 前面
    insert(oldEndVNode.el, container, oldStartVNode.el)
    // 移动 DOM 完成后，更新索引值，并指向下一个位置
    oldEndVNode = oldChildren[--oldEndIdx]
    newStartVNode = newChildren[++newStartIdx]
  }
}

我们逐行看：

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx)：双端 Diff 的主循环。两个条件都得成立才继续——旧数组头不能超过尾，新数组头也不能超过尾。
if (oldStartVNode.key === newStartVNode.key)：步骤 1，比头部和头部。
else if (oldEndVNode.key === newEndVNode.key)：步骤 2，比尾部和尾部。
else if (oldStartVNode.key === newEndVNode.key)：步骤 3，交叉比：旧头 vs 新尾。
else if (oldEndVNode.key === newStartVNode.key)：步骤 4，交叉比：旧尾 vs 新头。
patch(oldEndVNode, newStartVNode, container)：复用 DOM 之前还是要先打补丁，把文本、属性等同步一下。
insert(oldEndVNode.el, container, oldStartVNode.el)：这里的 insert 就是把节点的真实 DOM 插到“锚点”前面。这里把 oldEndVNode.el 插到 oldStartVNode.el 前面。
oldEndVNode = oldChildren[--oldEndIdx]：旧尾指针往左挪一格（--oldEndIdx 是“先减后用”）。
newStartVNode = newChildren[++newStartIdx]：新头指针往右挪一格。

这里有 4 条关键约定得记住：

命中步骤	命中的组合	做什么	锚点
步骤 1 命中	头对头，两个都在头部	不需要移动，只是 patch，然后两边的头指针都前移	——
步骤 2 命中	尾对尾，两个都在尾部	不需要移动，只是 patch，然后两边的尾指针都后移	——
步骤 3 命中	旧头对上新尾，原本在头部要跑到尾部去	移动到当前尾节点后面	`oldEndVNode.el.nextSibling`
步骤 4 命中	旧尾对上新头，原本在尾部要跑到头部去	移动到当前头节点前面	`oldStartVNode.el`

完整版 4 步循环

把 4 个步骤全写完整是这样：

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
  if (oldStartVNode.key === newStartVNode.key) {
    // 步骤一：oldStartVNode 和 newStartVNode 比较
    patch(oldStartVNode, newStartVNode, container)
    oldStartVNode = oldChildren[++oldStartIdx]
    newStartVNode = newChildren[++newStartIdx]
  } else if (oldEndVNode.key === newEndVNode.key) {
    // 步骤二：oldEndVNode 和 newEndVNode 比较
    // 都在尾部，不需要移动，但仍需打补丁
    patch(oldEndVNode, newEndVNode, container)
    oldEndVNode = oldChildren[--oldEndIdx]
    newEndVNode = newChildren[--newEndIdx]
  } else if (oldStartVNode.key === newEndVNode.key) {
    // 步骤三：oldStartVNode 和 newEndVNode 比较
    patch(oldStartVNode, newEndVNode, container)
    // 移动到当前尾节点后面（用尾节点的下一个兄弟作为锚点）
    insert(oldStartVNode.el, container, oldEndVNode.el.nextSibling)
    oldStartVNode = oldChildren[++oldStartIdx]
    newEndVNode = newChildren[--newEndIdx]
  } else if (oldEndVNode.key === newStartVNode.key) {
    // 步骤四：oldEndVNode 和 newStartVNode 比较
    patch(oldEndVNode, newStartVNode, container)
    // 移动到当前头节点前面（用头节点作为锚点）
    insert(oldEndVNode.el, container, oldStartVNode.el)
    oldEndVNode = oldChildren[--oldEndIdx]
    newStartVNode = newChildren[++newStartIdx]
  }
}

步骤 3 用 oldEndVNode.el.nextSibling 作锚点，步骤 4 用 oldStartVNode.el 作锚点：insert(el, parent, anchor) 的语义是“插到锚点之前”，所以想插到 A 后面，得借 A 的下一个兄弟来中转。走查那一节会把这一步完整拆开。

把 `while` 循环真跑一遍：第 1～4 轮走查

前面只把第 1 轮走了一遍就停了。可真实 DOM 的顺序这时还对不上新的一组子节点，说明 Diff 根本没干完，所以真实代码里比较逻辑必须包在 while 循环里反复跑。

现在我们按图 10-5 的例子从头走一遍，每一轮只盯三件事：

这一步命中了谁
真实 DOM 排队的样子变成什么样
四个索引各推到了哪

先说清楚循环条件。while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) 的意思是：旧数组的头指针不能越过尾指针，新数组的头指针也不能越过尾指针。

为什么是“小于等于”？因为每一轮更新结束之后，紧接着都会更新与本轮相关的两个索引，让它们朝各自方向前进一步（尾指针左移、头指针右移）。等到某一侧的头指针跑到了尾指针的外侧，说明这一侧已经全部处理完，循环就该停了。

第 1 轮收尾：移动之前 vs 移动之后（图 10-6、图 10-7）

第 1 轮我们在步骤 4 命中（旧尾 p-4 ↔ 新头 p-4）。这里有两个时刻值得停下来看一眼。

移动之前：四个索引各就各位，真实 DOM 还是老顺序 p-1、p-2、p-3、p-4，图里 ① ② ③ ④ 四条连线就是这一轮试过的四次比较：

图 10-6　新旧两组子节点以及真实 DOM 节点的状态

insert(oldEndVNode.el, container, oldStartVNode.el) 执行完，真实 DOM 变成 p-4、p-1、p-2、p-3（图里 p-4 被画成虚线、并用一条“移动”箭头搬到最上面，表示它搬家了）：

图 10-7　新旧两组子节点以及真实 DOM 节点的状态

⚠️ 此刻真实 DOM 是 p-4、p-1、p-2、p-3，而新的一组子节点要求的是 p-4、p-2、p-1、p-3——顺序还不一致。这就是必须用 while 循环继续跑的原因。

第 1 轮涉及的索引是 oldEndIdx 和 newStartIdx，它们已经各推进一步，接下来进入第 2 轮。

第 2 轮：命中步骤 2（尾对尾，不用搬家）

步骤 1：旧头 p-1 ↔ 新头 p-2，两者 key 值不同，不可复用，什么都不做。
步骤 2：旧尾 p-3 ↔ 新尾 p-3，两者 key 值相同，可以复用。而且它在新旧两组子节点里都待着尾部、位置没变，所以不需要移动真实 DOM，打补丁就够了。

这条分支的代码长这样（摘自上面那个 while 循环，只留下本轮命中的这一段，开头的 } 表示它接在步骤 1 分支后面）：

} else if (oldEndVNode.key === newEndVNode.key) {
  // 步骤二：oldEndVNode 和 newEndVNode 比较
  // 节点在新的顺序中仍然处于尾部，不需要移动，但仍需打补丁
  patch(oldEndVNode, newEndVNode, container)
  // 更新索引和头尾部节点变量
  oldEndVNode = oldChildren[--oldEndIdx]
  newEndVNode = newChildren[--newEndIdx]
}

patch(oldEndVNode, newEndVNode, container)：p-3 沿用了原来的真实 DOM，但“复用”不等于“什么都不做”——文本、属性还得按新 vnode 同步一遍，这就是打补丁。
oldEndVNode = oldChildren[--oldEndIdx]：旧尾指针向左挪一格，重新拿到当前的尾部节点。
newEndVNode = newChildren[--newEndIdx]：新尾指针也向左挪一格。

本轮只动了两个尾指针，两个头指针原地不动。这就是“尾对尾”的特点。

这一轮完成之后的整体状态如图 10-8 所示：

图 10-8　新旧两组子节点以及真实 DOM 节点的状态

真实 DOM 的顺序相比上一轮没有变化（还是 p-4、p-1、p-2、p-3），因为这一轮我们没有移动任何 DOM 节点，只是对 p-3 打了补丁。接下来，就根据图 10-8 所示的状态执行下一轮的比较。

第 3 轮：命中步骤 3（头尾交叉，`nextSibling` 锚点登场）

步骤 1：旧头 p-1 ↔ 新头 p-2，key 值不同，不可复用。
步骤 2：旧尾 p-2 ↔ 新尾 p-1，key 值不同，不可复用。
步骤 3：旧头 p-1 ↔ 新尾 p-1。两者的 key 值相同，可以复用。

在第三步的比较中，我们找到了相同的节点。这说明：节点 p-1 原本是头部节点，但在新的顺序中，它变成了尾部节点。

因此，我们需要将节点 p-1 对应的真实 DOM 移动到旧的一组子节点的尾部节点 p-2 所对应的真实 DOM 后面，同时还需要更新相应的索引到下一个位置，如图 10-9 所示。

图 10-9　新旧两组子节点以及真实 DOM 节点的状态

图里被画成虚线的 p-1 就是“马上要搬家”的那个节点，右侧的“移动”箭头表示它要插到 p-2 的后面。

⚠️ 这一步是整个双端 Diff 里最容易写错的锚点逻辑，我们把它拆开慢慢看。

这条分支摘自上面那个 while 循环，只留步骤 3 这一段；它是接在步骤 1、步骤 2 两个分支后面的第三级 else if：

} else if (oldStartVNode.key === newEndVNode.key) {
  // 步骤三：oldStartVNode 和 newEndVNode 比较
  // 调用 patch 函数在 oldStartVNode 和 newEndVNode 之间打补丁
  patch(oldStartVNode, newEndVNode, container)
  // 将旧的一组子节点的头部节点对应的真实 DOM 节点 oldStartVNode.el 移动到
  // 旧的一组子节点的尾部节点对应的真实 DOM 节点后面
  insert(oldStartVNode.el, container, oldEndVNode.el.nextSibling)
  // 更新相关索引到下一个位置
  oldStartVNode = oldChildren[++oldStartIdx]
  newEndVNode = newChildren[--newEndIdx]
}

patch(oldStartVNode, newEndVNode, container)：p-1 复用同一个真实 DOM，先把新旧 vnode 之间的差异补上。
insert(oldStartVNode.el, container, oldEndVNode.el.nextSibling)：本轮唯一的一次移动操作，锚点是 oldEndVNode.el.nextSibling。
oldStartVNode = oldChildren[++oldStartIdx]：旧头指针向右挪一格（p-1 处理完了）。
newEndVNode = newChildren[--newEndIdx]：新尾指针向左挪一格（p-1 也处理完了）。

小细节：锚点为什么不是 oldEndVNode.el？回到 insert(el, parent, anchor) 的语义——把 el 插到 anchor 之前。

我们真正想要的是“把 p-1 插到 p-2 后面”，而 insert 只支持“插到某个节点前面”，两句话对不上号。绕的办法是：取 p-2 的下一个兄弟节点 oldEndVNode.el.nextSibling 当锚点，把 p-1 插到它前面——效果就等于插到了 p-2 的后面。

⚠️ 如果 p-2 后面一个兄弟节点都没有呢？此时 oldEndVNode.el.nextSibling 是 null，而 insert 是允许把锚点传 null 的，含义是“插到这个父节点的最末尾”——结果同样正确。所以这一步绕这一下 nextSibling，不是为了麻烦，而是因为“某个节点后面”这件事在真实 DOM 里没法直接表达，只好借“它后面那个节点”来当中转。

这一轮走完以后，新旧两组子节点的头部索引和尾部索引发生重合（都停在同一个位置上了），但循环条件仍然成立，所以还会有下一轮更新。

第 4 轮：命中步骤 1（头对头，收工）

第一步：比较旧的一组子节点中的头部节点 p-2 与新的一组子节点中的头部节点 p-2。发现两者 key 值相同，可以复用。但两者在新旧两组子节点中都是头部节点，因此不需要移动，只需要调用 patch 函数进行打补丁即可。

这条分支的代码长这样：

if (oldStartVNode.key === newStartVNode.key) {
  // 调用 patch 函数在 oldStartVNode 与 newStartVNode 之间打补丁
  patch(oldStartVNode, newStartVNode, container)
  // 更新相关索引，指向下一个位置
  oldStartVNode = oldChildren[++oldStartIdx]
  newStartVNode = newChildren[++newStartIdx]
}

patch(oldStartVNode, newStartVNode, container)：两个节点都在头部，位置没变，只同步内容，不移动。
两个头指针各自向右挪一格：++oldStartIdx 和 ++newStartIdx。

至此，新旧两组子节点的头指针都跑到了尾指针的外侧，while 的条件不再成立，循环终止。

这一轮更新之后的最终状态如图 10-10 所示：

图 10-10　新旧两组子节点以及真实 DOM 节点的状态

此时，真实 DOM 节点的顺序与新的一组子节点的顺序相同了：p-4、p-2、p-1、p-3。双端 Diff 算法执行完毕。

四轮走查总表

这张表是本节最值钱的东西，建议对着图 10-6 ~ 图 10-10 再看一遍：

轮次	命中步骤	比较的两个节点	要移动真实 DOM 吗	锚点（插到它前面）	本轮推动的索引
第 1 轮	步骤 4（尾↔头）	旧尾 `p-4` ↔ 新头 `p-4`	要移动	`oldStartVNode.el`	`oldEndIdx` 左移、`newStartIdx` 右移
第 2 轮	步骤 2（尾↔尾）	旧尾 `p-3` ↔ 新尾 `p-3`	不移动	——	`oldEndIdx`、`newEndIdx` 都左移
第 3 轮	步骤 3（头↔尾）	旧头 `p-1` ↔ 新尾 `p-1`	要移动	`oldEndVNode.el.nextSibling`	`oldStartIdx` 右移、`newEndIdx` 左移
第 4 轮	步骤 1（头↔头）	旧头 `p-2` ↔ 新头 `p-2`	不移动	——	`oldStartIdx`、`newStartIdx` 都右移

把四个索引的具体数值也列出来，就更清楚了（每轮都是按上一轮的数值加一减一算出来的）：

所以双端 Diff 的规律可以浓缩成两句话：

只有交叉比较（步骤 3、步骤 4）才需要移动真实 DOM；头头、尾尾的比较一律原地打补丁。
每命中一步，就推走“本轮参与比较的那两个索引”，各推一格；四个索引两两交叉，循环就结束了。

10.2　双端比较的优势

理解了双端比较的原理，我们来看看跟简单 Diff 比，双端 Diff 有什么优势。拿第 9 章那个例子来说，如图 10-11 所示。

图 10-11　新旧两组子节点

旧子节点：p-1、p-2、p-3
新子节点：p-3、p-1、p-2

用简单 Diff 算法：会发生 2 次 DOM 移动，如图 10-12 所示。

图 10-12　两次 DOM 移动

用双端 Diff 算法呢？我们来按 4 步比较的思路走一遍。

图 10-13　新旧两组子节点与真实 DOM 节点的状态

第一轮比较：

步骤	比较的两个节点	`key`	结果
步骤 1	旧头 `p-1` vs 新头 `p-3`	不同	跳过
步骤 2	旧尾 `p-3` vs 新尾 `p-2`	不同	跳过
步骤 3	旧头 `p-1` vs 新尾 `p-2`	不同	跳过
步骤 4	旧尾 `p-3` vs 新头 `p-3`	相同	命中！

步骤 4 命中：原本在尾部的 p-3，在新顺序里要排到头部去。所以把 p-3 对应的真实 DOM 移到当前头节点 p-1 的真实 DOM 前面。

图 10-14　新旧两组子节点与真实 DOM 节点的状态

这一步移动完成后，真实 DOM 节点的顺序这时已经和新子节点对上了！但算法还没跑完，还要继续跑，做一些 patch。

第二轮比较：

步骤 1：旧头 p-1 vs 新头 p-1，key 相同 → 都在头部，不移动，只 patch，两个头指针都前移。

图 10-15　新旧两组子节点与真实 DOM 节点的状态

第三轮比较：

步骤 1：旧头 p-2 vs 新头 p-2，key 相同 → 都在头部，不移动，只 patch。

图 10-16　新旧两组子节点与真实 DOM 节点的状态

到此 newStartIdx 和 oldStartIdx 都大于 newEndIdx 和 oldEndIdx，循环结束。

结论：同样的例子，简单 Diff 要 2 次 DOM 移动，双端 Diff 只要 1 次。这就是双端 Diff 的优势。

10.3　非理想状况的处理方式

前面举的例子都比较理想——每一轮都会命中 4 步里的某一步。但现实往往没那么顺利。如图 10-17 这个例子：

图 10-17　第一轮比较都无法命中

旧子节点：p-1、p-2、p-3、p-4
新子节点：p-2、p-4、p-1、p-3

第一轮比较：

步骤	比较的两个节点	`key`	结果
步骤 1	旧头 `p-1` vs 新头 `p-2`	不同	跳过
步骤 2	旧尾 `p-4` vs 新尾 `p-3`	不同	跳过
步骤 3	旧头 `p-1` vs 新尾 `p-3`	不同	跳过
步骤 4	旧尾 `p-4` vs 新头 `p-2`	不同	跳过

⚠️ 4 步全没命中，怎么办？

既然头尾四个节点都没法复用，那就去中间找：拿新子节点的头节点 p-2 去旧数组里搜，看看有没有 key 相同的节点。

用代码实现：

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
  if (oldStartVNode.key === newStartVNode.key) {
    // 步骤一
  } else if (oldEndVNode.key === newEndVNode.key) {
    // 步骤二
  } else if (oldStartVNode.key === newEndVNode.key) {
    // 步骤三
  } else if (oldEndVNode.key === newStartVNode.key) {
    // 步骤四
  } else {
    // 四步都没命中：遍历旧的一组子节点，试图寻找与 newStartVNode 拥有相同 key 值的节点
    // idxInOld 是新头节点在旧数组中的位置
    const idxInOld = oldChildren.findIndex(
      node => node.key === newStartVNode.key
    )
  }
}

oldChildren.findIndex(...)：在旧数组里找到第一个 key === newStartVNode.key 的节点下标，找不到返回 -1。
idxInOld：存的是“新头节点”在旧数组里出现的位置。

拿到 idxInOld 之后能干什么？看图 10-18：

图 10-18　在旧子节点中寻找可复用节点

newStartVNode 是 p-2，在旧数组中索引为 1 的位置找到。说明 p-2 原本不是头节点，更新后要变成头节点，所以需要把 p-2 对应的真实 DOM 移到当前旧头节点 p-1 对应的真实 DOM 前面。

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
  if (oldStartVNode.key === newStartVNode.key) {
    // 步骤一
  } else if (oldEndVNode.key === newEndVNode.key) {
    // 步骤二
  } else if (oldStartVNode.key === newEndVNode.key) {
    // 步骤三
  } else if (oldEndVNode.key === newStartVNode.key) {
    // 步骤四
  } else {
    // 遍历旧 children，试图寻找与 newStartVNode 拥有相同 key 值的元素
    const idxInOld = oldChildren.findIndex(
      node => node.key === newStartVNode.key
    )
    // idxInOld 大于 0，说明找到了可复用的节点，需要把它对应的真实 DOM 移动到头部
    if (idxInOld > 0) {
      const vnodeToMove = oldChildren[idxInOld]
      patch(vnodeToMove, newStartVNode, container)
      // 以 oldStartVNode.el 作为锚点，把 vnodeToMove.el 移到它前面
      insert(vnodeToMove.el, container, oldStartVNode.el)
      // 因为 idxInOld 处的节点已经被移走，设置成 undefined 防止重复处理
      oldChildren[idxInOld] = undefined
      // 更新 newStartIdx 到下一个位置
      newStartVNode = newChildren[++newStartIdx]
    }
  }
}

我们逐行看：

if (idxInOld > 0)：> 0 而不是 >= 0 是因为：如果它本来就在头部位置（idxInOld === 0），就不需要移动了——位置没动嘛。
const vnodeToMove = oldChildren[idxInOld]：把要移动的节点拿出来。
patch(vnodeToMove, newStartVNode, container)：先打补丁再移动。
insert(vnodeToMove.el, container, oldStartVNode.el)：用头节点的真实 DOM 当锚点，把要移动的节点插到它前面。
oldChildren[idxInOld] = undefined：关键操作——把这个位置“清空”。如果不设为 undefined，下一轮循环时它仍然在数组里，可能会被重复处理。
newStartVNode = newChildren[++newStartIdx]：处理完了，新头指针前进一格。

这一步执行完后，新旧子节点和真实 DOM 的状态如图 10-19：

图 10-19　新旧两组子节点以及真实 DOM 节点的状态

真实 DOM 的顺序：p-2、p-1、p-3、p-4。

继续下一轮比较：

图 10-20　新旧两组子节点以及真实 DOM 节点的状态

步骤	比较的两个节点	`key`	结果
步骤 1	旧头 `p-1` vs 新头 `p-4`	不同	跳过
步骤 2	旧尾 `p-4` vs 新尾 `p-3`	不同	跳过
步骤 3	旧头 `p-1` vs 新尾 `p-3`	不同	跳过
步骤 4	旧尾 `p-4` vs 新头 `p-4`	相同	命中！

步骤 4 命中：把 p-4 移到 p-1 前面。如图 10-21。

图 10-21　移动节点 p-4

真实 DOM 顺序：p-2、p-4、p-1、p-3。

继续下一轮：步骤 1 命中（旧头 p-1 vs 新头 p-1），patch 即可。

图 10-22　新旧两组子节点与真实 DOM 节点的状态

处理 `undefined` 占位

undefined 占位（undefined placeholder）：

双端 Diff 把某个旧节点处理完、搬走之后，会把它在 oldChildren 数组里占的那个位置设成 undefined（空值），当作“这个位置已经用掉了”的占位符。

注意此时旧子节点的头节点是 undefined！因为前一轮我们把 idxInOld 位置设成了 undefined，它现在落在了 oldStartVNode 上。

这说明该节点已经被处理过了，不能再处理它，要直接跳过：

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
  // 增加两个判断分支，如果头尾部节点为 undefined，则说明该节点已经被处理过了，直接跳到下一个位置
  if (!oldStartVNode) {
    oldStartVNode = oldChildren[++oldStartIdx]
  } else if (!oldEndVNode) {
    oldEndVNode = oldChildren[--oldEndIdx]
  } else if (oldStartVNode.key === newStartVNode.key) {
    // 步骤一
  } else if (oldEndVNode.key === newEndVNode.key) {
    // 步骤二
  } else if (oldStartVNode.key === newEndVNode.key) {
    // 步骤三
  } else if (oldEndVNode.key === newStartVNode.key) {
    // 步骤四
  } else {
    const idxInOld = oldChildren.findIndex(
      node => node.key === newStartVNode.key
    )
    if (idxInOld > 0) {
      const vnodeToMove = oldChildren[idxInOld]
      patch(vnodeToMove, newStartVNode, container)
      insert(vnodeToMove.el, container, oldStartVNode.el)
      oldChildren[idxInOld] = undefined
      newStartVNode = newChildren[++newStartIdx]
    }
  }
}

if (!oldStartVNode)：头节点是 undefined，说明被处理过。指针往右挪一格重新拿节点。
else if (!oldEndVNode)：尾节点是 undefined，同理，指针往左挪。

处理完后看图 10-23：

图 10-23　新旧两组子节点与真实 DOM 节点的状态

再下一轮，4 步又重合了：旧头 p-3 vs 新头 p-3，步骤 1 命中，patch 即可。

图 10-24　新旧两组子节点与真实 DOM 节点的状态

循环结束。真实 DOM 的顺序：p-2、p-4、p-1、p-3，跟新子节点完全一致。

10.4　添加新元素

前面的非理想情况是“中间找到了可复用节点”。但还有一种可能：新数组里冒出来一个旧数组里根本没有的新节点。

看图 10-25 这个例子：

图 10-25　新增节点的情况

旧子节点：p-1、p-2、p-3
新子节点：p-4、p-1、p-3、p-2

第一轮比较 4 步都不命中，去旧数组里找 p-4——找不到。

图 10-26　在旧的一组子节点中找不到可复用的节点

这说明 p-4 是全新节点，得挂载。因为 p-4 是新子节点的头节点，所以应该挂载到当前头节点之前——也就是 oldStartVNode.el 前面。

代码实现：

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
  if (!oldStartVNode) {
    oldStartVNode = oldChildren[++oldStartIdx]
  } else if (!oldEndVNode) {
    oldEndVNode = oldChildren[--oldEndIdx]
  } else if (oldStartVNode.key === newStartVNode.key) {
    // 步骤一
  } else if (oldEndVNode.key === newEndVNode.key) {
    // 步骤二
  } else if (oldStartVNode.key === newEndVNode.key) {
    // 步骤三
  } else if (oldEndVNode.key === newStartVNode.key) {
    // 步骤四
  } else {
    const idxInOld = oldChildren.findIndex(
      node => node.key === newStartVNode.key
    )
    if (idxInOld > 0) {
      const vnodeToMove = oldChildren[idxInOld]
      patch(vnodeToMove, newStartVNode, container)
      insert(vnodeToMove.el, container, oldStartVNode.el)
      oldChildren[idxInOld] = undefined
    } else {
      // idxInOld <= 0：找不到匹配节点，把 newStartVNode 作为新节点挂载到头部
      patch(null, newStartVNode, container, oldStartVNode.el)
    }
    newStartVNode = newChildren[++newStartIdx]
  }
}

else 分支（紧跟在 if (idxInOld > 0) 后面）：idxInOld <= 0，找不到任何匹配节点——这是个全新节点。
patch(null, newStartVNode, container, oldStartVNode.el)：第一个参数传 null 表示“全新挂载”，把 oldStartVNode.el 当锚点插到它前面。
newStartVNode = newChildren[++newStartIdx]：挂完了，新头指针前进。

图 10-27　新旧两组子节点以及真实 DOM 节点的状态

循环结束后还有遗漏？

这样就完美了吗？我们再看一个稍微不同的例子。如图 10-28：

图 10-28　新旧两组子节点与真实 DOM 节点的状态

旧子节点：p-1、p-2、p-3
新子节点：p-4、p-1、p-2、p-3

按双端 Diff 的思路走：

第一轮步骤 2 命中：旧尾 p-3 vs 新尾 p-3，patch + 双尾指针后移。

图 10-29　新旧两组子节点以及真实 DOM 节点的状态

第二轮步骤 2 命中：旧尾 p-2 vs 新尾 p-2，patch + 双尾指针后移。

图 10-30　新旧两组子节点与真实 DOM 节点的状态

第三轮步骤 2 命中：旧尾 p-1 vs 新尾 p-1，patch + 双尾指针后移。

图 10-31　新旧两组子节点与真实 DOM 节点的状态

循环结束。但是 p-4 完全没有被处理过！这就是双端 Diff 的一个缺陷——循环里没碰到它。

循环结束后挂载新节点

修法：在 while 循环结束后，检查索引值的关系，看看有没有“遗留”：

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
  // 省略循环体内的 4 步比较
}

// 循环结束后检查索引值的情况
if (oldEndIdx < oldStartIdx && newStartIdx <= newEndIdx) {
  // 满足条件说明有新节点遗留，需要挂载它们
  for (let i = newStartIdx; i <= newEndIdx; i++) {
    patch(null, newChildren[i], container, oldStartVNode.el)
  }
}

if (oldEndIdx < oldStartIdx && newStartIdx <= newEndIdx)：
- oldEndIdx < oldStartIdx：旧数组的头尾指针“错位”了，说明旧数组已经处理完；
- newStartIdx <= newEndIdx：但新数组还有遗留节点没处理。
- 两个条件一起 = 新数组里有需要挂载的新节点。
for (let i = newStartIdx; i <= newEndIdx; i++)：遍历遗留区间，把每个节点都挂上去。
patch(null, newChildren[i], container, oldStartVNode.el)：null 表示全新挂载，oldStartVNode.el 作为锚点。

10.5　移除不存在的元素

解决了新增节点，再看删除的情况。如图 10-32：

图 10-32　移除节点的情况

旧子节点：p-1、p-2、p-3
新子节点：p-1、p-3

按双端 Diff 思路：

第一轮步骤 1 命中（旧头 p-1 vs 新头 p-1），patch + 双头指针前移。

图 10-33　新旧两组子节点以及真实 DOM 节点的状态

第二轮：步骤 2 命中（旧尾 p-3 vs 新尾 p-3），patch + 双尾指针后移。此时 newStartIdx > newEndIdx，循环结束。

图 10-34　新旧两组子节点以及真实 DOM 节点的状态

但旧数组里还遗留着一个 p-2，得把它卸载掉！

跟处理新增节点类似，再加一个 else...if 分支：

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
  // 省略循环体内的 4 步比较
}

if (oldEndIdx < oldStartIdx && newStartIdx <= newEndIdx) {
  // 添加新节点
  // 省略代码
} else if (newEndIdx < newStartIdx && oldStartIdx <= oldEndIdx) {
  // 移除操作
  for (let i = oldStartIdx; i <= oldEndIdx; i++) {
    unmount(oldChildren[i])
  }
}

else if (newEndIdx < newStartIdx && oldStartIdx <= oldEndIdx)：
- newEndIdx < newStartIdx：新数组头尾指针错位，说明新数组已经处理完；
- oldStartIdx <= oldEndIdx：旧数组还有遗留节点。
- 两个条件一起 = 旧数组里有需要卸载的节点。
for (let i = oldStartIdx; i <= oldEndIdx; i++) { unmount(oldChildren[i]) }：把遗留区间里的旧节点全部卸载。

10.6　总结

本章我们介绍了双端 Diff 算法的原理及其优势。顾名思义，双端 Diff 算法指的是，在新旧两组子节点的四个端点之间分别进行比较，并试图找到可复用的节点。相比简单 Diff 算法，双端 Diff 算法的优势在于，对于同样的更新场景，执行的 DOM 移动操作次数更少。

下一章预告：第 11 章我们会讲快速 Diff 算法——这是 Vue 3 真正采用的方案。它借鉴了文本 Diff 的思路，先处理相同的前缀和后缀，再处理中间部分，思路更清晰、性能更优。

名词速查

词	一句话
双端（two-ended）	同时看两组子节点的开头和结尾
4 个索引	头尾各一个，同时指向新旧两组子节点的头和尾
4 步比较循环	头头 → 尾尾 → 头尾 → 尾头，按顺序试

本章小结

双端 Diff = 同时从新旧两组子节点的两端向中间夹。简单 Diff 只从一头扫，双端 Diff 同时看头看尾。
4 个索引：oldStartIdx / oldEndIdx / newStartIdx / newEndIdx，分别指向新旧两组子节点的头尾。每次循环后某些索引会前进（取决于哪一步命中）。
4 步比较循环：步骤 1 头头、步骤 2 尾尾、步骤 3 头尾、步骤 4 尾头。命中哪步就走对应分支，patch 之后更新对应索引。
锚点是双端 Diff 的关键：insert(el, parent, anchor) 的语义是“插到 anchor 之前”。所以步骤 4（尾↔头）直接拿头节点当锚点；步骤 3（头↔尾）想要“插到尾节点后面”，只能取 oldEndVNode.el.nextSibling（尾节点的下一个兄弟）当锚点绕一步实现；尾节点后面没兄弟时 nextSibling 是 null，insert 会把它理解为“插到最后面”，结果依然正确。
一次完整的 4 轮走查：第 1～4 轮依次命中步骤 4、步骤 2、步骤 3、步骤 1（见图 10-6 ~ 图 10-10）。规律是只有交叉比较（步骤 3、步骤 4）才移动真实 DOM，头头、尾尾一律原地 patch；每命中一步，就推走本轮参与比较的那两个索引各一格，四个索引两两交叉时循环结束。
4 步都不命中怎么办：用 oldChildren.findIndex(node => node.key === newStartVNode.key) 去旧数组里找——idxInOld > 0 就移 DOM 到头部；idxInOld <= 0 就当作全新节点挂载。
undefined 占位：把处理过的旧节点设为 undefined，下次循环碰到直接 if (!oldStartVNode) oldStartVNode = oldChildren[++oldStartIdx] 跳过。
循环结束后处理剩余：oldEndIdx < oldStartIdx && newStartIdx <= newEndIdx → 挂载新节点；newEndIdx < newStartIdx && oldStartIdx <= oldEndIdx → 卸载旧节点。
优势：跟简单 Diff 相比，同样例子的 DOM 移动次数更少（典型 2 次 → 1 次）。
缺陷：4 步都不命中的“非理想情况”得用 findIndex 兜底，代码比较啰嗦；有时候循环跑完还会有遗漏，得在循环后处理。

| undefined 占位 | 把处理过的旧节点在旧数组里的位置设成 undefined，下次循环直接跳过 |