渲染器——双端Diff算法

简单 Diff 算法利用虚拟节点的 key 属性，尽可能地复用 DOM 元素，并通过移动 DOM 的方式来完成更新，从而减少不断地创建和销毁DOM 元素带来的性能开销。但是，简单 Diff 算法仍然存在很多缺陷，这些缺陷可以通过双端 Diff 算法解决。

1、双端比较的原理

简单 Diff 算法的问题在于，它对 DOM 的移动操作并不是最优的。我们拿上一章的例子来看，如下图所示：
在这里插入图片描述
在这个例子中，如果使用简单 Diff 算法来更新它，则会发生两次 DOM 移动操作，如下图所示：
在这里插入图片描述
第一次 DOM 移动操作会将真实 DOM 节点 p-1 移动到真实DOM 节点 p-3 后面。第二次移动操作会将真实 DOM 节点 p-2 移动到真实 DOM 节点 p-1 后面。最终，真实 DOM 节点的顺序与新的一组子节点顺序一致：p-3、p-1、p-2。

然而，上述更新过程并非最优解。在这个例子中，其实只需要通过一步 DOM 节点的移动操作即可完成更新，即只需要把真实 DOM 节点 p-3 移动到真实 DOM 节点 p-1 前面，如下图所示：
在这里插入图片描述
可以看到，理论上只需要一次 DOM 移动操作即可完成更新。但简单 Diff 算法做不到这一点，不过双端Diff 算法可以做到。接下来，我们就来讨论双端 Diff 算法的原理。

顾名思义，双端 Diff 算法是一种同时对新旧两组子节点的两个端点进行比较的算法。因此，我们需要四个索引值，分别指向新旧两组子节点的端点，如下图所示：
在这里插入图片描述
用代码来表达四个端点，如下面 patchChildren 和patchKeyedChildren 函数的代码所示：

01 function patchChildren(n1, n2, container) {
02   if (typeof n2.children === 'string') {
03     // 省略部分代码
04   } else if (Array.isArray(n2.children)) {
05     // 封装 patchKeyedChildren 函数处理两组子节点
06     patchKeyedChildren(n1, n2, container)
07   } else {
08     // 省略部分代码
09   }
10 }
11
12 function patchKeyedChildren(n1, n2, container) {
13   const oldChildren = n1.children
14   const newChildren = n2.children
15   // 四个索引值
16   let oldStartIdx = 0
17   let oldEndIdx = oldChildren.length - 1
18   let newStartIdx = 0
19   let newEndIdx = newChildren.length - 1
20 }

在上面这段代码中，我们将两组子节点的打补丁工作封装到了patchKeyedChildren 函数中。在该函数内，首先获取新旧两组子节点 oldChildren 和 newChildren，接着创建四个索引值，分别指向新旧两组子节点的头和尾，即 oldStartIdx、oldEndIdx、newStartIdx 和 newEndIdx。有了索引后，就可以找到它所指向的虚拟节点了，如下面的代码所示：

01 function patchKeyedChildren(n1, n2, container) {
02   const oldChildren = n1.children
03   const newChildren = n2.children
04   // 四个索引值
05   let oldStartIdx = 0
06   let oldEndIdx = oldChildren.length - 1
07   let newStartIdx = 0
08   let newEndIdx = newChildren.length - 1
09   // 四个索引指向的 vnode 节点
10   let oldStartVNode = oldChildren[oldStartIdx]
11   let oldEndVNode = oldChildren[oldEndIdx]
12   let newStartVNode = newChildren[newStartIdx]
13   let newEndVNode = newChildren[newEndIdx]
14 }

其中，oldStartVNode 和 oldEndVNode 是旧的一组子节点中的第一个节点和最后一个节点，newStartVNode 和newEndVNode 则是新的一组子节点的第一个节点和最后一个节点。有了这些信息之后，我们就可以开始进行双端比较了。怎么比较呢？如下图所示：
在这里插入图片描述
在双端比较中，每一轮比较都分为四个步骤，如上图中的连线所示：

  • 第一步：比较旧的一组子节点中的第一个子节点 p-1 与新的一组子节点中的第一个子节点 p-4，看看它们是否相同。由于两者的 key 值不同，因此不相同，不可复用，于是什么都不做。
  • 第二步：比较旧的一组子节点中的最后一个子节点 p-4 与新的一组子节点中的最后一个子节点 p-3，看看它们是否相同。由于两者的 key 值不同，因此不相同，不可复用，于是什么都不做。
  • 第三步：比较旧的一组子节点中的第一个子节点 p-1 与新的一组子节点中的最后一个子节点 p-3，看看它们是否相同。由于两者的 key 值不同，因此不相同，不可复用，于是什么都不做。
  • 第四步：比较旧的一组子节点中的最后一个子节点 p-4 与新的一组子节点中的第一个子节点 p-4。由于它们的 key 值相同，因此可以进行 DOM 复用。

可以看到，我们在第四步时找到了相同的节点，这说明它们对应的真实 DOM 节点可以复用。对于可复用的 DOM 节点，我们只需要通过 DOM 移动操作完成更新即可。那么应该如何移动 DOM 元素呢？为了搞清楚这个问题，我们需要分析第四步比较过程中的细节。我们注意到，第四步是比较旧的一组子节点的最后一个子节点与新的一组子节点的第一个子节点，发现两者相同。这说明：节点 p-4 原本是最后一个子节点，但在新的顺序中，它变成了第一个子节点。换句话说，节点 p-4 在更新之后应该是第一个子节点。对应到程序的逻辑，可以将其翻译为：将索引 oldEndIdx 指向的虚拟节点所对应的真实 DOM 移动到索引 oldStartIdx 指向的虚拟节点所对应的真实 DOM 前面。如下面的代码所示：

