14_第_9_章_简单_Diff_算法

约 17027 字大约 57 分钟

2026-10-05

本章预备：先把要用的几个词认下来

这一章我们要反复用到一批词。它们在原书里是直接使用的，但对我们零基础的人来说每一个都像黑话。所以先集中解释一遍，后面再出现时就不再重复解释。

这一章新出现的 7 个词

真实 DOM：

真正挂在页面上、用户能看见能点的那部分 DOM，也就是上一章 renderer.render() 的最终产物。

比喻：按图纸盖出来的、已经交房的真房子。

子节点（children）：

vnode.children 这个属性，装的要么是一段字符串（纯文本内容），要么是一个数组（里面装着一堆子 vnode）。

比喻：图纸上这个房间的内部说明——“就一句话”，或者“里面还有 3 个隔间”。

卸载（unmount）：第 8 章已经讲过——把已经造出来的真实 DOM 元素从页面上摘下来。

比喻：搬家走了，把留下的空位收拾干净。

复用：

新旧两个 vnode 认定为“同一个东西”，直接沿用原来的真实 DOM，不重新创建。比喻：还是那个同事，只是换了工位，工位不用重新布置。

移动：

真实 DOM 节点本身不变，只改变它在父节点里的位置。比喻：书架上那本《Vue.js 入门》从第 1 格挪到第 3 格——书没重印，只是换了格子。

key：

你写在虚拟节点上的一个“身份证号”，用来告诉框架“这个节点和上次的那个是同一个东西”。在真实项目里，它就是你写在标签上的那个 key，比如 <li :key="item.id">。

比喻 1（身份证）：key 就是虚拟节点的“身份证号”。三个人的长相可能都一般，但身份证号各不相同，一对照就知道谁是谁。

比喻 2（行李条）：给每件行李贴行李条号。转运时箱子换来换去，外表一模一样，但行李条号贴在上面没变，所以不会拿错。

比喻 3（门牌号）：村子里三家房子都叫“平房”，但门牌 1 号、2 号、3 号各不相同。朋友换了顺序串门，只要按门牌号找，再怎么换都找不错人。

el：

vnode 上的一个属性，指向这个 vnode 对应的真实 DOM 节点。

比喻：设计图上标着“这一格对应真房子的哪一间”。

索引（index）：

数组里某个元素的位置编号。

比喻：一排座位，你管最前面那个位置叫“第 0 个位置”。

⚠️ JavaScript 数组的下标从 0 开始数，所以第一个元素的下标是 0，第二个是 1，第三个是 2。

结论：本章所有“索引”都指旧数组里的下标，全是从 0 数起的。

顺带回顾几个老词

下面这几个词前面章节已经建过卡，这里只做一句话回顾，后文直接用：

词	一句话回顾
DOM（Document Object Model）	浏览器里真实存在的一棵节点树，你在开发者工具里点开 `<body>` 看到的那棵层层嵌套的树就是它。比喻：眼前这栋已经盖好的真房子
虚拟 DOM / vnode（virtual node）	用普通的 JavaScript 对象（形如 `{ type, children }`）把“这个位置应该显示什么”描述出来的一份草稿；草稿树上每一个节点，就叫一个 vnode。比喻：装修开工前画在纸上的施工草图——草图上标着有几个房间、每个房间干什么用，但纸上的房子还不是房子
渲染器（renderer）	负责把虚拟 DOM 变成真实 DOM 的那个模块，上一章的主角。比喻：施工队——你交给它图纸，它负责真的把房子盖起来
挂载（mount）	把一个还停留在草稿阶段的 vnode，真的变成真实 DOM 并插进页面。比喻：照着图纸砌墙——图纸上写着“这里有一面墙”，挂载就是真的把砖砌上去
`patch`（打补丁）	拿新的 vnode 去更新旧的 vnode 所对应的真实 DOM，把有差异的地方补上。比喻：旧毛衣改小一码——毛线还是那团毛线，只改要改的地方

Vue 源码里大量使用 patch 这个词，本章的 patch、patchChildren、patchElement、unmount 是一家人：patch 前缀表示“在已有的基础上改”。

为什么非要有个 Diff 算法

从本章开始，我们将介绍渲染器的核心 Diff 算法。diff 这个词是英文 difference（差异）的缩写。

结论：简单来说，当新旧 vnode 的子节点都是一组节点时，为了以最小的性能开销完成更新操作，需要比较两组子节点，用于比较的算法就叫作 Diff 算法。

比喻：出门前列购物清单，你只买两张清单不一样的那些东西，而不是把冰箱推倒重装。购物清单就是新 vnode，旧冰箱就是真实 DOM，两相对照找不同，就是 Diff。

渲染器为什么需要它？因为操作 DOM 的性能开销通常比较大，而渲染器的核心 Diff 算法就是为了解决这个问题而诞生的。

“操作 DOM 慢”是本章从头到尾反复用到的理由，我们在这里一次性讲清楚，后面所有优化都是在为它服务：

为什么操作 DOM 慢？ 浏览器要把一个网页显示出来，内部要走好几道工序：解析 HTML/JS、排版（reflow / layout，算出每个元素该摆在哪个坐标）、绘制（paint，一笔一笔画上去）、合成。

问题在于：你在 JavaScript 里每增删改一个真实 DOM 节点，浏览器就可能被迫把这些工序从头重做一遍。删掉一个节点，它后面所有兄弟节点的位置都要重新算；插入一个节点，后面所有内容都要重新排列，然后整块重新画一遍。

比喻：你在一本已经排好版的书中间插一页——插进去的瞬间，后面所有页码都得重排、整本书都得重新装订。而“改一改草稿上的购物清单”是纯脑力活，一秒钟就能改完。

结论：改数据是纯内存操作，几乎不花钱；改 DOM 是让浏览器返工，两者不在一个量级上。

所以本章的全部内容，其实都在回答同一个问题：怎么用最少的 DOM 操作，把页面更新对？

结论：记住这张图就够了——Diff 算法是“省钱的那一步”，它省下的正是下面“改真实 DOM”的开销。

9.1　减少 DOM 操作的性能开销

核心 Diff 只关心新旧虚拟节点都存在一组子节点的情况。在上一章中，我们针对两组子节点的更新，采用了一种简单直接的手段，即卸载全部旧子节点，再挂载全部新子节点。

这么做的确可以完成更新，但由于一个真实 DOM 元素都没有复用，所以会产生极大的性能开销。

比喻：房间要换一批家具，你是“把旧家具全搬出去、再把新家具全搬进来”，还是“能留的家具留在原位，只搬走不要的、搬来缺的”？前者简单但费劲，后者要动脑子但省力。上一章用的是前者，本章要一步步把它改造成后者。

一个能体现问题的例子

我们拿一个最小的例子来看：一个 div 里有 3 个 p，每个 p 里写一个字。现在要把三个字从 1、2、3 改成 4、5、6。

// 旧 vnode
const oldVNode = {
  type: 'div',
  children: [
    { type: 'p', children: '1' },
    { type: 'p', children: '2' },
    { type: 'p', children: '3' }
  ]
}

// 新 vnode
const newVNode = {
  type: 'div',
  children: [
    { type: 'p', children: '4' },
    { type: 'p', children: '5' },
    { type: 'p', children: '6' }
  ]
}

这两个对象是照着上一章的写法手写的虚拟 DOM。先逐行认一遍：

const oldVNode = { ... }：旧的那份“施工草图”，装进变量 oldVNode（old = 旧的，VNode = 虚拟节点）。const 表示“这个变量后面不再改指向”。
type: 'div'：最外层是一个 div 标签。type 是 vnode 最重要的字段，整个 patch 函数全靠它判断该走哪条路。
children: [ ... ]：方括号 = 数组 = 房间里的家具清单。之所以是数组，是因为一个位置可以装很多个子节点。
{ type: 'p', children: '1' }：清单上的第一件“家具”——一个 p 标签，里面写着字 1。

⚠️ 注意 children: '1' 用的是引号而不是方括号——一段纯文字用不着清单，一个位置就够了。

