web全栈体系 | web全栈体系

10.1 双端比较的原理

简单 Diff 算法的问题在于，它对 DOM 的移动操作并不是最优的，我们举个例子：上图如果使用简单 Diff，则会发生两次 DOM 移动操作：上述两次移动操作，其实只需要把真实 DOM 节点 p-3 移动到真实 DOM 节点 p-1 之前这一次操作即可：上述操作，我们可以通过双端 Diff 算法实现。双端 Diff 算法是同时比较两组子节点的头尾进行比较的一种算法。首先，我们需要设定四个索引，分别指向新旧子节点的两端：

我们在 patchChildren 和 patchKeyedChildren 函数中定义了四个端点：

javascript

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
}

在 patchKeyedChildren 函数中，我们首先获取新旧子节点集，然后创建四个索引分别指向新旧子节点的起始和结束位置。然后，我们可以利用这些索引找到对应的虚拟节点：

javascript

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]
}

双端比较过程可以分为四步：

首先，我们比较旧子节点集的第一个节点和新子节点集的第一个节点，如果它们的 key 值不同，则说明它们不可复用。
然后，我们比较旧子节点集的最后一个节点和新子节点集的最后一个节点，如果它们的 key 值不同，同样，它们也不可复用。
接下来，我们比较旧子节点集的第一个节点和新子节点集的最后一个节点，如果它们的 key 值不同，那么它们也不可复用。
最后，我们比较旧子节点集的最后一个节点和新子节点集的第一个节点，如果它们的 key 值相同，说明它们可复用。

当我们发现可复用的元素之后，只需将其移动到正确位置即可，上面我们如果我们在比较过程中发现旧子节点集的最后一个节点与新子节点集的第一个节点相同，那么我们就应该将这个节点从尾部移动到头部。对应的代码如下：

javascript

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
  let oldStartVNode = oldChildren[oldStartIdx]
  let oldEndVNode = oldChildren[oldEndIdx]
  let newStartVNode = newChildren[newStartIdx]
  let newEndVNode = newChildren[newEndIdx]

  if (oldStartVNode.key === newStartVNode.key) {
    // 比较头部
  } else if (oldEndVNode.key === newEndVNode.key) {
    // 比较尾部
  } else if (oldStartVNode.key === newEndVNode.key) {
    // 旧头部与新尾部比较
  } else if (oldEndVNode.key === newStartVNode.key) {
    // 新头部与旧尾部比较
    patch(oldEndVNode, newStartVNode, container)

    // oldEndVNode.el 移动到 oldStartVNode.el 前面
    insert(oldEndVNode.el, container, oldStartVNode.el)

    // 更新索引值，指向下一个位置
    oldEndVNode = oldChildren[--oldEndIdx]
    newStartVNode = newChildren[++newStartIdx]
  }
}

上述代码，我们使用一系列的 if...else if... 语句比较四个索引指向的虚拟节点在比较过程的最后一步，我们发现具有相同 key 值的节点，说明它们可以复用。因此，我们只需要将尾部元素移动到头部，即我们只需要以头部元素 oldStartVNode.el 作为锚点，将尾部元素 oldEndVNode.el 移动到锚点前面即可，注意移动之前，我们还需要调用 patch 函数为新旧虚拟节点打补丁。

完成 DOM 移动操作之后，接下来的关键步骤是更新索引值，由于第四步中涉及的两个索引分别是 oldEndIdx 和 newStartIdx，所以我们需要更新两者的值，让它们各自朝正确的方向前进一步，并指向下一个节点：此时，真实 DOM 节点顺序为 p-4、p-1、p-2、p-3，这与新的一组子节点顺序不一致。这是因为 Diff 算法还没结束，我们还需继续下一轮更新，我们将其封装到一个 while 循环中：

javascript

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) {
    // ...
  }
}

上述代码，整个 while 循环执行的条件是：头部索引值要小于等于尾部索引值。第一轮更新后循环条件仍然成立，如上图所示，因此需要进行下一轮的比较：

