面试官：说一说 vue3 的快速 diff 算法（二）

在上一篇文章 # 面试官：说一说 vue3 的快速 diff 算法（一） 中，提到了 vue3 快速 diff 算法的预处理过程；
这次，我们来看看快速 diff 算法是如何高效移动节点的。

首先，我们来回顾一下，经过预处理后节点存在一种情况，即不满足下列任意一个条件：

• i > oldEnd && i <= newEnd；
• i > newEnd && i <= oldEnd；

这个时候我们就要考虑是否需要对节点进行移动，如下图：

我们在之前的代码基础上，增加一个 else 来处理这种情况：

function patchVnode(oldChildren, newChildren) {
    /** 省略 处理前置节点 */
    
    /** 省略 处理后置节点 */
    
    /** 省略 挂载剩余的新节点 */
    if (i > oldEnd && i <= newEnd) {
    } else
    /** 卸载多余旧子节点 */
    if (i > newEnd && i <= oldEnd) {
    } else {
    /** 处理非理想情况 */   
    }
}

构建 source 数组

首先，我们构建一个 source 数组，数组长度等于 i 到 newEnd 之间的节点个数；数组中的用 -1 来初始化：

具体代码如下：

function patchVnode(oldChildren, newChildren) {
    /** 省略 处理前置节点 */
    
    /** 省略 处理后置节点 */
    
    /** 省略 挂载剩余的新节点 */
    if (i > oldEnd && i <= newEnd) {
    } else
    /** 卸载多余旧子节点 */
    if (i > newEnd && i <= oldEnd) {
    } else {
        /** 处理非理想情况 */ 
        // 确定数组长度
        const count = newEnd - i + 1
        const source = new Array(count)
        // 用 -1 初始化数组
        source.fill(-1)
    }
}

那么，这个 source 数组的作用是什么呢？

实际上，它是用来计算出一个最长递增子序列的；通过这个最长递增子序列，我们就可以确定如何通过最少的操作来移动节点。

填充 source 数组

那又要怎么通过这个 source 数组来计算 最长递增子序列 呢？我们接着往下看：

首先，我们要找到新子节点在旧子节点中的对应节点 x，并把这个节点 x 对应的索引 index 保存在 source 数组中：

建立索引表

由于我们需要在旧子节点中找新子节点对应的节点，所以具体代码实现上，我们可以先遍历一遍新子节点，为 i 到 newEnd 区间的新子节点建立一张索引表；
这样有助于减少我们查找节点时的时间复杂度，具体代码如下：

function patchVnode(oldChildren, newChildren) {
    /** 省略 处理前置节点 */
    
    /** 省略 处理后置节点 */
    
    /** 省略 挂载剩余的新节点 */
    if (i > oldEnd && i <= newEnd) {
    } else
    /** 卸载多余旧子节点 */
    if (i > newEnd && i <= oldEnd) {
    } else {
        /** 处理非理想情况 */ 
        // 确定数组长度
        const count = newEnd - i + 1
        const source = new Array(count)
        // 用 -1 初始化数组
        source.fill(-1)
        
        // 为新子节点建立索引表
        const keyToIndex = {}
        for(let j = i; j <= newEnd; j++) {
            const newVnode = newChildren[j]
            // 用 新子节点的 key 来建立索引
            keyToIndex[newVnode.key] = j
        }
    }
}

针对我们的例子，keyToIndex 的结果就是下面这样：

keyToIndex = {
    3: 1, 
    2: 2, 
    5: 3, 
    7: 4
 }

更新 source 数组

有了索引表，接下来就可以去更新 source 数组了；

具体做法就是：遍历 i 到 oldEnd 区间旧子节点，通过 keyToIndex 索引，查找旧子节点中有没有和新子节点一致的节点。

