这是聊diff 的第三篇文章，聊聊vue3的diff思路.思路次要来自 vue-design 我的项目

【第一篇】和面试官聊聊Diff___React
【第二篇】和面试官聊聊Diff___vue2
【第三篇】和面试官聊聊Diff___Vue3(本文)

为了更好的浏览体验,倡议从第一篇看起
我是一名前端的小学生。行文中对某些设计原理了解有误非常欢送大家探讨斧正，谢谢啦！当然有好的倡议也谢谢提出来

（玩笑）

Let's start

Vue3_diff

过程剖析

本文重视的是patch过程，具体的细节和边界就没有思考。

==另外注意==
三篇文章 diff 的解说，为了不便展现节点复用，用了 children 保留内容，实际上这是不合理的，因为children不同还会递归补丁（patch）
diff也不是vue optimize的全副，只是其中一部分，例如compile时确定节点类型，不同类型不同的 mount/patch 解决形式等等。
Vue2.x的 diff 绝对于 react 更好一些，防止了一些不必要的比对。

我先假如有如下节点, key 是 Vnode 的 key, children 代表该节点的内容

// 以前的节点const preNodes = [  {key: "k-1", children: "<span>old1</span>"},  {key: "k-2", children: "<span>old2</span>"},  {key: "k-3", children: "<span>old3</span>"},  {key: "k-4", children: "<span>old4</span>"},  {key: "k-5", children: "<span>old5</span>"},  {key: "k-6", children: "<span>old6</span>"},]// 新节点，最初更新的后果const nextNodes = [  {key: "k-11", children: "<span>11</span>"},  {key: "k-0", children: "<span>0</span>"},  {key: "k-5", children: "<span>5</span>"},  {key: "k-13", children: "<span>13</span>"},  {key: "k-1", children: "<span>1</span>"},  {key: "k-7", children: "<span>7</span>"},  {key: "k-16", children: "<span>16</span>"},  {key: "k-3", children: "<span>3</span>"},  {key: "k-15", children: "<span>15</span>"},  {key: "k-17", children: "<span>7</span>"},  {key: "k-4", children: "<span>4</span>"},  {key: "k-6", children: "<span>6</span>"}]

diff 是基于新旧的 diff, 先要明确这个大前提，如果刚刚开始没有节点，则会先 mount 而不会 patch。
最初冀望的后果（老节点都失去了复用）

另外新产生节点（newNodes）是基于老节点的，于是

// 最终的节点数据,因为最终的节点是基于老节点的，这里做个模仿let newNodes = JSON.parse(JSON.stringify(preNodes));

preNodes: 老节点；
nextNodes：新节点；
newNodes: 新产生节点，最初用于渲染为实在dom.其实vue2晚期就是先齐全产生新节点，最初再渲染为实在dom.前面版本变为一次（patch）优化遍历时就更新相应的Dom.
中心思想提炼：从老节点中找到与新节点中key雷同的节点，进行复用。

具体思路：

1. 先找两端雷同的节点（key雷同），找到即再往两头找。

如图，J 从结尾找， preEndIndex 和 nextEndIndex 别离对应老节点和新节点的开端索引。找到就减少 J 或者缩小 preEndIndex 和 nextEndIndex。

代码如下

let j = 0;let preEndIndex = preNodes.length - 1;let nextEndIndex = nextNodes.length - 1;let preVNode = preNodes[j];let nextVNode = nextNodes[j];while(preVNode.key === nextVNode.key){  j++;  preVNode = preNodes[j];  nextVNode = nextNodes[j];}preVNode = preNodes[preEndIndex];nextVNode = nextNodes[nextEndIndex];while(preVNode.key === nextVNode.key){  preVNode = preNodes[--preEndIndex];  nextVNode = nextNodes[--nextEndIndex];}

思考到一种状况

下面的状况会呈现老节点比对完了，新节点还存在，那么最初会造成 J > preEndIndex[状况1],同理,老节点未比对完，新节点曾经比对完,那么会呈现 J > nextEndIdnex[状况2].
针对这两种状况，