首先，我们比较旧子节点头部节点 p-1 与新子节点头部节点 p-2。这里的头部节点指向的是由 oldStartIdx 和 newStartIdx 索引标识的节点。由于 p-1 与 p-2 的 key 值不同，它们不能复用，故不进行任何操作。
接着，我们比较旧子节点尾部节点 p-3 与新子节点尾部节点 p-3。它们的 key 值相同，故可复用。并且，由于都在尾部，无需移动 DOM，只需打补丁即可。代码如下：

javascript

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
  // 头部节点比较
  if (oldStartVNode.key === newStartVNode.key) {
    // 省略操作
  }
  // 尾部节点比较
  else if (oldEndVNode.key === newEndVNode.key) {
    // 双方都在尾部，只需打补丁
    patch(oldEndVNode, newEndVNode, container);
    // 更新索引和节点
    oldEndVNode = oldChildren[--oldEndIdx];
    newEndVNode = newChildren[--newEndIdx];
  }
  // 省略其他情况
}

在这一轮更新完成之后，新旧两组子节点与真实 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 后面，并更新相关索引到下一个位置。如下图所示

实现如下：

javascript

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

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

然后我们比较旧子节点组中的头部节点 p-2 与新子节点组中的头部节点 p-2。发现它们的 key 值相同，是可复用的，但无需移动，只需调用 patch 函数进行打补丁即可。整体代码实现如下：

javascript

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
  if (oldStartVNode.key === newStartVNode.key) {
    // 调用 patch 函数在 oldStartVNode 与 newStartVNode 之间打补丁
    patch(oldStartVNode, newStartVNode, container)
    // 更新相关索引，指向下一个位置
    oldStartVNode = oldChildren[++oldStartIdx]
    newStartVNode = newChildren[++newStartIdx]
  } else if (oldEndVNode.key === newEndVNode.key) {
    patch(oldEndVNode, newEndVNode, container)
    oldEndVNode = oldChildren[--oldEndIdx]
    newEndVNode = newChildren[--newEndIdx]
  } else if (oldStartVNode.key === newEndVNode.key) {
    patch(oldStartVNode, newEndVNode, container)
    insert(oldStartVNode.el, container, oldEndVNode.el.nextSibling)
    oldStartVNode = oldChildren[++oldStartIdx]
    newEndVNode = newChildren[--newEndIdx]
  } else if (oldEndVNode.key === newStartVNode.key) {
    patch(oldEndVNode, newStartVNode, container)
    insert(oldEndVNode.el, container, oldStartVNode.el)
    oldEndVNode = oldChildren[--oldEndIdx]
    newStartVNode = newChildren[++newStartIdx]
  }
}

在这轮更新完成后，真实 DOM 节点的顺序与新子节点组的顺序相同了：p-4, p-2, p-1, p-3。同时，因为 newStartIdx 和 oldStartIdx 的值都小于 newEndIdx 和 oldEndIdx，所以循环终止，双端 Diff 算法执行完毕：

10.2 双端比较的优势

我们使用双端 Diff 算法对演示下最上面提及的简单 Diff 二次移动 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 节点的顺序已经与新的一组子节点的顺序一致了。但双端比较依然会继续下一轮比较：

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

此时，双端 Diff 算法仍然没有停止，开始新一轮的比较：

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

此时，索引 newStartIdx 比 newEndIdx 大，oldStartIdx 比 oldEndIdx 大，循环结束，于是更新结束。同样例子简单 Diff 两次完成 DOM 移动操作，双端 Diff 算法只需要一次 DOM 移动操作即可完成更新。

10.3 非理想状况的处理方式

在双端Diff算法中，有时我们会遇到一种情况，即旧子节点和新子节点的头尾均无法匹配。在这种情况下，我们需要采取额外的步骤来处理。下面以一个例子来具体说明：旧的子节点组：p-1、p-2、p-3、p-4。新的子节点组：p-2、p-4、p-1、p-3。在尝试使用双端 Diff 算法进行比较时，我们会发现无法找到匹配的节点。

这时，我们用新的一组子节点的头部节点去旧的一组节点寻找：

javascript

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 值的节点
		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)
      // 由于位置 idxInOld 处的节点所对应的真实 DOM 已经移动到了别处，因此将其设置为 undefined
			oldChildren[idxInOld] = undefined
      // 最后更新 newStartIdx 到下一个位置
			newStartVNode = newChildren[++newStartIdx]
		}
	}
}