const newVNode = { ... }：新的那份草图。结构一模一样，只有三个 p 里的字变了。这个“结构一样、只有内容变”的特点，正是我们要抓住的重点。

按照上一章的做法（全删全建），当更新子节点时，我们需要执行 6 次 DOM 操作：

卸载所有旧子节点，需要 3 次 DOM 删除操作；
挂载所有新子节点，需要 3 次 DOM 添加操作。

把它画出来就很直观了：

但是，通过观察上面新旧 vnode 的子节点，可以发现：

更新前后的所有子节点都是 p 标签，即标签元素不变；
只有 p 标签的子节点（文本节点）会发生变化。

文本节点（text node）：

只装一段文字、没有自己的标签的那个最小节点。比如 <p>1</p> 里那个孤零零的 1，它就是 p 的文本子节点。

比喻：<p> 是信封，文本节点是信封里那张写着字的纸条——换张纸条不用换信封。

小细节：children 写成字符串（如 children: '1'）时，就表示这个位置放的是一个文本节点。这是上一章 8.9 节规范化时要处理的情况。

具体看：oldVNode 的第一个子节点是一个 p 标签，且该 p 标签的子节点类型是文本节点，内容是 '1'。而 newVNode 的第一个子节点也是一个 p 标签，它的子节点的类型也是文本节点，内容是 '4'。更新前后改变的只有 p 标签文本节点的内容——p 标签本身根本没变。

所以，最理想的更新方式是，直接更新这个 p 标签的文本节点的内容。这样只需要一次 DOM 操作，即可完成一个 p 标签更新。新旧虚拟节点都有 3 个 p 标签作为子节点，所以一共只需要 3 次 DOM 操作就可以完成全部节点的更新。

做法	这个例子需要的 DOM 操作	复用情况
上一章：卸载全部旧子节点，再挂载全部新子节点	6 次	一个真实 DOM 元素都没有复用
本章第一步：按位置复用	3 次	三个 `p` 标签都保留，只更新文本节点

结论：6 次 → 3 次，相比原来性能提升了一倍。 对照着上面这张图看：Diff 算法的思路可以概括成一句话——能不改的就不改，能留的就留着，只改真正变了的那一点点。

第一步优化：按位置复用

按照这个思路，我们可以重新实现两组子节点的更新逻辑：

function patchChildren(n1, n2, container) {
  if (typeof n2.children === 'string') {
    // 省略部分代码
  } else if (Array.isArray(n2.children)) {
    // 重新实现两组子节点的更新方式
    // 新旧 children
    const oldChildren = n1.children
    const newChildren = n2.children
    // 遍历旧的 children
    for (let i = 0; i < oldChildren.length; i++) {
      // 调用 patch 函数逐个更新子节点
      patch(oldChildren[i], newChildren[i])
    }
  } else {
    // 省略部分代码
  }
}

我们逐行看：

function patchChildren(n1, n2, container)：patchChildren（给子节点打补丁）专门负责“一个元素里面的子节点怎么更新”。三个参数：n1 是旧的 vnode、n2 是新的 vnode、container 是它们共同的父容器。
const oldChildren = n1.children：拿到旧的一组子节点（旧数组）。
const newChildren = n2.children：拿到新的一组子节点（新数组）。
for (let i = 0; i < oldChildren.length; i++)：遍历旧数组的下标。
patch(oldChildren[i], newChildren[i])：把同一个下标 i 上的一对节点（旧 i、新 i）一起交给 patch 去“打补丁”。patch 发现新旧子节点只有文本内容不同，于是只更新文本。

请注意这一行里的 i——旧数组和新数组用的是同一个下标，这正是“按位置复用”这个名字的来源：位置相同，就当成同一个东西。

patch 发现新旧子节点只有文本内容不同，因此只会更新其文本节点的内容。这样，我们就成功地将 6 次 DOM 操作减少为 3 次。

小细节：注意这一版代码的 patch 少传了 container 参数，这是照抄原书这一阶段的写法，后面几节会补上。

图 9-1 是整个更新过程的示意图，其中：

菱形代表新子节点
矩形代表旧子节点
圆形代表真实 DOM 节点

图 9-1　仅更新文本子节点

图 9-1 的简化示意

这种做法的问题

这种做法虽然能够减少 DOM 操作次数，但问题也很明显。上面那段代码偷偷做了一个假设：我们遍历的是旧的一组子节点，并假设新的一组子节点的数量与之相同，只有在这种情况下，这段代码才能正确地工作。

打个生活化的比方：四个人排成一队照相，现在队伍中间来了第五个人。

如果你只是“照着位置一个一个换人”——第 1 个位置换人、第 2 个位置换人——你会发现整个队伍全错位了：队伍末尾多出来一个人没人管，而第 1 个位置上的人被顶到了队伍外面。

新旧两组子节点的数量未必相同。 当新的一组子节点的数量少于旧的一组子节点的数量时，意味着有些节点在更新后应该被卸载，如图 9-2 所示。

图 9-2　卸载已经不存在的节点

在图 9-2 中，旧的一组子节点中一共有 4 个 p 标签，而新的一组子节点中只有 3 个 p 标签。这说明第 4 个 p 在新版里没有对应的东西了，它属于“多出来的旧货”，更新过程中需要把它卸载。

反过来也可能：类似地，新的一组子节点的数量也可能比旧的一组子节点的数量多，如图 9-3 所示。

图 9-3　挂载新的节点

在图 9-3 中，新的一组子节点比旧的一组子节点多了一个 p 标签。这个 p 在旧版里找不到对应，它属于“新到的货”，更新时应该把它挂载（新建并插进页面）进去。

于是我们面对的是三种情况：

新旧两组子节点的数量关系	多出来的是什么	更新时怎么处理
一样多	没有，都能配对	逐个 `patch`
新的一组更少	多余的旧节点	卸载它们（见图 9-2）
新的一组更多	多出来的新节点	挂载它们（见图 9-3）

遍历“较短”的那一组

看完上面三种情况就能想到一个统一办法：既然多的那一组必然是“多出来的部分”，那就先按位置把能配对的都配对掉，剩下的再单独处理。

所以在进行新旧两组子节点的更新时，不应该总是遍历旧的一组子节点或遍历新的一组子节点，而是应该遍历其中长度较短的那一组——这样我们才能尽可能多地调用 patch 函数进行更新（能复用的一个都不放过）。接着，再对比新旧两组子节点的长度，如果新的一组子节点更长，则说明有多出来的新子节点需要挂载，否则说明有多出来的旧子节点需要卸载。

比喻：两摞书要并成一摞，先把两摞共同拥有的那几本按顺序对齐放好，上边多的那几本单独补进去，下边多出来的那几本直接处理掉。对齐的部分是“复用”，上边多的是“挂载”，下边多的是“卸载”。

最终实现如下：

function patchChildren(n1, n2, container) {
  if (typeof n2.children === 'string') {
    // 省略部分代码
  } else if (Array.isArray(n2.children)) {
    const oldChildren = n1.children
    const newChildren = n2.children
    // 旧的一组子节点的长度
    const oldLen = oldChildren.length
    // 新的一组子节点的长度
    const newLen = newChildren.length
    // 两组子节点的公共长度，即两者中较短的那一组子节点的长度
    const commonLength = Math.min(oldLen, newLen)
    // 遍历 commonLength 次
    for (let i = 0; i < commonLength; i++) {
      patch(oldChildren[i], newChildren[i], container)
    }
    // 如果 newLen > oldLen，说明有新子节点需要挂载
    if (newLen > oldLen) {
      for (let i = commonLength; i < newLen; i++) {
        patch(null, newChildren[i], container)
      }
    } else if (oldLen > newLen) {
      // 如果 oldLen > newLen，说明有旧子节点需要卸载
      for (let i = commonLength; i < oldLen; i++) {
        unmount(oldChildren[i])
      }
    }
  } else {
    // 省略部分代码
  }
}

我们逐行看：