function patchVnode(oldChildren, newChildren) {
    /** 省略 处理前置节点 */
    
    /** 省略 处理后置节点 */
    
    /** 省略 挂载剩余的新节点 */
    if (i > oldEnd && i <= newEnd) {
    } else
    /** 卸载多余旧子节点 */
    if (i > newEnd && i <= oldEnd) {
    } else {
        /** 处理非理想情况 */ 
        // 确定数组长度
        const count = newEnd - i + 1
        const source = new Array(count)
        // 用 -1 初始化数组
        source.fill(-1)
        
        const oldStart = i
        const newStart = i
        // 为新子节点建立索引表
        const keyToIndex = {}
        for(let j = newStart; j <= newEnd; j++) {
            const newVnode = newChildren[j]
            // 用 新子节点的 key 来建立索引
            keyToIndex[newVnode.key] = j
        }
        
        // 遍历 `i` 到 `newEnd` 区间的旧子节点
        for(let j = oldStart; j <= oldEnd; j++) {
            const oldVnode = oldChildren[j]
            // 通过 keyToIndex 索引，查找旧子节点中有没有和新子节点一致的节点
            const k = keyToIndex[oldVnode.key]
            // 如果 k 不等于 undefined，说明找到了匹配的节点
            if (typeof k !== 'undefined') {
                newVnode = newChildren[k]
                // 注意，这里针对相同的节点还需要进行 patch 打补丁的操作。
                patch(oldVnode, newVnode)
                // 这里需要用 k - newStart 拿到正确的索引
                source[k - newStart] = j
            } else {
                // 如果没找到，说明这个旧子节点没有匹配的新子节点，直接卸载就行
                unmount(oldVnode)
            }
        } 
    }
}

这里需要注意几点：

• 针对相同的节点还是需要进行 patch 打补丁的操作；
• 填充 source 数组时，需要使用 k - newStart；这是因为 k 反映的是经过预处理后的新子节点在旧子节点中的位置，并不是从 0 开始，所以需要减去预处理的节点数量（即 newStart），才能得到正确的位置；
• 如果在旧子节点中没有找到匹配的新子节点，则需要卸载这个旧子节点。

判断节点是否需要移动

经过上面的步骤，我们的 source 数组已经更新完毕；接下来我们需要判断节点是否需要移动。

那么在什么情况下节点才是需要移动的呢？我们不妨假设一下，如果节点不需要移动会发生什么：

如果节点不需要移动，那么说明我们在遍历旧子节点，并且在旧子节点中寻找匹配的新子节点这一过程中，k 值一定是递增的；

如下图所示：

因此，我们可以用一个变量 pos 来记录我们在遍历过程中遇到的最大 k 值，通过比较 pos 和 k 值，我们就能知道是否存在需要移动节点的情况；

具体代码如下：

function patchVnode(oldChildren, newChildren) {
    /** 省略 处理前置节点 */
    
    /** 省略 处理后置节点 */
    
    /** 省略 挂载剩余的新节点 */
    if (i > oldEnd && i <= newEnd) {
    } else
    /** 卸载多余旧子节点 */
    if (i > newEnd && i <= oldEnd) {
    } else {
        /** 处理非理想情况 */ 
        // 确定数组长度
        const count = newEnd - i + 1
        const source = new Array(count)
        // 用 -1 初始化数组
        source.fill(-1)
        
        const oldStart = i
        const newStart = i
        // 表示是否存在需要移动的节点
        let moved = false
        // 记录遍历过程中的最大 k 值
        let pos = 0
        const keyToIndex = {}
        for(let j = newStart; j <= newEnd; j++) {
            const newVnode = newChildren[j]
            keyToIndex[newVnode.key] = j
        }
        
        for(let j = oldStart; j <= oldEnd; j++) {
            const oldVnode = oldChildren[j]
            const k = keyToIndex[oldVnode.key]
            if (typeof k !== 'undefined') {
                newVnode = newChildren[k]
                patch(oldVnode, newVnode)
                source[k - newStart] = i
                // 判断 k 和 pos 值的大小
                // 如果 k < pos，说明需要移动节点
                // 否则更新 pos 的值
                if (k < pos) {
                    moved = true
                } else {
                    pos = k
                }
            } else {
                unmount(oldVnode)
            }
        } 
    }
}

移动元素

确定了是否有需要移动的元素之后，下一步我们就要考虑怎么去移动元素了。

计算最长递增子序列

还记得我们一开始构建的 source 数组吗？这时候就可以派上用场了！

通过 source 数组，我们就能计算出一个最长递增子序列；在我们的例子中，这个最长递增子序列就是 [1, 2]。

这里的 [1, 2] 表示的含义是：source 数组中，索引为 1 和索引为 2 的元素能够满足 最长递增子序列。

