一步一步教你认识Vue3的双端Diff算法

站长

2023年09月26日 13:22 · 阅读数 12

前言

各位前端同学或多或少都听说过Diff算法吧，作为Vue的核心算法，它帮助我们用更少的变更次数去完成页面的更新，而这个Diff算法也是很值得我们去学习研究的。

下面通过用例结合代码的方式去详细介绍vue3 Diff的核心原理。

文章有点长，但是十分详细，有兴趣的朋友可以慢慢看。

必读

文章主要分为：获取新老节点边界，节点更新 两部分

其中节点更新又分为，两种简单情况，一种复杂情况，其中获取新老节点边界和两种简单情况算简单内容，节点更新乱序部分算复杂内容。

建议：分段阅读，先把简单部分过一遍，文中提供了用例，可以跟着代码打一下理解一下。简单部分过了之后，再去仔细阅读复杂情况，内容有点复杂有点绕，需要仔细阅读才能理解。（这部分也是Diff核心）

注：新老节点 在本文中相当于新虚拟节点列表和旧虚拟节点列表，方便阅读简写了

Diff的作用

介绍原理之前，先了解下Diff算法的作用是什么？ 组件更新时，会形成新的 VNode，新旧VNode 进行比较 patch，通过 diff 算法找出更新的地方，然后执行对应的 DOM 操作 diff 的过程 为什么需要Diff算法呢？我们知道当获得一个新的VNode的时候，我们如果想要渲染到页面上，最简单的方法就是直接把老的节点一股脑全删了，然后把新的节点放上去。但是这样会有个问题，有一些节点其实没有变动，可能只是换了位置，直接粗暴的删除再更新非常影响性能，通过diff算法我们可以知道如何通过最短变动最小的方式去完成我们的更新。

Diff的原理

了解Diff之前我们先简单了解一下，Vnode的基本格式 Vnode: h(type, props, children)，type指vnode的类型（包括组件，元素等），props指接收的参数（对于组件类型为其props等值，对于元素类型为其属性值），children指子vnode（默认是数组）。 Diff算法比较的是vnode的children数组的变化。下面提供一个案例：

let oldVnode = [
  h("p", { key: "A" }, "A"),
  h("p", { key: "B" }, "B"),
];
let newVnode = [
  h("p", { key: "A" }, "A"),
  h("p", { key: "B" }, "B"),
  h("p", { key: "C" }, "C"),
];

这里定义了两个新老vnode，如果使用Diff算法的话，将会在老vnode的基础上新增一个新节点 C 即 [A，B] > [A, B, C]

Diff详解

我们从简单到困难逐步实现Diff

一、初始化diffVNode函数（即Diff函数）

在使用Diff算法之前我们需要了解新老Vnode的边界在哪，就是说在哪个位置新老节点发生了改变。

以上面为例，我们可以实现一个diffVNode函数：

// 接收新老节点arr
function diffVNode(oldV, newV) {
  let i = 0; // 定义初始头指针
  let e1 = oldV.length - 1; // 定义老节点尾指针
  let e2 = newV.length - 1; // 定义老节点尾指针
}

// 转虚拟节点函数
function h(type, props, children) {
    return {type: type,props: props, children: children}
}

// 判断节点是否相同
function isSameVNodeType(n1, n2) {
  return n1.type == n2.type && n1.props.key == n2.props.key;
}

通过函数我们可以看到，我们定义了头尾指针共四个指针，因为头指针都是从0开始，因此新老节点共用一个头指针。

二、确定新老节点的边界条件

接下来就是要确定新老节点的边界条件。

获取新老节点的头边界

基于diffVNode，我们新增一个循环

// 接收新老节点arr
function diffVNode(oldV, newV) {
  ...
  while (i <= e1 && i <= e2) {
    // 获取i指针处的新老虚拟节点
    const n1 = oldV[i];
    const n2 = newV[i];
    // 判断i指针处的新老节点是否相同
    if (isSameVNodeType(n1, n2)) {
      // 如果新老节点相同，需要执行patch函数去递归比较n1，n2，看子节点是否更新
      console.log("patch");
    } else {
      break;
    }
    i++; // 如果新老节点相同，指针往前一位
  }
}

我们循环比较新老节点，从头开始，如果节点相同则，调用patch函数递归比较，头指针往前一步，如果新老节点不同，终止循环。\

一步一步教你认识Vue3的双端Diff算法

对于这个例子，我们可以得到新老节点的头边界为2

let oldVnode = [
  h("p", { key: "A" }, "A"),
  h("p", { key: "B" }, "B"),
];
let newVnode = [
  h("p", { key: "A" }, "A"),
  h("p", { key: "B" }, "B"),
  h("p", { key: "C" }, "C"),
];

分析：oldVnode 的第0项和第1项完全相等于 newVnode 的第0项和第1项，oldVnode和newVnode在第2项开始不同

总结：通过while循环，比较oldV和newV数组的共同节点的虚拟节点，先判断虚拟节点是否一致，一致则递归比较它们的children节点。这里通过三个指针i和e1和e2来实现判断，如果前面的节点都相同，i会一直往后遍历，如果最后i指向了oldV和newV的末尾，那么就说明它们前面完全相同，如果出现两个节点出现不同则说明出现头边界，循环结束

从头部开始新节点和老节点完全相同的部分是 [0 ~ i](不含i)和[0 ~ i](不含i)

获取新老节点的尾边界

获取了新老节点的头边界，同样的我们也需要获取新老节点的尾边界，从后往前，直到找到这两个虚拟节点到哪个位置开始二者出现变化为止。 所以我们再创建一个循环，获取新老节点的尾边界

// 接收新老节点arr
function diffVNode(oldV, newV) {
  ...
  // 获取头边界
  while (i <= e1 && i <= e2) {
    ...
  }
  while (i <= e1 && i <= e2) {
    // 获取i指针处的新老虚拟节点
    const n1 = oldV[e1];
    const n2 = newV[e2];
    // 判断i指针处的新老节点是否相同
    if (isSameVNodeType(n1, n2)) {
      // 如果新老节点相同，需要执行patch函数去递归比较n1，n2，看子节点是否更新
      console.log("patch");
    } else {
      break;
    }
    e1--; // 如果新老节点相同，老虚拟节点尾指针退一位
    e2--; // 如果新老节点相同，新虚拟节点尾指针退一位
  }
}

我们循环比较新老节点，从尾开始，如果节点相同则，调用patch函数递归比较，新老节点的尾指针退一步（即e1--和e2--），如果新老节点不同，终止循环。\

一步一步教你认识Vue3的双端Diff算法

对于这个例子，我们可以得到新老节点的尾边界为0，-1

let oldVnode = [
  h("p", { key: "D" }, "D"),
  h("p", { key: "A" }, "A"),
  h("p", { key: "B" }, "B"),
  h("p", { key: "C" }, "C"),
];
let newVnode = [
  h("p", { key: "A" }, "A"),
  h("p", { key: "B" }, "B"),
  h("p", { key: "C" }, "C"),
];

分析：oldVnode 和 newVnode 的后3项相等，因此指针一直往前，当oldVnode到0的时候，newVnode到-1，此时二者不等，得到尾边界0，-1

总结：通过while循环，比较oldV和newV数组的共同节点的虚拟节点，先判断虚拟节点是否一致，一致则递归比较它们的children节点。这里通过三个指针i和e1和e2来实现判断，如果后面的节点都相同，e1和e2都会往前遍历，如果最后e1和e2都指向了oldV和newV的开头，那么就说明它们后面完全相同，如果出现两个节点出现不同则说明出现尾边界，循环结束 从尾部开始新节点和老节点完全相同的部分是 [e1 ~ oldV.length-1](不含e1)和[e2 ~ newV.length-1](不含e2)

分析新老节点边界值（重点）

通过上面的代码我们可以确定新节点和老节点从头开始和从尾开始，第一次不相等的位置。下面来分析下新老节点边界值：

尾节点是递减的，初始值为节点数组的长度，头节点是递增的，初始值为0
尾部开始新节点和老节点完全相同的部分是 [e1 ~ oldV.length-1](不含e1)和[e2 ~ newV.length-1](不含e2)，从头部开始新节点和老节点完全相同的部分是 [0 ~ i](不含i)和[0 ~ i](不含i)，所以i ~ e1 和 i ~ e2 相当于新老节点不同的部分
基于2可以得出，新老节点真实存在不同的部分，如[a,b,c,d,e]和[a,b,f,d,e],其中存在不同的部分f，则必然存在 e1-i >= 0 && e2 -i>= 0
如果存在e1 - i < 0 || e2 -i < 0，则新老节点可能存在包含关系，如[a,b,c,d,e]和[a,d,e]

确定新老节点的边界条件完整代码

function diffVNode(oldV, newV) {
  let i = 0; // 定义初始头指针
  let e1 = oldV.length - 1; // 定义老节点尾指针
  let e2 = newV.length - 1; // 定义老节点尾指针
  while (i <= e1 && i <= e2) {
    // 获取i指针处的新老虚拟节点
    const n1 = oldV[i];
    const n2 = newV[i];
    // 判断i指针处的新老节点是否相同
    if (isSameVNodeType(n1, n2)) {
      // 如果新老节点相同，需要执行patch函数去递归比较n1，n2，看子节点是否更新
      console.log("patch");
    } else {
      break;
    }
    i++; // 如果新老节点相同，指针往前一位
  }
  while (i <= e1 && i <= e2) {
    // 获取i指针处的新老虚拟节点
    const n1 = oldV[e1];
    const n2 = newV[e2];
    // 判断i指针处的新老节点是否相同
    if (isSameVNodeType(n1, n2)) {
      // 如果新老节点相同，需要执行patch函数去递归比较n1，n2，看子节点是否更新
      console.log("patch");
    } else {
      break;
    }
    e1--; // 如果新老节点相同，老虚拟节点尾指针退一位
    e2--; // 如果新老节点相同，新虚拟节点尾指针退一位
  }
  // i 的值等于新老虚拟节点的头边界， e1，e2 的值等于新老虚拟节点的尾边界
}

