前言
diff 算法是一种通过同层的树节点进行比拟的高效算法，防止了对树进行逐层搜寻遍历，所以工夫复杂度只有 O(n)。diff 算法的在很多场景下都有利用，例如在 vue 虚构 dom 渲染成实在 dom 的新旧 VNode 节点比拟更新时，就用到了该算法。
diff 算法有两个比较显著的特点：比拟只会在同层级进行, 不会跨层级比拟。
在 diff 比拟的过程中，循环从两边向两头收拢。
Vue2的diff算法外围
基本原理
- 首先进行新老节点头尾比照，头与头、尾与尾比照，寻找未挪动的节点。
- 新老节点头尾比照完后，进行穿插比照，头与尾、尾与头比照，这一步即寻找挪动后可复用的节点。
- 而后在残余新老结点中比照寻找可复用节点，创立一个老节点keyToIndex的哈希表map记录 key，而后持续遍历新节点索引通过 key 查找能够复用的旧的节点。
- 节点遍历实现后，通过新老索引，进行移除多余老节点或者减少新节点的操作。
diff流程
应用具体例子来进行剖析逻辑，如图所示为新老节点old与new的节点。
第一步：初始化
let oldStartIdx = 0 // 老vnode遍历的开始下标let newStartIdx = 0 // 新vnode遍历的开始下标let oldEndIdx = oldCh.length - 1 // 老vnode 列表长度let oldStartVnode = oldCh[0] // 老vnode列表第一个子元素let oldEndVnode = oldCh[oldEndIdx] // 老vnode列表最初一个子元素let newEndIdx = newCh.length - 1 // 新vnode列表长度let newStartVnode = newCh[0] // 新vnode列表第一个子元素let newEndVnode = newCh[newEndIdx] // 新vnode列表最初一个子元素通过第一步之后，咱们初始的新旧节点VNode节点如下图所示：
第二步：循环遍历节点
循环过程中首先对新老 VNode 节点的头尾进行比拟，寻找雷同节点，如果有雷同节点满足 sameVnode（能够复用的雷同节点） 则间接进行 patchVnode (该办法进行节点复用解决)，并且依据具体情景，挪动新老节点的 VNode 索引，以便进入下一次循环解决，一共有 2 * 2 = 4 种情景。
- 情景1：当新老 VNode 节点的 start 满足 sameVnode 时，间接 patchVnode 即可，同时新老 VNode 节点的开始索引都加 1。
if (sameVnode(oldStartVnode, newStartVnode)) {patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)oldStartVnode = oldCh[++oldStartIdx]newStartVnode = newCh[++newStartIdx]}- 情景2：当新老 VNode 节点的 end 满足 sameVnode 时，同样间接 patchVnode 即可，同时新老 VNode 节点的完结索引都减 1。
else if (sameVnode(oldEndVnode, newEndVnode)) {patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx)oldEndVnode = oldCh[--oldEndIdx]newEndVnode = newCh[--newEndIdx]}- 情景3：当老 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]}- 情景4：当老 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];}- 都不满足：通过查找当时建设好的以旧的 VNode 为 key 值，对应 index 序列为 value 值的哈希表。从这个哈希表中找到与 newStartVnode 统一 key 的旧的 VNode 节点，如果两者满足 sameVnode 的条件，在进行 patchVnode 的同时会将这个实在 dom 挪动到 oldStartVnode 对应的实在 dom 的后面；如果没有找到，则阐明以后索引下的新的 VNode 节点在旧的 VNode 队列中不存在，无奈进行节点的复用，那么就只能调用 createElm 创立一个新的 dom 节点放到以后 newStartIdx 的地位。
else { // 创立一个 { key: oldVnode } 的映射表 if (isUndef(oldKeyToIdx)) oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx) // 查找这个表，如果 newStartVnode 中有 key，则间接去映射表中查；否则通过 findIdxInOld 查 idxInOld = isDef(newStartVnode.key) ? oldKeyToIdx[newStartVnode.key] : findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx) if (isUndef(idxInOld)) { // 如果没找到，那么新建节点 createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx)} else { vnodeToMove = oldCh[idxInOld] // 雷同节点的话 if (sameVnode(vnodeToMove, newStartVnode)) { // 进行patch patchVnode(vnodeToMove, newStartVnode, insertedVnodeQueue) // 因为该地位对应的节点处理完毕，因而，将该地位设置为 undefined，后续指针遍历进来后能够间接跳过遍历下一个 oldCh[idxInOld] = undefined // 后挪动对应的实在DOM canMove && nodeOps.insertBefore(parentElm, vnodeToMove.elm, oldStartVnode.elm) } else { // 不是雷同节点的话，那么须要新建节点 createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx) }} newStartVnode = newCh[++newStartIdx]}实例流程
- 再来看咱们的实例，第一次循环后，找到了旧节点的开端和新节点的结尾(都是 D)雷同，于是间接复用 D 节点作为 diff 后创立的第一个实在节点。同时旧节点的 endIndex 挪动到了 C，新节点的 startIndex 挪动到了 C。
- 紧接着开始第二次循环，第二次循环后，同样是旧节点的开端和新节点的结尾(都是 C)雷同，同理，diff 后创立了 C 的实在节点插入到第一次创立的 B 节点前面。同时旧节点的 endIndex 挪动到了 B，新节点的 startIndex 挪动到了 E。
- 接下来第三次循环中，发现 patchVnode 的 4 种情景都不合乎，于是在旧节点队列中查找以后的新节点 E，后果发现没有找到，这时候只能间接创立新的实在节点 E，插入到第二次创立的 C 节点之后。同时新节点的 startIndex 挪动到了 A。旧节点的 startIndex 和 endIndex 都放弃不动。
- 第四次循环中，发现了新旧节点的结尾(都是 A)雷同，于是 diff 后创立了 A 的实在节点，插入到前一次创立的 E 节点前面。同时旧节点的 startIndex 挪动到了 B，新节点的 startIndex 挪动到了 B。
- 第五次循环中，情景同第四次循环一样，因而 diff 后创立了 B 实在节点 插入到前一次创立的 A 节点前面。同时旧节点的 startIndex 挪动到了 C，新节点的 startIndex 挪动到了 F。
这时候发现新节点的 startIndex 曾经大于 endIndex 了。不再满足循环的条件了。因而完结循环，接下来走前面的逻辑。
第三步：新增或删除节点
当 while 循环完结后，依据新老节点的数目不同，做相应的节点增加或者删除。若新节点数目大于老节点则须要把多进去的节点创立进去退出到实在 dom 中，反之若老节点数目大于新节点则须要把多进去的老节点从实在 dom 中删除。至此整个 diff 过程就曾经全副实现了。
// oldStartIdx > oldEndIdx 阐明老的 vnode 先遍历完 if (oldStartIdx > oldEndIdx) {// 就增加从 newStartIdx 到 newEndIdx 之间的节点refElm = isUndef(newCh[newEndIdx + 1]) ? null : newCh[newEndIdx + 1].elmaddVnodes(parentElm, refElm, newCh, newStartIdx, newEndIdx, insertedVnodeQueue)// 否则就阐明新的 vnode 先遍历完} else if (newStartIdx > newEndIdx) {// 就删除掉老的 vnode 里没有遍历的节点removeVnodes(oldCh, oldStartIdx, oldEndIdx)}}再回过头看咱们的实例，新节点的数目大于旧节点，须要创立 newStartIdx 和 newEndIdx 之间的所有节点。在咱们的实例中就是节点 F，因而间接创立 F 节点对应的实在节点放到 B 节点前面即可。
至此，vue2整个 Diff 流程的外围逻辑源码到这就完结了，再来看一下 Vue 3 里做了哪些扭转吧。
Vue3的diff算法外围
基本原理
- 首先进行新老节点头尾比照，头与头、尾与尾比照，寻找未挪动的节点。
- 而后创立一个新节点在旧节点中的地位的映射表，这个映射表的元素如果不为空，代表可复用。
- 而后依据这个映射表计算出最长递增子序列，这个序列中的结点代表能够原地复用。之后挪动剩下的新结点到正确的地位即递增序列的间隙中。
diff流程
应用具体例子来进行剖析逻辑，如图所示为新老节点old与new的节点。
第一步：初始化
let i = 0; // 新老vnode遍历的开始下标const l2 = c2.length; // 新vnode的遍历长度let e1 = c1.length - 1; // 老vnode的开端下标let e2 = l2 - 1; // 新vnode的开端下标通过第一步之后，咱们初始的新旧节点VNode节点如下图所示：
第二步：头部节点比照
首先对新老 VNode 节点的头部开始进行比拟，寻找雷同节点，如果有雷同节点满足 sameVnode（能够复用的雷同节点）则间接进行 patch (该办法进行节点复用解决)。
// 1. sync from start// (a b) c// (a b) d ewhile (i <= e1 && i <= e2) {const prevChild = c1[i];const nextChild = c2[i];// 如果不是雷同节点，遍历终止if (!isSameVNodeType(prevChild, nextChild)) {break;}// 是雷同节点，持续往后遍历，新老节点开端索引加一patch(prevChild, nextChild, container, parentAnchor, parentComponent);i++;}如图所示，来看咱们的实例，经验头部节点遍历后，找到了旧节点的头部和新节点的头部(都是a、b)雷同，遍历实现后旧节点挪动到了c，新节点的挪动到了f。
第三步：尾部节点比照
首先对新老 VNode 节点的尾部开始进行比拟，寻找雷同节点，如果有雷同节点满足 sameVnode（能够复用的雷同节点）则间接进行 patch (该办法进行节点复用解决)。
// 2. sync from end// a (b c)// d e (b c)while (i <= e1 && i <= e2) {// 从右向左取值const prevChild = c1[e1];const nextChild = c2[e2];// 如果不是雷同节点，遍历终止if (!isSameVNodeType(prevChild, nextChild)) {break;}// 是雷同节点，持续往后遍历，新老节点开端索引减一patch(prevChild, nextChild, container, parentAnchor, parentComponent);e1--;e2--;}如图所示，来看咱们的实例，经验头部节点遍历后，找到了旧节点的尾部和新节点的尾部(都是g)雷同，遍历实现后旧节点挪动到了f，新节点的挪动到了h。
第四步：残余节点比照
遍历完头尾节点后存在两种非凡状况。
- 老节点先遍历完，新节点还残余：创立残余新节点。
// 老节点先遍历完，新节点还残余// (a b)// (a b) c// i = 2, e1 = 1, e2 = 2// (a b)// c (a b)// i = 0, e1 = -1, e2 = 0if (i > e1 && i <= e2) {// 如果是这种状况的话就阐明 e2 也就是新节点的数量大于旧节点的数量// 也就是说新增了 vnode// 应该循环 c2// 锚点的计算：新的节点有可能须要增加到尾部，也可能增加到头部，所以须要指定增加的问题// 要增加的地位是以后的地位(e2 开始)+1// 因为对于往左侧增加的话，应该获取到 c2 的第一个元素// 所以咱们须要从 e2 + 1 取到锚点的地位const nextPos = e2 + 1;const anchor = nextPos < l2 ? c2[nextPos].el : parentAnchor;while (i <= e2) {patch(null, c2[i], container, anchor, parentComponent);i++;}}- 新节点先遍历完，老节点还残余：删除残余旧节点。
// 新节点先遍历完，老节点还残余// (a b) c// (a b)// i = 2, e1 = 2, e2 = 1// a (b c)// (b c)// i = 0, e1 = 0, e2 = -1else if (i > e2 && i <= e1) {// 这种状况的话阐明新节点的数量是小于旧节点的数量的// 那么咱们就须要把多余的while (i <= e1) {hostRemove(c1[i].el);i++;}}- 新老节点都有残余：在新老残余节点中寻找可复用节点。
创立新节点残余节点对应的映射表keyToNewIndexMap。
// 左右两边都比对完了，而后剩下的就是两头部位程序变动的// 例如上面的状况// a,b,[c,d,e,f],g// a,b,[f,c,d,e,h],glet s1 = i; // 2let s2 = i; // 2const keyToNewIndexMap = new Map(); // 新节点残余节点映射哈希表let moved = false; // 挪动标识let maxNewIndexSoFar = 0; // 判断是否须要挪动// 先把 key 和 newIndex 绑定好，不便后续基于 key 找到 newIndex// 工夫复杂度是 O(1)for (let i = s2; i <= e2; i++) { // i= 2-6const nextChild = c2[i];keyToNewIndexMap.set(nextChild.key, i);}// keyToNewIndexMap = { f: 2, c: 3, d: 4, e: 5, h: 6 }
再创立一个newIndexToOldIndexMap数组，用来存储新节点数组中的残余节点在旧节点数组上的索引，前面将应用它计算出一个最长递增子序列，并初始化数组为0。
// 须要解决新节点的数量const toBePatched = e2 - s2 + 1; // 6 - 2 + 1 = 5let patched = 0; // 记录新老节点都有的数量// 初始化 从新的index映射为老的index// 创立数组的时候给定数组的长度，这个是性能最快的写法const newIndexToOldIndexMap = new Array(toBePatched);// 初始化为 0 , 前面解决的时候 如果发现是 0 的话，那么就阐明新值在老的外面不存在for (let i = 0; i < toBePatched; i++) newIndexToOldIndexMap[i] = 0;// [0, 0, 0, 0, 0]- 遍历老节点，存储新节点数组中的残余节点在旧节点数组上的索引，后果如下图所示。
// 遍历老节点// 1. 须要找出老节点有，而新节点没有的 -> 须要把这个节点删除掉// 2. 新老节点都有的，—> 须要 patch// 老节点 => [c,d,e,f]// 新节点残余索引 keyToNewIndexMap = { f: 2, c: 3, d: 4, e: 5, h: 6 }for (i = s1; i <= e1; i++) {const prevChild = c1[i];// 如果新老节点都有的数量大于新节点的数量的话，那么这里在解决老节点的时候就间接删除即可if (patched >= toBePatched) {hostRemove(prevChild.el);continue;}let newIndex; // 老节点在新节点的索引if (prevChild.key != null) {// 这里就能够通过key疾速的查找了， 看看在新的外面这个节点存在不存在// 工夫复杂度O(1)newIndex = keyToNewIndexMap.get(prevChild.key);} else {// 如果没key 的话，那么只能是遍历所有的新节点来确定以后节点存在不存在了// 工夫复杂度O(n)for (let j = s2; j <= e2; j++) {if (isSameVNodeType(prevChild, c2[j])) {newIndex = j;break;}}}// 因为有可能 nextIndex 的值为0（0也是正常值）// 所以须要通过值是不是 undefined 或者 null 来判断if (newIndex === undefined) {// 以后节点的key 不存在于 newChildren 中，须要把以后节点给删除掉hostRemove(prevChild.el);} else {// 老节点 => [c,d,e,f]// 新节点残余索引 keyToNewIndexMap = { f: 2, c: 3, d: 4, e: 5, h: 6 }// 老节点在新节点中的索引newIndex: [3,4,5,2]// i + 1 是因为 i 有可能是0 (0 的话会被认为新节点在老的节点中不存在)newIndexToOldIndexMap[newIndex - s2] = i + 1;// newIndexToOldIndexMap = [6, 3, 4, 5, 0]// 来确定两头的节点是不是须要挪动// 新的 newIndex 如果始终是升序的话，那么就阐明没有挪动// 所以咱们能够记录最初一个节点在新的外面的索引，而后看看是不是升序// 不是升序的话，咱们就能够确定节点挪动过了if (newIndex >= maxNewIndexSoFar) {maxNewIndexSoFar = newIndex;} else {moved = true;}patch(prevChild, c2[newIndex], container, null, parentComponent); // 持续递归diffpatched++; // 记录新老节点都有的数量}}- 计算newIndexToOldIndexMap数组，失去最长增长子序列。
// 利用最长递增子序列来优化挪动逻辑// 因为元素是升序的话，那么这些元素就是不须要挪动的// 而咱们就能够通过最长递增子序列来获取到升序的列表// 在挪动的时候咱们去比照这个列表，如果比照上的话，就阐明以后元素不须要挪动// 通过 moved 来进行优化，如果没有挪动过的话 那么就不须要执行算法// getSequence 返回的是 newIndexToOldIndexMap 的索引值// 所以前面咱们能够间接遍历索引值来解决，也就是间接应用 toBePatched 即可const increasingNewIndexSequence = moved? getSequence(newIndexToOldIndexMap): [];// increasingNewIndexSequence = [1,2,3]/*最长增长子序列办法贪婪加二分获取最长序列依据前驱序列失去正确索引序列*/function getSequence(arr) {const preIndex = new Array(arr.length), indexResult = [0];let resultLastIndex, left, right, mid;const len = arr.length;for (let i = 0; i < len; i++) {const arrI = arr[i];if (arrI !== 0) {resultLastIndex = indexResult[indexResult.length - 1];// 以后项大于最初一项，间接退出后果resif (arr[resultLastIndex] < arrI) {preIndex[i] = resultLastIndex;indexResult.push(i);continue;}// 以后项小于最初一项，二分查找+替换，找到并替换比以后项大的那项left = 0, right = indexResult.length - 1;while (left < right) { // 重合就阐明找到了 对应的值,工夫复杂度O(logn)mid = (left + right) >> 1;// mid的值比以后项小，所以不包含mid的值if (arr[indexResult[mid]] < arrI) {left = mid + 1;} else {right = mid;}}// 只替换比以后项大的那一项，如果雷同、比以后项的还小就不换了if (arrI < arr[indexResult[left]]) {if (left > 0) {preIndex[i] = indexResult[left - 1];}indexResult[left] = i;}}}// 利用前驱节点从新计算resultlet length = indexResult.length; //总长度let prev = indexResult[length - 1]; // 最初一项while (length-- > 0) { // 依据前驱节点一个个向前查找indexResult[length] = prev;prev = preIndex[prev];}return indexResult;}- 遍历新节点，依据最长增长子序列进行挪动、增加、删除节点。
- 第一个节点为h，在newIndexToOldIndexMap中值为0，阐明是新增的节点，创立
- 第二个节点为e，索引为3，与最长增长子序列中3命中，跳过
- 第三个节点为d，索引为2，与最长增长子序列中2命中，跳过
- 第四个节点为c，索引为1，与最长增长子序列中1命中，跳过
- 第五个节点为f，索引为0，均不合乎，进行hostInsert，将节点f的实在dom挪动到节点nextChild节点c的后面
- 遍历完结实现
let j = increasingNewIndexSequence.length - 1; // 2// 遍历新节点，用toBePatched，是之前记录的新节点个数// 1. 须要找出老节点没有，而新节点有的(如节点h) -> 须要把这个节点创立// 2. 最初须要挪动一下地位，比方 [c,d,e,f] -> [f,c,d,e]// 这里倒循环是因为在 insert 的时候，须要保障锚点是解决完的节点（也就是曾经确定地位了）// 因为 insert 逻辑是应用的 insertBefore()// [ 0:a, 1:b, 2:f, 3:c, 4:d, 5:e, 6:h, 7:g ], s2 = 2for (let i = toBePatched - 1; i >= 0; i--) { // 4, 3, 2, 1, 0与increasingNewIndexSequence下标雷同// 确定以后要解决的节点索引，拿到正确的下标const nextIndex = s2 + i; // 6 -> 'h'const nextChild = c2[nextIndex]; // 'h'节点// 锚点等于以后节点索引+1// 也就是以后节点的前面一个节点(又因为是倒遍历，所以锚点是地位确定的节点)const anchor = nextIndex + 1 < l2 ? c2[nextIndex + 1].el : parentAnchor;// newIndexToOldIndexMap = [6, 3, 4, 5, 0]if (newIndexToOldIndexMap[i] === 0) {// 阐明新节点在老的外面不存在，须要创立patch(null, nextChild, container, anchor, parentComponent);} else if (moved) {// 须要挪动// 1. j 曾经没有了 阐明剩下的都须要挪动了// 2. 最长子序列外面的值和以后的值匹配不上， 阐明以后元素须要挪动if (j < 0 || increasingNewIndexSequence[j] !== i) {// 挪动的话应用 insert 即可hostInsert(nextChild.el, container, anchor);} else {// 这里就是命中了 index 和 最长递增子序列的值// 所以能够挪动指针了j--;}}}diff差异总结
- vue2、vue3 的 diff 算法实现差别次要体现在：解决完首尾节点后，对残余节点的解决形式。
- vue2 是通过对旧节点列表建设一个 { key, oldVnode }的映射表，而后遍历新节点列表的残余节点，依据newVnode.key在旧映射表中寻找可复用的节点，而后打补丁并且挪动到正确的地位。
- vue3 则是建设一个存储新节点数组中的残余节点在旧节点数组上的索引的映射关系数组，建设实现这个数组后也即找到了可复用的节点，而后通过这个数组计算失去最长递增子序列，这个序列中的节点放弃不动，而后将新节点数组中的残余节点挪动到正确的地位。
（本文作者：林督俊）
本文系哈啰技术团队出品，未经许可，不得进行商业性转载或者应用。非商业目标转载或应用本文内容，敬请注明“内容转载自哈啰技术团队”。