Vue 系列（十）：聊聊 Diff 算法

在上一篇文章中，我们对渲染器进行了简单地介绍，本篇我们将以图文的方式对 vue 中的 Diff 算法进行详细地介绍。

为什么需要 Diff 算法

在上一篇文章中，我们要对节点进行更新的时候都是采用的简单粗暴的方式：卸载旧节点挂载新节点，比如：

<!--旧节点-->
<template>
  <div>
    <p>Text1</p>
    <p>Text2</p>
  </div>
</template>

<!--新节点-->
<template>
  <div>
    <p>Text3</p>
    <p>Text4</p>
  </div>
</template>

在上一章中，如果我们要将上面的旧节点更新为新节点，需要把 div 下的 p 节点全部卸载掉，然后再挂载新的 p 节点，这样就会产生4次DOM操作：

• 卸载两次 p 节点
• 挂载两次 p 节点

可以看到，我们没有复用任何DOM，如果节点过多，这将会产生极大的性能开销。在上面这个例子中，我们其实没有必要去卸载掉 p 节点而是可以直接复用，这样我们只需要更新 p 节点内的文本即可，这样就只会产生2次DOM操作：

• 更新两次 p 节点

再来看一个例子：

<!--旧节点-->
<template>
  <div>
    <p>Text1</p>
    <div>Text2</div>
    <span>Text3</span>
    <p>Text4</p>
  </div>
</template>

<!--新节点-->
<template>
  <div>
    <span>Text3</span>
    <p>Text1</p>
    <div>Text2</div>
    <p>Text5</p>
  </div>
</template>

这个例子如果按照之前的算法，则需要进行7次DOM操作：

• 依次卸载 p、div、span
• 依次挂载 span、p、div
• 更新最后 p 节点中的文本内容

通过观察上面的例子，我们其实可以发现除了最后的 p 节点，其他新节点和旧节点只是顺序发生了改变，但是因为 节点中没有 key 所以我们不能通过移动操作来更新节点，再引入key之前我们通过图示来理解一下diff算法是如何进行比较以及更新的。

可以看到，比较的级别一定是同级，不会跨级比较，如果父节点不相同，则直接丢弃，父节点相同则进行下一级的比较，下图展示了 diff 算法的比较以及更新过程：

引入Key

在上一节图示的例子中，我们发现其实是可以通过移动节点来完成更新的，但是因为没有引入 key，所以无法进行移动操作。当然这时候可能你会有疑问了，为什么不通过节点的类型来判断是否可以进行节点复用从而通过移动节点来完成更新呢？我们来看下面的例子：

<!--旧节点-->
<template>
  <div>
    <p>Text1</p>
    <p>Text2</p>
    <p>Text3</p>
  </div>
</template>

<!--新节点-->
<template>
  <div>
    <p>Text3</p>
    <p>Text1</p>
    <p>Text2</p>
  </div>
</template>

在上面的代码中，我们是可以通过移动节点来完成更新的，但是因为都是 p 节点，我们没有办法找到每个子节点之间的对应关系，所以无法进行复用，但是如果我们引入了 key 就可以很好地解决这个问题了：

<!--旧节点-->
<template>
  <div>
    <p key="1">Text1</p>
    <p key="2">Text2</p>
    <p key="3">Text3</p>
  </div>
</template>

<!--新节点-->
<template>
  <div>
    <p key="3">Text3</p>
    <p key="1">Text1</p>
    <p key="2">Text2</p>
  </div>
</template>

可以看到，因为引入了 key，我们可以找到新旧节点之间的对应关系，这样就可以进行节点的复用了。对于上面这个例子，我们已经知道了可以复用节点，那么我们要如何去移动节点呢？我们先看一个不需要移动的例子：

<!--旧节点-->
<template>
  <div>
    <p key="1">Text1</p>
    <p key="2">Text2</p>
    <p key="3">Text3</p>
  </div>
</template>

<!--新节点-->
<template>
  <div>
    <p key="1">Text4</p>
    <p key="2">Text5</p>
    <p key="3">Text6</p>
  </div>
</template>

我们根据上面的列子来走一遍节点的更新过程：

• 遍历新节点，首先取新节点中的第一个节点 p，她的 key 为 1，我们这时去旧节点中寻找 key=1 的节点，看看能不能找到，发现能找到，说明可以进行节点复用，执行 patch 操作，并且该新节点在旧节点中的索引为 0。
• 取新节点中的第二个节点 p，她的 key 为 2，我们同样去旧节点中寻找 key=2 的节点，发现也能找到，执行 patch 操作，并且该新节点在旧节点中的索引为1。
• 取新节点中的第三个节点 p，她的 key 为 3，我们也去旧节点中寻找 key=3 的节点，同样也能找到，并且该新节点在旧节点中的索引为2，执行 patch 操作，并且该新节点在旧节点中的索引为2。

如果我们在遍历新节点的过程中记录下她们在旧节点中的索引位置，并按照先后顺序进行排列，可以得到一个序列：0,1,2。可以发现这是一个递增序列，这说明我们不需要进行节点的移动。这其实就是判断节点是否需要移动的关键，了解这个关键点之后我们再用同样的方法看一下上面需要进行移动的那个例子：