01 function patchKeyedChildren(n1, n2, container) {
02   const oldChildren = n1.children
03   const newChildren = n2.children
04   // 四个索引值
05   let oldStartIdx = 0
06   let oldEndIdx = oldChildren.length - 1
07   let newStartIdx = 0
08   let newEndIdx = newChildren.length - 1
09   // 四个索引指向的 vnode 节点
10   let oldStartVNode = oldChildren[oldStartIdx]
11   let oldEndVNode = oldChildren[oldEndIdx]
12   let newStartVNode = newChildren[newStartIdx]
13   let newEndVNode = newChildren[newEndIdx]
14
15   if (oldStartVNode.key === newStartVNode.key) {
16     // 第一步：oldStartVNode 和 newStartVNode 比较
17   } else if (oldEndVNode.key === newEndVNode.key) {
18     // 第二步：oldEndVNode 和 newEndVNode 比较
19   } else if (oldStartVNode.key === newEndVNode.key) {
20     // 第三步：oldStartVNode 和 newEndVNode 比较
21   } else if (oldEndVNode.key === newStartVNode.key) {
22     // 第四步：oldEndVNode 和 newStartVNode 比较
23     // 仍然需要调用 patch 函数进行打补丁
24     patch(oldEndVNode, newStartVNode, container)
25     // 移动 DOM 操作
26     // oldEndVNode.el 移动到 oldStartVNode.el 前面
27     insert(oldEndVNode.el, container, oldStartVNode.el)
28
29     // 移动 DOM 完成后，更新索引值，并指向下一个位置
30     oldEndVNode = oldChildren[--oldEndIdx]
31     newStartVNode = newChildren[++newStartIdx]
32   }
33 }

在这段代码中，我们增加了一系列的 if…else if… 语句，用来实现四个索引指向的虚拟节点之间的比较。拿上例来说，在第四步中，我们找到了具有相同 key 值的节点。这说明，原来处于尾部的节点在新的顺序中应该处于头部。于是，我们只需要以头部元素 oldStartVNode.el 作为锚点，将尾部元素oldEndVNode.el 移动到锚点前面即可。但需要注意的是，在进行 DOM 的移动操作之前，仍然需要调用 patch 函数在新旧虚拟节点之间打补丁。

在这一步 DOM 的移动操作完成后，接下来是比较关键的步骤，即更新索引值。由于第四步中涉及的两个索引分别是oldEndIdx 和 newStartIdx，所以我们需要更新两者的值，让它们各自朝正确的方向前进一步，并指向下一个节点。下图给出了更新前新旧两组子节点以及真实 DOM 节点的状态：
在这里插入图片描述
下图给出了在第四步的比较中，第一步 DOM 移动操作完成后，新旧两组子节点以及真实 DOM 节点的状态：
在这里插入图片描述
此时，真实 DOM 节点顺序为 p-4、p-1、p-2、p-3，这与新的一组子节点顺序不一致。这是因为 Diff 算法还没有结束，还需要进行下一轮更新。因此，我们需要将更新逻辑封装到一个while 循环中，如下面的代码所示：

01 while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
02   if (oldStartVNode.key === newStartVNode.key) {
03     // 步骤一：oldStartVNode 和 newStartVNode 比较
04   } else if (oldEndVNode.key === newEndVNode.key) {
05     // 步骤二：oldEndVNode 和 newEndVNode 比较
06   } else if (oldStartVNode.key === newEndVNode.key) {
07     // 步骤三：oldStartVNode 和 newEndVNode 比较
08   } else if (oldEndVNode.key === newStartVNode.key) {
09     // 步骤四：oldEndVNode 和 newStartVNode 比较
10     // 仍然需要调用 patch 函数进行打补丁
11     patch(oldEndVNode, newStartVNode, container)
12     // 移动 DOM 操作
13     // oldEndVNode.el 移动到 oldStartVNode.el 前面
14     insert(oldEndVNode.el, container, oldStartVNode.el)
15
16     // 移动 DOM 完成后，更新索引值，指向下一个位置
17     oldEndVNode = oldChildren[--oldEndIdx]
18     newStartVNode = newChildren[++newStartIdx]
19   }
20 }

由于在每一轮更新完成之后，紧接着都会更新四个索引中与当前更新轮次相关联的索引，所以整个 while 循环执行的条件是：头部索引值要小于等于尾部索引值。

在第一轮更新结束后循环条件仍然成立，因此需要进行下一轮的比较，如上图所示：

  • 第一步：比较旧的一组子节点中的头部节点 p-1 与新的一组子节点中的头部节点 p-2，看看它们是否相同。由于两者的 key 值不同，不可复用，所以什么都不做。

这里，我们使用了新的名词：头部节点。它指的是头部索引oldStartIdx 和 newStartIdx 所指向的节点。

  • 第二步：比较旧的一组子节点中的尾部节点 p-3 与新的一组子节点中的尾部节点 p-3，两者的 key 值相同，可以复用。另外，由于两者都处于尾部，因此不需要对真实 DOM 进行移动操作，只需要打补丁即可，如下面的代码所示：
01 while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
02   if (oldStartVNode.key === newStartVNode.key) {
03     // 步骤一：oldStartVNode 和 newStartVNode 比较
04   } else if (oldEndVNode.key === newEndVNode.key) {
05     // 步骤二：oldEndVNode 和 newEndVNode 比较
06     // 节点在新的顺序中仍然处于尾部，不需要移动，但仍需打补丁
07     patch(oldEndVNode, newEndVNode, container)
08     // 更新索引和头尾部节点变量
09     oldEndVNode = oldChildren[--oldEndIdx]
10     newEndVNode = newChildren[--newEndIdx]
11   } else if (oldStartVNode.key === newEndVNode.key) {
12     // 步骤三：oldStartVNode 和 newEndVNode 比较
13   } else if (oldEndVNode.key === newStartVNode.key) {
14     // 步骤四：oldEndVNode 和 newStartVNode 比较
15     patch(oldEndVNode, newStartVNode, container)
16     insert(oldEndVNode.el, container, oldStartVNode.el)
17     oldEndVNode = oldChildren[--oldEndIdx]
18     newStartVNode = newChildren[++newStartIdx]
19   }
20 }

