10.1 双端比较的原理

双端 Diff 用四个索引同时从新旧两组子节点的两端向中间比较，让「本来就该待在原处」的节点尽快出局，从而少移动 DOM。

一、为什么需要双端比较

简单 Diff（第 9 章）只从头部单向扫描，每命中一个可复用节点就移动一次真实 DOM，遇到「头尾互换」的更新会多动几次。

更新（旧 → 新）简单 Diff双端 Diff
p-1、p-2、p-3 → p-3、p-1、p-2移动 2 次移动 1 次

单端扫描时，p-3、p-2 这两个节点都要被搬到别处；双端比较在同一轮里同时看头和尾，能一次性把「原本在尾部、现在要去头部」的节点处理掉。

二、四个索引与四个节点变量

需要四个索引值，分别指向新旧两组子节点的端点；再用四个变量缓存当前索引指向的虚拟节点。

索引初始值指向的节点变量
oldStartIdx0oldStartVNode（旧子节点的第一个节点）
oldEndIdxoldChildren.length - 1oldEndVNode（旧子节点的最后一个节点）
newStartIdx0newStartVNode（新子节点的第一个节点）
newEndIdxnewChildren.length - 1newEndVNode（新子节点的最后一个节点）

三、四步比较顺序

每一轮比较都分四步，顺序是「两端先平行、后交叉」：

步骤比较对象命中含义是否需要移动 DOM索引推进
1旧头 vs 新头节点仍在头部否，只打补丁oldStartIdx++、newStartIdx++
2旧尾 vs 新尾节点仍在尾部否，只打补丁oldEndIdx--、newEndIdx--
3旧头 vs 新尾旧头节点被挪到了尾部是，旧头节点移到旧尾节点之后oldStartIdx++、newEndIdx--
4旧尾 vs 新头旧尾节点被挪到了头部是，旧尾节点移到旧头节点之前oldEndIdx--、newStartIdx++
  • 第 3 步的锚点用 oldEndVNode.el.nextSibling：把旧头节点插到「旧尾节点的下一个兄弟节点」之前，效果就是放到旧尾节点后面；
  • 第 4 步的锚点用 oldStartVNode.el：把旧尾节点插到旧头节点前面。

比较的是 key：key 不同就什么都不做，只有 key 相同才会复用并操作真实 DOM。

每一步命中后，都要同时更新索引和对应的节点变量（如 oldStartVNode = oldChildren[++oldStartIdx]），只改索引不改变量会拿旧值继续比较。

四、多轮比较：用 while 循环驱动

只要 oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx 就继续下一轮。用书中那组例子推演一遍：

  • 旧子节点：p-1、p-2、p-3、p-4
  • 新子节点：p-4、p-2、p-1、p-3
轮次命中步骤本轮操作操作后的真实 DOM操作后的索引（旧 / 新）
1第 4 步（旧尾 p-4 = 新头 p-4）打补丁后把 p-4 移到 p-1 之前p-4、p-1、p-2、p-3(0, 2) / (1, 3)
2第 2 步（旧尾 p-3 = 新尾 p-3）仍在尾部，只打补丁，不移动 DOMp-4、p-1、p-2、p-3(0, 1) / (1, 2)
3第 3 步（旧头 p-1 = 新尾 p-1）打补丁后把 p-1 移到 p-2 之后p-4、p-2、p-1、p-3(1, 1) / (1, 1)
4第 1 步（旧头 p-2 = 新头 p-2）都在头部，只打补丁p-4、p-2、p-1、p-3(2, 1) / (2, 1)

第 4 轮结束后 oldStartIdx（2）已大于 oldEndIdx（1），同时 newStartIdx（2）已大于 newEndIdx（1），循环条件不成立 → 双端 Diff 执行完毕，最终 DOM 与新子节点顺序一致。

五、核心实现

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]

  while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
    if (oldStartVNode.key === newStartVNode.key) {
      // 第一步：旧头 vs 新头 —— 都在头部，不需要移动
      patch(oldStartVNode, newStartVNode, container)
      oldStartVNode = oldChildren[++oldStartIdx]
      newStartVNode = newChildren[++newStartIdx]
    } else if (oldEndVNode.key === newEndVNode.key) {
      // 第二步：旧尾 vs 新尾 —— 仍在尾部，不需要移动
      patch(oldEndVNode, newEndVNode, container)
      oldEndVNode = oldChildren[--oldEndIdx]
      newEndVNode = newChildren[--newEndIdx]
    } else if (oldStartVNode.key === newEndVNode.key) {
      // 第三步：旧头 vs 新尾 —— 旧头节点要挪到尾部
      patch(oldStartVNode, newEndVNode, container)
      // 插到「旧尾节点的下一个兄弟节点」之前，即旧尾节点之后
      insert(oldStartVNode.el, container, oldEndVNode.el.nextSibling)
      oldStartVNode = oldChildren[++oldStartIdx]
      newEndVNode = newChildren[--newEndIdx]
    } else if (oldEndVNode.key === newStartVNode.key) {
      // 第四步：旧尾 vs 新头 —— 旧尾节点要挪到头部
      patch(oldEndVNode, newStartVNode, container)
      // 插到旧头节点之前
      insert(oldEndVNode.el, container, oldStartVNode.el)
      oldEndVNode = oldChildren[--oldEndIdx]
      newStartVNode = newChildren[++newStartIdx]
    }
  }
}

四步都命中不了时会卡住循环，需要额外的处理步骤，见 10.3 非理想状况的处理方式。

相关

最近更新:
Contributors: liujw