都要防止循环，引入label解决。
另外，状况1须要（从newNodes中）删除多余的节点，状况2须要（向newNodes）减少新节点中未遍历的节点。

于是把原来代码改一下：

// ....outer: {  while(preVNode.key === nextVNode.key){    j++;    if(j> preEndIndex || j > newEndIndex) {      break outer;    }    preVNode = preNodes[j];    nextVNode = nextNodes[j];  }  preVNode = preNodes[preEndIndex];  nextVNode = nextNodes[nextEndIndex];  while(preVNode.key === nextVNode.key){    if(j> preEndIndex || j > nextEndIndex) {      break outer;    }    preVNode = preNodes[--preEndIndex];    nextVNode = nextNodes[--nextEndIndex];  }}if(j > preEndIndex) {  // 老节点遍历完了，新节点还存在，将新节点放入。  for(let i = j; i< nextEndIndex; i++){    const addedNode = nextNodes[i];    // 留神： 框架外部是利用appendchild 更新dom.    newNodes.splice(i,0,addedNode);  }}else if(j > nextEndIndex){  // 新节点遍历完了，老节点还存在，将老节点删除。  const deleteLen = preEndIndex - j;  // 留神： 框架外部是重写removeChild 更新dom.  newNodes.splice(i,deleteLen);}else {  //均还有不同节点时 }

大多数状况就像刚开始的例子一样： 两头都还存在不同的节点，须要挪动和新增。这个状况是patch次要解决的中央,代码写在下面的 else 外面。

具体思路是怎么呢，

2. 产生一个老节点可复用节点的映射数组

学生成一个每项为 -1 的数组noPatchedIndex，长度为新节点未遍历的节点长度。

遍历未比对的老节点和新节点（这里有个优化细节：新节点不必遍历，因为构造的特殊性，间接生成key 对应 index 的对象 keyInIndex 例如{k-1: 0, k-2: 1, ...}，前面间接取）。

未比对老节点中如果存在未比对新节点雷同的节点那么在 noPatchedIndex 相应地位保存起来它在老节点中的索引。

另外判断时，新节点中不存在还需删除老节点，并且得出是否须要挪动元素（索引数组 noPatchedIndex 中存在非递增排序，即数组中以后项不能大于之后的项）

大略这个意思

新生成节点。k-2在新节点(nextNodes)中不存在，所以被删除。

3. 解决须要挪动的状况（复用节点解决）

大略有如下步骤：

①找出 noPatchedIndex 最大递增子序列 lisArr索引数组
②将未比对新节点与顺次插入到新节点。

针对①，这里有一个函数 lis，

lis([3,1,5,4,2]) //[1, 4] | 1,2 为最大递增子序列lis([1,2,3]) //[0, 1, 2] | 1,2,3 为最大递增子序列lis([0,-1,8,6,10,7]) //[1, 3, 5] | -1,6,7 为最大递增子序列

lis 具体实现请参考我的另一篇文章 [算法篇---寻找最大递增子序列]()

于是有

针对②，为什么要找最大递增子序列 lisArr呢，因为对于 lisArr 外面的项程序是不必动的，新节点的未比对节点只须要在这些项前后插入即可。
具体实现就是遍历noPatchedIndex 与 lisArr ：

noPatchedIndex 项等于 -1,示意，老节点中不存在的项，须要新增
noPatchedIndex 索引与 lisArr 不相等时，须要挪动老节点到响应的地位
noPatchedIndex 索引与 lisArr 相等时，不做操作。

须要留神：遍历都是从后向前遍历，目标是避免数组长度变换影响索引值进而影响节点取值，插入，删除。

为了直观的了解，上面来一波操作图：i 与 j 为 noPatchedIndex与 lisArr

删除的为红色，新增的为绿色，复用的节点为灰色；
节点复用插入时调用的是DOM API [insertBefore]()这个是先回增加该节点如果存在反复是会删除原有节点的；
插入地位为节点 nextNodes[nopatchedIndex[lisArr[j]]] 对应在 oldNodes 的地位

1)i =10, j = 2 ; 节点 k-4 复用

2)i=9, j=1

3)i=8, j=1. 新增

4)i=7,j=1. k-3复用