最长递增子序列 [1, 2] 还有另外一个含义：当新子节点中的节点能够满足最长递增子序列中的索引时，这个元素就不需要移动。

移动元素

由于最长递增子序列 [1, 2] 中的索引是从 0 开始计数的，因此我们还需要对剩余的新子节点重新编号，使其索引从 0 开始计数，这样便于后续比较：

我们用两个指针 s 和 j，分别指向最长递增子序列和重新编号的新子节点的最后一个位置：

接下来，我们使用一个 for 循环，让指针 j 向索引小的方向移动；
在移动过程中，我们通过判断 j 是否等于 seq[s]：

• 如果等于，则说明 j 指向的当前元素不需要移动，直接让 j-- 即可；
• 如果不等于，则说明当前元素需要移动。

这里需要注意的是： 除了判断 j 是否等于 seq[s] 之外，我们还需要判断一下 source 数组中对应的值是否为 -1；

这是因为我们一开始用 -1 填充 source 数组，后来又将其中的值更新为了 新子节点在旧子节点中对应的索引；

如果此时 source 的值仍为 -1，就说明在旧子节点中没有找到对应的节点，这是个全新的节点，我们需要挂载它。

代码如下：

function patchVnode(oldChildren, newChildren) {
    /** 省略 处理前置节点 */
    
    /** 省略 处理后置节点 */
    
    /** 省略 挂载剩余的新节点 */
    if (i > oldEnd && i <= newEnd) {
    } else
    /** 卸载多余旧子节点 */
    if (i > newEnd && i <= oldEnd) {
    } else {
        /** 处理非理想情况 */ 
        // 确定数组长度
        const count = newEnd - i + 1
        const source = new Array(count)
        // 表示是否存在需要移动的节点
        let moved = false
        /** 省略部分代码 */
        if (moved) {
            // 计算最长递增子序列
            const seq = lis(source)
            
            // 指针 s 指向最长递增子序列的最后元素
            let s = seq.length - 1
            // 指针 i 指向经过预处理后剩余的新子节点的最后一个元素
            let j = count - 1
            for (j; j >=0; j--) {
                if (source[j] === -1) {
                    // 说明这是个全新节点
                    // TODO 挂载节点
                } else if (j !== seq[s]) {
                    // 说明该节点需要移动
                    // TODO 移动节点
                } else {
                    // 说明该节点满足最长递增子序列
                    // 直接让 s 指向下一个位置即可
                    s--
                }
            }
        }
    }
}

总结

以上就是 vue3 快速 diff 算法的全部内容啦；我们来简单回顾总结一下整个过程：

1. 针对新旧子节点的前置节点、后置节点进行预处理；

   • 使用指针 j 指向新、旧头节点，同时从新、旧节点的头部向尾部开始遍历；
   • 使用指针 newEnd 指向新节点尾部，指针oldEnd 指向旧节点尾部，同时从新、旧节点的尾部向头部开始遍历

2. 预处理完毕后，判断是否有节点需要新增/卸载；

   • 当满足 (oldEnd < j && newEnd >= j) 时，挂载 j 至 newEnd 区间的节点；
   • 当满足 (oldEnd >= j && newEnd < j) 时，卸载 j 至 oldEnd 区间的节点。

3. 如果不存在节点需要新增/卸载，也就是 步骤3 中的条件时，判断是否有节点需要进行移动操作；

   • 构建 source 数组，数组长度等于 newVnode 未处理节点的长度，并用 -1 初始化；source 数组将用来存储新子节点中的节点在旧子节点中的位置索引；
   • 新增变量 moved，代表是否需要移动节点；
   • 新增变量 pos，代表遍历旧的一组子节点的过程中遇到的最大索引值 k；
   • 通过比较 k 与 pos 的值来判断是否需要移动节点。

4. 如果存在需要移动节点的情况，即 moved 为 true：

   • 根据 source 算出最长递增子序列 seq；
   • 用索引 j 指向新的一组子节点中的最后一个节点；用索引 s 指向最长递增子序列中的最后一个元素。
   • 循环新子节点，判断 source[j] 的值是否为 -1，如果是则说明 j 指向的节点是个全新的节点；
   • 同时，比较 j 与最长递增子序列值的关系，如果 j === seq[s]，则说明 j 对应的元素不需要移动；否则就需要移动对应元素。