在这一轮更新完成之后，新旧两组子节点与真实 DOM 节点的状态如下图所示：
在这里插入图片描述
真实 DOM 的顺序相比上一轮没有变化，因为在这一轮的比较中没有对 DOM 节点进行移动，只是对 p-3 节点打补丁。接下来，我们再根据上图所示的状态执行下一轮的比较：

  • 第一步：比较旧的一组子节点中的头部节点 p-1 与新的一组子节点中的头部节点 p-2，看看它们是否相同。由于两者的 key 值不同，不可复用，因此什么都不做。
  • 第二步：比较旧的一组子节点中的尾部节点 p-2 与新的一组子节点中的尾部节点 p-1，看看它们是否相同，由于两者的 key 值不同，不可复用，因此什么都不做。
  • 第三步：比较旧的一组子节点中的头部节点 p-1 与新的一组子节点中的尾部节点 p-1。两者的 key 值相同，可以复用。

在第三步的比较中，我们找到了相同的节点，这说明：节点 p-1 原本是头部节点，但在新的顺序中，它变成了尾部节点。因此，我们需要将节点 p-1 对应的真实 DOM 移动到旧的一组子节点的尾部节点 p-2 所对应的真实 DOM 后面，同时还需要更新相应的索引到下一个位置，如下图所示：
在这里插入图片描述
这一步的代码实现如下：

01 while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
02   if (oldStartVNode.key === newStartVNode.key) {
03   } else if (oldEndVNode.key === newEndVNode.key) {
04     patch(oldEndVNode, newEndVNode, container)
05     oldEndVNode = oldChildren[--oldEndIdx]
06     newEndVNode = newChildren[--newEndIdx]
07   } else if (oldStartVNode.key === newEndVNode.key) {
08     // 调用 patch 函数在 oldStartVNode 和 newEndVNode 之间打补丁
09     patch(oldStartVNode, newEndVNode, container)
10     // 将旧的一组子节点的头部节点对应的真实 DOM 节点 oldStartVNode.el 移动到
11     // 旧的一组子节点的尾部节点对应的真实 DOM 节点后面
12     insert(oldStartVNode.el, container, oldEndVNode.el.nextSibling)
13     // 更新相关索引到下一个位置
14     oldStartVNode = oldChildren[++oldStartIdx]
15     newEndVNode = newChildren[--newEndIdx]
16   } else if (oldEndVNode.key === newStartVNode.key) {
17     patch(oldEndVNode, newStartVNode, container)
18     insert(oldEndVNode.el, container, oldStartVNode.el)
19
20     oldEndVNode = oldChildren[--oldEndIdx]
21     newStartVNode = newChildren[++newStartIdx]
22   }
23 }

如上面的代码所示，如果旧的一组子节点的头部节点与新的一组子节点的尾部节点匹配，则说明该旧节点所对应的真实 DOM 节点需要移动到尾部。因此，我们需要获取当前尾部节点的下一个兄弟节点作为锚点，即 oldEndVNode.el.nextSibling。最后，更新相关索引到下一个位置。

通过上图可知，此时，新旧两组子节点的头部索引和尾部索引发生重合，但仍然满足循环的条件，所以还会进行下一轮的更新。而在接下来的这一轮的更新中，更新步骤也发生了重合。

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

代码实现如下：

01 while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
02   if (oldStartVNode.key === newStartVNode.key) {
03     // 调用 patch 函数在 oldStartVNode 与 newStartVNode 之间打补丁
04     patch(oldStartVNode, newStartVNode, container)
05     // 更新相关索引，指向下一个位置
06     oldStartVNode = oldChildren[++oldStartIdx]
07     newStartVNode = newChildren[++newStartIdx]
08   } else if (oldEndVNode.key === newEndVNode.key) {
09     patch(oldEndVNode, newEndVNode, container)
10     oldEndVNode = oldChildren[--oldEndIdx]
11     newEndVNode = newChildren[--newEndIdx]
12   } else if (oldStartVNode.key === newEndVNode.key) {
13     patch(oldStartVNode, newEndVNode, container)
14     insert(oldStartVNode.el, container, oldEndVNode.el.nextSibling)
15
16     oldStartVNode = oldChildren[++oldStartIdx]
17     newEndVNode = newChildren[--newEndIdx]
18   } else if (oldEndVNode.key === newStartVNode.key) {
19     patch(oldEndVNode, newStartVNode, container)
20     insert(oldEndVNode.el, container, oldStartVNode.el)
21
22     oldEndVNode = oldChildren[--oldEndIdx]
23     newStartVNode = newChildren[++newStartIdx]
24   }
25 }

在这一轮更新之后，新旧两组子节点与真实 DOM 节点的状态如下图所示：
在这里插入图片描述
此时，真实 DOM 节点的顺序与新的一组子节点的顺序相同了：p-4、p-2、p-1、p-3。另外，在这一轮更新完成之后，索引 newStartIdx 和索引 oldStartIdx 的值都小于 newEndIdx 和oldEndIdx，所以循环终止，双端 Diff 算法执行完毕。

2、双端比较的优势

理解了双端比较的原理之后，我们来看看与简单 Diff 算法相比，双端 Diff 算法具有怎样的优势。我们拿下图所示的例子来看：
在这里插入图片描述
上图给出了新旧两组子节点的节点顺序。当使用简单 Diff 算法对此例进行更新时，会发生两次 DOM 移动操作，下图所示：
在这里插入图片描述
如果使用双端 Diff 算法对此例进行更新，会有怎样的表现呢？接下来，我们就以双端比较的思路来完成此例的更新，看一看双端 Diff 算法能否减少 DOM 移动操作次数。

下图给出了算法执行之前新旧两组子节点与真实 DOM 节点的状态：
在这里插入图片描述
接下来，我们按照双端比较的步骤执行更新：

  • 第一步：比较旧的一组子节点中的头部节点 p-1 与新的一组子节点中的头部节点 p-3，两者 key 值不同，不可复用。
  • 第二步：比较旧的一组子节点中的尾部节点 p-3 与新的一组子节点中的尾部节点 p-2，两者 key 值不同，不可复用。
  • ●第三步：比较旧的一组子节点中的头部节点 p-1 与新的一组子节点中的尾部节点 p-2，两者 key 值不同，不可复用。
  • 第四步：比较旧的一组子节点中的尾部节点 p-3 与新的一组子节点中的头部节点 p-3，发现可以进行复用。