const oldLen = oldChildren.length：量出旧数组有几个元素。
const newLen = newChildren.length：量出新数组有几个元素。.length：数组自带的属性，一眼就能看出数组有多长。
const commonLength = Math.min(oldLen, newLen)：取两个长度中较短的那个，作为“公共长度”。Math.min（取最小值）：给一组数，它返回最小的那个。比喻：两个人比身高，矮的那个就是“公共长度”——只有矮到对方肩膀的部分，两个人才都对得上。
for (let i = 0; i < commonLength; i++)：只在公共长度范围内逐个 patch，保证每一次 patch 拿到的都是同一个下标上的旧节点和新节点。
patch(oldChildren[i], newChildren[i], container)：这一行注意多了第三个参数 container——告诉 patch 这些节点住在哪个父容器里。
if (newLen > oldLen)：新数组更长，说明公共长度之后还剩下一些新节点，需要挂载。
patch(null, newChildren[i], container)：patch 的第一个参数传 null，意思是“我这边没有旧节点”——patch 一看没有旧节点，就知道这不是“更新”，而是“挂载”，于是走挂载的分支。
else if (oldLen > newLen)：旧数组更长，说明公共长度之后还剩下一些旧节点，需要卸载。
unmount(oldChildren[i])：把这多余的旧节点从页面里删掉。

commonLength 这个变量其实是整段代码的“总开关”，画成图最好懂：

这样，无论新旧两组子节点的数量关系如何，渲染器都能够正确地挂载或卸载它们。

结论：这一小节到这里的成果是，DOM 操作从 6 次降到了 3 次，并且数量不等时也不会错乱。

小细节：但它还有个大问题——它只认位置，不认人。下一节就解决这件事。

9.2　DOM 复用与 `key` 的作用

在上一节中，我们通过减少 DOM 操作的次数，提升了更新性能。但这种方式仍然存在可优化的空间。

问题出在哪？上一节是“认位置”的，而真实情况里位置变了但人没变太常见了。举个例子，假设新旧两组子节点的内容如下：

// oldChildren
[
  { type: 'p' },
  { type: 'div' },
  { type: 'span' }
]

// newChildren
[
  { type: 'span' },
  { type: 'p' },
  { type: 'div' }
]

oldChildren / newChildren：两组子节点，它们身上的东西一模一样，只有摆放顺序换了。就像书架上三本书《JS 入门》《HTML 精讲》《CSS 手册》，你只是想把顺序调成《CSS 手册》《JS 入门》《HTML 精讲》——书还是那三本书，一本都不用买新的。

如果使用上一节介绍的算法来完成上述两组子节点的更新，则需要 6 次 DOM 操作：

位置	旧子节点 → 新子节点	`patch` 的判断	做法	DOM 操作数
第 0 位	`{ type: 'p' }` → `{ type: 'span' }`	标签不同	卸载 `{ type: 'p' }`，再挂载 `{ type: 'span' }`	2 次
第 1 位	`{ type: 'div' }` → `{ type: 'p' }`	标签不同	卸载 `{ type: 'div' }`，再挂载 `{ type: 'p' }`	2 次
第 2 位	`{ type: 'span' }` → `{ type: 'div' }`	标签不同	卸载 `{ type: 'span' }`，再挂载 `{ type: 'div' }`	2 次
合计				6 次

为什么 patch 会卸载再挂载？ 因为 patch 是个“按位置比对的补丁工”——你把第 0 位的 p 和第 0 位的 span 递给它，它一看“标签都不一样”，就认定这是两个完全无关的东西，于是拆掉旧的、装上新的。

因此，一共进行 6 次 DOM 操作才能完成上述案例的更新。但是，观察新旧两组子节点，很容易发现，二者只是顺序不同。所以最优的处理方式是，通过 DOM 的移动来完成子节点的更新，这要比不断地执行子节点的卸载和挂载性能更好。

处理方式	DOM 操作数	三个真实元素的下场
卸载 + 挂载（按位置比对）	6 次	全部拆掉重建
移动	2 次	三个都不重建，挪两下位置就行

结论：卸载+挂载 = 把旧家具搬出去、把新家具搬进来；移动 = 家具还在，只是挪了个位置。 后者便宜得多，这个对比记住就够了。

通过 `type` 来判断不够

但是，想要通过 DOM 的移动来完成更新，必须要保证一个前提：新旧两组子节点中的确存在可复用的节点。这个很好理解，如果新的子节点没有在旧的一组子节点中出现，就无法通过移动节点的方式完成更新。

所以现在问题变成了：应该如何确定新的子节点是否出现在旧的一组子节点中呢？拿上面的例子来说，怎么确定新的一组子节点中第 1 个子节点 { type: 'span' } 与旧的一组子节点中第 3 个子节点相同呢？

一种解决方案是，通过 vnode.type 来判断，只要 vnode.type 的值相同，我们就认为两者是相同的节点。但这种方式并不可靠，思考如下例子：

// oldChildren
[
  { type: 'p', children: '1' },
  { type: 'p', children: '2' },
  { type: 'p', children: '3' }
]

// newChildren
[
  { type: 'p', children: '3' },
  { type: 'p', children: '1' },
  { type: 'p', children: '2' }
]

观察上面这两组节点：它们全都是 p 标签。这个案例完全可以通过移动 DOM 的方式来完成更新（三个真实元素一个都不用重建，挪两下位置就行）。

但是——所有节点的 vnode.type 属性值都相同，这就导致我们无法确定新旧两组子节点中节点的对应关系，也就无法得知应该进行怎样的 DOM 移动才能完成更新。

打个比方：三个同事工牌上的部门都写着“技术部”，你想知道新排班表里的小王就是原来那位小王，但你没有别的信息，无从下手。

引入 `key`

这时，我们就需要引入额外的 key 来作为 vnode 的标识：

// oldChildren
[
  { type: 'p', children: '1', key: 1 },
  { type: 'p', children: '2', key: 2 },
  { type: 'p', children: '3', key: 3 }
]

// newChildren
[
  { type: 'p', children: '3', key: 3 },
  { type: 'p', children: '1', key: 1 },
  { type: 'p', children: '2', key: 2 }
]

这里说的 key 属性，就是本章开头那张概念卡里说的“身份证号”。

规则只有一条：只要两个虚拟节点的 type 属性值和 key 属性值都相同，我们就认为它们是相同的，即可以进行 DOM 的复用。

小细节：注意是“都相同”——标签对得上、身份证号也对得上，才算同一个人。

图 9-4 展示了有 key 和无 key 时新旧两组子节点的映射情况。

图 9-4　有 key 与无 key

由图 9-4 可知，如果没有 key，我们无法知道新子节点与旧子节点间的映射关系，也就无法知道应该如何移动节点——三条线索全指向“卸载重挂”，那还不如一开始就用最笨的办法。

有 key 的话情况则不同，我们根据子节点的 key 属性，能够明确知道新子节点在旧子节点中的位置，这样就可以进行相应的 DOM 移动操作了。

结论：key 的真正价值不是“加速渲染”，而是把“哪个新节点对应哪个旧节点”这个说不清的问题变成一个可以用 === 比出来的问题。

可复用还要再 `patch`

有必要强调的一点是，DOM 可复用并不意味着不需要更新，如下面的两个虚拟节点所示：

const oldVNode = { type: 'p', key: 1, children: 'text 1' }
const newVNode = { type: 'p', key: 1, children: 'text 2' }

这两个虚拟节点拥有相同的 key 值和 vnode.type 属性值。这意味着，在更新时可以复用 DOM 元素，即只需要通过移动操作来完成更新。但仍需要对这两个虚拟节点进行打补丁操作，因为新的虚拟节点（newVNode）的文本子节点的内容已经改变了（由 'text 1' 变成 'text 2'）。

比喻：key 相同只说明“还是那个工位上的那个人”，但人换了个名牌，工位里挂着的东西还是要换。所以“能复用”和“不用更新”是两码事。

因此，在讨论如何移动 DOM 之前，我们需要先完成打补丁操作：

