另一个思路 - 双端比较

双端比较的原理

双端比较:新旧 children 各设头尾两个指针,一轮最多做头头、尾尾、头尾、尾头四次比较,命中即复用并向中间收拢

刚刚提到了 React 的 Diff 算法是存在优化空间的，想要要找到优化的关键点，我们首先要知道它存在什么问题。来看下图：

在这个例子中，我们可以通过肉眼观察从而得知最优的解决方案应该是：把li-c 节点对应的真实 DOM 移动到最前面即可，只需要一次移动即可完成更新。然而，React 所采用的 Diff 算法在更新如上案例的时候，会进行两次移动：

显然，这种做法必然会造成额外的性能开销。那么有没有办法来避免这种多余的 DOM 移动呢？当然有办法，那就是我们接下来要介绍的一个新的思路：双端比较 。

所谓双端比较，就是同时从新旧 children 的两端开始进行比较的一种方式，所以我们需要四个索引值，分别指向新旧 children 的两端，如下图所示：

我们使用四个变量 oldStartIdx、oldEndIdx、newStartIdx 以及 newEndIdx 分别存储旧 children 和新 children 的两个端点的位置索引，可以用如下代码来表示：

    let oldStartIdx = 0
    let oldEndIdx = prevChildren.length - 1
    let newStartIdx = 0
    let newEndIdx = nextChildren.length - 1

除了位置索引之外，我们还需要拿到四个位置索引所指向的 VNode：

    let oldStartVNode = prevChildren[oldStartIdx]
    let oldEndVNode = prevChildren[oldEndIdx]
    let newStartVNode = nextChildren[newStartIdx]
    let newEndVNode = nextChildren[newEndIdx]

有了这些基础信息，我们就可以开始执行双端比较了，在一次比较过程中，最多需要进行四次比较：

  • 1、使用旧 children 的头一个 VNode 与新 children 的头一个 VNode 比对，即 oldStartVNode 和 newStartVNode 比较对。
  • 2、使用旧 children 的最后一个 VNode 与新 children 的最后一个 VNode 比对，即 oldEndVNode 和 newEndVNode 比对。
  • 3、使用旧 children 的头一个 VNode 与新 children 的最后一个 VNode 比对，即 oldStartVNode 和 newEndVNode 比对。
  • 4、使用旧 children 的最后一个 VNode 与新 children 的头一个 VNode 比对，即 oldEndVNode 和 newStartVNode 比对。

在如上四步比对过程中，试图去寻找可复用的节点，即拥有相同 key 值的节点。这四步比对中，在任何一步中寻找到了可复用节点，则会停止后续的步骤，可以用下图来描述在一次比对过程中的四个步骤：

如下代码是该比对过程的实现：

    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 比对
    }

每次比对完成之后，如果在某一步骤中找到了可复用的节点，我们就需要将相应的位置索引后移/前移 一位。以上图为例：

  • 第一步：拿旧 children 中的 li-a 和新 children 中的 li-d 进行比对，由于二者 key 值不同，所以不可复用，什么都不做。
  • 第二步：拿旧 children 中的 li-d 和新 children 中的 li-c 进行比对，同样不可复用，什么都不做。
  • 第三步：拿旧 children 中的 li-a 和新 children 中的 li-c 进行比对，什么都不做。
  • 第四部：拿旧 children 中的 li-d 和新 children 中的 li-d 进行比对，由于这两个节点拥有相同的 key 值，所以我们在这次比对的过程中找到了可复用的节点。

由于我们在第四步的比对中找到了可复用的节点，即 oldEndVNode 和 newStartVNode 拥有相同的 key 值，这说明：li-d 节点所对应的真实 DOM 原本是最后一个子节点，并且更新之后它应该变成第一个子节点。所以我们需要把 li-d 所对应的真实 DOM 移动到最前方即可：

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)
  // 更新完成后，将容器中最后一个子节点移动到最前面，使其成为第一个子节点
  container.insertBefore(oldEndVNode.el, oldStartVNode.el)
  // 更新索引，指向下一个位置
  oldEndVNode = prevChildren[--oldEndIdx]
  newStartVNode = nextChildren[++newStartIdx]
}

这一步更新完成之后，新的索引关系可以用下图来表示：

由于 li-d 节点所对应的真实 DOM 元素已经更新完成且被移动，所以现在真实 DOM 的顺序是：li-d、li-a、li-b、li-c，如下图所示：

