前言

距离vue3版本的发布也过了将近一年多的时间了，vue3也开始趋近于稳定，本章将对vue3的diff算法做一个浅入的分析

React与Vue2的diff缺陷

react: 核心diff采用的是新旧节点从首部开始对比直到对比出最先一个无法匹配上的节点跳出，此时记录为lastplaceindex, 随后拿着剩余的新节点集合对比剩余的旧节点集合，对比旧节点的oldIndex，判断位置所在，这里暂时不详细阐述React的详细Diff操作了，但是React Diff算法里存在着一点性能缺陷 — React在操作移动的时候会有一定的性能牺牲(后续会出React的Diff算法，如果感兴趣的话可以加微信)

vue2.x: vue2.x吸取了React的经验，采用了名为双端队列的对比方法，有效的解决了react遗留下来的性能缺陷，但是也可以发现vue2.x版本还是存在着一定的问题，那就是vue2.x版本

对于增删操作不是那么敏感
每次都需要对同一个节点最高可达5次的对比操作

Vue3 — inferno

Vue3采用的是inferno里实现的diff算法，以下是diff算法的对比图

数据来源于js-framework-benchmark，下面我们就来介绍下它的原理

浅显易出的例子

exp1:

  var text1 = 'text'
  var text2 = 'text'
复制代码

对比上述两个字符串时，我们可以发现text1 === text2，我们完全不需要做任何其他操作，全部都能狗复用

exp2:

  var text1 = 'I love React very much'
  var text2 = 'I love Vue very much'
复制代码

可以发现两者对比后差异仅在React与Vue两个字符上，其余都可以复用原来的

exp3:

  var text1 = 'I love martin'
  var text2 = 'I love martin too'
复制代码

对比我们可以发现两者区别是text2多了too其余都可以复用，所以在具体操作的时候我们只需要在旧节点增加too即可

exp4:

  var text1 = 'I love martin too'
  var text2 = 'I love martin'
复制代码

对比后我们可以发现两者的区别是text1多了too，我们只需要在旧节点最后删除too即可

通过上面的例子，我们可以发现这种方法可以快速掌握增删的操作，对于这些操作我们完全可以避免再次调用patch方法，从而让性能更上一个台阶

相同的前缀和后缀

根据上面例子我们可以提取出基本的操作步骤

从首部开始查找新旧节点的所有的相同之处直到遇到第一个不相同的节点或者结束字符串的遍历，此时记录j为当前索引，j为第一个不同的节点索引
从尾部开始倒序查找新旧节点的所有相同之处知道遇到第一个不相同的节点或者小于j，此时记录新节点newEnd，旧节点prevEnd，两者的值为第一个不同的节点索引
对比j与newEnd和prevEnd的值大小

  a. j > prevEnd且j <= newEnd，表明旧节点已经遍历完成而新节点没有遍历完成，表示j到newEnd范围里的所有节点都需要添加
  b. j > newEnd且j <= prevEnd，表明新节点已经遍历完成而旧节点没有遍历完成，表示j到prevEnd范围里的所有的值都需要被删除掉
  c. j < prevEnd且j < newEnd，表明新旧节点都没有遍历完成，此时就会进入最核心的diff算法（等下会讲解到）
  d. j > newEnd且j > prevEnd，表明新旧节点都已经遍历完成不需要重新创建
复制代码

核心diff – 确定是否有移动节点以及怎么移动

与React和Vue2.x一样，在确定新旧节点里是否有位置移动的时候我们要做以下两点:

确定是否有移动
移动的节点是怎么移动的