• 遍历新节点，首先取新节点中的第一个节点 p，她的 key 为 3，我们去旧节点中寻找 key=3 的节点，发现能找到，这时执行patch操作，我们记录下新节点在旧节点中的索引为 2
• 然后去取新节点中的第二个节点 p，她的 key 为 1，我们去旧节点中寻找 key=1 的节点，发现能找到，执行 patch 操作，我们找到新节点在旧节点中的索引为 0，可以发现序列 2,0 不是一个递增的序列，那说明我们需要对 key=1 的旧节点进行移动，这里移动的就是真实节点了，我们需要将 key=1 的真实节点挂载到 key=3 的节点后面即可
• 最后我们取新节点中的第三个节点 p，她的 key 为 2，我们去旧节点中寻找 key=2 的节点，发现也能找到，执行 patch 操作，我们找到新节点在旧节点中的索引为 1，可以发现序列 2,1（这里需要注意，我们每次遍历的时候，记录的都是最大的索引）也不是一个递增的序列，那说明我们需要对 key=2 的旧节点进行移动，和上一次移动一样，我们将 key=2 的真实节点挂载到 key=1 的节点后面即可。

移动过程的图示如下：

这里的核心就是：每次遍历新节点的时候，都记录遍历过程中遇到的最大索引，如果后面的索引值大于这个值，则刷新这个最大索引，并且不需要移动当前节点，如果后面的索引值小于这个值，则需要对真实节点进行移动。

通过上面的例子，我们知道了如何去进行节点复用以及怎样去移动节点，但是上面的例子没有处理删除节点和新增节点的情况。上面的例子只是一个节点复用和移动的思路，在 vue 中并不是采用我们如上说的这个算法，那么接下来我们就看看在 vue 中真正的 diff 算法是怎样的。

快速 Diff 算法

快速Diff算法，顾名思义，该算法的速度非常快，所以 vue3 借鉴了该算法。那么接下来我们就来介绍一下diff算法的思路和实现实现原理。

我们先来看两段文本：

I am a C++ programmer.

I am a Java programmer.

快速diff算法借鉴了纯文本diff算法的思路，她有一个预处理的过程，如下图：

绿色文字就是预处理的内容，可以发现两端文字存在相同的地方，而这段相同的地方就是不需要进行diff核心操作的部分，红色的部分才是需要真正进行diff核心操作的。对于节点来说，快速diff算法也是这样的思路：

接下来我们就通过不同的场景来看看快速diff算法到底是如何工作的。

只需要新增节点的场景

<!--旧节点-->
<template>
  <div>
    <p key="key-1">1</p>
    <p key="key-2">2</p>
  </div>
</template>

<!--新节点-->
<template>
  <div>
    <p key="key-1">1</p>
    <p key="key-3">3</p>
    <p key="key-4">4</p>
    <p key="key-2">2</p>
  </div>
</template>

观察上面这个例子，我们可以发现，新节点跟旧节点对比，新节点只是新增了两个子节点：key-3、key-4。那么我们现在来看看快速diff算法是如何将旧节点更新为新节点的：

首先我们定义三个索引：start、oldEnd、newEnd，如下图所示，然后我们还需要两个while循环，一个从前遍历，一个从后遍历，当两个节点的key不相等的时候终止循环

接下来我们就按照这个思路通过图示来完成上面这个例子的更新:

• 首先开启第一个while循环，从前开始遍历，当遍历到第二个节点的时候，发现新旧节点的key不相等，终止循环

• 然后开启第二个while循环，从后开始遍历，当遍历至倒数第二个节点的时候，发现新旧节点的key不相等，终止循环

• 通过上面两步，我们就处理完了前后相同的节点了，处理完的节点如下图所示，其中虚线框表示已经处理完成的节点，可以发现，当 oldEnd < start && newEnd >= start 时，有新增的节点，从 start 到 newEnd 之间的节点都是需要新增的

• 最后一步，我们只需要把新增的两个节点挂载到key-2的前面即可

只需要删除节点的场景

<!--旧节点-->
<template>
  <div>
    <p key="key-1">1</p>
    <p key="key-3">3</p>
    <p key="key-4">4</p>
    <p key="key-2">2</p>
  </div>
</template>

<!--新节点-->
<template>
  <div>
    <p key="key-1">1</p>
    <p key="key-2">2</p>
  </div>
</template>

其实删除节点与新增节点非常相似，我们来看看具体的更新过程：

• 与新增节点一样，首先开启第一个while循环，从前开始遍历，当遍历到第二个节点的时候，发现新旧节点的key不相等，终止循环

• 然后开启第二个while循环，从后开始遍历，当遍历至倒数第二个节点的时候，发现新旧节点的key不相等，终止循环

• 通过上面两步，我们就处理完了前后相同的节点了，处理完的节点如下图所示，其中虚线框表示已经处理完成的节点，可以发现，当 start > newEnd && start <= oldEnd 时，有需要删除的节点，从 start 到 oldEnd 之间的节点都是需要删除的

