参考自Vue源码系列-Vue中文社区

前言

Vue中更新节点，当新 VNode 和旧 VNode 都是元素节点且都有子节点时，Vue会循环对比新旧 VNode 的子节点数组，然后根据不同情况做不同处理。

虽然这种方法能解决问题，但是当更新子节点特别多时，循环算法的时间复杂度就会很高，所以Vue对此进行了优化。

优化前存在的问题

现在有新的 newChildren 数组和旧的 oldChildren 数组：

newChildren = ['a','b','c','d'];
oldChildren = ['a','b','c','e'];

按照之前的解决方案：先循环 newChildren 数组，把第一个节点与 oldChildren 里的子节点逐一对比，再根据情况去处理。如果像上面的代码一样，前三个子节点都没有变化，只修改了最后一个子节点，但因为循环查找，还是要循环16次才能发现，所以前面做的15次循环全是无用功。

优化策略分析

Vue的策略是不按照循序去循环 newChildren 和 oldChildren 这两个数组，而是先去比较特殊位置的子节点，比如：

• 把 newChildren 数组里的第一个未处理子节点和 oldChildren 数组的第一个未处理子节点做对比，如果相同，就更新节点。
• 如果不同，把 newChildren数组里最后一个未处理子节点和 oldChildren 数组里最后一个未处理子节点做比对，如果相同，就更新节点。
• 如果不同，把 newChildren数组里最后一个未处理子节点和 oldChildren 数组里第一个未处理子节点做比对，如果相同，就更新节点。
• 如果不同，把 newChildren数组里第一个未处理子节点和 oldChildren 数组里最后一个未处理子节点做比对，如果相同，就更新节点。
• 如果四种情况试完如果还不同，就按照之前循环的方式来查找节点。

四种情况分别分别被称作：

不相同才往后继续。

• 新前与旧前

  如果相同，直接更新，因为位置也相同，无需移动。

• 新后与旧后

  如果相同，直接更新，因为位置也相同，无需移动。

• 新后与旧前

  如果相同，更新，但因为位置不同，所以需要移动位置

• 新前与旧后

  如果相同，更新，但因为位置不同，所以需要移动位置

如果上面的情况都不满足，再通过之前的循环方式查找

源码解析

从上面的优化策略中，知道对比子节点是先对比特殊位置的子节点，对比成功就进行更新处理，也就是说有可能处理第一个，也有可能是处理最后一个，所以在循环的时候就不可能只是从前往后循环，而是从两边向中间循环。

首先定义四个变量

• newStartIdx：新子节点数组里开始位置的下标；
• newEndIdx：新子节点数组里结束位置的下标；
• oldStartIdx：旧子节点数组里开始位置的下标；
• oldEndIdx：旧子节点数组里结束位置的下标；

在循环的时候，每处理一个节点，就将下标向图中箭头的方向移动一个位置，newStartIdx和 oldStartIdx 往后加1，newEndIdx和 oldEndIdx往前减1。

理解了这个概念后，就可以解析源码了:

1. 定义需要的变量

   function updateChildren (parentElm, oldCh, newCh, insertedVnodeQueue, removeOnly) {
       let oldStartIdx = 0               // oldChildren开始索引
       let oldEndIdx = oldCh.length - 1   // oldChildren结束索引
       let oldStartVnode = oldCh[0]        // oldChildren中所有未处理节点中的第一个
       let oldEndVnode = oldCh[oldEndIdx]   // oldChildren中所有未处理节点中的最后一个
   ​
       let newStartIdx = 0               // newChildren开始索引
       let newEndIdx = newCh.length - 1   // newChildren结束索引
       let newStartVnode = newCh[0]        // newChildren中所有未处理节点中的第一个
       let newEndVnode = newCh[newEndIdx]  // newChildren中所有未处理节点中的最后一个A
   }
   

2. 如果 oldStartVNode 不存在，则跳过，将 oldStartIdx 加1，对比下一个

   while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
       if (isUndef(oldStartVnode)) {
           oldStartVnode = oldCh[++oldStartIdx];
       }
   }
   

3. 如果oldEndVnode不存在，则跳过，将oldEndIdx减1，比对前一个

   else if (isUndef(oldEndVnode)) {
       oldEndVnode = oldCh[--oldEndIdx];
   }
   

4. 如果新前与旧前节点相同，就把两个节点进行patch更新，同时oldStartIdx和newStartIdx都加1，后移一个位置

   else if (sameVnode(oldStartVnode, newStartVnode)) {
       patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue)
       oldStartVnode = oldCh[++oldStartIdx]
       newStartVnode = newCh[++newStartIdx]
   }
   

5. 如果新后与旧后节点相同，就把两个节点进行patch更新，同时oldEndIdx和newEndIdx都减1，前移一个位置

   else if (sameVnode(oldEndVnode, newEndVnode)) {
       patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue)
       oldEndVnode = oldCh[--oldEndIdx]
       newEndVnode = newCh[--newEndIdx]
   }
   

6. 如果新后与旧前节点相同，先把两个节点进行patch更新，然后把旧前节点移动到oldChilren中所有未处理节点之后，最后把oldStartIdx加1，后移一个位置，newEndIdx减1，前移一个位置

   else if (sameVnode(oldStartVnode, newEndVnode)) {
       patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue)
       canMove && nodeOps.insertBefore(parentElm, oldStartVnode.elm, nodeOps.nextSibling(oldEndVnode.elm))
       oldStartVnode = oldCh[++oldStartIdx]
       newEndVnode = newCh[--newEndIdx]
   }
   

7. 如果新前与旧后节点相同，先把两个节点进行patch更新，然后把旧后节点移动到oldChilren中所有未处理节点之前，最后把newStartIdx加1，后移一个位置，oldEndIdx减1，前移一个位置

   else if (sameVnode(oldEndVnode, newStartVnode)) { // Vnode moved left
       patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue)
       canMove && nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm)
       oldEndVnode = oldCh[--oldEndIdx]
       newStartVnode = newCh[++newStartIdx]
   }
   

8. 不属于以上四种情况，就进行常规的循环比对patch。

9. 如果oldStartIdx大于oldEndIdx了，那就表示oldChildren比newChildren先循环完毕，那么newChildren里面剩余的节点都是需要新增的节点，把[newStartIdx, newEndIdx]之间的所有节点都插入到OldChildren中。

   if (oldStartIdx > oldEndIdx) {
       refElm = isUndef(newCh[newEndIdx + 1]) ? null : newCh[newEndIdx + 1].elm
       addVnodes(parentElm, refElm, newCh, newStartIdx, newEndIdx, insertedVnodeQueue)
   }
   

10. 如果newStartIdx大于newEndIdx了，那就表示newChildren比oldChildren先循环完毕，那么oldChildren里面剩余的节点都是需要删除的节点，把[oldStartIdx, oldEndIdx]之间的所有节点都删除

    else if (newStartIdx > newEndIdx) {
        removeVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx)
    }
    

小结

1. 分析了循环更新子节点存在的性能问题，数据量大时，时间复杂度高。
2. 分析Vue中的优化策略，先对比特殊位置的子节点，分别是：新前与旧前、新后与旧后、新后与旧前、新前与旧后。如果都不相同，在通过循环遍历对比。
3. 理解源码，通过源码解析，在脑海中绘制一条清晰的思路线。