function patchChildren(n1, n2, container) {
  if (typeof n2.children === 'string') {
    // 省略部分代码
  } else if (Array.isArray(n2.children)) {
    const oldChildren = n1.children
    const newChildren = n2.children

    // 遍历新的 children
    for (let i = 0; i < newChildren.length; i++) {
      const newVNode = newChildren[i]
      // 遍历旧的 children
      for (let j = 0; j < oldChildren.length; j++) {
        const oldVNode = oldChildren[j]
        // 如果找到了具有相同 key 值的两个节点，说明可以复用，但仍然需要调用 patch 函数更新
        if (newVNode.key === oldVNode.key) {
          patch(oldVNode, newVNode, container)
          break // 这里需要 break
        }
      }
    }

  } else {
    // 省略部分代码
  }
}

我们逐行看：

外层 for 循环：遍历新的一组子节点。
内层 for 循环：遍历旧的一组子节点，试图找到一个和当前 newVNode 的 key 相同的旧节点。
if (newVNode.key === oldVNode.key)：找到了 key 相同的节点，说明它们对应同一个真实 DOM。
patch(oldVNode, newVNode, container)：复用 DOM 并打补丁（更新内容）。
break：找到之后要 break，不然会一直循环下去，导致反复 patch 同一个节点。

一个具体的例子

在上面这段代码中，我们重新实现了新旧两组子节点的更新逻辑。可以看到，我们使用了两层 for 循环，外层循环用于遍历新的一组子节点，内层循环则遍历旧的一组子节点。在内层循环中，我们逐个对比新旧子节点的 key 值，试图在旧的子节点中找到可复用的节点。一旦找到，则调用 patch 函数进行打补丁。

以下面的新旧两组子节点为例：

const oldVNode = {
  type: 'div',
  children: [
    { type: 'p', children: '1', key: 1 },
    { type: 'p', children: '2', key: 2 },
    { type: 'p', children: 'hello', key: 3 }
  ]
}

const newVNode = {
  type: 'div',
  children: [
    { type: 'p', children: 'world', key: 3 },
    { type: 'p', children: '1', key: 1 },
    { type: 'p', children: '2', key: 2 }
  ]
}

// 首次挂载
renderer.render(oldVNode, document.querySelector('#app'))
setTimeout(() => {
  // 1 秒钟后更新
  renderer.render(newVNode, document.querySelector('#app'))
}, 1000);

运行上面这段代码，1 秒钟后，key 值为 3 的子节点对应的真实 DOM 的文本内容会由字符串 'hello' 更新为字符串 'world'。

先看清这段示例代码：新旧两个 vnode 的子节点数量、标签、key 全都一样，唯一的变化有两处——key 为 3 的那个节点换了位置（从第 3 个变成第 1 个），并且它的文字从 'hello' 变成了 'world'。

renderer.render(oldVNode, ...)：先挂载旧 vnode，页面上出现 1、2、hello 三段。
setTimeout(..., 1000)：等 1 秒钟，好让你在浏览器里亲眼看看“什么都没发生”的那 1 秒钟里页面是稳的。
renderer.render(newVNode, ...)：1 秒后拿新 vnode 去更新，触发本章讲的 Diff 算法。

下面我们详细分析上面这段代码在执行更新操作时具体发生了什么：

取新的一组子节点中的第一个子节点，即 key 值为 3 的节点。尝试在旧的一组子节点中寻找具有相同 key 值的节点。我们发现，旧的子节点 oldVNode[2] 的 key 值为 3，于是调用 patch 函数进行打补丁。在这一步操作完成之后，渲染器会把 key 值为 3 的虚拟节点所对应的真实 DOM 的文本内容由字符串 'hello' 更新为字符串 'world'。
取新的一组子节点中的第二个子节点，即 key 值为 1 的节点。尝试在旧的一组子节点中寻找具有相同 key 值的节点。我们发现，旧的子节点 oldVNode[0] 的 key 值为 1，于是调用 patch 函数进行打补丁。由于 key 值等于 1 的新旧子节点没有任何差异，所以什么都不会发生。
取新的一组子节点中的第三个子节点，即 key 值为 2 的节点。尝试在旧的一组子节点中寻找具有相同 key 值的节点。我们发现，旧的子节点 oldVNode[1] 的 key 值为 2，于是调用 patch 函数进行打补丁。同样，由于 key 值等于 2 的新旧子节点没有任何差异，所以什么也不会发生。

经过这三步，所有节点对应的真实 DOM 元素都更新完毕了。 但此时真实 DOM 仍然保持旧的一组子节点的顺序，即 key 值为 3 的节点对应的真实 DOM 仍然是最后一个子节点。

由于在新的一组子节点中，key 值为 3 的节点已经变为第一个子节点了，因此我们还需要通过移动节点来完成真实 DOM 顺序的更新——这正是下一节要解决的问题。

9.3　判断节点是否需要移动

上一节我们通过引入 key 属性实现了对 DOM 的复用，但还有一个问题没解决——怎么判断哪些节点需要移动？

思考方向可以反过来：不先想“怎么判断要移动”，而是先想“什么时候不用移动”。

答案很简单——当新旧两组子节点的节点顺序不变时，就不需要额外的移动操作。

节点顺序不变：不需要移动

我们先看一个不需要移动的例子，如图 9-5 所示。

图 9-5　节点顺序不变

在图 9-5 中，新旧两组子节点的顺序没有发生变化，图中也给出了旧的一组子节点中各个节点的索引：

key 值为 1 的节点在旧 children 数组中的索引为 0
key 值为 2 的节点在旧 children 数组中的索引为 1
key 值为 3 的节点在旧 children 数组中的索引为 2

接着，我们对新旧两组子节点采用上一节介绍的更新算法，看看当新旧两组子节点的顺序没有发生变化时，这个算法跑下来会记下什么：

取新的一组子节点中的第一个节点 p-1，它的 key 为 1。尝试在旧的一组子节点中找到具有相同 key 值的可复用节点，发现能够找到，并且该节点在旧的一组子节点中的索引为 0。
取新的一组子节点中的第二个节点 p-2，它的 key 为 2。尝试在旧的一组子节点中找到具有相同 key 值的可复用节点，发现能够找到，并且该节点在旧的一组子节点中的索引为 1。
取新的一组子节点中的第三个节点 p-3，它的 key 为 3。尝试在旧的一组子节点中找到具有相同 key 值的可复用节点，发现能够找到，并且该节点在旧的一组子节点中的索引为 2。

在这个过程中，每一次寻找可复用的节点时，都会记录该可复用节点在旧的一组子节点中的位置索引。如果把这些位置索引值按照先后顺序排列，则可以得到一个序列：0、1、2。

结论：这是一个递增的序列，在这种情况下不需要移动任何节点。

比喻：你按名字挨个点名，点到的顺序正好就是队形原本的顺序，那队伍根本不用重排。只有当点名顺序和队形顺序对不上时，才需要有人挪位置。

节点顺序变了：需要移动

我们再来看看另外一个例子，如图 9-6 所示。

图 9-6　节点顺序变化

图 9-6 的简化示意

同样，我们根据图 9-6 中给出的例子再次执行更新算法：

取新的一组子节点中的第一个节点 p-3，它的 key 为 3。尝试在旧的一组子节点中找到具有相同 key 值的可复用节点，发现能够找到，并且该节点在旧的一组子节点中的索引为 2。
取新的一组子节点中的第二个节点 p-1，它的 key 为 1。尝试在旧的一组子节点中找到具有相同 key 值的可复用节点，发现能够找到，并且该节点在旧的一组子节点中的索引为 0。

到了这一步我们发现，索引值递增的顺序被打破了。节点 p-1 在旧 children 中的索引是 0，它小于节点 p-3 在旧 children 中的索引 2。这说明节点 p-1 在旧 children 中排在节点 p-3 前面，但在新的 children 中，它排在节点 p-3 后面。

结论：节点 p-1 对应的真实 DOM 需要移动。

取新的一组子节点中的第三个节点 p-2，它的 key 为 2。尝试在旧的一组子节点中找到具有相同 key 值的可复用节点，发现能够找到，并且该节点在旧的一组子节点中的索引为 1。

到了这一步我们发现，节点 p-2 在旧 children 中的索引 1 要小于节点 p-3 在旧 children 中的索引 2。这说明，节点 p-2 在旧 children 中排在节点 p-3 前面，但在新的 children 中，它排在节点 p-3 后面。