按照上面的c点情况我们会进入到最核心的Diff算法里
talk is cheap
show me code
开卷:

  const source = []
  const keyIndexMap = new Map()
  let uid = 0
  function sureIsMove(nChildren, oChildren) {
    let moved = false
    let lastPlaceIndex = 0
    
    for (let i = 0; i < nChildren.length; i++) {
      const key = nChildren[i].data?.key || uid++
      source[i] = -1
      keyIndexMap[key] = i
    }
    
    for (let i = 0; i < oChildren.length; i++) {
      const oldNode = oChildren[i]
      const key = oldNode.data?.key
      const index = keyIndex.get(key)
      
      if (~index) { // 抽象渗漏
        source[index] = i
        
        if (index < lastPlaceIndex) {
          moved = true
        } else {
          lastPlaceIndex = index
        }
      }
    }
    
    return moved
  }
  
  function moveNode() {
    const moved = sureIsMove.apply(null, arguments)
    const lisSource = lis(source)
    if（moved) {
      let x = nChildren.length - 1
      let y = lisSource.length - 1
      let end = nextEnd + 1 // nextEnd是上一步从尾部开始遍历获取到的第一个不同值的索引值
      for (; x >= 0; x--) {
        if (source[x] === -1) { // 新增节点
          const node = nChildren[x].tag
          const el = docuement.createElement(node)
          ......
          const oldEl = nChildren[--end].el
          const container = oldEl.parentNode
          container.insertBefore(el, oldEl)
        } else if (x !== y) { // 要移动
          const el = nChildren[x].el
          ......
          const oldEl = nChildren[--end].el
          const container = oldEl.parentNode
          container.insertBefore(el, oldEl)
        } else {
          y--
        }
      }
    }
  }
复制代码

我们逐步分析下上面的代码

首先我们创建了一个source数组，它的作用是用来存储新节点里所对应旧节点集合的位置
举例:
oldChildren = [b, a, c]
newChildren = [a, b, c]
source = [1, 0, 2]
我们可以发现source所在的下标是newChildren的下标，随后newChildren下标所对应oldCHildren的下标是source里的值，也就是说source其实是newChildren与oldChildren下标的一个集合
我们创建了一个keyIndexMap用于存储newChildren的字典表，key为节点所对应的key值，value则是newChildren所对应的下标，存储该字典是为了方便后面收集source时一种性能优化，空间换时间～
开始第一个目标: 确定是否移动，这里面的思路类似于React的Diff算法，我们预暂了一个lastplaceIndex的值，用它来标记当前newChildren移动到的最新下标，我们可以看到，在遍历oldChildren的时候我们会去keyIndexMap里查找对应key的下标值index（也就是位于newChildren的下标值），如果找到了则代表节点可以复用，此时收集对应oldChildren的下标值放入到source中，然后判断index的值与lastPlaceIndex的大小，若是index < lastPlaceIndex则代表移动了，若是没有则将index赋值给lastPlaceIndex，为什么是这么做就能确定是否移动了呢？我们可以发现oldChildren是正序遍历，如果旧节点位置越靠后找到的newChildren位置却越靠前说明位置发生了移动，该旧节点已经被移到了前面
确定了是否移动后，我们需要考虑的是如何移动的问题，这里我们要预先从source里取出最长递增子序列
什么是最长递增子序列：
const source = [2, 3, 1, 5]
最长递增子序列则是[2, 3, 5]

那么我们可以认为最长递增子序列是一串在newChildren里并没有发生顺序变化的最长队列，我们针对这一串序列不进行任何移动操作，反言之其余的都需要进行处理
我们知道了这个之后就开始做如何移动的处理，首先我们获取出source里最长递增子序列(这里要注意的是我们取出的lissource是一个下标集合而不是一个值集合)，然后我们开始分析移动逻辑:

  首先我们根据source算出最长递增子序列lisSource，随后我们倒序遍历newChildren并且同时取lisSource的最后一个值
  1. source[x] === -1表明该值是一个新增加的值，所以要增新增处理，
     对应这种安插在中间的值DomOM提供的API里可以使用insertBefore方法
     insertBefore需要三个参数: 1. parentNode 2.node 3. referrenceNode
     因为我们是倒序遍历，所以我们将新增的值安插到nextEnd + 1的值的前面，那么自然
     parentNode = nextEnd + 1的el的父节点，而referrenceNode则是nextEnd + 1,最后
     nextEnd -= 1
  2.  x ! == y表面当前的节点不处于最长递增子序列里，所以要发生移动
      那么道理一样，我们是倒序遍历的，所以我们只需要将该值安插到nextEnd + 1的前面即可
  3. 若是x === y，那么表明该节点是不需要移动的，我们只需要将y减一即可
复制代码

至此，大致原理基本讲完，大家也可以自己去尝试着写写看