p2 最终移动如下图：上述代码，我们首先在旧的子节点组中寻找与新的子节点组头部节点相同的节点，并将其索引存储在变量 idxInOld 中。查看 idxInOld 是否大于 0。如果找到了匹配的节点（即idxInOld > 0），我们将该节点对应的真实 DOM 移动到当前的头部节点前，并更新相关索引到下一个位置。注意在移动节点之前，我们需要调用 patch 函数进行更新代码最终执行后如下图：此时，真实 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 节点的顺序是：p-2、p-4、p-1、p-3。接着，进行下一轮的比较。值得注意的是，旧子节点组的首节点现在是 undefined，意味着该节点已被处理，我们可以直接跳过。为此，我们需要补充这部分逻辑的代码：

javascript

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
    // 最上面增加两个判断，如果节点为 undefined，说明已处理，直接跳到下一个位置
    if (!oldStartVNode) {
        oldStartVNode = oldChildren[++oldStartIdx];
    } else if (!oldEndVNode) {
        oldEndVNode = oldChildren[--oldEndIdx];
    } 
    // 后续逻辑省略...
}

在这一轮比较过后，新旧两组子节点与真实 DOM 节点的状态：接着进行最后一轮的比较：

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

在第一步中找到了可复用的节点。由于两者都是头部节点，因此不需要进行 DOM 移动操作，直接打补丁即可。在这一轮比较过后，最终状态如图：这时，满足循环停止的条件，于是更新完成。最终，真实 DOM 节点的顺序与新的一组子节点的顺序一致，都是：p-2、p-4、p-1、p3。

10.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。下面的代码展示了如何实现这个挂载操作：

javascript

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
  if (!oldStartVNode) {
    oldStartVNode = oldChildren[++oldStartIdx]
  } else if (!oldEndVNode) {
    oldEndVNode = newChildren[--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 {
      // 将 newStartVNode 作为新节点挂载到头部，使用当前头部节点
      // oldStartVNode.el 作为锚点
      patch(null, newStartVNode, container, oldStartVNode.el)
    }
    newStartVNode = newChildren[++newStartIdx]
  }
}

当 idxInOld > 0 不成立时，说明 newStartVNode 是一个全新的节点。因为它是头节点，我们应将其作为新的头节点进行挂载。因此，我们在调用 patch 函数挂载节点时，使用 oldStartVNode.el 作为锚点。执行结果如下图所示：

然而，这个算法并不完美。例如，看下面例子新子节点集合的顺序为 p-4、p-1、p-2、p-3 时，我们按照双端 Diff 算法的思路来执行更新下：

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

在第二步中找到了可复用的节点，因此进行更新，结果如图：接着进行下一轮更新：

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

在第二步中找到了可复用的节点，因此再次进行更新，结果如图：接着，进行下一轮的更新：

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

在第二步中找到了可复用的节点，因此再次进行更新，结果如图：当这一轮更新完毕后，由于变量 oldStartIdx 的值大于 oldEndIdx 的值，满足更新停止的条件，因此更新停止。但通过观察可知，节点 p-4 在整个更新过程中被遗漏了，没有得到任何处理，这说明我们的算法是有缺陷的。为了弥补这个缺陷，我们需要添加额外的处理代码：

javascript

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

在这个改进后的版本中，如果 oldEndIdx < oldStartIdx && newStartIdx <= newEndIdx 成立，这意味着新子节点集合中有未处理的节点需要作为新节点挂载。这些新节点的索引值在 newStartIdx 和 newEndIdx 这个区间内。因此，我们使用一个 for 循环来遍历这个区间内的节点并逐一挂载。挂载时的锚点仍然使用当前的头节点 oldStartVNode.el，这样我们就完成了对新增元素的处理。

10.1 双端比较的原理 ​

10.2 双端比较的优势 ​

10.3 非理想状况的处理方式 ​

10.4 添加新元素 ​

10.1 双端比较的原理

10.2 双端比较的优势

10.3 非理想状况的处理方式

10.4 添加新元素