这是 聊diff 的第二篇文章，聊聊vue2的diff思路.思路次要来自 vue-design 我的项目
【第一篇】和面试官聊聊Diff___React
【第二篇】和面试官聊聊Diff___vue2(本文)
【第三篇】和面试官聊聊Diff___Vue3
为了更好的浏览体验,倡议从第一篇看起
我是一名前端的小学生。行文中对某些设计原理了解有误非常欢送大家探讨斧正，谢谢啦！当然有好的倡议也谢谢提出来
（玩笑）
Let's start
vue2_diff
比对流程
本文重视的是patch过程，具体的细节和边界就没有思考。
==另 外 注 意==
- 三篇文章 diff 的解说，为了不便展现 节点复用， 用了
children保留内容，实际上这是不合理的，因为children不同还会递归补丁（patch）- diff也不是vue optimize的全副，只是其中一部分，例如compile时确定节点类型，不同类型 不同的
mount/patch解决形式等等。
Vue2.x的 diff 绝对于 react 更好一些，防止了一些不必要的比对。
基本思路
当初比如说由若干个新老节点（preNodes / nextNodes ）。
应用nextStartIdx、nextEndIdx、nextStartNode、nextEndNode保留 ==新节点== 首尾索引和首尾节点。
应用preStartIdx、preEndIdx、preStartNode、preEndNode保留 ==老节点== 首尾索引和首尾节点。
先将新旧节点首尾一一比对，遇到
undefined跳过- 如果雷同则
前移/后移比对节点（首首雷同，均后移；尾尾雷同，均前移；首尾雷同，新首后移，旧尾前移；尾首雷同）。 - 如果存在 首尾遍历了全副节点， 那么 删除多余节点（状况①）或新增节点（状况②）即可
- 如果雷同则
雷同的都比对结束后，将新节点（
nextNodes）中未比对的每个节点与老节点（preNodes）中未比对节点（是一个key和index对应的map）中所有节点比对- 如果存在雷同，将老节点中相应节点重置为
undefined, 否者在 新生成节点中 增加/删除相应节点。
- 如果存在雷同，将老节点中相应节点重置为
状况①（也可能是首尾/尾首比对），再持续循环， 会有 preStartIdx > preEndIdx, 表明有新增节点，要增加
状况②（也可能是首尾/尾首比对），再持续循环， 会有 nextStartIdx > nextEndIdx, 表明有多余节点，要删除
代码体现：
if(preStartIdx > preEndIdx) { // 有间断多余的新节点需减少 const addStartIndex = nextStartIdx > 0 ? nextStartIdx-1 : 0; let insertIndex = newNodes.findIndex(node => nextNodes[addStartIndex].key === node.key) for(let i = nextStartIdx; i<= nextEndIdx; i++){ newNodes.splice(insertIndex +1, 0, nextNodes[i]) insertIndex++; }}else if(nextStartIdx > nextEndIdx) { //有间断多余的旧节点，需删除(开端开始删除) 123456 | 1256 // const delStartIndex = preStartIdx > 0 ? preEndIdx -1 : 0; let deleteIndex = newNodes.findIndex(node => preNodes[preEndIdx].key === node.key) for(let i=preEndIdx; i>=preStartIdx; i--){ if(preNodes[i] === undefined) continue; newNodes.splice(deleteIndex, 1); deleteIndex--; }}比方有以下节点：
// 旧节点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>"}, {key: "k-7", children: "<span>old7</span>"}, {key: "k-8", children: "<span>old8</span>"},]// 新节点const nextNodes = [ {key: "k-8", children: "<span>8</span>"}, {key: "k-7", children: "<span>7</span>"}, {key: "k-12", children: "<span>12</span>"}, {key: "k-5", children: "<span>5</span>"}, {key: "k-3", children: "<span>3</span>"}, {key: "k-11", children: "<span>11</span>"}, {key: "k-2", children: "<span>2</span>"}, {key: "k-13", children: "<span>13</span>"}, {key: "k-9", children: "<span>9</span>"}, {key: "k-1", children: "<span>1</span>"},]通过补丁diff后,冀望失去后果
能够看到老节点都失去了复用~~
用图来具体实现下面节点变换过程。
图例解说
==留神==： 图中删除插入是我用数组代替节点插入 的操作（ 例如insertbefore），其实失常 节点插入 时，就会检测插入节点是否存在，如果存在是不会插入反复节点的，只会将原来节点调换至新的地位。
例子1
这个例子就是把下面提到的图形解剖一步步出现。一大波图来袭
### 阐明
- 应用
nextStartIdx、nextEndIdx、nextStartNode、nextEndNode保留 ==新节点== 首尾索引和首尾节点。- 应用
preStartIdx、preEndIdx、preStartNode、preEndNode保留 ==老节点== 首尾索引和首尾节点。- 绿色示意新增节点，红色示意删除节点，湖蓝色示意复用节点。
初始状态
preStartIdx = 0；preEndIdx = 7；nextStartIdx = 0；nextEndIdx = 9；
尾首雷同，将旧首节点（k-1）插入到旧尾节点(k-8)前面。且 preStartIdx + 1, nextEndIdx -1
preStartIdx = 1；preEndIdx = 7；nextStartIdx = 0；nextEndIdx = 8；
尾首雷同，将旧尾节点（ k-8）插入到旧首节点(k-2)后面。且 nextStartIdx + 1, preEndIdx -1
preStartIdx = 1；preEndIdx = 6；nextStartIdx = 1；nextEndIdx = 8；
尾首雷同，将旧尾节点（k-7）插入到旧首节点(k-2)后面。且 nextStartIdx + 1, preEndIdx -1
preStartIdx = 1；preEndIdx = 5；nextStartIdx =2；nextEndIdx = 8；
两边(首尾)比对实现，开始两头比对（newNodes 未比对节点与 preNodes 未比对所有节点一一比对），k-12在老节点未比对区间无雷同，减少到k-2后面
preStartIdx = 1；preEndIdx = 5；nextStartIdx = 3；nextEndIdx = 8；
找到 k-5 雷同（复用）,k-5 减少到 k-2 后面,删除原来( newNodes)的 k-5，老节点中 k-5置为undefined
preStartIdx = 1；preEndIdx = 5；nextStartIdx = 4；nextEndIdx = 8；
找到 k-3雷同（复用）,k-3减少到 k-2后面,删除原来( newNodes)的 k-3，老节点中 k-3 置为undefined
preStartIdx = 1；preEndIdx = 5；nextStartIdx = 5；nextEndIdx = 8；k-11未找到雷同节点，k-11 减少到 k-2 后面
preStartIdx = 1；preEndIdx = 5；nextStartIdx = 6；nextEndIdx = 8；
首首节点 k-2 雷同，k-2 减少到 k-2 后面, 删除原来的 k-2
因为undefined会跳过，即preStartIdx = 3；preEndIdx = 5；nextStartIdx = 0；nextEndIdx = 9；k-13 未找到雷同节点，k-13 减少到 k-4 后面
preStartIdx = 3；preEndIdx = 5；nextStartIdx = 8；nextEndIdx = 8；
新节点前后索引相等，k-9 增加到 k-4 后面
满足 nextStartIdx >nextEndIdx 删除多余节点
最初后果
兄弟们，点个赞啊，累死我了，哎~~~(图搞了我两个多小时)
加深了解的例子
这个例子节点为;
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>"}, {key: "k-7", children: "<span>old7</span>"}, {key: "k-8", children: "<span>old8</span>"}, {key: "k-9", children: "<span>old9</span>"},]// /* 旧首==新尾 旧尾==新首 旧尾==新首 首首 旧首==新尾 尾尾*/const nextNodes = [ {key: "k-9", children: "<span>9</span>"}, {key: "k-12", children: "<span>12</span>"}, {key: "k-8", children: "<span>8</span>"}, {key: "k-13", children: "<span>13</span>"}, {key: "k-6", children: "<span>6</span>"}, {key: "k-2", children: "<span>2</span>"}, {key: "k-15", children: "<span>15</span>"}, {key: "k-5", children: "<span>5</span>"}, {key: "k-14", children: "<span>14</span>"}, {key: "k-19", children: "<span>19</span>"}, {key: "k-7", children: "<span>7</span>"}, {key: "k-3", children: "<span>3</span>"}, {key: "k-1", children: "<span>1</span>"},]为什么非凡呢，因为会产生首尾和两头比对穿插进行（其实原本就相互影响），
这个我就不去画图解释了，这个例子为加深了解所用。
代码实现
代码
间接贴代码了
function vue2_diff(){ 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>"}, {key: "k-7", children: "<span>old7</span>"}, {key: "k-8", children: "<span>old8</span>"}, ] const nextNodes = [ {key: "k-8", children: "<span>8</span>"}, {key: "k-7", children: "<span>7</span>"}, {key: "k-12", children: "<span>12</span>"}, {key: "k-5", children: "<span>5</span>"}, {key: "k-3", children: "<span>3</span>"}, {key: "k-11", children: "<span>11</span>"}, {key: "k-2", children: "<span>2</span>"}, {key: "k-13", children: "<span>13</span>"}, {key: "k-9", children: "<span>9</span>"}, {key: "k-1", children: "<span>1</span>"}, ] let preStartIdx = 0; let nextStartIdx = 0; let preStartNode = preNodes[0]; let nextStartNode = nextNodes[0]; let preEndIdx = preNodes.length - 1; let nextEndIdx = nextNodes.length - 1; let preEndNode = preNodes[preEndIdx]; let nextEndNode = nextNodes[nextEndIdx]; const newNodes = JSON.parse(JSON.stringify(preNodes)); function isSameNode(node1, node2){ return node1.key === node2.key; } while(preStartIdx <= preEndIdx && nextStartIdx <= nextEndIdx){ if(preStartNode === undefined){ console.log('undefined: ', preStartNode); preStartNode = preNodes[++preStartIdx]; }else if(preEndNode === undefined){ console.log('undefined: ', preEndNode); preEndNode = preNodes[--preEndIdx] }else if(isSameNode(preStartNode, nextStartNode)){ // 新旧首首雷同 preStartNode = preNodes[++preStartIdx]; nextStartNode = nextNodes[++nextStartIdx]; }else if(isSameNode(preEndNode, nextEndNode)) { // 新旧尾尾雷同 preEndNode = preNodes[--preEndIdx]; nextEndNode = nextNodes[--nextEndIdx]; }else if(isSameNode(preStartNode, nextEndNode)) { //执行 将旧首节点插入到旧尾节点前面 const insertPos = newNodes.findIndex(node => node.key === preEndNode.key); const deletePos = newNodes.findIndex(node => node.key === preStartNode.key); // 增加 newNodes.splice(insertPos+1, 0, preStartNode); // 删除 const delIndex = insertPos < deletePos ? deletePos + 1 : deletePos; newNodes.splice(delIndex, 1); preStartNode = preNodes[++preStartIdx]; nextEndNode = nextNodes[--nextEndIdx]; }else if(isSameNode(preEndNode, nextStartNode)) { //执行 将旧尾节点插入（insertBefore）到旧首节点后面 const insertPos = newNodes.findIndex(node => node.key === preStartNode.key); const deletePos = newNodes.findIndex(node => node.key === preEndNode.key); // 增加 newNodes.splice(insertPos, 0, preEndNode); // 删除 const delIndex = insertPos < deletePos ? deletePos + 1 : deletePos; newNodes.splice(delIndex, 1); nextStartNode = nextNodes[++nextStartIdx]; preEndNode = preNodes[--preEndIdx]; }else { const oldKeyInIndex = {}; for(let i=preStartIdx; i<=preEndIdx; i++){ if(!preNodes[i]) continue; // 解决undefined状况 oldKeyInIndex[preNodes[i].key] = i; } const moveNodeIndex = oldKeyInIndex[nextStartNode.key] if(moveNodeIndex !== undefined){ //找到即 insertBefore,将以后节点插入到旧开始节点在newNodes的地位的前面 const insertPos = newNodes.findIndex(node => node.key === preStartNode.key); const deletePos = newNodes.findIndex(node => node.key === preNodes[moveNodeIndex].key); newNodes.splice(insertPos, 0, preNodes[moveNodeIndex]); newNodes.splice(deletePos+1, 1); preNodes[moveNodeIndex] = undefined; }else {//增加 const insertPos = newNodes.findIndex(node => preStartNode.key === node.key); newNodes.splice(insertPos, 0, nextStartNode); } nextStartNode = nextNodes[++nextStartIdx]; } } if(preStartIdx > preEndIdx) { // 有间断多余的新节点需减少 const addStartIndex = nextStartIdx > 0 ? nextStartIdx-1 : 0; let insertIndex = newNodes.findIndex(node => nextNodes[addStartIndex].key === node.key) for(let i = nextStartIdx; i<= nextEndIdx; i++){ newNodes.splice(insertIndex +1, 0, nextNodes[i]) insertIndex++; } }else if(nextStartIdx > nextEndIdx) { //有间断多余的旧节点，需删除(开端开始删除) 123456 | 1256 // const delStartIndex = preStartIdx > 0 ? preEndIdx -1 : 0; let deleteIndex = newNodes.findIndex(node => preNodes[preEndIdx].key === node.key) for(let i=preEndIdx; i>=preStartIdx; i--){ if(preNodes[i] === undefined) continue; newNodes.splice(deleteIndex, 1); deleteIndex--; } } console.log('vue2 diff: ', newNodes); }总结
本文中例子只是为了更好了解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 ⇲
以上。