// 转虚拟节点函数
function h(type, props, children) {
    return {type: type,props: props, children: children}
}

// 判断节点是否相同
function isSameVNodeType(n1, n2) {
  return n1.type == n2.type && n1.props.key == n2.props.key;
}

三、新老虚拟节点更新的三种情况（Diff核心）

1.分析新老节点更新可能出现的三种情况

上面的代码中，我们已经成功获取了新老节点的头尾边界，那么我们可以开始去分析一下新老节点可以分成多少种情况。首先我们确定了新老节点的头尾边界，举个例子：

let oldVnode = [
  h("p", { key: "A" }, "A"),
  h("p", { key: "B" }, "B"),
  h("p", { key: "C" }, "C"),
  h("p", { key: "D" }, "D"),
];
let newVnode = [
  h("p", { key: "A" }, "A"),
  h("p", { key: "B" }, "B"),
  h("p", { key: "C" }, "C"),
];

对于这两个新老节点，我们可以获得头尾边界分别为 3 （头边界），3 2 （尾边界）

边界的意义是指到某个下标位置时的虚拟节点，新老虚拟节点不相同。

因此可以大致分为三种情况，两种简单情况一种复杂情况：

（一）新节点比老节点长，头边界或者尾边界存在完全包含的情况，需要新增节点

    新节点完全是在老节点的基础上新增，如 [A,B] => [A,B,C] 或 [C,A,B] 或 [A, C, B]

（二）老节点比新节点长，头边界或者尾边界存在完全包含的情况，需要删除节点

    新节点完全是在老节点的基础上删除，如 [A,B,C] => [B,C] 或 [A,B] 或 [A,C]

（三）老节点，新节点长短不定，头边界或者尾边界不存在完全包含的情况，需要灵活增删

    新节点和老节点边界不存在完全重合的情况，如 [A,B,C] => [A,D,C,B] 或 [F,A,C] 或 [D,B,C,A]

总结

情况1和情况2属于完全包含的简单类型，对老节点内部元素节点进行更新或删除完成。情况3属于乱序的情况，需要基于最长子序列等算法完成更新注意：下面的代码演示是通过操作数组的方式模拟虚拟节点Diff的过程，真正的Vue3的Vnode Diff过程，会在操作数组的地方调用patch函数去创建，修改，更新实际的节点

四、新节点比老节点长，头边界或者尾边界存在完全包含的情况（情况一）

举例

let oldVnode = [
  h("p", { key: "A" }, "A"),
  h("p", { key: "B" }, "B"),
];
let newVnode = [
  h("p", { key: "A" }, "A"),
  h("p", { key: "B" }, "B"),
  h("p", { key: "C" }, "C"),
];

通过上面的算法我们可以知道

此时 头指针 i = 2 （即当下标为2时，oldVnode[i] != newVnode[i]）此时 尾指针 e1 = 1，e2 = 2 （即当oldVnode下标为1时即最后一项时，当newVnode下标为2时即最后一项时，oldVnode[e1] != newVnode[e2]）

分析

可以看到此时 新老节点的头指针(i=2) 要大于旧节点的尾指针(e1=1) 即 i - e1 > 0，说明此时出现包含的情况，即从头尾出发新节点完全包含老节点

而且二者 i 值是完全相等的，说明从 0 - i 项，新老节点的内容完全相同，即对于老节点转换到新节点这个过程而言第0项和第1项，无需改动。

同理：[e1 ~ oldV.length-1](不含e1)和[e2 ~ newV.length-1](不含e2)范围内，新老节点的内容完全相同，因为此时e1 == oldV.length-1 且 e2 = newV.length-1，都指向最后一项，说明二者尾部没有相同的部分

因为i - e1 > 0 即从头尾出发新节点包含了老节点，因此对于新节点而言e2 - i这部分是需要新增的。结合上面的例子即增加 h("p", { key: "C" }, "C")。

基于diffVNode函数，我们需要新增对于情况一的处理逻辑

function diffVNode(oldV, newV) {
  let i = 0; // 定义初始头指针
  let e1 = oldV.length - 1; // 定义老节点尾指针
  let e2 = newV.length - 1; // 定义老节点尾指针
  ... // 获取新老节点边界的逻辑
  if (i > e1 && i <= e2) {
    // 判断当前元素添加位置
    let insertType = e1 >= 0; // 因为e1的值是递减的，如果小于0了，说明旧节点的头指针指向首项之前了，要往首项之前加，反之从e1项开始加
    let i_place = insertType ? e1 + 1 : 0;

    while (i <= e2) {
      oldV.splice(i_place, 0, newV[i]);
      i_place++;
      i++;
    }
  }
}

验证

用例一：

let oldVnode = [
  h("p", { key: "A" }, "A"),
  h("p", { key: "B" }, "B"),
  h("p", { key: "C" }, "C"),
];
let newVnode = [
  h("p", { key: "A" }, "A"),
  h("p", { key: "B" }, "B"),
  h("p", { key: "D" }, "D"),
  h("p", { key: "E" }, "E"),
  h("p", { key: "C" }, "C"),
];
diffVNode(oldVnode, newVnode)

效果：

一步一步教你认识Vue3的双端Diff算法

用例二：

let oldVnode = [
  h("p", { key: "A" }, "A"),
  h("p", { key: "B" }, "B"),
  h("p", { key: "C" }, "C"),
];
let newVnode = [
  h("p", { key: "A" }, "A"),
  h("p", { key: "B" }, "B"),
  h("p", { key: "C" }, "C"),
  h("p", { key: "D" }, "D"),
  h("p", { key: "E" }, "E"),
];
diffVNode(oldVnode, newVnode)

效果：

一步一步教你认识Vue3的双端Diff算法