结论：节点 p-2 对应的真实 DOM 也需要移动。

以上就是 Diff 算法在执行更新的过程中，判断节点是否需要移动的方式。在这个例子中，我们得出了节点 p-1 和节点 p-2 需要移动的结论。这是因为它们在旧 children 中的索引要小于节点 p-3 在旧 children 中的索引。如果我们按照先后顺序记录在寻找节点过程中所遇到的位置索引，将会得到序列：2、0、1。可以发现，这个序列不具有递增的趋势。

例子	各节点在旧 `children` 中的索引	记录下来的索引序列	判断结果
图 9-5：节点顺序不变	`p-1` 为 `0`、`p-2` 为 `1`、`p-3` 为 `2`	`0`、`1`、`2`	递增，不需要移动任何节点
图 9-6：节点顺序变化	`p-3` 为 `2`、`p-1` 为 `0`、`p-2` 为 `1`	`2`、`0`、`1`	不具有递增趋势，`p-1` 和 `p-2` 需要移动

比喻：排队时报数，从第 3 个位置开始点，然后喊到了第 1 个位置——只要号码往回走了，就说明这个人得挪一下。整个算法其实只用了“号码有没有回退”这一个判断。

`lastIndex`：最大索引值

其实我们可以将节点 p-3 在旧 children 中的索引定义为：在旧 children 中寻找具有相同 key 值节点的过程中，遇到的最大索引值。如果在后续寻找的过程中，存在索引值比当前遇到的最大索引值还要小的节点，则意味着该节点需要移动。

lastIndex：

一个变量，用来记着“到目前为止，我在旧数组里找到过的最大索引值”。名字里的 last 是“上一个/最近的那个”，Index 是“索引”。

比喻 1（跑步记号）：你沿着旧队伍从后往前跑，手里举着一块写数字的牌子。每找到一个旧队员，就看他的位置号：比牌子上的大，就把牌子上的数字改大；比牌子上的小，说明这个人已经跑到牌子后面去了，他得搬家。

比喻 2（削苹果看果皮）：削着削着发现这一刀又削回了刚才削过的地方，说明这块果皮没得省了。

我们可以用 lastIndex 变量存储整个寻找过程中遇到的最大索引值：

function patchChildren(n1, n2, container) {
  if (typeof n2.children === 'string') {
    // 省略部分代码
  } else if (Array.isArray(n2.children)) {
    const oldChildren = n1.children
    const newChildren = n2.children

    // 用来存储寻找过程中遇到的最大索引值
    let lastIndex = 0
    for (let i = 0; i < newChildren.length; i++) {
      const newVNode = newChildren[i]
      for (let j = 0; j < oldChildren.length; j++) {
        const oldVNode = oldChildren[j]
        if (newVNode.key === oldVNode.key) {
          patch(oldVNode, newVNode, container)
          if (j < lastIndex) {
            // 如果当前找到的节点在旧 children 中的索引小于最大索引值 lastIndex，
            // 说明该节点对应的真实 DOM 需要移动
          } else {
            // 如果当前找到的节点在旧 children 中的索引不小于最大索引值，
            // 则更新 lastIndex 的值
            lastIndex = j
          }
          break // 这里需要 break
        }
      }
    }

  } else {
    // 省略部分代码
  }
}

如以上代码注释所示，如果新旧节点的 key 值相同，说明我们在旧 children 中找到了可复用 DOM 的节点。此时我们用该节点在旧 children 中的索引 j 与 lastIndex 进行比较：

判断条件	当前 `oldVNode` 对应的真实 DOM	`lastIndex` 怎么处理
`j < lastIndex`	需要移动	不动，保持当前遇到的最大索引值
否则	不需要移动	把 `j` 的值赋给 `lastIndex`，保证它始终存储着当前遇到的最大索引值

把这两行注释翻译成人话，再配上 lastIndex 的变化过程，就是下面这张图：

有个细节值得停一下：只有不移动的时候才更新 lastIndex。为什么？

因为一旦某个节点需要移动，算法并没有去修改它在旧数组里的位置（数组的顺序始终是老的），此时把 lastIndex 改成那个较小的 j 只会让牌子越举越低，后面的判断全部失真。

结论：lastIndex 永远是“我见过的最靠右的那个旧索引”。

结论：简单 Diff 算法判断移动的全部秘密，就是这四行代码——维护一个 lastIndex，用它当“最靠右的旧位置”的标尺，新节点的旧位置一旦落到标尺左边，就搬家。

现在，我们已经找到了需要移动的节点，下一节我们将讨论如何移动节点，从而完成节点顺序的更新。

9.4　如何移动元素

在上一节中，我们讨论了如何判断节点是否需要移动。移动节点指的是，移动一个虚拟节点所对应的真实 DOM 节点，并不是移动虚拟节点本身。既然移动的是真实 DOM 节点，那么就需要取得对它的引用才行。我们知道，当一个虚拟节点被挂载后，其对应的真实 DOM 节点会存储在它的 vnode.el 属性中，如图 9-7 所示。

图 9-7　虚拟节点引用了真实 DOM 元素

因此，在代码中，我们可以通过旧子节点的 vnode.el 属性取得它对应的真实 DOM 节点。

为什么 el 这么重要？ 因为 JavaScript 里的数组（也就是虚拟节点数组）只是一堆“图纸”，你没法直接拖动图纸来改变页面。真正能动的是那个“已经盖好的房子”——真实 DOM 节点。而拿到它的唯一钥匙就是 vnode.el。

比喻：想把书架上的书挪个位置，你得先伸手摸到那本书（el），而不能去动书架的目录卡（vnode）。

当更新操作发生时，渲染器会调用 patchElement 函数在新旧虚拟节点之间进行打补丁。回顾一下 patchElement 函数的代码：

function patchElement(n1, n2) {
  // 新的 vnode 也引用了真实 DOM 元素
  const el = n2.el = n1.el
  // 省略部分代码
}

可以看到，patchElement 函数首先将旧节点的 n1.el 属性赋值给新节点的 n2.el 属性。这个赋值语句的真正含义其实就是 DOM 元素的复用。在复用了 DOM 元素之后，新节点也将持有对真实 DOM 的引用，如图 9-8 所示。

小细节：这行赋值是整个“复用”的机关所在，值得盯一会儿看。

换个角度说：n2.el = n1.el 之后，同一个真实 DOM 元素会被两个 vnode 同时指着。这在内存上是允许的。

小细节：因为接下来旧 vnode 就会被丢弃——它的使命已经完成了。比喻：交接钥匙——老员工把办公室钥匙交给新员工，老员工就该走了，房子还是那间房子。

图 9-8　使新的子节点也引用真实 DOM 元素

可以看到，无论是新子节点还是旧子节点，都存在对真实 DOM 的引用，在此基础上，我们就可以进行 DOM 移动操作了。

结论：到这里，9.4 的准备工作就齐了——我们已经能徒手拿到任何一个真实 DOM 元素的“把手”（el），下一小节就是怎么握着把手把它挪到该在的位置上。

一个具体的移动例子

为了阐述具体应该怎样移动 DOM 节点，我们仍然引用上一节的更新案例，如图 9-9 所示。

图 9-9　新旧子节点的关系

图 9-9 的简化示意

更新步骤如下：

取新的一组子节点中第一个节点 p-3，它的 key 为 3，尝试在旧的一组子节点中找到具有相同 key 值的可复用节点。发现能够找到，并且该节点在旧的一组子节点中的索引为 2。此时变量 lastIndex 的值为 0，索引 2 不小于 0，所以节点 p-3 对应的真实 DOM 不需要移动，但需要更新变量 lastIndex 的值为 2。
取新的一组子节点中第二个节点 p-1，它的 key 为 1，尝试在旧的一组子节点中找到具有相同 key 值的可复用节点。发现能够找到，并且该节点在旧的一组子节点中的索引为 0。此时变量 lastIndex 的值为 2，索引 0 小于 2，所以节点 p-1 对应的真实 DOM 需要移动。