可以看到，在第四步的比较中，我们找到了可复用的节点 p-3。该节点原本处于所有子节点的尾部，但在新的一组子节点中它处于头部。因此，只需要让节点 p-3 对应的真实 DOM 变成新的头部节点即可。在这一步移动操作之后，新旧两组子节点以及真实 DOM 节点的状态如下图所示：
在这里插入图片描述
观察上图能够发现，在这一轮比较过后，真实 DOM 节点的顺序已经与新的一组子节点的顺序一致了。换句话说，我们完成了更新，不过算法仍然会继续执行。开始下一轮的比较：

  • 第一步：比较旧的一组子节点中的头部节点 p-1 与新的一组子节点中的头部节点 p-1，两者的 key 值相同，可以复用。但由于两者都处于头部，因此不需要移动，只需要打补丁即可。

在这一轮比较过后，新旧两组子节点与真实 DOM 节点的状态如下图所示：
在这里插入图片描述此时，双端 Diff 算法仍然没有停止，开始新一轮的比较：

  • 第一步：比较旧的一组子节点中的头部节点 p-2 与新的一组子节点中的头部节点 p-2，两者的 key 值相同，可以复用。但由于两者都处于头部，因此不需要移动，只需要打补丁即可。

在这一轮比较过后，新旧两组子节点与真实 DOM 节点的状态如下图所示：
在这里插入图片描述
到这一步后，索引 newStartIdx 和 oldStartIdx 的值比索引newEndIdx 和 oldEndIdx 的值大，于是更新结束。可以看到，对于同样的例子，采用简单 Diff 算法需要两次 DOM 移动操作才能完成更新，而使用双端 Diff 算法只需要一次 DOM 移动操作即可完成更新。

3、非理想状况的处理方式

在上一节的讲解中，我们用了一个比较理想的例子。我们知道，双端 Diff 算法的每一轮比较的过程都分为四个步骤。在上一节的例子中，每一轮比较都会命中四个步骤中的一个，这是非常理想的情况。但实际上，并非所有情况都这么理想，如下图所示：
在这里插入图片描述
在这个例子中，新旧两组子节点的顺序如下：

  • 旧的一组子节点：p-1、p-2、p-3、p-4。
  • 新的一组子节点：p-2、p-4、p-1、p-3。

当我们尝试按照双端 Diff 算法的思路进行第一轮比较时，会发现无法命中四个步骤中的任何一步。

  • 第一步：比较旧的一组子节点中的头部节点 p-1 与新的一组子节点中的头部节点 p-2，不可复用。
  • 第二步：比较旧的一组子节点中的尾部节点 p-4 与新的一组子节点中的尾部节点 p-3，不可复用。
  • 第三步：比较旧的一组子节点中的头部节点 p-1 与新的一组子节点中的尾部节点 p-3，不可复用。
  • 第四步：比较旧的一组子节点中的尾部节点 p-4 与新的一组子节点中的头部节点 p-2，不可复用。

在四个步骤的比较过程中，都无法找到可复用的节点，应该怎么办呢？这时，我们只能通过增加额外的处理步骤来处理这种非理想情况。既然两个头部和两个尾部的四个节点中都没有可复用的节点，那么我们就尝试看看非头部、非尾部的节点能否复用。具体做法是，拿新的一组子节点中的头部节点去旧的一组子节点中寻找，如下面的代码所示：

01 while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
02   if (oldStartVNode.key === newStartVNode.key) {
03     // 省略部分代码
04   } else if (oldEndVNode.key === newEndVNode.key) {
05     // 省略部分代码
06   } else if (oldStartVNode.key === newEndVNode.key) {
07     // 省略部分代码
08   } else if (oldEndVNode.key === newStartVNode.key) {
09     // 省略部分代码
10   } else {
11     // 遍历旧的一组子节点，试图寻找与 newStartVNode 拥有相同 key 值的节点
12     // idxInOld 就是新的一组子节点的头部节点在旧的一组子节点中的索引
13     const idxInOld = oldChildren.findIndex(
14       node => node.key === newStartVNode.key
15     )
16   }
17 }

在上面这段代码中，我们遍历旧的一组子节点，尝试在其中寻找与新的一组子节点的头部节点具有相同 key 值的节点，并将该节点在旧的一组子节点中的索引存储到变量 idxInOld 中。这么做的目的是什么呢？想要搞清楚这个问题，本质上需要我们先搞清楚：在旧的一组子节点中，找到与新的一组子节点的头部节点具有相同 key 值的节点意味着什么？如下图所示：
在这里插入图片描述
观察上图，当我们拿新的一组子节点的头部节点 p-2 去旧的一组子节点中查找时，会在索引为 1 的位置找到可复用的节点。这意味着，节点 p-2 原本不是头部节点，但在更新之后，它应该变成头部节点。所以我们需要将节点 p-2 对应的真实DOM 节点移动到当前旧的一组子节点的头部节点 p-1 所对应的真实 DOM 节点之前。具体实现如下：