• 最后一步，我们只需要把 start 到 oldEnd 之间的节点全部卸载掉即可

需要移动节点的场景

我们前面介绍的两种情况都是比较特殊的场景，前后两端的节点比较完成之后剩下的节点要么全部新增要么全部卸载，接下来我们会介绍需要进行节点移动的情况，这也是快速diff算法最复杂的地方。首先看如下节点：

<!--旧节点-->
<template>
  <div>
    <p key="key-1">1</p>
    <p key="key-2">2</p>
    <p key="key-3">3</p>
    <p key="key-4">4</p>
    <p key="key-6">6</p>
    <p key="key-5">5</p>
  </div>
</template>

<!--新节点-->
<template>
  <div>
    <p key="key-1">1</p>
    <p key="key-3">3</p>
    <p key="key-4">4</p>
    <p key="key-2">2</p>
    <p key="key-7">7</p>
    <p key="key-5">5</p>
  </div>
</template>

通过下图可以直观地看到，只有前后两个节点可以复用，中间的节点既存在需要移动的，也存在需要新增和删除的情况：

可以看到三个索引值 start、oldEnd、newEnd 不满足我们上面介绍过的两种情况：oldEnd < start && newEnd >= start 和 start > newEnd && start <= oldEnd，所以我们就需要增加额外的逻辑来处理这种情况。

• 我们需要根据新节点构建出一个名为 source 的数组，这个数组的长度等于未处理过的新节点的长度，数组中每个元素的初始值为 -1，我们之后会用这个数组构建出一个最长递增子序列，初始化后的数组如下：

• 然后我们还需要根据新节点建立一张索引表，这张索引表用来存储节点的key和节点索引之间的映射，我们可以通过遍历一遍新节点来构建出这样的索引表，如下图所示：

• 接下来我们要遍历一遍旧节点，在遍历的过程中，用旧节点的 key 与索引表中的 key 进行匹配，如果能匹配上，我们先进行 patch 操作，然后填充 source 数组，这时会将 source 数组中的 -1 修改为旧节点的索引，即：新节点在原来旧节点中的位置。如果没有匹配上，说明该节点在新节点中不存在了，应该删除掉该旧节点，更新过程如下：

通过上面的操作，我们得到了一个全新的 source 数组：[2, 3, 1, -1]，为了接下来的移动操作，我们要根据 source 数组计算出一个最长递增子序列，那么何为最长递增子序列呢？举个例子，现在有一个数组：[8, 7, 9, 10, 0, 11, 5]，她的最长递增子序列就是：[7, 9, 10, 11]，可以看到，如果给定一个数值序列，找到它的一个子序列，并且该子序列中的值是递增的，我们就说该子序列是递增子序列，并且子序列中的元素不一定要在原序列中是连续的。那么接下来我们找到上述 source 数组中的递增子序列就简单了，我们很容易得出，上述数组中的递增子序列是 [2, 3]。

好了，有了这个最长递增子序列，我们就可以开始着手对节点进行移动了，在移动之前我们还需要对最长递增子序列 [2, 3] 进行处理，我们定义一个变量 seq，她的值是最长递增子序列中的元素在 source 数组中的位置索引，即 [0, 1]，如下图：

接下来我们就可以正式开始对剩余的节点进行处理了。

• 首先我们对新节点进行重新的编号，其实就是忽略已经处理过的首尾节点，对剩余的节点进行编号，重新编号是为了让子序列 seq 与新的索引值产生对应关系，可以看到重新编号后的 key-3 和 key-4 对应的索引值为 0 和 1 ，这样就跟 seq 产生了对应关系，这说明：在新的一组子节点中，重新编号后索引值为 0 和 1 的这两个节点在更新前后顺序没有发生变化。这才是重新编号的意义。

• 然后我们需要定义两个变量：seqEndIndex 和 sourceEndIndex，她们分别指向 seq 的末尾和新的一组子节点（重新编号后）的末尾，如下图：

• 变量定义好之后，我们从后向前遍历新节点，首先遇到 key-7，发现该节点在 source 数组中相同位置的值为 -1，那说明该节点是新增节点，需要进行挂载：

• 接着 sourceEndIndex 上移，sourceEndIndex = 2，这时 source[2] = 1 说明节点不是新增的，接着我们判断 sourceEndIndex 是否和 seq[seqEndIndex] 是否相等，发现 1 !== 2 所以节点是需要移动的，我们找到节点的真实位置，然后进行移动：

• sourceEndIndex 继续上移，此时 sourceEndIndex = 1，这时 source[2] = 3 说明节点不是新增的，接着我们判断 sourceEndIndex 是否和 seq[seqEndIndex] 是否相等，发现 1 === 1 所以节点是不需要移动的。这时我们只需要让 sourceEndIndex 和 seqEndIndex 继续上移即可：

• sourceEndIndex 和 seqEndIndex 上移，发现跟上一步的处理方式一样，到此我们就处理完所有节点了：

最后