到了这一步，我们发现，节点 p-1 对应的真实 DOM 需要移动，但应该移动到哪里呢？我们知道，新 children 的顺序其实就是更新后真实 DOM 节点应有的顺序。所以节点 p-1 在新 children 中的位置就代表了真实 DOM 更新后的位置。

由于节点 p-1 在新 children 中排在节点 p-3 后面，所以我们应该把节点 p-1 所对应的真实 DOM 移动到节点 p-3 所对应的真实 DOM 后面。移动后的结果如图 9-10 所示。

可以看到，这样操作之后，此时真实 DOM 的顺序为 p-2、p-3、p-1。

取新的一组子节点中第三个节点 p-2，它的 key 为 2，尝试在旧的一组子节点中找到具有相同 key 值的可复用节点。发现能够找到，并且该节点在旧的一组子节点中的索引为 1。此时变量 lastIndex 的值为 2，索引 1 小于 2，所以节点 p-2 对应的真实 DOM 需要移动。

图 9-10　把节点 p-1 对应的真实 DOM 移动到节点 p-3 对应的真实 DOM 后面

第三步与第二步类似，节点 p-2 对应的真实 DOM 也需要移动。同样，由于节点 p-2 在新 children 中排在节点 p-1 后面，所以我们应该把节点 p-2 对应的真实 DOM 移动到节点 p-1 对应的真实 DOM 后面。移动后的结果如图 9-11 所示。

图 9-11　把节点 p-2 对应的真实 DOM 移动到节点 p-1 对应的真实 DOM 后面

结论：经过这一步移动操作之后，我们发现，真实 DOM 的顺序与新的一组子节点的顺序相同了——p-3、p-1、p-2。至此，更新操作完成。

移动的代码实现

观察图 9-11 我们可以发现，节点 p-2 在新的一组子节点中排在节点 p-1 后面，所以我们应该把节点 p-2 对应的真实 DOM 移动到节点 p-1 对应的真实 DOM 后面。

也就是说，在新的一组子节点中，节点 p-2 的前一个节点是 p-1，所以我们要把节点 p-2 的真实 DOM 移动到节点 p-1 的真实 DOM 后面。

规律一句话：要移动的节点，永远插到“它在新数组里的前一个兄弟节点”后面。 下面这张图说明“前一个兄弟”该怎么找：

⚠️ 为什么用“前一个兄弟”而不是“后一个兄弟”？因为只有“插到某个节点后面”这种说法，才不会让后面的兄弟节点全都挪位置。如果你说“插到 p-1 前面”，浏览器就得先把 p-1 后面那一整串（哪怕只有一个 p-2）搬开，麻烦得多。

按照这个思路，我们就可以实现节点移动逻辑：

function patchChildren(n1, n2, container) {
  if (typeof n2.children === 'string') {
    // 省略部分代码
  } else if (Array.isArray(n2.children)) {
    const oldChildren = n1.children
    const newChildren = n2.children

    let lastIndex = 0
    for (let i = 0; i < newChildren.length; i++) {
      const newVNode = newChildren[i]
      let j = 0
      let find = false
      for (j; j < oldChildren.length; j++) {
        const oldVNode = oldChildren[j]
        if (newVNode.key === oldVNode.key) {
          find = true
          patch(oldVNode, newVNode, container)
          if (j < lastIndex) {
            // 当前找到的节点在旧 children 中的索引小于最大索引值 lastIndex，
            // 说明该节点对应的真实 DOM 需要移动
            // 获取当前 newVNode 节点的前一个 vnode 节点
            const prevVNode = newChildren[i - 1]
            if (prevVNode) {
              // 获取 prevVNode 对应真实 DOM 的下一个兄弟节点，作为锚点 anchor
              const anchor = prevVNode.el.nextSibling
              // 把当前 newVNode 对应的真实 DOM 插入到 anchor 前面，
              // 也就是 prevVNode 对应真实 DOM 的后面
              insert(newVNode.el, container, anchor)
            }
          } else {
            lastIndex = j
          }
          break
        }
      }
    }

  } else {
    // 省略部分代码
  }
}

关键的几行：

const prevVNode = newChildren[i - 1]：用 i - 1 这个下标，取当前新节点的前一个兄弟节点。

⚠️ i 是当前节点在新数组里的下标，所以当 i 为 0（当前节点是第一个）时，i - 1 就是 -1，数组取 -1 会得到 undefined——所以下面必须用 if (prevVNode) 挡一下，第一个节点没有“前一个兄弟”，不用移动。

const anchor = prevVNode.el.nextSibling：拿到那个前一个兄弟节点真实 DOM 的下一个兄弟作为锚点。
insert(newVNode.el, container, anchor)：调用 insert 把当前节点的真实 DOM 插到锚点前面，等价于“放到前一个兄弟后面”。

锚点（anchor，锚）：

一次插入 / 移动的“参照物”，语义是“把这个节点插到锚点的前面”。

比喻 1（钉在墙上的钉子）：钉子不移动，它只负责告诉你“画框挂在钉子左边”。浏览器不会说“插到某个位置”，它只会说“插到某个节点之前”，所以你必须先给它一个节点。

比喻 2（排队插队）：队伍里你想站到某个人后面，可你没法指着“某个位置”说话，只能指着一个人说“我站他后面”。那个人就是锚点。

为什么要取 prevVNode.el.nextSibling 而不是直接用 prevVNode.el？因为我们想要的是“插到前一个兄弟后面”这个位置，而浏览器只认“插到某个节点前面”。前一个兄弟后面那个位置，正好就是它的下一个兄弟的前面——如果它没有下一个兄弟（已经是最后一个），nextSibling 就会得到 null，而“插在一个不存在的节点前面”在 DOM 里的含义就是“插到最后面”，正好是我们想要的。

insertBefore：

浏览器原生提供的一个 DOM 方法，意思是“把 el 插到 anchor 这个节点的前面”。它是浏览器真正干活的入口，本章的 insert 渲染器选项就是它的一层薄包装。

nextSibling（下一个兄弟）：

DOM 原生属性，返回“紧挨着我的下一个同级节点”。

它返回的东西可能是文本节点（文字），不一定是一个元素。 小细节：如果我是最后一个，就返回 null（意思是“后面没人了，插到我后面就是最后面”）。

一句话把这段代码串起来：j < lastIndex 成立 = 这个节点要搬家；家搬到哪儿 = 它的前一个兄弟后面；而浏览器只认“锚点前面”，所以锚点 = 前一个兄弟的下一个兄弟。

在上面这段代码中，如果条件 j < lastIndex 成立，则说明当前 newVNode 所对应的真实 DOM 需要移动。根据前文的分析可知，我们需要获取当前 newVNode 节点的前一个虚拟节点，即 newChildren[i - 1]，然后使用 insert 函数完成节点的移动，其中 insert 函数依赖浏览器原生的 insertBefore 函数：

const renderer = createRenderer({
  // 省略其他选项

  insert(el, parent, anchor = null) {
    // insertBefore 需要锚点元素 anchor
    parent.insertBefore(el, anchor)
  }

  // 省略其他选项
})

const renderer = createRenderer({ ... })：上一章的渲染器是通过 createRenderer（创建渲染器）创建出来的，它接收一个“选项对象”，里面装着所有跟具体平台打交道的函数（insert、remove、createElement……）。
insert(el, parent, anchor = null)：这是本章用到的那一个选项。= 后面的 null 就是默认值——调用方不传 anchor 时，它就是 null。
parent.insertBefore(el, anchor)：真正干活的一行，把 el 插到 parent 里 anchor 的前面。传 anchor = null 就等于“插到这个父元素的最末尾”，所以同一个 insert 函数既能“插到中间”，也能“追加到最后”，一箭双雕。

结论：渲染器核心不认识浏览器，所有跟具体平台打交道的动作都收在“渲染器选项”里。

所以 patchChildren 里写的是 insert(...)（抽象动作），而不是 parent.insertBefore(...)（浏览器具体动作）——核心只提要求，具体的活儿由外面那套实现来完成。

9.5　添加新元素