01 while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
02   if (oldStartVNode.key === newStartVNode.key) {
03     // 省略部分代码
04   } else if (oldEndVNode.key === newEndVNode.key) {
05     // 省略部分代码
06   } else if (oldStartVNode.key === newEndVNode.key) {
07     // 省略部分代码
08   } else if (oldEndVNode.key === newStartVNode.key) {
09     // 省略部分代码
10   } else {
11     // 遍历旧 children，试图寻找与 newStartVNode 拥有相同 key 值的元素
12     const idxInOld = oldChildren.findIndex(
13       node => node.key === newStartVNode.key
14     )
15     // idxInOld 大于 0，说明找到了可复用的节点，并且需要将其对应的真实 DOM 移动到头部
16     if (idxInOld > 0) {
17       // idxInOld 位置对应的 vnode 就是需要移动的节点
18       const vnodeToMove = oldChildren[idxInOld]
19       // 不要忘记除移动操作外还应该打补丁
20       patch(vnodeToMove, newStartVNode, container)
21       // 将 vnodeToMove.el 移动到头部节点 oldStartVNode.el 之前，因此使用后者作为锚点
22       insert(vnodeToMove.el, container, oldStartVNode.el)
23       // 由于位置 idxInOld 处的节点所对应的真实 DOM 已经移动到了别处，因此将其设置为 undefined
24       oldChildren[idxInOld] = undefined
25       // 最后更新 newStartIdx 到下一个位置
26       newStartVNode = newChildren[++newStartIdx]
27     }
28   }
29 }

在上面这段代码中，首先判断 idxInOld 是否大于 0。如果条件成立，则说明找到了可复用的节点，然后将该节点对应的真实DOM 移动到头部。为此，我们先要获取需要移动的节点，这里的 oldChildren[idxInOld] 所指向的节点就是需要移动的节点。在移动节点之前，不要忘记调用 patch 函数进行打补丁。接着，调用 insert 函数，并以现在的头部节点对应的真实 DOM 节点 oldStartVNode.el 作为锚点参数来完成节点的移动操作。当节点移动完成后，还有两步工作需要做：

  • 由于处于 idxInOld 处的节点已经处理过了（对应的真实DOM 移到了别处），因此我们应该将 oldChildren[idxInOld]设置为 undefined。
  • 新的一组子节点中的头部节点已经处理完毕，因此将newStartIdx 前进到下一个位置。

经过上述两个步骤的操作后，新旧两组子节点以及真实 DOM 节点的状态如下图所示：
在这里插入图片描述
此时，真实 DOM 的顺序为：p-2、p-1、p-3、p-4。接着，双端 Diff 算法会继续进行，如下图所示：
在这里插入图片描述

  • 第一步：比较旧的一组子节点中的头部节点 p-1 与新的一组子节点中的头部节点 p-4，两者 key 值不同，不可复用。
  • 第二步：比较旧的一组子节点中的尾部节点 p-4 与新的一组子节点中的尾部节点 p-3，两者 key 值不同，不可复用。
  • 第三步：比较旧的一组子节点中的头部节点 p-1 与新的一组子节点中的尾部节点 p-3，两者 key 值不同，不可复用。
  • 第四步：比较旧的一组子节点中的尾部节点 p-4 与新的一组子节点中的头部节点 p-4，两者的 key 值相同，可以复用。

在这一轮比较的第四步中，我们找到了可复用的节点。因此，按照双端 Diff 算法的逻辑移动真实 DOM，即把节点 p-4 对应的真实 DOM 移动到旧的一组子节点中头部节点 p-1 所对应的真实 DOM 前面，如下图所示：
在这里插入图片描述
此时，真实 DOM 节点的顺序是：p-2、p-4、p-1、p-3。接着，开始下一轮的比较。

第一步：比较旧的一组子节点中的头部节点 p-1 与新的一组子节点中的头部节点 p-1，两者的 key 值相同，可以复用。

在这一轮比较中，第一步就找到了可复用的节点。由于两者都处于头部，所以不需要对真实 DOM 进行移动，只需要打补丁即可。在这一步操作过后，新旧两组子节点与真实 DOM 节点的状态如下图所示：
在这里插入图片描述
此时，真实 DOM 节点的顺序是：p-2、p-4、p-1、p-3。接着，进行下一轮的比较。需要注意的一点是，此时旧的一组子节点的头部节点是 undefined。这说明该节点已经被处理过了，因此不需要再处理它了，直接跳过即可。为此，我们需要补充这部分逻辑的代码，具体实现如下：

01 while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
02   // 增加两个判断分支，如果头尾部节点为 undefined，则说明该节点已经被处理过了，直接跳到下一个位置
03   if (!oldStartVNode) {
04     oldStartVNode = oldChildren[++oldStartIdx]
05   } else if (!oldEndVNode) {
06     oldEndVNode = oldChildren[--oldEndIdx]
07   } else if (oldStartVNode.key === newStartVNode.key) {
08     // 省略部分代码
09   } else if (oldEndVNode.key === newEndVNode.key) {
10     // 省略部分代码
11   } else if (oldStartVNode.key === newEndVNode.key) {
12     // 省略部分代码
13   } else if (oldEndVNode.key === newStartVNode.key) {
14     // 省略部分代码
15   } else {
16     const idxInOld = oldChildren.findIndex(
17       node => node.key === newStartVNode.key
18     )
19     if (idxInOld > 0) {
20       const vnodeToMove = oldChildren[idxInOld]
21       patch(vnodeToMove, newStartVNode, container)
22       insert(vnodeToMove.el, container, oldStartVNode.el)
23       oldChildren[idxInOld] = undefined
24       newStartVNode = newChildren[++newStartIdx]
25     }
26
27   }
28 }

观察上面的代码，在循环开始时，我们优先判断头部节点和尾部节点是否存在。如果不存在，则说明它们已经被处理过了，直接跳到下一个位置即可。在这一轮比较过后，新旧两组子节点与真实 DOM 节点的状态如下图所示：
在这里插入图片描述
现在，四个步骤又重合了，接着进行最后一轮的比较。

  • 第一步：比较旧的一组子节点中的头部节点 p-3 与新的一组子节点中的头部节点 p-3，两者的 key 值相同，可以复用。

在第一步中找到了可复用的节点。由于两者都是头部节点，因此不需要进行 DOM 移动操作，直接打补丁即可。在这一轮比较过后，最终状态如下图所示：
在这里插入图片描述

4、添加新元素