这样，一次比对就完成了，并且位置索引已经更新，我们需要进行下轮的比对，那么什么时候比对才能结束呢？如下代码所示：

    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 比对
      }
    }

我们将每一轮比对所做的工作封装到一个 while 循环内，循环结束的条件是要么 oldStartIdx 大于 oldEndIdx，要么 newStartIdx 大于 newEndIdx。

还是观察上图，我们继续进行第二轮的比对：

  • 第一步：拿旧 children 中的 li-a 和新 children 中的 li-b 进行比对，由于二者 key 值不同，所以不可复用，什么都不做。

  • 第二步：拿旧 children 中的 li-c 和新 children 中的 li-c 进行比对，此时，由于二者拥有相同的 key，所以是可复用的节点，但是由于二者在新旧 children 中都是最末尾的一个节点，所以是不需要进行移动操作的，只需要调用 patch 函数更新即可，同时将相应的索引前移一位，如下高亮代码所示：

    while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) { if (oldStartVNode.key === newStartVNode.key) { // 步骤一：oldStartVNode 和 newStartVNode 比对 } else if (oldEndVNode.key === newEndVNode.key) { // 步骤二：oldEndVNode 和 newEndVNode 比对

    // 调用 patch 函数更新
patch(oldEndVNode, newEndVNode, container)
// 更新索引，指向下一个位置
oldEndVNode = prevChildren[--oldEndIdx]
newEndVNode = nextChildren[--newEndIdx]

    } else if (oldStartVNode.key === newEndVNode.key) { // 步骤三：oldStartVNode 和 newEndVNode 比对 } else if (oldEndVNode.key === newStartVNode.key) { // 步骤四：oldEndVNode 和 newStartVNode 比对

    // 先调用 patch 函数完成更新
patch(oldEndVNode, newStartVNode, container)
// 更新完成后，将容器中最后一个子节点移动到最前面，使其成为第一个子节点
container.insertBefore(oldEndVNode.el, oldStartVNode.el)
// 更新索引，指向下一个位置
oldEndVNode = prevChildren[--oldEndIdx]
newStartVNode = nextChildren[++newStartIdx]

    } }

由于没有进行移动操作，所以在这一轮比对中，真实 DOM 的顺序没有发生变化，下图表示了在这一轮比对结束之后的状况：

由于此时循环条件成立，所以会继续下一轮的比较：

  • 第一步：拿旧 children 中的 li-a 和新 children 中的 li-b 进行比对，由于二者 key 值不同，所以不可复用，什么都不做。
  • 第二步：拿旧 children 中的 li-b 和新 children 中的 li-a 进行比对，不可复用，什么都不做。
  • 第三步：拿旧 children 中的 li-a 和新 children 中的 li-a 进行比对，此时，我们找到了可复用的节点。

这一次满足的条件是：oldStartVNode.key === newEndVNode.key ，这说明：li-a 节点所对应的真实 DOM 原本是第一个子节点，但现在变成了“最后”一个子节点，这里的“最后”一词使用了引号，这是因为大家要明白“最后”的真正含义，它并不是指真正意义上的最后一个节点，而是指当前索引范围内的最后一个节点。所以移动操作也是比较明显的，我们将 oldStartVNode 对应的真实 DOM 移动到 oldEndVNode 所对应真实 DOM 的后面即可，如下高亮代码所示：

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
  if (oldStartVNode.key === newStartVNode.key) {
    // 步骤一：oldStartVNode 和 newStartVNode 比对
  } else if (oldEndVNode.key === newEndVNode.key) {
    // 步骤二：oldEndVNode 和 newEndVNode 比对

    // 调用 patch 函数更新
    patch(oldEndVNode, newEndVNode, container)
    // 更新索引，指向下一个位置
    oldEndVNode = prevChildren[--oldEndIdx]
    newEndVNode = nextChildren[--newEndIdx]
  } else if (oldStartVNode.key === newEndVNode.key) {
    // 步骤三：oldStartVNode 和 newEndVNode 比对

    // 调用 patch 函数更新
    patch(oldStartVNode, newEndVNode, container)
    // 将 oldStartVNode.el 移动到 oldEndVNode.el 的后面，也就是 oldEndVNode.el.nextSibling 的前面
    container.insertBefore(
      oldStartVNode.el,
      oldEndVNode.el.nextSibling
    )
    // 更新索引，指向下一个位置
    oldStartVNode = prevChildren[++oldStartIdx]
    newEndVNode = nextChildren[--newEndIdx]
  } else if (oldEndVNode.key === newStartVNode.key) {
    // 步骤四：oldEndVNode 和 newStartVNode 比对

    // 先调用 patch 函数完成更新
    patch(oldEndVNode, newStartVNode, container)
    // 更新完成后，将容器中最后一个子节点移动到最前面，使其成为第一个子节点
    container.insertBefore(oldEndVNode.el, oldStartVNode.el)
    // 更新索引，指向下一个位置
    oldEndVNode = prevChildren[--oldEndIdx]
    newStartVNode = nextChildren[++newStartIdx]
  }
}