本节我们将讨论添加新节点的情况，如图 9-12 所示。

图 9-12　新增节点 p-4

观察图 9-12 可知，在新的一组子节点中，多出来一个节点 p-4，它的 key 值为 4，这个节点在旧的一组子节点里翻遍了也找不到，因此应该将其视为新增节点。对于新增节点，在更新时我们应该正确地将它挂载，这主要分为两步：

想办法找到新增节点——怎么知道它是新增的
将新增节点挂载到正确位置——不仅要建出来，还得插对地方

⚠️ 第二步是新手最容易翻车的地方：挂载 ≠ 追加到末尾。如果新节点本该排在中间，你却把它 append 到了最后，页面上就会出现“新来的元素全跑到最下面去了”的诡异现象。所以挂载同样需要锚点。

模拟执行更新逻辑

首先，我们来看一下如何找到新增节点。为了搞清楚这个问题，我们需要根据图 9-12 中给出的例子模拟执行简单 Diff 算法的逻辑。在此之前，我们需要弄清楚新旧两组子节点与真实 DOM 元素的当前状态，如图 9-13 所示。

图 9-13　新旧两组子节点与真实 DOM 元素的当前状态

接着，我们开始模拟执行简单 Diff 算法的更新逻辑。

取新的一组子节点中第一个节点 p-3，它的 key 值为 3，尝试在旧的一组子节点中寻找可复用的节点。发现能够找到，并且该节点在旧的一组子节点中的索引值为 2。此时，变量 lastIndex 的值为 0，索引值 2 不小于 lastIndex 的值 0，所以节点 p-3 对应的真实 DOM 不需要移动，但是需要将变量 lastIndex 的值更新为 2。
取新的一组子节点中第二个节点 p-1，它的 key 值为 1，尝试在旧的一组子节点中寻找可复用的节点。发现能够找到，并且该节点在旧的一组子节点中的索引值为 0。此时变量 lastIndex 的值为 2，索引值 0 小于 lastIndex 的值 2，所以节点 p-1 对应的真实 DOM 需要移动，并且应该移动到节点 p-3 对应的真实 DOM 后面。经过这一步的移动操作后，真实 DOM 的状态如图 9-14 所示。

图 9-14　真实 DOM 的当前状态

此时真实 DOM 的顺序为 p-2、p-3、p-1。

取新的一组子节点中第三个节点 p-4，它的 key 值为 4，尝试在旧的一组子节点中寻找可复用的节点。由于在旧的一组子节点中，没有 key 值为 4 的节点，因此渲染器会把节点 p-4 看作新增节点并挂载它。那么，应该将它挂载到哪里呢？为了搞清楚这个问题，我们需要观察节点 p-4 在新的一组子节点中的位置。由于节点 p-4 出现在节点 p-1 后面，所以我们应该把节点 p-4 挂载到节点 p-1 所对应的真实 DOM 后面。在经过这一步挂载操作之后，真实 DOM 的状态如图 9-15 所示。

图 9-15　真实 DOM 的当前状态

此时真实 DOM 的顺序是：p-2、p-3、p-1、p-4，其中 p-4 是刚刚挂载的。

小细节：注意 p-4 的插入位置——它跑到了中间，而不是被追加到最后。它能被放对位置，靠的还是上一节那套“锚点”办法。

取新的一组子节点中第四个节点 p-2，它的 key 值为 2，尝试在旧的一组子节点中寻找可复用的节点。发现能够找到，并且该节点在旧的一组子节点中的索引值为 1。此时变量 lastIndex 的值为 2，索引值 1 小于 lastIndex 的值 2，所以节点 p-2 对应的真实 DOM 需要移动，并且应该移动到节点 p-4 对应的真实 DOM 后面。经过这一步移动操作后，真实 DOM 的状态如图 9-16 所示。

图 9-16　真实 DOM 的当前状态

此时真实 DOM 的顺序是：p-3、p-1、p-4、p-2。至此，真实 DOM 的顺序已经与新的一组子节点的顺序相同了，更新完成。

代码实现：挂载新节点

接下来，我们着手实现代码：

function patchChildren(n1, n2, container) {
  if (typeof n2.children === 'string') {
    // 省略部分代码
  } else if (Array.isArray(n2.children)) {
    const oldChildren = n1.children
    const newChildren = n2.children

    let lastIndex = 0
    for (let i = 0; i < newChildren.length; i++) {
      const newVNode = newChildren[i]
      let j = 0
      // 在第一层循环中定义变量 find，代表是否在旧的一组子节点中找到可复用的节点，
      // 初始值为 false，代表没找到
      let find = false
      for (j; j < oldChildren.length; j++) {
        const oldVNode = oldChildren[j]
        if (newVNode.key === oldVNode.key) {
          // 一旦找到可复用的节点，则将变量 find 的值设为 true
          find = true
          patch(oldVNode, newVNode, container)
          if (j < lastIndex) {
            const prevVNode = newChildren[i - 1]
            if (prevVNode) {
              const anchor = prevVNode.el.nextSibling
              insert(newVNode.el, container, anchor)
            }
          } else {
            lastIndex = j
          }
          break
        }
      }
      // 如果代码运行到这里，find 仍然为 false，
      // 说明当前 newVNode 没有在旧的一组子节点中找到可复用的节点
      // 也就是说，当前 newVNode 是新增节点，需要挂载
      if (!find) {
        // 为了将节点挂载到正确位置，我们需要先获取锚点元素
        // 首先获取当前 newVNode 的前一个 vnode 节点
        const prevVNode = newChildren[i - 1]
        let anchor = null
        if (prevVNode) {
          // 如果有前一个 vnode 节点，则使用它的下一个兄弟节点作为锚点元素
          anchor = prevVNode.el.nextSibling
        } else {
          // 如果没有前一个 vnode 节点，说明即将挂载的新节点是第一个子节点
          // 这时我们使用容器元素的 firstChild 作为锚点
          anchor = container.firstChild
        }
        // 挂载 newVNode
        patch(null, newVNode, container, anchor)
      }
    }

  } else {
    // 省略部分代码
  }
}

这一版相对上一版只多了一个变量和几行代码，我们只看新增的部分：

let find = false：find 就是一个“找到没有”的小旗子。let 表示它之后还会被改（const 就不行了）。初始 false = 还没找到。
find = true：在旧数组里匹配上了 key，把小旗子竖起来。
if (!find)：! 是 JS 里的“取反”，!false 就是 true。内层循环跑完了，小旗子还趴着，就说明旧数组里压根没有这个 key——它是个新增节点。

⚠️ 为什么需要这个 find？因为内层循环的 break 只会告诉“代码停在哪”，不会告诉“到底找到没有”。循环正常走完（没被 break 打断）本身就是“没找到”的信号，Vue 选择了更直白的方式：用一个变量把这件事记下来。

如果内层循环结束后，变量 find 的值仍然为 false，则说明当前 newVNode 是一个全新的节点，需要挂载它。为了将节点挂载到正确位置，我们需要先获取锚点元素：

找到 newVNode 的前一个虚拟节点，即 prevVNode，如果存在，则使用它对应的真实 DOM 的下一个兄弟节点作为锚点元素
如果不存在，则说明即将挂载的 newVNode 节点是容器元素的第一个子节点，此时应该使用容器元素的 container.firstChild 作为锚点元素

container.firstChild：

容器里排在最前面的那个节点（不一定是元素，也可能是文本）。first 就是“第一”。

为什么新增的第一个节点要拿 firstChild 当锚点？ 因为“插到 firstChild 前面”翻译过来就是“插到最前面”。看这张图：

结论：两种情况其实是同一个道理——都是“插到某个节点的前面”，只是找参照物的方法不同。

最后，将锚点元素 anchor 作为 patch 函数的第四个参数，调用 patch 函数完成节点的挂载。

第一个参数传 null 是关键：上一节说过，patch 一看第一个参数是空的，就知道“没有旧节点可比”，于是走挂载分支。

但由于目前实现的 patch 函数还不支持传递第四个参数，所以我们需要调整 patch 函数的代码，如下所示：