在上一节中，我们讲解了非理想情况的处理，即在一轮比较过程中，不会命中四个步骤中的任何一步。这时，我们会拿新的一组子节点中的头部节点去旧的一组子节点中寻找可复用的节点，然而并非总能找得到，如下图的例子所示：
在这里插入图片描述
在这个例子中，新旧两组子节点的顺序如下：

  • 旧的一组子节点：p-1、p-2、p-3。
  • 新的一组子节点：p-4、p-1、p-3、p-2。

首先，我们尝试进行第一轮比较，发现在四个步骤的比较中都找不到可复用的节点。于是我们尝试拿新的一组子节点中的头部节点 p-4 去旧的一组子节点中寻找具有相同 key 值的节点，但在旧的一组子节点中根本就没有 p-4 节点，如下图所示：
在这里插入图片描述

这说明节点 p-4 是一个新增节点，我们应该将它挂载到正确的位置。那么应该挂载到哪里呢？很简单，因为节点 p-4 是新的一组子节点中的头部节点，所以只需要将它挂载到当前头部节点之前即可。“当前”头部节点指的是，旧的一组子节点中的头部节点所对应的真实 DOM 节点 p-1。下面是用来完成挂载操作的代码：

01 while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
02   // 增加两个判断分支，如果头尾部节点为 undefined，则说明该节点已经被处理过了，直接跳到下一个位置
03   if (!oldStartVNode) {
04     oldStartVNode = oldChildren[++oldStartIdx]
05   } else if (!oldEndVNode) {
06     oldEndVNode = newChildren[--oldEndIdx]
07   } else if (oldStartVNode.key === newStartVNode.key) {
08     // 省略部分代码
09   } else if (oldEndVNode.key === newEndVNode.key) {
10     // 省略部分代码
11   } else if (oldStartVNode.key === newEndVNode.key) {
12     // 省略部分代码
13   } else if (oldEndVNode.key === newStartVNode.key) {
14     // 省略部分代码
15   } else {
16     const idxInOld = oldChildren.findIndex(
17       node => node.key === newStartVNode.key
18     )
19     if (idxInOld > 0) {
20       const vnodeToMove = oldChildren[idxInOld]
21       patch(vnodeToMove, newStartVNode, container)
22       insert(vnodeToMove.el, container, oldStartVNode.el)
23       oldChildren[idxInOld] = undefined
24     } else {
25       // 将 newStartVNode 作为新节点挂载到头部，使用当前头部节点 oldStartVNode.el 作为锚点
26       patch(null, newStartVNode, container, oldStartVNode.el)
27     }
28     newStartVNode = newChildren[++newStartIdx]
29   }
30 }

如上面的代码所示，当条件 idxInOld > 0 不成立时，说明newStartVNode 节点是全新的节点。又由于 newStartVNode 节点是头部节点，因此我们应该将其作为新的头部节点进行挂载。所以，在调用 patch 函数挂载节点时，我们使用oldStartVNode.el 作为锚点。在这一步操作完成之后，新旧两组子节点以及真实 DOM 节点的状态如下图所示：
在这里插入图片描述

当新节点 p-4 挂载完成后，会进行后续的更新，直到全部更新完成为止。但这样就完美了吗？答案是否定的，我们再来看另外一个例子，如下图所示：
在这里插入图片描述
这个例子与上一个的例子的不同之处在于，我们调整了新的一组子节点的顺序：p-4、p-1、p-2、p-3。下面我们按照双端Diff 算法的思路来执行更新，看看会发生什么：

  • 第一步：比较旧的一组子节点中的头部节点 p-1 与新的一组子节点中的头部节点 p-4，两者的 key 值不同，不可以复用。
  • 第二步：比较旧的一组子节点中的尾部节点 p-3 与新的一组子节点中的尾部节点 p-3，两者的 key 值相同，可以复用。

在第二步中找到了可复用的节点，因此进行更新。更新后的新旧两组子节点以及真实 DOM 节点的状态如下图所示：
在这里插入图片描述
接着进行下一轮的比较：

  • 第一步：比较旧的一组子节点中的头部节点 p-1 与新的一组子节点中的头部节点 p-4，两者的 key 值不同，不可以复用。
  • 第二步：比较旧的一组子节点中的尾部节点 p-2 与新的一组子节点中的尾部节点 p-2，两者的 key 值相同，可以复用。

我们又在第二步找到了可复用的节点，于是再次进行更新。更新后的新旧两组子节点以及真实 DOM 节点的状态如下图所示：
在这里插入图片描述
接着，进行下一轮的更新：

  • 第一步：比较旧的一组子节点中的头部节点 p-1 与新的一组子节点中的头部节点 p-4，两者的 key 值不同，不可以复用。
  • 第二步：比较旧的一组子节点中的尾部节点 p-1 与新的一组子节点中的尾部节点 p-1，两者的 key 值相同，可以复用。

还是在第二步找到了可复用的节点，再次进行更新。更新后的新旧两组子节点以及真实 DOM 节点的状态如下图所示：
在这里插入图片描述
当这一轮更新完毕后，由于变量 oldStartIdx 的值大于oldEndIdx 的值，满足更新停止的条件，因此更新停止。但通过观察可知，节点 p-4 在整个更新过程中被遗漏了，没有得到任何处理，这说明我们的算法是有缺陷的。为了弥补这个缺陷，我们需要添加额外的处理代码，如下所示：

01 while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
02   // 省略部分代码
03 }
04
05 // 循环结束后检查索引值的情况，
06 if (oldEndIdx < oldStartIdx && newStartIdx <= newEndIdx) {
07   // 如果满足条件，则说明有新的节点遗留，需要挂载它们
08   for (let i = newStartIdx; i <= newEndIdx; i++) {
09     patch(null, newChildren[i], container, oldStartVNode.el)
10   }
11 }

我们在 while 循环结束后增加了一个 if 条件语句，检查四个索引值的情况。根据上图可知，如果条件 oldEndIdx <oldStartIdx && newStartIdx <= newEndIdx 成立，说明新的一组子节点中有遗留的节点需要作为新节点挂载。哪些节点是新节点呢？索引值位于 newStartIdx 和 newEndIdx 这个区间内的节点都是新节点。于是我们开启一个 for 循环来遍历这个区间内的节点并逐一挂载。挂载时的锚点仍然使用当前的头部节点 oldStartVNode.el，这样就完成了对新增元素的处理。