在这一步的更新中，真实 DOM 的顺序是有变化的，li-a 节点对应的真实 DOM 被移到了 li-b 节点对应真实 DOM 的后面，同时由于位置索引也在相应的移动，所以在这一轮更新之后，现在的结果看上去应该如下图所示：

现在 oldStartIdx 和 oldEndIdx 指向了同一个位置，即旧 children 中的 li-b 节点。同样的 newStartIdx 和 newEndIdx 也指向了同样的位置，即新 children 中的 li-b。由于此时仍然满足循环条件，所以会继续下一轮的比对：

  • 第一步：拿旧 children 中的 li-b 和新 children 中的 li-b 进行比对，二者拥有相同的 key，可复用。

此时，在第一步的时候就已经找到了可复用的节点，满足的条件是：oldStartVNode.key === newStartVNode.key ，但是由于该节点无论是在新 children 中还是旧 children 中，都是“第一个”节点，所以位置不需要变化，即不需要移动操作，只需要调用 patch 函数更新即可，同时也要将相应的位置所以下移一位，如下高亮代码所示：

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
  if (oldStartVNode.key === newStartVNode.key) {
    // 步骤一：oldStartVNode 和 newStartVNode 比对

    // 调用 patch 函数更新
    patch(oldStartVNode, newStartVNode, container)
    // 更新索引，指向下一个位置
    oldStartVNode = prevChildren[++oldStartIdx]
    newStartVNode = nextChildren[++newStartIdx]
  } else if (oldEndVNode.key === newEndVNode.key) {
    // 省略...
  } else if (oldStartVNode.key === newEndVNode.key) {
    // 省略...
  } else if (oldEndVNode.key === newStartVNode.key) {
    // 省略...
  }
}

在这一轮更新完成之后，虽然没有进行任何移动操作，但是我们发现，真实 DOM 的顺序，已经与新 children 中节点的顺序保持一致了，也就是说我们圆满的完成了目标，如下图所示：

另外，观察上图可以发现，此时 oldStartIdx 和 newStartIdx 分别比 oldEndIdx 和 newEndIdx 要大，所以这将是最后一轮的比对，循环将终止，以上就是双端比较的核心原理。

TIP

完整代码&在线体验地址：https://codesandbox.io/s/xvmqn58jqw (opens new window)

双端比较的优势

理解了双端比较的原理之后，我们来看一下双端比较所带来的优势，还是拿之前的例子，如下：

前面分析过，如果采用 React 的方式来对上例进行更新，则会执行两次移动操作，首先会把 li-a 节点对应的真实 DOM 移动到 li-c 节点对应的真实 DOM 的后面，接着再把 li-b 节点所对应的真实 DOM 移动到 li-a 节点所对应真实 DOM 的后面，即：

接下来我们采用双端比较的方式，来完成上例的更新，看看会有什么不同，如下图所示：

我们按照双端比较的思路开始第一轮比较，按步骤执行：

  • 第一步：拿旧 children 中的 li-a 和新 children 中的 li-c 进行比对，由于二者 key 值不同，所以不可复用，什么都不做。
  • 第二步：拿旧 children 中的 li-c 和新 children 中的 li-b 进行比对，不可复用，什么都不做。
  • 第三步：拿旧 children 中的 li-a 和新 children 中的 li-b 进行比对，不可复用，什么都不做。
  • 第四步：拿旧 children 中的 li-c 和新 children 中的 li-c 进行比对，此时，两个节点拥有相同的 key 值，可复用。