5)i=6, j=0

6)i=5, j=0

7)i=4, j=0.插入（波及到减少和删除），这里因为插入的是老节点，而原节点（2）在插入地位（0）前面，所以新增之后删除的索引地位要减一（代码中会有体现）

8)i=3,j=0新增

9)i=2, j=0.插入（波及到减少和删除），这里因为插入的是老节点，而原节点（9）在插入地位（0）前面，所以新增之后删除的索引地位要减一（代码中会有体现）

10)i=1,j=0

11)i=0, j=0,新增

12) i= -1, 循环完结。

最初后果来看，k-5, k-1, k-2, k-4, k-6 失去了复用, 那么k-2 到哪去了呢，新节点nextNodes不含该节点天然在挪动（move）前就删除了！后面提到了。
至此，diff过程完结了置信其实看图也能够看明确

哎，画图太累了，当初真心对那么文章配有图解说的博主瑞思拜（respect!!!）。absolute!!!

最初奉上全副代码。

全副代码

// 老节点const preNodes = [  {key: "k-1", children: "<span>old1</span>"},  {key: "k-2", children: "<span>old2</span>"},  {key: "k-3", children: "<span>old3</span>"},  {key: "k-4", children: "<span>old4</span>"},  {key: "k-5", children: "<span>old5</span>"},  {key: "k-6", children: "<span>old6</span>"},]// 新节点const nextNodes = [  {key: "k-11", children: "<span>11</span>"},  {key: "k-0", children: "<span>0</span>"},  {key: "k-5", children: "<span>5</span>"},  {key: "k-13", children: "<span>13</span>"},  {key: "k-1", children: "<span>1</span>"},  {key: "k-7", children: "<span>7</span>"},  {key: "k-6", children: "<span>6</span>"},  {key: "k-3", children: "<span>3</span>"},  {key: "k-15", children: "<span>15</span>"},  {key: "k-17", children: "<span>7</span>"},  {key: "k-4", children: "<span>4</span>"},  {key: "k-6", children: "<span>6</span>"}]// 最终的节点数据,因为最终的节点是基于老节点的，这里做个模仿let newNodes = JSON.parse(JSON.stringify(preNodes));//两个都从右边开始比对的索引let j = 0;let preEndIndex = preNodes.length - 1;let nextEndIndex = nextNodes.length - 1;let preVNode = preNodes[j];let nextVNode = nextNodes[j];outer: {  while(preVNode.key === nextVNode.key){    j++;    if(j> preEndIndex || j > newEndIndex) {      break outer;    }    preVNode = preNodes[j];    nextVNode = nextNodes[j];  }  preVNode = preNodes[preEndIndex];  nextVNode = nextNodes[nextEndIndex];  while(preVNode.key === nextVNode.key){    if(j> preEndIndex || j > nextEndIndex) {      break outer;    }    preVNode = preNodes[--preEndIndex];    nextVNode = nextNodes[--nextEndIndex];  }}if(j > preEndIndex) {  // 老节点遍历完了，新节点还存在，将新节点放入。  for(let i = j; i< nextEndIndex; i++){    const addedNode = nextNodes[i];    // 留神： 框架外部是利用appendchild 更新dom.    newNodes.splice(i,0,addedNode);  }}else if(j > nextEndIndex){  // 新节点遍历完了，老节点还存在，将老节点删除。  const deleteLen = preEndIndex - j;  // 留神： 框架外部是重写removeChild 更新dom.  newNodes.splice(i,deleteLen);}else {  //保留是否须要挪动  let moved = false;  const preStart = j;  const nextStart = j;  let pos = 0;  //保留新节点key-index 的map, 防止屡次循环  const keyInIndex = {}; //{ k-1: 1, k-2: 2, k-3:3,...  }  //新节点未比对的节点长度  const newLength = nextEndIndex - nextStart + 1;  for(let i = nextStart; i< newLength; i++) {    keyInIndex[nextNodes[i].key] = i  }  const oldLength = preEndIndex - preStart + 1;  //避免老节点比新节点多时，删除已找到的反复的节点  let patched = 0;  // 产生新节点能复用的老节点的索引数组  const noPatchedIndex = Array(newLength).fill(-1); //-1状态保留  for(let i = preStart; i< oldLength; i++) {    const preNode = preNodes[i];    if(patched <= nextEndIndex) {      //保留老节点key在新节点中对应的index      const k = keyInIndex[preNode.key];      if(typeof k !== 'undefined'){        let idx = k - preStart;        noPatchedIndex[idx] = i;        patched++;        // 筛选出须要往前调换的元素        if(k < pos) moved = true;        else pos = k;      }else {        // 动静查找删除项索引        const deleteIndex = newNodes.findIndex(node => node.key === preNodes[i].key)        newNodes.splice(deleteIndex,1);      }    }else {      newNodes.splice(i,1)    }  }    //解决须要挪动的状况  if(moved){    const newNodesCopy = JSON.parse(JSON.stringify(newNodes))    //最大递增子序列索引    const lisArr = lis(noPatchedIndex);    let j = lisArr.length - 1;    //遍历新节点中未比对的节点，从前面遍历，避免更新过程index非预期变动。    for(let i=newLength - 1; i>=0; i--){      const current = noPatchedIndex[i];      // 更新的理论地位      const pos = i+nextStart;      let insertPos = newNodes.findIndex(node => node.key === nextNodes[nextStart+lisArr[j]].key);      if(current === -1){// -1即为新增的状况        // 留神 [1,2,3].splice(0,4) => [4,1,2,3]        newNodes.splice(insertPos+1, 0, nextNodes[pos]);        continue;      }else if(lisArr[j] !== i) {//能够复用非递增节点的状况        /*          insertBefore 作用： 如果给定的子节点是对文档中现有节点的援用，insertBefore() 会将其从以后地位挪动到新地位          以下的操作就是实现 insertBefore 办法。        */        //挪动元素在新节点的地位        let oldPos = newNodes.findIndex(node => node.key === nextNodes[pos].key);        //须要删除插入的节点对应原来的节点        //新节点中插入老节点对应的地位        newNodes.splice(insertPos+1, 0, newNodes[oldPos]);        // 判断插入节点的地位在被插入地位的后面还是前面，如果是前面就加1        oldPos = insertPos > oldPos ? oldPos : oldPos+1;        newNodes.splice(oldPos, 1)      }else {        j--;      }    }  }}console.log('newNodes: ', newNodes);// 寻找最大递增子序列 索引// https://en.wikipedia.org/wiki/Longest_increasing_subsequence/*  [3,1,5,4,2] => [1,2]*/function lis(arr) {  const p = arr.slice();  const result = [0]; // 索引数组  let i;  let j;  let u;  let v;  let 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;      //result长度大于1时      while (u < v) {        // 取中位数        c = ((u + v) / 2) | 0;        if (arr[result[c]] < arrI) {          u = c + 1;        } else {          v = c; //result中位数大于等于 以后项。v取中位数        }      }      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;}

总结

本文中例子只是为了更好了解diff思路, patch过程与真实情况还有些差别

反复节点问题。新老节点有反复节点时，本文diff函数没解决这种状况。
仅是用数组模仿了Vnode,实在的Vnode 不止 key和children,还有更多的参数
比对雷同节点时，仅比对了 key, 实在其实还波及到 class（类名）、attrs（属性值）、孩子节点（递归）等属性比对;另外下面的children也要比对若不同也要递归遍历
插入、删除、增加节点我用的数组。其实应该用 insertbefore 、 delete、add。这些办法均是独自封装不能采纳绝对应的 Dom Api,因为 vue 不止用在浏览器环境。
...

Vue@3.2⇲ 曾经进去了，React@18也快了，哎，框架学不完。还是多看看不变的货色吧（js, 设计模式，数据结构，算法...）
哎哎哎，，同志，看完怎么不点赞，别看他人就说你呢，你几个意思？

参考

站在他人肩膀能看的更远。

【举荐】vue-design
【掘金小册】分析Vue.js外部运行机制
【Vue patch源码地址】vue-next ⇲

另外，大佬们正在翻译 vue3的英文文档 docs-next-zh-cn

以上。