5、移除不存在的元素

解决了新增节点的问题后，我们再来讨论关于移除元素的情况，如下图的例子所示：
在这里插入图片描述
在这个例子中，新旧两组子节点的顺序如下：

  • 旧的一组子节点：p-1、p-2、p-3。
  • 新的一组子节点：p-1、p-3。

可以看到，在新的一组子节点中 p-2 节点已经不存在了。为了搞清楚应该如何处理节点被移除的情况，我们还是按照双端Diff 算法的思路执行更新。

第一步：比较旧的一组子节点中的头部节点 p-1 与新的一组子节点中的头部节点 p-1，两者的 key 值相同，可以复用。

在第一步的比较中找到了可复用的节点，于是执行更新。在这一轮比较过后，新旧两组子节点以及真实 DOM 节点的状态如下图所示：
在这里插入图片描述
接着，执行下一轮更新：

  • 第一步：比较旧的一组子节点中的头部节点 p-2 与新的一组子节点中的头部节点 p-3，两者的 key 值不同，不可以复用。
  • 第二步：比较旧的一组子节点中的尾部节点 p-3 与新的一组子节点中的尾部节点 p-3，两者的 key 值相同，可以复用。

在第二步中找到了可复用的节点，于是进行更新。更新后的新旧两组子节点以及真实 DOM 节点的状态如下图所示：
在这里插入图片描述
此时变量 newStartIdx 的值大于变量 newEndIdx 的值，满足更新停止的条件，于是更新结束。但观察上图可知，旧的一组子节点中存在未被处理的节点，应该将其移除。因此，我们需要增加额外的代码来处理它，如下所示：

01 while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
02   // 省略部分代码
03 }
04
05 if (oldEndIdx < oldStartIdx && newStartIdx <= newEndIdx) {
06   // 添加新节点
07   // 省略部分代码
08 } else if (newEndIdx < newStartIdx && oldStartIdx <= oldEndIdx) {
09   // 移除操作
10   for (let i = oldStartIdx; i <= oldEndIdx; i++) {
11     unmount(oldChildren[i])
12   }
13 }

与处理新增节点类似，我们在 while 循环结束后又增加了一个else…if 分支，用于卸载已经不存在的节点。由上图可知，索引值位于 oldStartIdx 和 oldEndIdx 这个区间内的节点都应该被卸载，于是我们开启一个 for 循环将它们逐一卸载。

6、总结

双端 Diff 算法指的是，在新旧两组子节点的四个端点之间分别进行比较，并试图找到可复用的节点。相比简单 Diff 算法，双端Diff 算法的优势在于，对于同样的更新场景，执行的 DOM 移动操作次数更少。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/201244.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

Nginx部署前端项目

Nginx部署前端项目

Nginx部署前端项目 1.在nginx官网http://nginx.org/en/download.html &#xff0c;下载稳定版本&#xff1a; 2.解压后&#xff0c;点击根目录中的nginx.exe即可启动Nginx&#xff0c;或是在nginx安装目录中启动cmd并输入以下命令启动&#xff1a; nginx.exe 或 start nginx3…
阅读更多...
Cannot read properties of undefined (reading ‘resetFields‘)“ 报错解决

Cannot read properties of undefined (reading ‘resetFields‘)“ 报错解决

遇到这种报错 先去相关页面搜索关键字 定位到具体的报错代码 Cannot read properties of undefined (reading ‘resetFields’)" 关键字&#xff1a;resetFields 此方法作用&#xff1a;对整个表单进行重置 将所有字段值重置为初始值并移除校验结果 报错场景&#xff1a;…
阅读更多...
SWT/Jface(1): 表格的创建和渲染

SWT/Jface(1): 表格的创建和渲染

前言 使用JFace创建表格还是比较方便的, 如果仅仅是创建空表格的话, 以下2步即可完成: 创建TableViewer对象, 指定样式, 比如是否支持多行选择, 有无边框, 是否支持滚动条等创建TableColumn对象: 包括列展示名称, 宽度和样式等, 最终绑定到table对象 实例 创建表格 //注意…
阅读更多...
深入浅出 Linux 中的 ARM IOMMU SMMU I

深入浅出 Linux 中的 ARM IOMMU SMMU I

Linux 系统下的 SMMU 介绍 在计算机系统架构中&#xff0c;与传统的用于 CPU 访问内存的管理的 MMU 类似&#xff0c;IOMMU (Input Output Memory Management Unit) 将来自系统 I/O 设备的 DMA 请求传递到系统互连之前&#xff0c;它会先转换请求的地址&#xff0c;并对系统 I…
阅读更多...
灵活运用Vue 3中的setup函数—深入解析Composition API

灵活运用Vue 3中的setup函数—深入解析Composition API

新建项目&#xff0c;项目主入口为App.vue&#xff08;主组件&#xff09;&#xff0c;新建child.vue&#xff08;子组件&#xff09;。 1.1 setup 执行 时机问题 1.在主组件里引入子组件和ref&#xff1a; import {ref} from vue import child from ./components/child.vue2…
阅读更多...
爆款文章有诀窍，内容创作者如何能持续产出优质内容

爆款文章有诀窍，内容创作者如何能持续产出优质内容

内容营销人有没有这么一种共鸣&#xff1a;10 万 那么多&#xff0c;为什么不能多我一个&#xff1f; 通常&#xff0c;我们把浏览量 / 阅读量高、转评赞数量高的内容看作爆款&#xff0c;而数据如果达到 10 万 则是超级爆款。因为&#xff0c;阅读量高意味着内容得到了大量的曝…
阅读更多...
Unsupervised Condition GAN

Unsupervised Condition GAN

Unsupervised Condition GAN主要有两种做法&#xff1a; Direct Transformation 直接输入domain X图片&#xff0c;经过Generator后生成对应的domain Y的图像。这种转化input和output不能够差太多。通常只能实现较小的转化&#xff0c;比如改变颜色等。 Projection to Commo…
阅读更多...
人工智能的时代---AI的影响