到了第四步，对于 li-c 节点来说，它原本是整个 children 的最后一个子节点，但是现在变成了新 children 的第一个子节点，按照上端比较的算法逻辑，此时会把 li-c 节点所对应的真实 DOM 移动到 li-a 节点所对应真实 DOM 的前面，即：

可以看到，我们只通过一次 DOM 移动，就使得真实 DOM 的顺序与新 children 中节点的顺序一致，完成了更新。换句话说，双端比较在移动 DOM 方面更具有普适性，不会因为 DOM 结构的差异而产生影响。

非理想情况的处理方式

在之前的讲解中，我们所采用的是较理想的例子，换句话说，在每一轮的比对过程中，总会满足四个步骤中的一步，但实际上大多数情况下并不会这么理想，如下图所示：

上图中 ①、②、③、④ 这四步中的每一步比对，都无法找到可复用的节点，这时应该怎么办呢？没办法，我们只能拿新 children 中的第一个节点尝试去旧 children 中寻找，试图找到拥有相同 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 {
    // 遍历旧 children，试图寻找与 newStartVNode 拥有相同 key 值的元素
    const idxInOld = prevChildren.findIndex(
      node => node.key === newStartVNode.key
    )
  }
}

这段代码增加了 else 分支，用来处理在四个步骤的比对中都没有成功的情况，我们遍历了旧的 children，并试图找到与新 children 中第一个节点拥有相同 key 值的节点，并把该节点在旧 children 中的位置索引记录下来，存储到 idxInOld 常量中。这里的关键点并不在于我们找到了位置索引，而是要明白**在旧的 children 中找到了与新 children 中第一个节点拥有相同 key 值的节点，意味着什么？**这意味着：旧children 中的这个节点所对应的真实 DOM 在新 children 的顺序中，已经变成了第一个节点。所以我们需要把该节点所对应的真实 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 = prevChildren.findIndex(
      node => node.key === newStartVNode.key
    )
    if (idxInOld >= 0) {
      // vnodeToMove 就是在旧 children 中找到的节点，该节点所对应的真实 DOM 应该被移动到最前面
      const vnodeToMove = prevChildren[idxInOld]
      // 调用 patch 函数完成更新
      patch(vnodeToMove, newStartVNode, container)
      // 把 vnodeToMove.el 移动到最前面，即 oldStartVNode.el 的前面
      container.insertBefore(vnodeToMove.el, oldStartVNode.el)
      // 由于旧 children 中该位置的节点所对应的真实 DOM 已经被移动，所以将其设置为 undefined
      prevChildren[idxInOld] = undefined
    }
    // 将 newStartIdx 下移一位
    newStartVNode = nextChildren[++newStartIdx]
  }
}

如果 idxInOld 存在，说明我们在旧 children 中找到了相应的节点，于是我们拿到该节点，将其赋值给 vnodeToMove 常量，意味着该节点是需要被移动的节点，同时调用 patch 函数完成更新，接着将该节点所对应的真实 DOM 移动到最前面，也就是 oldStartVNode.el 前面，由于该节点所对应的真实 DOM 已经被移动，所以我们将该节点置为 undefined，这是很关键的一步，最后我们将 newStartIdx 下移一位，准备进行下一轮的比较。我们用一张图来描述这个过程结束之后的状态：

这里大家需要注意，由上图可知，由于原本旧 children 中的 li-b 节点，此时已经变成了 undefined，所以在后续的比对过程中 oldStartIdx 或 oldEndIdx 二者当中总会有一个位置索引优先达到这个位置，也就是说此时 oldStartVNode 或 oldEndVNode 两者之一可能是 undefined，这说明该位置的元素在之前的比对中被移动到别的位置了，所以不再需要处理该位置的节点，这时我们需要跳过这一位置，所以我们需要增加如下高亮代码来完善我们的算法：

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
  if (!oldStartVNode) {
    oldStartVNode = prevChildren[++oldStartIdx]
  } else if (!oldEndVNode) {
    oldEndVNode = prevChildren[--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 = prevChildren.findIndex(
      node => node.key === newStartVNode.key
    )
    if (idxInOld >= 0) {
      const vnodeToMove = prevChildren[idxInOld]
      patch(vnodeToMove, newStartVNode, container)
      prevChildren[idxInOld] = undefined
      container.insertBefore(vnodeToMove.el, oldStartVNode.el)
    }
    newStartVNode = nextChildren[++newStartIdx]
  }
}

