vue-vue2和vue3的diff算法

核心要点

• 数据变化时，vue如何更新节点
• 虚拟DOM 和 真实DOM 的区别
• vue2 diff 算法
• vue3 diff 算法

一、 数据变化时，vue如何更新节点

首先渲染真实DOM的开销是很大，比如有时候我们修改了某个数据且修改的数据量很大时，此时会频繁的操作真实dom，会不断的引起整个dom树的重绘和重排；vue是根据真实DOM生成一颗 虚拟DOM，当 虚拟DOM 某个节点的数据改变后会生成一个新的newVnode，然后newVnode和oldVnode作对比，发现有不一样的地方就直接修改在真实的DOM上

二、虚拟DOM 和 真实DOM 的区别

虚拟DOM是将真实的DOM的数据抽取出来，以对象的形式模拟树形结构；

//真实DOM
<div><p>123</p>
</div>//虚拟DOM
var Vnode = {tag: 'div',children: [{ tag: 'p', text: '123' }]
};

三、vue2 diff 算法

核心原理

• 深度优先，同层比较，时间复杂度只有 O(n)；
• 双针比较，新头与旧头比较，新尾与旧尾比较，旧头与新尾比较，新头与旧尾比较

diff算法流程

（1）diff算法是发生在更新的过程，而更新的情况有以下几种情况

• 老的是Text，新的是Text，直接更新
• 老的是Array，新的是Text，把旧的全部删掉，更新为Text
• 老的是Text，新的是Array，删掉旧的文本，更新为新的Array元素
• 老的是Array，新的是Array，调用updateChildren函数比较子节点，这是diff的核心

（2）老的是Array，新的是Array的情况下，调用updateChildren函数，diff核心流程

• 新旧节点VNode节点如下图所示
  
• 循环遍历节点
  ① 情况：当新老 VNode 节点的 start 满足 sameVnode 时，直接 patchVnode 即可，同时新老 VNode 节点的开始索引都加 1

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

  ② 情况：当新老 VNode 节点的 end 满足 sameVnode 时，同样直接 patchVnode 即可，同时新老 VNode 节点的结束索引都减 1

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

  ③ 情况：当老 VNode 节点的 start 和新 VNode 节点的 end 满足 sameVnode 时，这说明这次数据更新后 oldStartVnode 已经跑到了 oldEndVnode 后面去了。这时候在 patchVnode 后，还需要将当前真实 dom 节点移动到 oldEndVnode 的后面，同时老 VNode 节点开始索引加 1，新 VNode 节点的结束索引减 1

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

  ④ 情况：当老 VNode 节点的 end 和新 VNode 节点的 start 满足 sameVnode 时，这说明这次数据更新后 oldEndVnode 跑到了 oldStartVnode 的前面去了。这时候在 patchVnode 后，还需要将当前真实 dom 节点移动到 oldStartVnode 的前面，同时老 VNode 节点结束索引减 1，新 VNode 节点的开始索引加 1。

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

  ⑤ 以上都不满足的情况：如果新旧子节点都存在key，那么会根据oldVnode的key生成一张hash表，用当前新节点，暂时称为S的key与hash表做匹配，匹配成功就判断S和匹配节点是否为sameNode，如果是，就在真实dom中将成功的节点移到最前面，否则，将S生成对应的节点插入到dom中对应的oldS位置，S指针向中间移动，被匹配old中的节点置为undefined。如果没有key,则直接将S生成新的节点插入真实DOM（ps：这下可以解释为什么v-for的时候需要设置key了，如果没有key那么就只会做四种匹配，就算指针中间有可复用的节点都不能被复用了）

四、vue3 diff 算法

核心原理

• 深度优先，同层比较，时间复杂度只有 O(n)；
• 双端对比算法：先看左侧，看完左侧看右侧，然后锁定中间乱序的部分
• 最长递增子序列：针对中间乱序部分，采用最长递增子序列的算法，计算出乱序部分可以复用的最长连续节点

diff算法流程

（1）diff算法是发生在更新的过程，而更新的情况有以下几种情况

• 老的是Text，新的是Text，直接更新
• 老的是Array，新的是Text，把旧的全部删掉，更新为Text
• 老的是Text，新的是Array，删掉旧的文本，更新为新的Array元素
• 老的是Array，新的是Array，调用updateChildren函数比较子节点，这是diff的核心

（2）老的是Array，新的是Array的情况下，调用updateChildren函数，diff核心流程

• 先处理左侧，先从左侧开始进行对比，很明显左侧的A、B都是相同的，然后锁定左侧相同的部分，处理右侧乱序部分

  

• 再处理右侧，从右侧开始对比，很明显右侧的B、C都是相同的，然后锁定右侧相同部分，处理左侧乱序部分

  

• 若新的比老的长，创建，可以看到下图新的比老的多，新的多了一个D，多出来的这个节点就需要创建并添加到尾部

  

• 老的比新的长，删除，可以看到下图老的比新的多了个C，多出来的这个节点需要删除

  

• 乱序部分，采用最长递增子序列的算法，最大递增子序列的作用就是通过新旧节点变化前后的映射，创建一个递增数组，这样就可以知道哪些节点在变化前后相对位置没有发生变化，哪些节点需要进行移动，如下图计算出E、F、Y、J 是不需要操作的节点，直接复用，然后移动K节点，即可完成一次更新；关于最长递增子序列的算法参考视频，算法核心：动态规划+二分法实现+驱节点向前（回溯） 的方式，实现了O（n logn）的时间复杂度查找

  

参考文章

• Vue2、Vue3的diff对比
• 根据大崔哥的mini-vue来理解vue3中的diff算法
• 手写Vue3框架教程（核心原理、组件渲染、diff算法、生命周期…)