人工智能的时代---AI的影响

人工智能&#xff08;AI&#xff09;是当前科技领域的一个热门话题&#xff0c;它正在以前所未有的速度改变着我们的生活方式和工作方式。从智能家居到自动驾驶&#xff0c;从智能医疗到智能金融&#xff0c;人工智能正在渗透到我们生活的方方面面。在这篇文章中&#xff0c;我…
阅读更多...
Java项目实战《苍穹外卖》 三、登录功能

Java项目实战《苍穹外卖》 三、登录功能

测测你是什么人格吧&#xff0c;地址&#xff1a; MBTI 16种人格测试官网 系列文章目录 苍穹外卖是黑马程序员2023年的Java实战项目&#xff0c;作为业余练手用&#xff0c;需要源码或者课程的可以找我&#xff0c;无偿分享 Java项目实战《苍穹外卖》 一、项目概述Java项目实战…
阅读更多...
10月起个税系统升级，3个月个税零申报将收到提示

10月起个税系统升级，3个月个税零申报将收到提示

近日&#xff0c;自然人电子税务局扣缴端升级了&#xff0c;升级后对于工资薪金收入连续三个月为零的纳税人&#xff0c;系统会自动出现以下提示。这个提示主要为了避免企业长期对已经离职的员工进行零申报&#xff0c;导致数据不准确和资源浪费。HR在申报个税时&#xff0c;一…
阅读更多...
虚拟摇杆OnJoystickMove未被调用，角色不移动

虚拟摇杆OnJoystickMove未被调用，角色不移动

更改interaction type 为 event notification
阅读更多...
什么是应急演练脚本?其设计原则是什么?

什么是应急演练脚本?其设计原则是什么?

应急演练脚本是一种系统性、有计划的模拟性文件&#xff0c;旨在测试和评估组织在紧急情况下的应对能力。这种脚本提供了一系列步骤和场景&#xff0c;以确保团队能够高效、协调地应对各种紧急事件。以下将详细探讨应急演练脚本的定义、设计原则以及实施过程。 一、应急演练脚本…
阅读更多...
React整理总结（五、Redux）

React整理总结（五、Redux）

1.Redux核心概念 纯函数 确定的输入&#xff0c;一定会产生确定的输出&#xff1b;函数在执行过程中&#xff0c;不能产生副作用 store 存储数据 action 更改数据 reducer 连接store和action的纯函数 将传入的state和action结合&#xff0c;生成一个新的state dispatc…
阅读更多...
IPFoxy：什么是数据中心代理IP？好用吗？

IPFoxy：什么是数据中心代理IP？好用吗？

数据中心代理是代理IP中最常见的类型&#xff0c;也被称为机房IP。这些代理服务器为用户分配不属于 ISP&#xff08;互联网服务提供商&#xff09;而来自第三方云服务提供商的 IP 地址。数据中心代理的最大优势——它们允许在访问网络时完全匿名。 如果你正在寻找海外代理IP&am…
阅读更多...
【Java 进阶篇】揭秘 Jackson：Java 对象转 JSON 注解的魔法

【Java 进阶篇】揭秘 Jackson：Java 对象转 JSON 注解的魔法

嗨&#xff0c;亲爱的同学们&#xff01;欢迎来到这篇关于 Jackson JSON 解析器中 Java 对象转 JSON 注解的详细解析指南。JSON&#xff08;JavaScript Object Notation&#xff09;是一种常用于数据交换的轻量级数据格式&#xff0c;而 Jackson 作为一款优秀的 JSON 解析库&am…
阅读更多...
js进阶笔记之原型，原型链

js进阶笔记之原型，原型链

目录 1、原型对象 constructor 属性 对象原型 2、原型链 3、instanceof 4、原型继承 1、原型对象 面向过程就是分析出解决问题所需要的步骤&#xff0c;然后用函数把这些步骤一步一步实现&#xff0c;使用的时候再一个一个的依次调用就可以了。 面向对象是把事务分解成为…
阅读更多...
python刷题笔记1（42例题）

python刷题笔记1（42例题）

1. split()函数 str.split([sep [, maxsplit]]) 分割字符串&#xff0c;返回一个数组 2. 判断子串 # 判断子串是否在主串里面&#xff0c;是则输出“Yes”&#xff0c;否则输出“No” str1 input("子串&#xff1a;") str2 input("主串:") if str1 in s…
阅读更多...
最新绿豆APP源码苹果CMS影视插件版本/原生JAVA源码+反编译开源+免授权

最新绿豆APP源码苹果CMS影视插件版本/原生JAVA源码+反编译开源+免授权

源码简介&#xff1a; 最新绿豆APP源码苹果CMS影视插件版本&#xff0c;它是原生JAVA源码反编译开源免授权&#xff0c;绿豆影视对接苹果CMS&#xff0c;它可以支持多功能自定义DIY页面布局。 1、新版绿豆视频APP视频6.1插件版反编译指南及教程 2、后端插件开源&#xff0c;可…
阅读更多...
创建 Springboot 项目

创建 Springboot 项目

前言 创建 Spring Boot 项目是很多Java开发人员入门的重要一步&#xff01; 欢迎来到本篇关于创建 Spring Boot 项目的博客&#xff01;Spring Boot作为一个快速、便捷的开发框架&#xff0c;为我们提供了简化和加速应用程序开发的利器。 在这个数字化时代&#xff0c;快速响…
阅读更多...
在Jupyter Lab中使用多个环境，及魔法命令简介

在Jupyter Lab中使用多个环境，及魔法命令简介

一、Jupyter Lab使用conda虚拟环境 1、给虚拟环境添加 ipykernel 方法一: 创建环境时直接添加ipykernel 方法&#xff1a;conda create -n 【虚拟环境名称】python3.8 ipykernel实例如下&#xff1a; conda create -n tensorflow_cpu python3.8 ipykernel 方法二&#xff…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023