完整代码

 function diffVNode(oldV, newV) {
  let i = 0; // 定义初始头指针
  let e1 = oldV.length - 1; // 定义老节点尾指针
  let e2 = newV.length - 1; // 定义老节点尾指针
  while (i <= e1 && i <= e2) {
    // 获取i指针处的新老虚拟节点
    const n1 = oldV[i];
    const n2 = newV[i];
    // 判断i指针处的新老节点是否相同
    if (isSameVNodeType(n1, n2)) {
      // 如果新老节点相同，需要执行patch函数去递归比较n1，n2，看子节点是否更新
      console.log("patch");
    } else {
      break;
    }
    i++; // 如果新老节点相同，指针往前一位
  }
  while (i <= e1 && i <= e2) {
    // 获取i指针处的新老虚拟节点
    const n1 = oldV[e1];
    const n2 = newV[e2];
    // 判断i指针处的新老节点是否相同
    if (isSameVNodeType(n1, n2)) {
      // 如果新老节点相同，需要执行patch函数去递归比较n1，n2，看子节点是否更新
      console.log("patch");
    } else {
      break;
    }
    e1--; // 如果新老节点相同，老虚拟节点尾指针退一位
    e2--; // 如果新老节点相同，新虚拟节点尾指针退一位
  }
  // i 的值等于新老虚拟节点的头边界， e1，e2 的值等于新老虚拟节点的尾边界

  // 情况一
  if (i > e1 && i <= e2) {
    // 判断当前元素添加位置=
    let insertType = e1 >= 0; // 因为e1的值是递减的，如果小于0了，说明旧节点的头指针指向首项之前了，要往首项之前加，反之从e1项开始加
    let i_place = insertType ? e1 + 1 : 0;

    while (i <= e2) {
      oldV.splice(i_place, 0, newV[i]);
      i_place++;
      i++;
    }
  } 

// 转虚拟节点函数
function h(type, props, children) {
  return { type: type, props: props, children: children };
}

// 判断节点是否相同
function isSameVNodeType(n1, n2) {
  return n1.type == n2.type && n1.props.key == n2.props.key;
}

五、老节点比新节点长，头边界或者尾边界存在完全包含的情况（情况二）

情况二和情况一很类似，也是存在完全包含，但是老的比新的长要删除

举例

let oldVnode = [
  h("p", { key: "A" }, "A"),
  h("p", { key: "B" }, "B"),
  h("p", { key: "C" }, "C"),
];
let newVnode = [
  h("p", { key: "A" }, "A"),
  h("p", { key: "B" }, "B"),
];

通过上面的算法我们可以知道

此时 头指针 i = 2 （即当下标为2时，oldVnode[i] != newVnode[i]）此时 尾指针 e1 = 2，e2 = 1 （即当oldVnode下标为2时即最后一项时，当newVnode下标为1时即最后一项时，oldVnode[e1] != newVnode[e2]）

分析

可以看到此时 新老节点的头指针(i=2) 要大于新节点的尾指针(e2=1) 即 i - e2 > 0，说明此时出现包含的情况，即从头尾出发老节点完全包含新节点

而且二者 i 值是完全相等的，说明从 0 - i 项，新老节点的内容完全相同，即对于老节点转换到新节点这个过程而言第0项和第1项，无需改动。

因为i - e2 > 0 即从头尾出发老节点包含了新节点，因此对于老节点而言e1 - i这部分是需要删除的。结合上面的例子即删除 h("p", { key: "C" }, "C")。

基于diffVNode函数，我们需要新增对于情况二的处理逻辑

function diffVNode(oldV, newV) {
  let i = 0; // 定义初始头指针
  let e1 = oldV.length - 1; // 定义老节点尾指针
  let e2 = newV.length - 1; // 定义老节点尾指针
  ... // 获取新老节点边界的逻辑
  if (i > e1 && i <= e2) {
    // 情况一
  } else if (i > e2) {
    // 判断当前元素删除是队头减还是队尾减
    let insertType = e2 >= 0; // 因为e2的值是递减的，如果小于0了，说明新节点的头指针指向首项之前了，所以要从头开始删除元素，反之从e2 + 1处开始删除元素
    let i_place = insertType ? e2 + 1 : 0;

    while (i <= e1) {
      oldV.splice(i_place, 1);
      i++;
    }
  }
}

验证

用例一：

let oldVnode = [
 h("p", { key: "A" }, "A"),
  h("p", { key: "B" }, "B"),
  h("p", { key: "C" }, "C"),
  h("p", { key: "D" }, "D"),
  h("p", { key: "E" }, "E"),
];
let newVnode = [
  h("p", { key: "A" }, "A"),
  h("p", { key: "B" }, "B"),
  h("p", { key: "C" }, "C"),
  h("p", { key: "E" }, "E"),
];
diffVNode(oldVnode, newVnode)

效果：

一步一步教你认识Vue3的双端Diff算法

用例二：

let oldVnode = [
 h("p", { key: "A" }, "A"),
  h("p", { key: "B" }, "B"),
  h("p", { key: "C" }, "C"),
  h("p", { key: "D" }, "D"),
  h("p", { key: "E" }, "E"),
];
let newVnode = [
  h("p", { key: "C" }, "C"),
  h("p", { key: "D" }, "D"),
  h("p", { key: "E" }, "E"),
];
diffVNode(oldVnode, newVnode)

效果：

一步一步教你认识Vue3的双端Diff算法

用例三：


let oldVnode = [
 h("p", { key: "A" }, "A"),
  h("p", { key: "B" }, "B"),
  h("p", { key: "C" }, "C"),
  h("p", { key: "D" }, "D"),
  h("p", { key: "E" }, "E"),
];
let newVnode = [
  h("p", { key: "A" }, "A"),
  h("p", { key: "B" }, "B"),
  h("p", { key: "C" }, "C"),
];
diffVNode(oldVnode, newVnode)

效果：

一步一步教你认识Vue3的双端Diff算法

完整代码

function diffVNode(oldV, newV) {
  let i = 0; // 定义初始头指针
  let e1 = oldV.length - 1; // 定义老节点尾指针
  let e2 = newV.length - 1; // 定义老节点尾指针
  while (i <= e1 && i <= e2) {
    // 获取i指针处的新老虚拟节点
    const n1 = oldV[i];
    const n2 = newV[i];
    // 判断i指针处的新老节点是否相同
    if (isSameVNodeType(n1, n2)) {
      // 如果新老节点相同，需要执行patch函数去递归比较n1，n2，看子节点是否更新
      console.log("patch");
    } else {
      break;
    }
    i++; // 如果新老节点相同，指针往前一位
  }
  while (i <= e1 && i <= e2) {
    // 获取i指针处的新老虚拟节点
    const n1 = oldV[e1];
    const n2 = newV[e2];
    // 判断i指针处的新老节点是否相同
    if (isSameVNodeType(n1, n2)) {
      // 如果新老节点相同，需要执行patch函数去递归比较n1，n2，看子节点是否更新
      console.log("patch");
    } else {
      break;
    }
    e1--; // 如果新老节点相同，老虚拟节点尾指针退一位
    e2--; // 如果新老节点相同，新虚拟节点尾指针退一位
  }
  // i 的值等于新老虚拟节点的头边界， e1，e2 的值等于新老虚拟节点的尾边界

  if (i > e1 && i <= e2) {
    // 判断当前元素添加位置
    let insertType = e1 >= 0; // 因为e1的值是递减的，如果小于0了，说明旧节点的头指针指向首项之前了，要往首项之前加即0，反之从e1 + 1项开始加
    let i_place = insertType ? e1 + 1 : 0;

    while (i <= e2) {
      oldV.splice(i_place, 0, newV[i]);
      i_place++;
      i++;
    }
  } else if (i > e2) {
    // 判断当前元素删除是队头减还是队尾减
    let insertType = e2 >= 0; // 因为e2的值是递减的，如果小于0了，说明新节点的头指针指向首项之前了，所以要从头开始删除元素，反之从e2 + 1处开始删除元素
    let i_place = insertType ? e2 + 1 : 0;

    while (i <= e1) {
      oldV.splice(i_place, 1);
      i++;
    }
  } 
}

// 转虚拟节点函数
function h(type, props, children) {
  return { type: type, props: props, children: children };
}

// 判断节点是否相同
function isSameVNodeType(n1, n2) {
  return n1.type == n2.type && n1.props.key == n2.props.key;
}

六、老节点，新节点长短不定，二者头边界或者尾边界不存在完全包含的情况（情况三）（困难情况）（乱序）

    如果新老节点不存在任意边界包含的情况
    比如新老节点中间存在了部分不同节点，新老节点两端存在了部分不同节点等
    通常这种被称为乱序的情况，也是Diff算法最复杂的情况。

对于这种情况，Vue3的Diff算法是通过建立最长递增子序列和映射表的方式去灵活增删的，下面来详细解释Diff对于这部分做了什么？

一、准备

分析

通过上面的代码我们可以知道，通过双端指针确定的头尾边界可以帮助我们确定新节点和老节点头尾相同的部分，对于这部分我们是不需要改动的。 但是对于乱序的新老节点而言，我们可能是

头部分相同 ~ [A, B, C, D] => [A, B, E, F, G] 这里是A，B相同，C, D和E, F, G算乱序部分
尾部分相同 ~ [A, B, C, D] => [E, F, G, C, D] 这里是C，D相同，A, B和E, F, G算乱序部分
头尾部分相同 ~ [A, B, E, C, D] => [A, B, F, G, C, D] 这里是头：[A, B]，尾：[C，D]相同，E和 F，G算乱序部分
头尾完全不同 ~ [A, B, C, D] => [E, F, G, C, D, H] 这里A, B, C, D 和 E, F, G, C, D, H整个都算乱序部分

等多种情况。

通过对上面例子的分析，知道边界只能帮我们锁定到头和尾如 [A, B, E, C, D] => [A, B, F, G, C, D] ，只能帮我们锁定到A，B 及 C, D，旧节点的E 和新节点的F, G就属于边界无法帮我们锁定的部分，算作是乱序部分，对应这部分内容我们需要借助包括最长公共子序列等算法实现其更新

准备工作

对于乱序的情况下我们可以新增逻辑如下：

先缓存当前新老节点的头指针，记录新节点乱序部分的节点数量

let s1 = i; // 老节点开始的下标
let s2 = i; // 新节点开始的下标
const toBePatched = e2 - i + 1 // 新节点乱序部分的节点数量

老节点乱序部分的节点有可能在新节点乱序部分的节点中出现过，如果出现的次数等于新节点乱序部分的节点数量则说明，老节点后面的节点都是需要删除的，所以提供一个变量来缓存老节点在新节点出现的次数。如：[A, B, C, D, E, F] => [A, B, D, C, F] 乱序部分为 C, D, E 和 D, C，因为新节点乱序部分只有两个，旧节点的则有三个，而且D，C都在新节点出现了，说明旧节点乱序部分 C, D后面的可以直接删除

let patched = 0; // 记录当前老节点已经在新节点出现了多少次
//然后出现次数等于toBePatched即新节点乱序部分的节点数量之和，则说明后面的老的可以直接删除

老节点可能在新节点中存在，因此这里创建一个(key，index)的映射表，后续遍历老节点的时候可以基于此判断当前节点是否存在新节点中，以及在新节点的哪个位置。

const keyToNewIndexMap = new Map(); // 创建一个映射表存储新节点的key和对应元素的位置
// 把新节点的key和对应元素位置存到映射中
for (let i = s2; i <= e2; i++) {
  keyToNewIndexMap.set(newV[i].props.key, i);
}

了解过Diff算法的同学可能听说过，Vue3的Diff算法中使用了最长公共子序列，帮助我们避免不必要的DOM操作，如子序列在映射的过程中一直递增说明这部分旧节点的顺序没有改动等，所以这里需要创建一个新数组处理最长子序列(下面会详细说明)

// 建立一个数组用来处理最长子序列
const newIndexToOldIndexMap = new Array(toBePatched);
for (let i = 0; i < toBePatched; i++) newIndexToOldIndexMap[i] = 0; 
// 规定如果当前项的值是0说明是新增的节点，初始化一个长度和新增节点一样长的数组，默认里面全部都是新增节点

准备工作完整代码

let s1 = i; // 老节点开始的下标
let s2 = i; // 新节点开始的下标
const toBePatched = e2 - i + 1; // 新节点乱序部分的节点数量

let patched = 0; // 记录当前老节点已经在新节点出现了多少次
//然后出现次数等于toBePatched即新节点乱序部分的节点数量之和，则说明后面的老的可以直接删除

const keyToNewIndexMap = new Map(); // 创建一个映射表存储新节点的key和对应元素的位置
// 把新节点的key和对应元素位置存到映射中
for (let i = s2; i <= e2; i++) {
  keyToNewIndexMap.set(newV[i].props.key, i);
}

// 建立一个数组用来处理最长子序列
const newIndexToOldIndexMap = new Array(toBePatched);
for (let i = 0; i < toBePatched; i++) newIndexToOldIndexMap[i] = 0;
// 约定如果当前项的值是0说明是新增的节点，初始化一个长度和新增节点一样长的数组，默认里面全部都是新增节点

// 深拷贝一下oldV，下面会有操作oldV的行为，会改变数组，因此先缓存oldV
let cpOldV = JSON.parse(JSON.stringify(oldV));

二、删除不存在的节点，建立新老节点乱序部分的映射关系

上面初始化了很多数据，包括新增节点数量，处理最长子序列的数组等。下面就开始遍历老节点，并完善我们在准备阶段创建的数据。

因为对于情况三而言，我们比较的内容是新节点的头尾边界范围内的节点和老节点的头尾边界范围内的节点 即oldV的[i ~ e1] 和 newV的[i ~ e2] 这部分乱序节点的比较。

一、建立一个对于老节点[i ~ e1]的循环

所以下面建立一个对于老节点[i ~ e1]的循环，建立完善oldV的[i ~ e1] 和 newV的[i ~ e2] 间的关系

for (let i = s1; i <= e1; i++) { 
    const curVnode = cpOldV[i] // 获取老节点当前项
}

二、判断当前节点是否在新节点的新增节点列表中存在

判断 老节点当前指针指向的虚拟节点 是否出现在新节点新增节点的列表中，并获取其在新节点中的下标。\

可以看到我们在这里判断当前虚拟节点是否出现在映射表（keyToNewIndexMap）中，通过key和映射表可以快速获取当前节点在新节点乱序部分的位置，否则只能走遍历逻辑逐位去判断

for (let i = s1; i <= e1; i++) {
  const oVNode = cpOldV[i]; // 老节点当前指针指向的虚拟节点

  let newIndex; // 查找老节点元素在不在新节点元素里面，并且在新节点元素的哪个下标问题
  if (oVNode.props.key != null) {
    // 当节点的key存在时，走映射表
    newIndex = keyToNewIndexMap.get(oVNode.props.key); // 在老的节点在不在新节点上面
  } else {
    // 如果当前的key不存在，走循环遍历
    for (let j = s2; j < e2; j++) {
      if (isSameVNodeType(oVNode, newV[j])) {
        newIndex = j;
        break;
      }
    }
  }
}

三、基于当前节点在新节点的乱序部分中的位置，删除不存在的节点和完善newIndexToOldIndexMap数组(用于最长子序列)

上一步我们拿到当前节点在新节点的乱序部分中的位置，对于这个只有两种可能。（1）没找到当前节点在新节点的乱序部分中的位置，获得的下标是undefined （2）找到了获取到具体的下标

一、删除不存在的节点

如果当前下标是undefined的话，说明这个节点没有出现在新节点的新增节点列表中，要删除。

for (let i = s1; i <= e1; i++) {
  ... // 获取节点下标
  
  if(newIndex == undefined) {
      if (newIndex == undefined) {
        // 为了方便，通过遍历的方式实现
        oldV.forEach((item, index) => {
          if (item.props.key == oVNode.props.key) {
            oldV.splice(index, 1);
          }
        });
      }
  }
}

针对这部分，不妨通过用例稍微验证下：

let oldVnode = [
 h("p", { key: "A" }, "A"),
  h("p", { key: "B" }, "B"),
  h("p", { key: "G" }, "G"),
  h("p", { key: "C" }, "C"),
];
let newVnode = [
  h("p", { key: "A" }, "A"),
  h("p", { key: "B" }, "B"),
  h("p", { key: "H" }, "H"),
  h("p", { key: "C" }, "C"),
];
diffVNode(oldVnode, newVnode)

效果：

一步一步教你认识Vue3的双端Diff算法

分析：可以看到新老节点的乱序部分，分别是 G 和 H，而G并没出现在新节点乱序部分中，所以G被删除了，但是因为我们还没处理新增的逻辑，所以这里H还没加上去。

二、完善newIndexToOldIndexMap数组(用于最长子序列)

若当前节点在新节点的乱序部分中的位置不为undefined，则说明当前节点在新节点乱序部分中存在了。基于此去完善newIndexToOldIndexMap数组。

回顾上文，我们可以知道newIndexToOldIndexMap数组实际上是一个长度等于新节点的乱序部分的数组，每一项的对应的就是新节点的乱序部分的一项。

(1).分析newIndexToOldIndexMap：

举个例子 [A, B, C, D, E, F] => [A, B, K, D, C, H, E, F] ，可以看到新老节点乱序的部分是 [C, D] => [K, D, C, H]。

初始化的 newIndexToOldIndexMap 等于[0, 0, 0, 0]，其中每一个0都映射到[K, D, C, H]中的一项，如第一个0映射到K，以此类推。

分析newIndexToOldIndexMap数组可知 K在newIndexToOldIndexMap中的下标，可以通过加头边界值的方式去映射到其在新节点数组中的位置。如：k 在newIndexToOldIndexMap中的下标是0，而[A, B, C, D, E, F] => [A, B, K, D, C, H, E, F]的头边界值是2，所以k在[A, B, K, D, C, H, E, F]的位置实际上等于 0 （newIndexToOldIndexMap中的下标）+ 2（头边界）= 2

回看新老节点乱序的部分[C, D] => [K, D, C, H]，其实C，D也在新节点乱序部分节点中，上面的代码实际上循环的是老节点数组的乱序部分即 i 从老节点的头边界开始，即对应的是当前项在老节点数组的下标。

所以我们可以通过遍历[C, D]，映射到 newIndexToOldIndexMap中，以[A, B, C, D, E, F] => [A, B, K, D, C, H, E, F]为例，完成映射之后的newIndexToOldIndexMap是[0, 4, 3, 0]。

newIndexToOldIndexMap 某项的下标对应的是其在新节点乱序部分的下标，某一项值为 0 的时候认为当前的节点是新增的，某一项值非 0 的时候，说明当前节点在老节点乱序的部分存在，如 C 在[C, D] 一样，且当前项值为其在老节点数组的下标。（重点）

(2).完善newIndexToOldIndexMap代码：

通过上面的分析我们可以实现完善newIndexToOldIndexMap部分的代码：

for (let i = s1; i <= e1; i++) {
  ... // 获取节点下标
  
  if (newIndex == undefined) {
    oldV.forEach((item, index) => {
      if (item.props.key == oVNode.props.key) {
        oldV.splice(index, 1);
      }
    });
  } else {
    newIndexToOldIndexMap[newIndex - s2] = i + 1; // 0 意味着是新增的节点
    // 如果在新节点中找到了这个节点，则需要调用patch函数去递归比较，因为key相同但是其他属性可能改了，如children等
    // vue3源码中 patch(oVNode, newV[newIndex])
  }
}

同样的不妨通过用例来验证下：用例一：

let oldVnode = [
  h("p", { key: "A" }, "A"),
  h("p", { key: "B" }, "B"),
  h("p", { key: "C" }, "C"),
  h("p", { key: "D" }, "D"),
  h("p", { key: "E" }, "E"),
];
let newVnode = [
  h("p", { key: "A" }, "A"),
  h("p", { key: "B" }, "B"),
  h("p", { key: "F" }, "F"),
  h("p", { key: "C" }, "C"),
  h("p", { key: "D" }, "D"),
  h("p", { key: "G" }, "G"),
  h("p", { key: "E" }, "E"),
];
diffVNode(oldVnode, newVnode)

效果：

一步一步教你认识Vue3的双端Diff算法

解析：新老节点乱序部分分别为[C, D]和[F, C, D, G] ，生成的newIndexToOldIndexMap是 [0, 3, 4, 0]，因为3,4不等于0，说明对应的C和D在老节点中出现了，同时代码可以看到

newIndexToOldIndexMap[newIndex - s2] = i + 1;

当前节点在新节点存在时，会在新节点对应位置进行赋值，值为当前节点在老节点的位置就是 i，因为我们约定i为0的时候，当做是新增的节点，所以这里i要加一，这样子就完成了新老节点的乱序部分的映射。

用例二：

let oldVnode = [
  h("p", { key: "A" }, "A"),
  h("p", { key: "B" }, "B"),
  h("p", { key: "D" }, "D"),
  h("p", { key: "E" }, "E"),
];
let newVnode = [
  h("p", { key: "A" }, "A"),
  h("p", { key: "B" }, "B"),
  h("p", { key: "F" }, "F"),
  h("p", { key: "C" }, "C"),
  h("p", { key: "E" }, "E"),
];
diffVNode(oldVnode, newVnode)

效果：

一步一步教你认识Vue3的双端Diff算法

(3).优化newIndexToOldIndexMap代码：

在上面的代码中我们完成了新老节点乱序部分的映射，即完善了newIndexToOldIndexMap数组。

下面来思考两个问题：

（1）遍历的过程中我们会得到newIndex，即当前节点在新节点的位置，如果newIndex出现的次数等于新节点乱序部分的节点数量，意味着什么？（2）newIndexToOldIndexMap 得到的是新老节点的乱序部分的映射数组，那数组中非0项的大小和位置是否有什么特殊含义？

一、问题一：遍历的过程中我们会得到newIndex，即当前节点在新节点的位置，如果newIndex出现的次数等于新节点乱序部分的节点数量，意味着什么？

分析

遍历的过程中我们会得到newIndex，如果newIndex 不等于 undefined，则说明当前节点出现在了新节点的乱序部分中。

因为每一个newIndex都对应新节点乱序部分的一个真实节点，当在遍历过程中newIndex出现的数量等于新节点乱序部分的节点数量时，说明所有需要更新的节点都已经找完了，遍历后续的节点都可以直接删除。

举个例子： [A, B, H, C, D, K, E, F] => [A, B, C, D, E, F] 可以得到其乱序部分是 [ H, C, D, K] => [C, D] 所以我们在遍历 [ H, C, D, K] 的过程中，当遍历到D的时候，后续的节点就不用找 newIndex等操作了，因为 [H, C, D]的遍历中，已经把新节点的乱序部分全部找完了，即[C, D]。

看回去我们的准备工作：

const toBePatched = e2 - i + 1; // 新节点乱序部分的节点数量

let patched = 0; // 记录当前老节点已经在新节点出现了多少次
//然后出现次数等于toBePatched即新节点乱序部分的节点数量之和，则说明后面的老的可以直接删除

这里定义了toBePatched和patched两个变量，可以通过patched ++ 记录newIndex出现次数，当patched > toBePatched时，后面的可以全部删除。

完整代码如下：

for (let i = s1; i <= e1; i++) {
      const oVNode = cpOldV[i]; // 老节点当前指针指向的元素节点

      // 判断当前已经处理的节点是否超过新增的节点数，如果超过就直接将后续的移除
      if (patched >= toBePatched) {
        oldV.forEach((item, index) => {
          if (item.props.key == oVNode.props.key) {
            oldV.splice(index, 1);
          }
        });
        continue;
      }

      let newIndex; // 查找老节点元素在不在新节点元素里面，并且在新节点元素的哪个下标问题
      if (oVNode.props.key != null) {
        // 当节点的key存在时，走映射表
        newIndex = keyToNewIndexMap.get(oVNode.props.key); // 在老的节点在不在新节点上面
      } else {
        // 如果当前的key不存在，走循环遍历
        for (let j = s2; j < e2; j++) {
          if (isSameVNodeType(oVNode, newV[j])) {
            newIndex = j;
            break;
          }
        }
      }

      if (newIndex == undefined) {
        oldV.forEach((item, index) => {
          if (item.props.key == oVNode.props.key) {
            oldV.splice(index, 1);
          }
        });
      } else {
        newIndexToOldIndexMap[newIndex - s2] = i + 1; // 0 意味着是新增的节点
        // 如果在新节点中找到了这个节点，则需要调用patch函数去递归比较，因为key相同但是其他属性可能改了，如children等
        // vue3源码中 patch(oVNode, newV[newIndex])

        patched++; // 说明处理完了一个新的节点
      }
    }

不妨通过用例验证一下：

用例1：

let oldVnode =  [
    h("p", { key: "A" }, "A"),
    h("p", { key: "B" }, "B"),
    h("p", { key: "F" }, "F"),
      h("p", { key: "D" }, "D"),
    h("p", { key: "C" }, "C"),
    h("p", { key: "E" }, "E"),
];
let newVnode = [
    h("p", { key: "A" }, "A"),
    h("p", { key: "B" }, "B"),
    h("p", { key: "D" }, "D"),
    h("p", { key: "E" }, "E"),
];
diffVNode(oldVnode, newVnode)

用例效果:

一步一步教你认识Vue3的双端Diff算法

用例分析：代码遍历到D节点的时候就已经把新节点的乱序部分节点全部找完了，所以后面的直接删除就行。

二、问题二：newIndexToOldIndexMap 得到的是新老节点的乱序部分的映射数组，那数组中非0项的大小和位置是否有什么特殊含义？

我们先来看两个用例：

用例一：

let oldVnode = [
  h("p", { key: "A" }, "A"),
  h("p", { key: "B" }, "B"),
  h("p", { key: "C" }, "C"),
  h("p", { key: "D" }, "D"),
  h("p", { key: "E" }, "E"),
];
let newVnode = [
  h("p", { key: "A" }, "A"),
  h("p", { key: "B" }, "B"),
  h("p", { key: "F" }, "F"),
  h("p", { key: "C" }, "C"),
  h("p", { key: "D" }, "D"),
  h("p", { key: "G" }, "G"),
  h("p", { key: "E" }, "E"),
];
diffVNode(oldVnode, newVnode)

效果：

用例二：

let oldVnode = [
  h("p", { key: "A" }, "A"),
  h("p", { key: "B" }, "B"),
  h("p", { key: "C" }, "C"),
  h("p", { key: "D" }, "D"),
  h("p", { key: "E" }, "E"),
];
let newVnode = [
  h("p", { key: "A" }, "A"),
  h("p", { key: "B" }, "B"),
  h("p", { key: "F" }, "F"),
  h("p", { key: "D" }, "D"),
  h("p", { key: "C" }, "C"),
  h("p", { key: "G" }, "G"),
  h("p", { key: "E" }, "E"),
];
diffVNode(oldVnode, newVnode)

效果：

一步一步教你认识Vue3的双端Diff算法

分析：

可以看到两个用例只是更换了新节点乱序部分的 D，C 的位置，对应的newIndexToOldIndexMap也发生了改变，3，4的位置发生了交换。

分析可以知道，newIndexToOldIndexMap 下标对应的是当前节点在新节点乱序部分的下标值，下标对应的值对应当前节点在老节点数组的下标值。

如果老节点乱序部分转换到新节点乱序部分的过程中如果顺序没有改变即：C，D => C, D ，则newIndexToOldIndexMap的非0项应该是递增的，反之则说明顺序发生了改变。

基于此我们可以新增代码如下：

let move = false // 是否需要移动
let maxNewIndexSoFar = 0 // 判断是否递增

for (let i = s1; i <= e1; i++) {
      const oVNode = cpOldV[i]; // 老节点当前指针指向的元素节点

      // 判断当前已经处理的节点是否超过新增的节点数，如果超过就直接将后续的移除
      ...

      // 获取newIndex的值
      ...

      if (newIndex == undefined) {
        // 删除不存在节点
        ...
      } else {
      
        // 初始化一个maxNewIndexSoFar，每一次都和映射值去比较，如果映射值比他大那就直接更新映射值，如果后一个映射值一直都比maxNewIndexSoFar大，说明这个顺序的递增的没有移动
        if (newIndex >= maxNewIndexSoFar) {
          maxNewIndexSoFar = newIndex;
        } else {
          // 反之有顺序发生了移动
          move = true;
        }
      
        //完善newIndexToOldIndexMap
        ...
        patched++; // 说明处理完了一个新的节点
      }
    }

不妨通过用例验证一下：

用例一：

let oldVnode = [
  h("p", { key: "A" }, "A"),
  h("p", { key: "B" }, "B"),
  h("p", { key: "C" }, "C"),
  h("p", { key: "D" }, "D"),
  h("p", { key: "E" }, "E"),
];
let newVnode = [
  h("p", { key: "A" }, "A"),
  h("p", { key: "B" }, "B"),
  h("p", { key: "F" }, "F"),
  h("p", { key: "C" }, "C"),
  h("p", { key: "D" }, "D"),
  h("p", { key: "G" }, "G"),
  h("p", { key: "E" }, "E"),
];
diffVNode(oldVnode, newVnode)

效果：

一步一步教你认识Vue3的双端Diff算法

用例二：

let oldVnode = [
  h("p", { key: "A" }, "A"),
  h("p", { key: "B" }, "B"),
  h("p", { key: "C" }, "C"),
  h("p", { key: "D" }, "D"),
  h("p", { key: "E" }, "E"),
];
let newVnode = [
  h("p", { key: "A" }, "A"),
  h("p", { key: "B" }, "B"),
  h("p", { key: "F" }, "F"),
  h("p", { key: "D" }, "D"),
  h("p", { key: "C" }, "C"),
  h("p", { key: "G" }, "G"),
  h("p", { key: "E" }, "E"),
];
diffVNode(oldVnode, newVnode)

效果：

一步一步教你认识Vue3的双端Diff算法

总结

到这里我们最开始定义的基本数据都完成赋值了，包括newIndexToOldIndexMap，move等。同时删除了没有在新节点中出现过的虚拟节点。

最后基于newIndexToOldIndexMap，move等信息，完成新老乱序节点的新建和交互功能，diff算法就算结算了。（下一点进行）

完整代码如下:

export function diffVNode(oldV, newV) {
  let i = 0; // 定义初始头指针
  let e1 = oldV.length - 1; // 定义老节点尾指针
  let e2 = newV.length - 1; // 定义老节点尾指针
  while (i <= e1 && i <= e2) {
    // 获取i指针处的新老虚拟节点
    const n1 = oldV[i];
    const n2 = newV[i];
    // 判断i指针处的新老节点是否相同
    if (isSameVNodeType(n1, n2)) {
      // 如果新老节点相同，需要执行patch函数去递归比较n1，n2，看子节点是否更新
      console.log("patch");
    } else {
      break;
    }
    i++; // 如果新老节点相同，指针往前一位
  }
  while (i <= e1 && i <= e2) {
    // 获取i指针处的新老虚拟节点
    const n1 = oldV[e1];
    const n2 = newV[e2];
    // 判断i指针处的新老节点是否相同
    if (isSameVNodeType(n1, n2)) {
      // 如果新老节点相同，需要执行patch函数去递归比较n1，n2，看子节点是否更新
      console.log("patch");
    } else {
      break;
    }
    e1--; // 如果新老节点相同，老虚拟节点尾指针退一位
    e2--; // 如果新老节点相同，新虚拟节点尾指针退一位
  }
  // i 的值等于新老虚拟节点的头边界， e1，e2 的值等于新老虚拟节点的尾边界

  if (i > e1 && i <= e2) {
    // 判断当前元素添加位置
    let insertType = e1 >= 0; // 因为e1的值是递减的，如果小于0了，说明旧节点的头指针指向首项之前了，要往首项之前加即0，反之从e1 + 1项开始加
    let i_place = insertType ? e1 + 1 : 0;

    while (i <= e2) {
      oldV.splice(i_place, 0, newV[i]);
      i_place++;
      i++;
    }
  } else if (i > e2) {
    // 判断当前元素删除是队头减还是队尾减
    let insertType = e2 >= 0; // 因为e2的值是递减的，如果小于0了，说明新节点的头指针指向首项之前了，所以要从头开始删除元素，反之从e2 + 1处开始删除元素
    let i_place = insertType ? e2 + 1 : 0;

    while (i <= e1) {
      oldV.splice(i_place, 1);
      i++;
    }
  } else {
    let s1 = i; // 老节点开始的下标
    let s2 = i; // 新节点开始的下标

    let move = false; // 是否需要移动
    let maxNewIndexSoFar = 0; // 判断是否递增

    const toBePatched = e2 - i + 1; // 新增节点的数量

    let patched = 0; // 记录当前老节点已经在新节点出现了多少次
    //然后出现次数等于toBePatched即新增节点数量之和，则说明后面的老的可以直接删除

    const keyToNewIndexMap = new Map(); // 创建一个映射表存储新节点的key和对应元素的位置
    // 把新节点的key和对应元素位置存到映射中
    for (let i = s2; i <= e2; i++) {
      keyToNewIndexMap.set(newV[i].props.key, i);
    }

    // 建立一个数组用来处理最长子序列
    const newIndexToOldIndexMap = new Array(toBePatched);
    for (let i = 0; i < toBePatched; i++) newIndexToOldIndexMap[i] = 0;
    // 规定如果当前项的值是0说明是新增的节点，初始化一个长度和新增节点一样长的数组，默认里面全部都是新增节点

    // 深拷贝一下oldV，下面会有操作oldV的行为，会改变数组，因此先缓存oldV
    let cpOldV = JSON.parse(JSON.stringify(oldV));

    for (let i = s1; i <= e1; i++) {
      const oVNode = cpOldV[i]; // 老节点当前指针指向的元素节点

      // 判断当前已经处理的节点是否超过新增的节点数，如果超过就直接将后续的移除
      if (patched >= toBePatched) {
        oldV.forEach((item, index) => {
          if (item.props.key == oVNode.props.key) {
            oldV.splice(index, 1);
          }
        });
        continue;
      }

      let newIndex; // 查找老节点元素在不在新节点元素里面，并且在新节点元素的哪个下标问题
      if (oVNode.props.key != null) {
        // 当节点的key存在时，走映射表
        newIndex = keyToNewIndexMap.get(oVNode.props.key); // 在老的节点在不在新节点上面
      } else {
        // 如果当前的key不存在，走循环遍历
        for (let j = s2; j < e2; j++) {
          if (isSameVNodeType(oVNode, newV[j])) {
            newIndex = j;
            break;
          }
        }
      }

      if (newIndex == undefined) {
        oldV.forEach((item, index) => {
          if (item.props.key == oVNode.props.key) {
            oldV.splice(index, 1);
          }
        });
      } else {
        // 初始化一个maxNewIndexSoFar，每一次都和映射值去比较，如果映射值比他大那就直接更新映射值，如果后一个映射值一直都比maxNewIndexSoFar大，说明这个顺序的递增的没有移动
        if (newIndex >= maxNewIndexSoFar) {
          maxNewIndexSoFar = newIndex;
        } else {
          // 反之有顺序发生了移动
          move = true;
        }

        newIndexToOldIndexMap[newIndex - s2] = i + 1; // 0 意味着是新增的节点
        // 如果在新节点中找到了这个节点，则需要调用patch函数去递归比较，因为key相同但是其他属性可能改了，如children等
        // vue3源码中 patch(oVNode, newV[newIndex])

        patched++; // 说明处理完了一个新的节点
      }
    }
  }
}

// 转虚拟节点函数
function h(type, props, children) {
  return { type: type, props: props, children: children };
}

// 判断节点是否相同
function isSameVNodeType(n1, n2) {
  return n1.type == n2.type && n1.props.key == n2.props.key;
}

三、基于newIndexToOldIndexMap和最长递增子序列，完成剩余老节点乱序部分到新节点乱序部分的交换和新建

在上面的内容中我们获得了newIndexToOldIndexMap，新老节点乱序部分的映射数组，代表了老节点出现在新节点乱序部分的位置。比如 [A, B, C, D, E] => [A, B, F, C, D, G, E] 得到的newIndexToOldIndexMap是 [0, 3, 4, 0] ，新节点乱序部分的C 出现在老节点的（3 - 1）下标处，新节点乱序部分的D 出现在老节点的（4 - 1）下标处。

下面来详细描述下vue是然后完成老节点乱序部分到新节点乱序部分的交换和新建的

一、获得最长递增子序列

回顾上文，我们得到了newIndexToOldIndexMap即新老节点乱序部分的映射数组，项值为0代表当前节点为新增节点，项值非0代表当前节点在老节点中出现过，无需删除，且项值表示其在老节点中的位置。

如果非0项的项值如果是递增的则说明在老节点中出现过的节点，并且顺序没有发生改变，反之认为在老节点中出现过的节点顺序改变。

分析

不妨思考一个问题： [C, D, E] => [E, C, D]，如何完成转换呢？

方案一：把[C, D] 移到 [E] 的后面。方案二：把[E] 移到 [C, D] 的前面。

不难看出方案一我们移动了 C，D 两个节点，而方案二我们只移动了一个节点 E。显然方案二的性能会更好，因为只移动一个节点。

将[C, D, E] => [E, C, D]转成对应的 newIndexToOldIndexMap ，可以得到 [3, 1, 2]，所以我们可以知道newIndexToOldIndexMap 中最长的递增子序列，是无需改动的或交换位置的，如[3, 1, 2] 中的 [1, 2]

为了最少次数完成节点的更新，我们需要获取newIndexToOldIndexMap的最长的递增子序列

代码实现

最长递增子序列算法

// 最长递增子序列算法
function getSequence(arr) {
    const p = arr.slice();
    const result = [0];
    let i, j, u, v, c;
    const len = arr.length;
    for (i = 0; i < len; i++) {
        const arrI = arr[i];
        if (arrI !== 0) {
            j = result[result.length - 1];
            if (arr[j] < arrI) {
                p[i] = j;
                result.push(i);
                continue;
            }
            u = 0;
            v = result.length - 1;
            while (u < v) {
                c = (u + v) >> 1;
                if (arr[result[c]] < arrI) {
                    u = c + 1;
                } else {
                    v = c;
                }
            }
            if (arrI < arr[result[u]]) {
                if (u > 0) {
                    p[i] = result[u - 1];
                }
                result[u] = i;
            }
        }
    }
    u = result.length;
    v = result[u - 1];
    while (u-- > 0) {
        result[u] = v;
        v = p[v];
    }
    return result;
}

补充获取newIndexToOldIndexMap最长递增子序列

function diffVNode(oldV, newV) {
  ... //获取头尾边界

  if (i > e1 && i <= e2) {
    ... // 情况一
  } else if (i > e2) {
    ... // 情况二
  } else {
    ... // 获取newIndexToOldIndexMap

    // 获取最长子序列
    const increasingNewIndexSequence = getSequence(newIndexToOldIndexMap) || [];
    let j = increasingNewIndexSequence.length - 1;
  }
}

用例：

let oldVnode = [
  h("p", { key: "A" }, "A"),
  h("p", { key: "B" }, "B"),
  h("p", { key: "C" }, "C"),
  h("p", { key: "D" }, "D"),
  h("p", { key: "E" }, "E"),
];
let newVnode = [
  h("p", { key: "A" }, "A"),
  h("p", { key: "B" }, "B"),
  h("p", { key: "E" }, "E"),
  h("p", { key: "C" }, "C"),
  h("p", { key: "D" }, "D"),
];
diffVNode(oldVnode, newVnode)

效果：

一步一步教你认识Vue3的双端Diff算法

分析：

我们可以得到newIndexToOldIndexMap为[5, 3, 4]，说明其最长递增子序列应该是[3, 4]，所以通过最长递增子序列算法我们得到数组[1, 2] ，对应 3和4 在 [5, 3, 4]中的下标。

二、完成新节点的创建及旧节点的位置交换

上面我们已经获得了newIndexToOldIndexMap的最长递增子序列，即哪些老节点是不需要交换位置的。

所以接下来我们的目的就很明确了。

遍历新节点乱序部分
如果当前节点下标对应在newIndexToOldIndexMap值为0，则创建该节点
如果当前节点下标对应在newIndexToOldIndexMap值非0，且在最长递增子序列中存在映射，则无需操作
如果当前节点下标对应在newIndexToOldIndexMap值非0，且在最长递增子序列中不存在映射，则需要交换位置

（1）遍历新节点乱序部分

我们可以创建一个循环。值得注意的是采用倒叙循环，因为需要移动的值，要获取锚点插入，正序的话，这个锚点不好找，而前面的值，都可能不稳定

for (let i = toBePatched - 1; i >= 0; i--) {
  // 获取当前位置
  const nextIndex = i + s2; // 因为i是新增节点乱序部分的下标，并不是新节点数组的真实下标，所以这里需要加上头边界s2
  // 获取当前位置在新节点数组的节点
  const nextChild = newV[nextIndex];
  // 获取节点插入位置，如果这个位置没有大于列表长度，说明就是nextIndex + 1，否则加到最后
  const insertEl = nextIndex + 1 < newV.length ? newV[nextIndex + 1] : null; 
}

（2）当前节点下标对应在newIndexToOldIndexMap值为0，创建该节点

上面我们遍历新节点乱序部分，这部分节点和newIndexToOldIndexMap存在映射关系，所以当我们遍历到某一项其在newIndexToOldIndexMap中映射的值为0时，说明我们这个节点要新增。下面来实现一下这个代码：

for (let i = toBePatched - 1; i >= 0; i--) {
      // 获取当前位置
      const nextIndex = i + s2; // 因为i是新增节点乱序部分的下标，并不是新节点数组的真实下标，所以这里需要加上头边界s2
      // 获取当前位置在新节点数组的节点
      const nextChild = newV[nextIndex];
      // 获取节点插入位置，如果这个位置没有大于列表长度，说明就是nextIndex + 1，否则加到最后
      const insertEl = nextIndex + 1 < newV.length ? newV[nextIndex + 1] : null;
      // 如果某一项其在newIndexToOldIndexMap中映射的值为0，新增这个节点
      if (newIndexToOldIndexMap[i] == 0) {
        if (insertEl) {
          let before_index;
          // 找到才需要插入节点的下标，在这个位置插入我们新增的节点
          oldV.forEach((item, index) => {
            if (item.props.key == insertEl.props.key) {
              before_index = index;
            }
          });
          oldV.splice(before_index, 0, nextChild);
        } else {
          oldV.push(nextChild);
        }
      }
    }

同样的，不妨通过用例来验证下：

用例一：

let oldVnode = [
  h("p", { key: "A" }, "A"),
  h("p", { key: "B" }, "B"),
  h("p", { key: "C" }, "C"),
  h("p", { key: "D" }, "D"),
];
let newVnode = [
  h("p", { key: "A" }, "A"),
  h("p", { key: "B" }, "B"),
  h("p", { key: "E" }, "E"),  
  h("p", { key: "C" }, "C"),
  h("p", { key: "F" }, "F"),
  h("p", { key: "D" }, "D"),
];
diffVNode(oldVnode, newVnode)

效果：

一步一步教你认识Vue3的双端Diff算法

分析：可以看到新老节点乱序部分为 [C] 和 [E, C, D]，转换成newIndexToOldIndexMap是[0, 1, 0]，在上面的算法中如果我们遇到0就创建这个节点，如果非0，则跳过，最终完成节点的转换。

用例二：

let oldVnode = [
  h("p", { key: "C" }, "C"),
  h("p", { key: "D" }, "D"),
  h("p", { key: "A" }, "A"),
  h("p", { key: "B" }, "B"),
];
let newVnode = [
  h("p", { key: "E" }, "E"),  
  h("p", { key: "C" }, "C"),
  h("p", { key: "F" }, "F"),
  h("p", { key: "D" }, "D"),
  h("p", { key: "A" }, "A"),
  h("p", { key: "B" }, "B"),
];
diffVNode(oldVnode, newVnode)

效果:

一步一步教你认识Vue3的双端Diff算法

用例三：

let oldVnode = [
  h("p", { key: "A" }, "A"),
  h("p", { key: "B" }, "B"),
  h("p", { key: "C" }, "C"),
];
let newVnode = [
  h("p", { key: "A" }, "A"),
  h("p", { key: "B" }, "B"),
  h("p", { key: "E" }, "E"),  
  h("p", { key: "C" }, "C"),
  h("p", { key: "F" }, "F"),
];
diffVNode(oldVnode, newVnode)

效果:

一步一步教你认识Vue3的双端Diff算法

（3）如果当前节点下标对应在newIndexToOldIndexMap值非0，根据其在最长递增子序列中的映射，完成位置交换

分析：

上面我们处理了当前下标对应在newIndexToOldIndexMap值为0的情况，意味着当前节点要新增，这里处理下newIndexToOldIndexMap 非0 的情况。\

我们知道如果newIndexToOldIndexMap 非0，说明当前节点既在老节点中存在，又在新节点中存在。

如果非0项的值属于递增的状态说明这些节点其实并没有发生位置改变，即顺序的一致的，如果非0项的值不是递增，则说明有一些节点交换了位置，对于这部分节点我们需要更新其位置。

但是我们如何完成位置的更新呢？上面我们通过 最长递增子序列算法 获得了最长的，没有改变位置的节点数组。基于此我们来实现下newIndexToOldIndexMap非0项位置交换的代码。

步骤一：

首先要判断是否发生位置改变，如果位置没有发生改变即老节点部分顺序是一致的，是不需要交换位置的。如[A, B, C] => [A, D, B, C, E]，乱序部分是[B, C] 和 [D, B, C, E], B 依旧在 C的前面，所以我们不需要交换位置只要加上 D 和 E两个节点即可。

结合上面代码我们其实在获取newIndexToOldIndexMap时就定义了一个变量move 来判断是否发生移动。

代码如下：

for (let i = toBePatched - 1; i >= 0; i--) {
  // 获取当前节点，插入位置等信息
  ...
  // 如果某一项其在newIndexToOldIndexMap中映射的值为0，新增这个节点
  ...
  // 如果某一项其在newIndexToOldIndexMap中映射的值非0
  else {
      // 新增判断是否需要触发移动逻辑
      if(move) {
      }
  }
}

步骤二：

根据我们最长递增子序列完成映射，判断当前节点是否需要移动，并对需要移动的节点更新位置。

看个例子， [A, B, C, D] => [A, C, B, D, E] 我们可以得到乱序部分是 [B, C, D] 和 [C, B, D, E]，转成newIndexToOldIndexMap 可以得到 [3, 2, 4, 0] , 得到最长递增子序列是 [1，2] 即 newIndexToOldIndexMap 中项值为2 和 4 的下标。

我们定义一个指针 j 指向最长递增子序列 [1，2] 的尾节点，即 j = [1，2].length - 1
我们在遍历节点时候遇到项值为0的会走更新逻辑，所以对于[3, 2, 4, 0]，遇到 0 时会新增节点，所以先新增 E
继续遍历 i 走到下标为2的位置，项值为4（非0），进入非0 逻辑，可以看到最长递增子序列对应的是newIndexToOldIndexMap中最长递增子序列的下标值，如 [3, 2, 4, 0] 最长递增数组项是 2, 4，所以得到[1（2的下标）, 2（4的下标）]
因为进入了非0逻辑，开始判断，此时j = [1，2].length - 1 = 1，指向最长递增子序列第二项 [1，2] 即 2，因为遍历节点的过程中是从后往前的，此时 i = 2，因为 j指向的项值 2 等于当前节点 4的下标，说明当前节点属于最长递增子序列的一部分，无须移动。同时最长递增子序列的指针 j 向前移动一位 j-- 即 j = 0
继续遍历，此时 i = 1 而 j = 0，当j = 0时，最长递增子序列的指针指向[1，2]的第 0 项即 1，因为 j指向的项值 1 等于当前节点的下标 i，说明当前节点属于最长递增子序列的一部分，无须移动。同时最长递增子序列的指针 j 向前移动一位 j-- 即 j = -1。
继续遍历，此时 i = 0 而 j = -1，可以知道 j 已经指到头了，所以 [1, 2]的 j项已经不存在，相当于undefined，此时 j指向的项值 undefined 并不等于当前节点的下标 i（0），说明当前节点不属于最长递增子序列的一部分触发移动逻辑。

以上就是一个需要移动节点的完整流程。

基于此我们可以实现代码如下

for (let i = toBePatched - 1; i >= 0; i--) {
  // 获取当前节点，插入位置等信息
  ...
  // 如果某一项其在newIndexToOldIndexMap中映射的值为0，新增这个节点
  ...
  // 如果某一项其在newIndexToOldIndexMap中映射的值非0
  else {
      // 新增判断是否需要触发移动逻辑
      if (move) {
          if (j < 0 || i != increasingNewIndexSequence[j]) {
            if (insertEl) {
              // （注意：将当前节点移动到指定位置，因为这里是用数组的方式去模拟操作没有insert这些方法）
              // (就用比较蠢的现删掉老节点，再将新节点插入到指定位置模拟数组的移动）
            
              // 获取当前节点在老数组中的位置，然后将这个节点移动到目标位置
              let old_index = oldV.findIndex((item) => {
                return item.props.key == nextChild.props.key;
              });
              oldV.splice(old_index, 1);
              let before_index = oldV.findIndex((item) => {
                return item.props.key == insertEl.props.key;
              });
              oldV.splice(before_index, 0, nextChild);
             
            } else {
              // 先删掉老节点再将新节点插入到最后一位
            
              let old_index = oldV.findIndex((item) => {
                return item.props.key == nextChild.props.key;
              });
              oldV.splice(old_index, 1); // 当前节点从添加到最后
              oldV.push(nextChild);
            }
          } else {
            j--;
          }
        }
  }
}

同样的，不妨通过用例来验证下：

用例一：

let oldVnode = [
  h("p", { key: "A" }, "A"),
  h("p", { key: "B" }, "B"),
  h("p", { key: "C" }, "C"),
  h("p", { key: "D" }, "D"),
];
let newVnode = [
  h("p", { key: "A" }, "A"), 
  h("p", { key: "C" }, "C"),
  h("p", { key: "B" }, "B"),
  h("p", { key: "D" }, "D"),
  h("p", { key: "E" }, "E"), 
];
diffVNode(oldVnode, newVnode)

效果如下：

一步一步教你认识Vue3的双端Diff算法

用例二：

let oldVnode = [
  h("p", { key: "C" }, "C"),
  h("p", { key: "D" }, "D"),
];
let newVnode = [
  h("p", { key: "A" }, "A"), 
  h("p", { key: "C" }, "C"),
  h("p", { key: "B" }, "B"),
  h("p", { key: "D" }, "D"),
  h("p", { key: "E" }, "E"), 
];
diffVNode(oldVnode, newVnode)

效果：

一步一步教你认识Vue3的双端Diff算法

用例三：

let oldVnode = [
  h("p", { key: "B" }, "B"),
  h("p", { key: "E" }, "E"), 
  h("p", { key: "C" }, "C"),
  h("p", { key: "D" }, "D"),
];
let newVnode = [
  h("p", { key: "A" }, "A"), 
  h("p", { key: "C" }, "C"),
];
diffVNode(oldVnode, newVnode)

效果：

一步一步教你认识Vue3的双端Diff算法

Diff总结

到此Diff算法的完整实现就已经完成了。

首先通过双端指针获得新老节点的头尾边界。

通过判断边界我们可以知道是否出现包含的情况，对于这种情况，简单的删除和增加就能完成节点的更新。

如果没有出现包含意味着此时新老节点存在乱序的部分，需要节点最长递增子序列等算法完成节点的更新。

对于复杂情况首先建立新节点乱序部分的key，index映射表，和一个长度等长的数组存储新老节点的映射。

遍历老节点乱序部分，如果当前节点没有在新节点乱序部分出现则删除即可，如果出现了那么通过key，index映射表找到当前节点在新节点乱序部分的位置，并将当前节点在老节点处的下标存到新老节点的映射数组中指定的下标里面。

当老节点乱序部分遍历完成之后，就可以得到新老节点的映射数组，项值为0说明要新增，项值非0 说明当前节点在新老节点中都出现。

通过最长递增子序列找到新老节点的映射数组中不需要移动位置的节点。

开始遍历新老节点的映射数组，如果当前节点的值为0，创建这个节点，如果非0就判断当前节点是否和最长递增子序列存在映射关系，存在说明不需要移动，反之这个节点需要移动。

至此Vue3的双端Diff算法讲解完毕。

Vue3的双端Diff算法完整代码

export function diffVNode(oldV, newV) {
  let i = 0; // 定义初始头指针
  let e1 = oldV.length - 1; // 定义老节点尾指针
  let e2 = newV.length - 1; // 定义老节点尾指针
  while (i <= e1 && i <= e2) {
    // 获取i指针处的新老虚拟节点
    const n1 = oldV[i];
    const n2 = newV[i];
    // 判断i指针处的新老节点是否相同
    if (isSameVNodeType(n1, n2)) {
      // 如果新老节点相同，需要执行patch函数去递归比较n1，n2，看子节点是否更新
      console.log("patch");
    } else {
      break;
    }
    i++; // 如果新老节点相同，指针往前一位
  }
  while (i <= e1 && i <= e2) {
    // 获取i指针处的新老虚拟节点
    const n1 = oldV[e1];
    const n2 = newV[e2];
    // 判断i指针处的新老节点是否相同
    if (isSameVNodeType(n1, n2)) {
      // 如果新老节点相同，需要执行patch函数去递归比较n1，n2，看子节点是否更新
      console.log("patch");
    } else {
      break;
    }
    e1--; // 如果新老节点相同，老虚拟节点尾指针退一位
    e2--; // 如果新老节点相同，新虚拟节点尾指针退一位
  }
  // i 的值等于新老虚拟节点的头边界， e1，e2 的值等于新老虚拟节点的尾边界

  if (i > e1 && i <= e2) {
    // 判断当前元素添加位置
    let insertType = e1 >= 0; // 因为e1的值是递减的，如果小于0了，说明旧节点的头指针指向首项之前了，要往首项之前加即0，反之从e1 + 1项开始加
    let i_place = insertType ? e1 + 1 : 0;

    while (i <= e2) {
      oldV.splice(i_place, 0, newV[i]);
      i_place++;
      i++;
    }
  } else if (i > e2) {
    // 判断当前元素删除是队头减还是队尾减
    let insertType = e2 >= 0; // 因为e2的值是递减的，如果小于0了，说明新节点的头指针指向首项之前了，所以要从头开始删除元素，反之从e2 + 1处开始删除元素
    let i_place = insertType ? e2 + 1 : 0;

    while (i <= e1) {
      oldV.splice(i_place, 1);
      i++;
    }
  } else {
    let s1 = i; // 老节点开始的下标
    let s2 = i; // 新节点开始的下标

    let move = false; // 是否需要移动
    let maxNewIndexSoFar = 0; // 判断是否递增

    const toBePatched = e2 - i + 1; // 新增节点的数量

    let patched = 0; // 记录当前老节点已经在新节点出现了多少次
    //然后出现次数等于toBePatched即新增节点数量之和，则说明后面的老的可以直接删除

    const keyToNewIndexMap = new Map(); // 创建一个映射表存储新节点的key和对应元素的位置
    // 把新节点的key和对应元素位置存到映射中
    for (let i = s2; i <= e2; i++) {
      keyToNewIndexMap.set(newV[i].props.key, i);
    }

    // 建立一个数组用来处理最长子序列
    const newIndexToOldIndexMap = new Array(toBePatched);
    for (let i = 0; i < toBePatched; i++) newIndexToOldIndexMap[i] = 0;
    // 规定如果当前项的值是0说明是新增的节点，初始化一个长度和新增节点一样长的数组，默认里面全部都是新增节点

    // 深拷贝一下oldV，下面会有操作oldV的行为，会改变数组，因此先缓存oldV
    let cpOldV = JSON.parse(JSON.stringify(oldV));

    for (let i = s1; i <= e1; i++) {
      const oVNode = cpOldV[i]; // 老节点当前指针指向的元素节点

      // 判断当前已经处理的节点是否超过新增的节点数，如果超过就直接将后续的移除
      if (patched >= toBePatched) {
        oldV.forEach((item, index) => {
          if (item.props.key == oVNode.props.key) {
            oldV.splice(index, 1);
          }
        });
        continue;
      }

      let newIndex; // 查找老节点元素在不在新节点元素里面，并且在新节点元素的哪个下标问题
      if (oVNode.props.key != null) {
        // 当节点的key存在时，走映射表
        newIndex = keyToNewIndexMap.get(oVNode.props.key); // 在老的节点在不在新节点上面
      } else {
        // 如果当前的key不存在，走循环遍历
        for (let j = s2; j < e2; j++) {
          if (isSameVNodeType(oVNode, newV[j])) {
            newIndex = j;
            break;
          }
        }
      }

      if (newIndex == undefined) {
        oldV.forEach((item, index) => {
          if (item.props.key == oVNode.props.key) {
            oldV.splice(index, 1);
          }
        });
      } else {
        // 初始化一个maxNewIndexSoFar，每一次都和映射值去比较，如果映射值比他大那就直接更新映射值，如果后一个映射值一直都比maxNewIndexSoFar大，说明这个顺序的递增的没有移动
        if (newIndex >= maxNewIndexSoFar) {
          maxNewIndexSoFar = newIndex;
        } else {
          // 反之有顺序发生了移动
          move = true;
        }

        newIndexToOldIndexMap[newIndex - s2] = i + 1; // 0 意味着是新增的节点
        // 如果在新节点中找到了这个节点，则需要调用patch函数去递归比较，因为key相同但是其他属性可能改了，如children等
        // vue3源码中 patch(oVNode, newV[newIndex])

        patched++; // 说明处理完了一个新的节点
      }
    }

    // 获取最长子序列
    const increasingNewIndexSequence = getSequence(newIndexToOldIndexMap) || [];
    let j = increasingNewIndexSequence.length - 1;

    for (let i = toBePatched - 1; i >= 0; i--) {
      // 获取当前位置
      const nextIndex = i + s2; // 因为i是新增节点乱序部分的下标，并不是新节点数组的真实下标，所以这里需要加上头边界s2
      // 获取当前位置在新节点数组的节点
      const nextChild = newV[nextIndex];
      // 获取节点插入位置，如果这个位置没有大于列表长度，说明就是nextIndex + 1，否则加到最后
      const insertEl = nextIndex + 1 < newV.length ? newV[nextIndex + 1] : null;
      if (newIndexToOldIndexMap[i] == 0) {
        if (insertEl) {
          // 当前节点从添加到before_index位置
          let before_index = oldV.findIndex((item) => {
            return item.props.key == insertEl.props.key;
          });
          oldV.splice(before_index, 0, nextChild);
        } else {
          // 当前节点从添加到最后
          oldV.push(nextChild);
        }
      } else {
        // 有元素更新了位置就触发移动逻辑
        if (move) {
          if (j < 0 || i != increasingNewIndexSequence[j]) {
            if (insertEl) {
              // 获取当前节点在老数组中的位置，然后将这个节点移动到目标位置
              let old_index = oldV.findIndex((item) => {
                return item.props.key == nextChild.props.key;
              });
              oldV.splice(old_index, 1);
              let before_index = oldV.findIndex((item) => {
                return item.props.key == insertEl.props.key;
              });
              oldV.splice(before_index, 0, nextChild);
            } else {
              let old_index = oldV.findIndex((item) => {
                return item.props.key == nextChild.props.key;
              });
              oldV.splice(old_index, 1); // 当前节点从添加到最后
              oldV.push(nextChild);
            }
          } else {
            j--;
          }
        }
      }
    }
  }
}

// 转虚拟节点函数
function h(type, props, children) {
  return { type: type, props: props, children: children };
}

// 判断节点是否相同
function isSameVNodeType(n1, n2) {
  return n1.type == n2.type && n1.props.key == n2.props.key;
}

// 最长递增子序列
function getSequence(arr) {
  const p = arr.slice();
  const result = [0];
  let i, j, u, v, c;
  const len = arr.length;
  for (i = 0; i < len; i++) {
    const arrI = arr[i];
    if (arrI !== 0) {
      j = result[result.length - 1];
      if (arr[j] < arrI) {
        p[i] = j;
        result.push(i);
        continue;
      }
      u = 0;
      v = result.length - 1;
      while (u < v) {
        c = (u + v) >> 1;
        if (arr[result[c]] < arrI) {
          u = c + 1;
        } else {
          v = c;
        }
      }
      if (arrI < arr[result[u]]) {
        if (u > 0) {
          p[i] = result[u - 1];
        }
        result[u] = i;
      }
    }
  }
  u = result.length;
  v = result[u - 1];
  while (u-- > 0) {
    result[u] = v;
    v = p[v];
  }
  return result;
}

转载自:https://juejin.cn/post/7240721866548101157