当 oldStartVNode 或 oldEndVNode 不存在时，说明该节点已经被移动了，我们只需要跳过该位置即可。以上就是我们所说的双端比较的非理想情况的处理方式。

TIP

完整代码&在线体验地址：https://codesandbox.io/s/vjp265qxnl (opens new window)

添加新元素

在上一小节中，我们尝试拿着新 children 中的第一个节点去旧 children 中寻找与之拥有相同 key 值的可复用节点，然后并非总是能够找得到，当新的 children 中拥有全新的节点时，就会出现找不到的情况，如下图所示：

在新 children 中，节点 li-d 是一个全新的节点。在这个例子中 ①、②、③、④ 这四步的比对仍然无法找到可复用节点，所以我们会尝试拿着新 children 中的 li-d 节点去旧的 children 寻找与之拥有相同 key 值的节点，结果很显然，我们无法找到这样的节点。这时说明该节点是一个全新的节点，我们应该将其挂载到容器中，不过应该将其挂载到哪里呢？稍作分析即可得出结论，由于 li-d 节点的位置索引是 newStartIdx，这说明 li-d 节点是当前这一轮比较中的“第一个”节点，所以只要把它挂载到位于 oldStartIdx 位置的节点所对应的真实 DOM 前面就可以了，即 oldStartVNode.el，我们只需要增加一行代码即可实现该功能：

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
  if (!oldStartVNode) {
    oldStartVNode = prevChildren[++oldStartIdx]
  } else if (!oldEndVNode) {
    oldEndVNode = prevChildren[--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 = prevChildren.findIndex(
      node => node.key === newStartVNode.key
    )
    if (idxInOld >= 0) {
      const vnodeToMove = prevChildren[idxInOld]
      patch(vnodeToMove, newStartVNode, container)
      prevChildren[idxInOld] = undefined
      container.insertBefore(vnodeToMove.el, oldStartVNode.el)
    } else {
      // 使用 mount 函数挂载新节点
      mount(newStartVNode, container, false, oldStartVNode.el)
    }
    newStartVNode = nextChildren[++newStartIdx]
  }
}

如上高亮代码所示，如果条件 idxInOld >= 0 不成立，则说明 newStartVNode 是一个全新的节点，我们添加了 else 语句块用来处理全新的节点，在 else 语句块内调用 mount 函数挂载该全新的节点，根据上面的分析，我们只需要把该节点挂载到 oldStartVNode.el 之前即可，所以我们传递给 mount 函数的第四个参数就是 oldStartVNode.el。

TIP

完整代码&在线体验地址：https://codesandbox.io/s/n7y46ojv4m (opens new window)

但这么做真的就完美了吗？不是的，来看下面这个例子，我们更换新 children 中节点的顺序，如下图所示：

与之前的案例不同，在之前的案例中新 children 中节点的顺序为 li-d、li-a、li-c 最后是 li-b，我们观察上图可以发现，本例中新 children 的节点顺序为 li-d、li-a、li-b 最后是 li-c，那么顺序的不同会对结果产生影响吗？想弄明白这个问题很简单，我们只需要按照双端比较算法的思路来模拟执行一次即可得出结论：

  • 第一步：拿旧 children 中的 li-a 和新 children 中的 li-d 进行比对，由于二者 key 值不同，所以不可复用，什么都不做。
  • 第二步：拿旧 children 中的 li-c 和新 children 中的 li-c 进行比对，此时，二者拥有相同的 key 值。

在第二步中找到了可复用节点，接着使用 patch 函数对该节点进行更新，同时将相应的位置索引下移一位，如下图所示：

接着，开始下一轮的比较，重新从第一步开始。结果和上一轮相似，同样在第二步中找到可复用的节点，所以在在这一轮的更新完成之后，其状态如下图所示：

由上图可知，此时的 oldStartIdx 与 oldEndIdx 已经重合，它们的值都是 0，但是此时仍然满足循环条件，所以比对不会停止，会继续下一轮的比较。在新的一轮比较中，仍然会在第二步找到可复用的节点，所以在这一轮更新完成之后 oldEndIdx 将比 oldStartIdx 的值要小，如下图所示：