// patch 函数需要接收第四个参数，即锚点元素
function patch(n1, n2, container, anchor) {
  // 省略部分代码

  if (typeof type === 'string') {
    if (!n1) {
      // 挂载时将锚点元素作为第三个参数传递给 mountElement 函数
      mountElement(n2, container, anchor)
    } else {
      patchElement(n1, n2)
    }
  } else if (type === Text) {
    // 省略部分代码
  } else if (type === Fragment) {
    // 省略部分代码
  }
}

// mountElement 函数需要增加第三个参数，即锚点元素
function mountElement(vnode, container, anchor) {
  // 省略部分代码

  // 在插入节点时，将锚点元素透传给 insert 函数
  insert(el, container, anchor)
}

注意这条参数一路透传的链条，这是本章唯一的结构性改动：

结论：patch 和 mountElement 本身一句逻辑都没改，只是多接了一个参数、往下多传了一层。 “锚点”这个概念从 9.4 一路传到了浏览器，中间没走样。

9.6　移除不存在的元素

在更新子节点时，不仅会遇到新增元素，还会出现元素被删除的情况，如图 9-17 所示。

图 9-17　节点被删除的情况

在新的一组子节点中，节点 p-2 已经不存在了，这说明该节点被删除了。渲染器应该能找到那些需要删除的节点并正确地将其删除。

比喻：搬家时最难的不是扔东西，而是想清楚东西该摆哪儿；而删除只要一件事——把这个真实 DOM 从页面上摘掉，不用考虑任何位置。扔东西只要往门外一推。

具体要如何做呢？首先，我们来讨论如何找到需要删除的节点。以图 9-17 为例，我们来分析它的更新步骤。在模拟执行更新逻辑之前，我们需要清楚新旧两组子节点以及真实 DOM 节点的当前状态，如图 9-18 所示。

图 9-18　新旧两组子节点与真实 DOM 节点的当前状态

接着，我们开始模拟执行更新的过程。

取新的一组子节点中的第一个节点 p-3，它的 key 值为 3。尝试在旧的一组子节点中寻找可复用的节点。发现能够找到，并且该节点在旧的一组子节点中的索引值为 2。此时变量 lastIndex 的值为 0，索引 2 不小于 lastIndex 的值 0，所以节点 p-3 对应的真实 DOM 不需要移动，但需要更新变量 lastIndex 的值为 2。
取新的一组子节点中的第二个节点 p-1，它的 key 值为 1。尝试在旧的一组子节点中寻找可复用的节点。发现能够找到，并且该节点在旧的一组子节点中的索引值为 0。此时变量 lastIndex 的值为 2，索引 0 小于 lastIndex 的值 2，所以节点 p-1 对应的真实 DOM 需要移动，并且应该移动到节点 p-3 对应的真实 DOM 后面。经过这一步的移动操作后，真实 DOM 的状态如图 9-19 所示。

图 9-19　真实 DOM 的当前状态

至此，更新结束。我们发现，节点 p-2 对应的真实 DOM 仍然存在——注意上面那个“遗留节点”，它既没被移动，也没被卸载，就这么孤零零地留在了页面上。

所以需要增加额外的逻辑来删除遗留节点。

思路很简单：当基本的更新结束时，我们需要遍历旧的一组子节点，然后去新的一组子节点中寻找具有相同 key 值的节点。如果找不到，则说明应该删除该节点。

⚠️ 注意这个方向和主循环正好相反——主循环是“新找旧”，这里必须“旧找新”。一个漏了谁，另一个就得补上。

function patchChildren(n1, n2, container) {
  if (typeof n2.children === 'string') {
    // 省略部分代码
  } else if (Array.isArray(n2.children)) {
    const oldChildren = n1.children
    const newChildren = n2.children

    let lastIndex = 0
    for (let i = 0; i < newChildren.length; i++) {
      // 省略部分代码
    }

    // 上一步的更新操作完成后
    // 遍历旧的一组子节点
    for (let i = 0; i < oldChildren.length; i++) {
      const oldVNode = oldChildren[i]
      // 拿旧子节点 oldVNode 去新的一组子节点中寻找具有相同 key 值的节点
      const has = newChildren.find(
        vnode => vnode.key === oldVNode.key
      )
      if (!has) {
        // 如果没有找到具有相同 key 值的节点，则说明需要删除该节点
        // 调用 unmount 函数将其卸载
        unmount(oldVNode)
      }
    }

  } else {
    // 省略部分代码
  }
}

如以上代码及注释所示，在上一步的更新操作完成之后，我们还需要遍历旧的一组子节点，目的是检查旧子节点在新的一组子节点中是否仍然存在，如果已经不存在了，则调用 unmount 函数将其卸载。

for (let i = 0; i < oldChildren.length; i++)：又一层循环，注意这次遍历的是 oldChildren（旧的），不是新数组。
newChildren.find(vnode => vnode.key === oldVNode.key)：这里的 find（注意前面有个 .）是数组自带的一个方法，作用是“在数组里找出第一个符合条件的元素”，找不到就返回 undefined。vnode => vnode.key === oldVNode.key 叫箭头函数，是“临时写一个小函数”的最短写法。

⚠️ 它和上一节那个布尔变量 find（有没有找到）只是碰巧同名，不是同一个东西：一个是“数组工具方法”，一个是“我们自己的开关变量”。

if (!has)：has（有没有）为空，说明新数组里没有这个 key——这个节点是多余的老货，卸载掉。

名词速查

词	一句话
虚拟 DOM / vnode	施工草图
真实 DOM	盖好的房子
`patch`	打补丁
`mount` / `unmount`	挂载 / 卸载
`key`	身份证号
`anchor`	“插到它前面”的那个参照物

三种操作速查

操作	怎么认出来	做什么	锚点
移动	在旧数组中找到的索引 `j` 小于 `lastIndex`	`insert(newVNode.el, container, anchor)`	`prevVNode.el.nextSibling`
新增	内层循环跑完 `find` 还是 `false`	`patch(null, newVNode, container, anchor)`	有前一个兄弟就取 `prevVNode.el.nextSibling`，没有就取 `container.firstChild`
移除	旧子节点在新数组里找不到相同 `key`	`unmount(oldVNode)`	不需要位置

本章小结

为什么要有 Diff 算法：因为操作 DOM 的性能开销大（插入/删除一个真实节点，可能让浏览器把后面所有内容重排、重画），所以要尽量少动 DOM。Diff 算法负责“找出哪里不同”，剩下的任务才是“只改不同的地方”。
第一步优化：遍历新旧两组子节点中较短的那一组（commonLength），逐个 patch，再处理“多的那一组剩下的”——挂载新节点或卸载旧节点。6 次 DOM 操作降到 3 次。
第二步优化：靠 key 精确定位“哪个新节点对应哪个旧节点”。没有 key 就只能卸载重挂（6 次），有了 key 就能靠移动（2 次）搞定。
简单 Diff 算法的核心：用变量 lastIndex 记录“已见过的最大旧索引”，如果新节点对应的旧索引比 lastIndex 小，就需要移动。判断移动的实质就是新旧索引序列有没有“回头”。
怎么移动：把当前节点的真实 DOM 插到“前一个新兄弟节点”的真实 DOM 后面。浏览器只认“插到某节点前面”，所以锚点取 prevVNode.el.nextSibling，用 insert（底层是 insertBefore）完成。
新增节点：内层循环跑完，find 还是 false，说明当前 newVNode 在旧的里面不存在，是个全新节点。锚点同样取 prevVNode.el.nextSibling；如果没有前一个兄弟（它排第一），就用 container.firstChild。最后 patch(null, newVNode, container, anchor) 挂载——这要求 patch 和 mountElement 都能接收并向下传递 anchor。
删除节点：主循环是“新找旧”，漏掉的老货得反向再扫一遍：所有新节点处理完之后，遍历旧子节点，凡是 key 在新数组里找不到的，统统 unmount。

下一章预告：第 10 章我们会讲双端 Diff 算法——它和简单 Diff 不一样，同时从新旧两组子节点的“两端”往中间夹，通常能减少更多 DOM 移动，性能更好。