此时 oldEndIdx 的值将变成 -1，它要小于 oldStartIdx 的值，这时循环的条件不在满足，意味着更新完成。然而通过上图可以很容易的发现 li-d 节点被遗漏了，它没有得到任何的处理，通过这个案例我们意识到了之前的算法是存在缺陷的，为了弥补这个缺陷，我们需要在循环终止之后，对 oldEndIdx 和 oldStartIdx 的值进行检查，如果在循环结束之后 oldEndIdx 的值小于 oldStartIdx 的值则说明新的 children 中存在还没有被处理的全新节点 ，这时我们应该调用 mount 函数将其挂载到容器元素中，观察上图可知，我们只需要把这些全新的节点添加到 oldStartIdx 索引所指向的节点之前即可，如下高亮代码所示：

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
  // 省略...
}
if (oldEndIdx < oldStartIdx) {
  // 添加新节点
  for (let i = newStartIdx; i <= newEndIdx; i++) {
    mount(nextChildren[i], container, false, oldStartVNode.el)
  }
}

我们在循环结束之后，立即判断 oldEndIdx 的值是否小于 oldStartIdx 的值，如果条件成立，则需要使用 for 循环把所有位于 newStartIdx 到 newEndIdx 之间的元素都当做全新的节点添加到容器元素中，这样我们就完整的实现了完整的添加新节点的功能。

TIP

完整代码&在线体验地址：https://codesandbox.io/s/ryryx6n42m (opens new window)

移除不存在的元素

对于双端比较，最后一个需要考虑的情况是：当有元素被移除时的情况，如下图所示：

观察上图可以发现，在新 children 中 li-b 节点已经不存在了，所以完整的更新过程应该包含：移除已不存在节点所对应真实 DOM 的功能 。为了找到哪些节点需要移除，我们首先还是按照双端比较的算法步骤模拟执行一下即可：

  • 第一步：拿旧 children 中的 li-a 和新 children 中的 li-a 进行比对，此时，二者拥有相同的 key 值。

在第一轮的第一步比对中，我们就找到了可复用节点，所以此时会调用 patch 函数更新该节点，并更新相应的索引值，可以用下图表示这一轮更新完成之后算法所处的状态：

这时 newStartIdx 和 newEndIdx 的值相等，都是 1，不过循环的条件仍然满足，所以会立即进行下一轮比较：

  • 第一步：拿旧 children 中的 li-b 和新 children 中的 li-c 进行比对，由于二者 key 值不同，所以不可复用，什么都不做。
  • 第二步：拿旧 children 中的 li-c 和新 children 中的 li-c 进行比对，此时，二者拥有相同的 key 值。

在第二步的比对中找到了可复用节点 li-c，接着更新该节点，并将 oldEndIdx 和 newEndIdx 分别前移一位，最终结果如下：

由于此时 newEndIdx 的值小于 newStartIdx 的值，所以循环将终止，但是通过上图可以发现，旧 children 中的 li-b 节点没有得到被处理的机会，我们应该将其移除才行，然后本次循环结束之后并不满足条件 oldEndIdx < oldStartIdx 而是满足条件 newEndIdx < newStartIdx，基于此，我们可以认为循环结束后，一旦满足条件newEndIdx < newStartIdx 则说明有元素需要被移除。我们增加如下代码来实现该功能：

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
  // 省略...
}
if (oldEndIdx < oldStartIdx) {
  // 添加新节点
  for (let i = newStartIdx; i <= newEndIdx; i++) {
    mount(nextChildren[i], container, false, oldStartVNode.el)
  }
} else if (newEndIdx < newStartIdx) {
  // 移除操作
  for (let i = oldStartIdx; i <= oldEndIdx; i++) {
    container.removeChild(prevChildren[i].el)
  }
}

如上高亮代码所示，增加 else...if 语句块，用来处理当 newEndIdx < newStartIdx 时的情况，我们同样开启一个 for 循环，把所有位于 oldStartIdx 和 oldEndIdx 之间的节点所对应的真实 DOM 全部移除即可。

TIP

完整代码&在线体验地址：https://codesandbox.io/s/9jnvjj1mko (opens new window)

以上就是相对完整的双端比较算法的实现，这是 Vue2 所采用的算法，借鉴于开源项目：snabbdom (opens new window)，但最早采用双端比较算法的库是 citojs (opens new window)。

Last Updated:
Contributors: leeguooooo