又是金三银四的季节，最近小伙伴们都在问面试的问题，有算法的、有源码的、有项目的，还有问我能不能给找个对象的。今天我先选其中一个比较热的问题，也是之前我讲过很多次的，关于Vue VDOM DIFF。
说到Vue VDOM DIFF，但凡了解过一点原理的小伙伴都知道最长递增子序列，但是大多数人都不知道怎么就最长递增了，为什么React就不最长递增呢。其实最长递增子序列只是Vue VDOM DIFF中的一个小点，接下来我们来详细说下Vue VDOM DIFF到底是怎么回事。
哲学
做题之前，我们先来思考下人生，比如：
你的答案是什么，投资？抢银行？还是找家里要。
毫无疑问，最后一个方法才是最快捷安全的吧。
回到算法层面，最后一个方法其实就是尽可能多的去复用原先的资产，毕竟白手赚一个亿可比继承一个亿难多了。这种思想如果你能接受，就继续往下，不能接受就去重读下《出师表》，看看先帝创业的结果再来。
人生
接下来我们来看一个正经问题，有以下两组元素，如果让你从上面的老元素变换到下面的新元素，你会怎么做？
代码语言：javascript复制// old a b c d e f g
// new a b e c d h f g是不是又一道算法题，这个时候肯定有人想暴力替换。暴力法呢，也不是不可以，还是先参考先帝。让你赚一个亿，家里明明已经有九千万了，你只需要再赚一千万就行了，可是你非要把家里九千万都扔了再去重新赚一个亿，你是不是闲的？
所以怎么办呢，当然是要尽可能多的复用原先的资产了。比如这里的这两组元素，原先的abcefg都可以复用，接下来我们只需要调整下原先的cde的位置，再新增一个h，就完事了。是不是很简单！
VDOM DIFF
这不就是VDOM DIFF吗？
在网页与用户交流的过程中，用户就是上帝，我们要给上帝最好的体验，那当然得让上帝的页面看起来反应敏捷了。试想一下，上帝点击一个按钮，触发了页面的更新，你总不能把老页面的DOM元素全删除了然后再重新渲染吧，上帝怎么可能等你那么长时间！所以呢，我们要以最低的成本来更新页面，比如可以通过计算新老DOM变化的最小差值，最后更新DOM的时候只更新这个差值，甚至我们还可以把这个差值里的不重要的更新变成异步。
是不是很神奇，但是实际操作起来却没有那么简单，因为历史原因，DOM节点的属性值是非常多的:
这么多属性值，如果这个时候我们去diff这样的DOM节点，那真的得到天荒地老了。
谁跟你天荒地老，DOM节点的很多属性值我们平常是用不到的，所以可不可以优化一下呢。比如说，用到哪些属性值，就diff哪些不就行了吗。那这个时候我们也不用DOM了，而是自己去定义个js对象，对象中的key:value呢就包括我们属性名与属性值，每个js对象都对应一个DOM节点。
到这里，相信机智的你已经猜到了，这个我们自己定义的js对象就是传说中的屋子，哦，不对，是传说中的VDOM。
最近刚又看完《奇友》，台词里的《传说中的屋子》实在是太洗脑了。
VDOM DIFF算法
好了，接下来正题来了，那么下面这个到底怎么变换。其实这个问题在React与Vue中都有，并不局限于框架，而是个算法题，React的我已经讲过了，详情可以参考本公众号”bubucuo“中上一篇文章。关于Vue中呢，接下来我们细讲。
代码语言：javascript复制// old a b c d e f g
// new a b e c d h f g刚提到说这是个算法题，其实不完全是，因为纯算法题是没有场景的，但是这里我们有场景，比如上面的abc等都代表了DOM节点。
想一下你平常见过的网页，更新的时候很少很少会发生翻天覆地的变化吧，基本上都是比较小的变化，只是某一小部分的DOM节点需要更新。那这个时候是不是意味着大多数的节点和节点位置，其实根本就没有发生变化。注意，我说的是大多数的节点和节点位置，没有发生变化。
再回到刚刚这道算法题上来，从old->new，在实际场景中，大部分的节点和节点位置都和上次一样！
代码语言：javascript复制// old a b c d e f g
// new a b e c d h f g这说明了什么，new的前s个节点和后e个节点，节点本身和位置，都和old的一样，并且实际场景中，m n的值是非常接近于节总长度的。鉴于此，你还想暴力查询吗，根本没必要吧，直接从前后边按顺序查找不就行了。
因此到现在，相信很多人已经猜到了Vue是怎么处理VDOM DIFF的了，
- 从左边查找，比较new[i]和old[i]，如果节点可以复用，那么复用本节点并继续往后比较，即i 重复本步骤。如果不能复用，则中止本循环（0<= i <old.length, i<new.length）
- 从右边查找，比较new[e1]和old[e2]，如果节点可以复用，那么复用本节点并继续往后比较，即e1--; e2--; 重复本步骤。如果不能复用，则中止本循环（0<= e1 <old.length, 0<= e1 <new.length）。
- 经过以上两步骤之后，只剩下了中间有点乱的序列，接下来的核心算法就是这里这个中间部分。后文附上代码细说。
节点复用
在写完整的Vue3 VDOM DIFF之前，我们要先来了解下新节点如何复用老节点，其实就是判断这个新节点是否就是某个老节点本身，怎么判断呢，其实这个判断在Vue和React中一样的，三个条件同时满足即可：同一层级、同一类型以及key相同。
同一层级
关于同一层级这个条件，我在React VDOM DIFF文章中详细讲过，实际项目中的节点极少发生跨层级的变化。就像你家鹅丢了，你不会跑到南极找一样，当然有可能你家鹅真的在南极，比如被外星人抓走了，但是可能性太低，找的成本太高，所以普通人不做这种不划算的事情。
类型相同
这个没什么好说的吧，身份证性别都不一样，怎么能是同一个人呢？
别抬杠说变性了，和南极找鹅一个道理。
key相同
key就是节点在当前层级下的唯一凭证，相当于它们的身份证号，所以这个值在当前层级下不仅要唯一，还要稳定。所以平常定义key的时候，一定要满足这两个条件。比如用index或者Math.random()赋值key，那么key就是不稳定的，这样造成的后果就是组件更新的时候无法复用，导致组件不断卸载再重新渲染，某些情况下可能会导致bug。当然index可能会没那么严重，如果你的组件顺序是稳定的，那么用index一般也没事，但是还是不建议使用，毕竟项目代码的迭代通常是很频繁的。
那么接下来要用到的节点复用代码大家肯定就能理解了。
代码语言：javascript复制function isSameVnodeType(n1, n2) {
return n1.key === n2.key && n1.type === n2.type;
}Vue3 VDOM DIFF代码实现
实现Vue3的VDOM DIFF的时候，由于简单的单个节点只是通过isSameVnodeType判断就行了，并没有什么难点，接下来我们重点放在old与new都是数组的情况下，本文中所讲解的Vue3 VDOM DIFF算法也指的是old与new都是数组的情况。
上面已经提到了Vue3 VDOM DIFF的实现思想，三大步，左、右、中。接下来我们来按照Vue3源码来实现下这个diff代码。
注意事项
为了方便TDD，我做了部分的修改，比如上面的isSameVnodeType就不判断type了，修改之后如下：
代码语言：javascript复制function isSameVnodeType(n1, n2) {
return n1.key === n2.key;// && n1.type === n2.type;
}还有一个小修改就是关于新增节点、删除节点、移动节点和复用节点的的四个函数分别为mountElement、unmount、move与patch，但是实际上Vue3源码中在这里的新增节点用的也是patch，只是把old写成null了：
我们今天实现的代码中为了方便区分新增与复用，我就把新增写成mountElement了哈~
代码实现
我们先来认识几个变量，以下为了简单，老节点和新节点接下来我分别简称为old和new，注意它们都是数组：
代码语言：javascript复制 let i = 0; // 遍历的下标
const l1 = c1.length; // old的长度
const l2 = c2.length; // new的长度
let e1 = l1 - 1; // old的尾结点下标
let e2 = l2 - 1; // new的尾结点下标大家可能会吐槽上面的变量，命名过于简洁，但这其实就是Vue3的源码，接下来你还会见到更多的简洁命名，不过没关系，我会加上注释的。其实它们都是英文首字母，比如这里的c就是children，e就是end，当然是我猜的~
说到这里，就要夸下react的源码了，命名都很长，基本上看单词意思就知道这个变量是干嘛的。
不过感觉各有优缺点吧，Vue的示例很多，第一遍看diff源码的时候，我觉得很好懂，但是react就不是这样了~
接下来我们来看代码实现~
1. 从左边向右边查找
从左边往右查找，如果节点可以复用，则继续往右，不能就停止循环。注意下面while循环的终止条件包括两个：1. 数组越界 2. 节点不能再复用。
代码语言：javascript复制// *1. 从左边往右查找，如果节点可以复用，则继续往右，不能就停止循环
while (i <= e1 && i <= e2) {
const n1 = c1[i];
const n2 = c2[i];
if (isSameVnodeType(n1, n2)) {
patch(n1.key);
} else {
break;
}
i ;
}2. 从右边向左边查找
从右边往左边查找，如果节点可以复用，则继续往左，不能就停止循环。和上一步一样，下面while循环的终止条件包括两个：1. 数组越界 2. 节点不能再复用。
代码语言：javascript复制// *2. 从右边往左边查找，如果节点可以复用，则继续往左，不能就停止循环
while (i <= e1 && i <= e2) {
const n1 = c1[e1];
const n2 = c2[e2];
if (isSameVnodeType(n1, n2)) {
patch(n1.key);
} else {
break;
}
e1--;
e2--;
}3. old或者new已经遍历完成
经过以上两步，可能会出现以下两种情况：
3.1 old没了，而new还有
如下面的例子：
代码语言：javascript复制 // old (a b)
// new (a b) c那么这个时候，只需要把new剩下的元素逐个新增就行了，毕竟没老节点能让你复用了，只能自己动手丰衣足食了。实现代码如下：
代码语言：javascript复制if (i > e1) {
if (i <= e2) {
while (i <= e2) {
const n2 = c2[i];
mountElement(n2.key);
i ;
}
}
}3.2 new没了，而old还有
如下面的例子：
代码语言：javascript复制// old (a b) c
// new (a b)那么这个时候，只需要把old剩下的元素逐个删除就行了，毕竟没有新节点费尽心机的要利用你了，留着也没用了。实现代码如下：
代码语言：javascript复制// 这里的else if承接上段代码的if
else if (i > e2) {
while (i <= e1) {
const n1 = c1[i];
unmount(n1.key);
i ;
}
}4. ”凌乱的“中间
经过了上面1和2的左右夹击，old和new都还有残兵，也不满足3的条件，这个时候我们就要想办法复用了这”凌乱的“的中间部分节点了。参考例子如下：
代码语言：javascript复制// old [i ... e1 1]: a b [c d e] f g
// new [i ... e2 1]: a b [e c d h] f g经过第1步，patch了ab，经过第2步，patch了gf，接下来我们只剩下了凌乱的c d e和e c d h。这两部分如何复用呢，大家可以思考下。肉眼可见，cde是要要patch的，h是mountElement的，并且原先的cde要变成新顺序的ecd是要move的。
问题来了，鉴于中间顺序的凌乱，如果我们先遍历old，我们该如何高效地从new中对应的节点呢？当然你可以选择暴力找，但是如果new中的每个节点都通过for循环去old中暴力找，效率太低了。而且等会儿我们还要根据检查old和new的相对顺序变化来判断是否要移动节点呢，所以怎么办？
4.1 把new做成Map图
鉴于单纯地通过key去old数组中找节点不好找，大家都学过字典结构，那我们就把new数组的元素做成key:value的Map不就行了，代码如下：
代码语言：javascript复制const s1 = i;
const s2 = i;
const keyToNewIndexMap = new Map();
for (i = s2; i <= e2; i ) {
const nextChild = c2[i];
keyToNewIndexMap.set(nextChild.key, i);
}学过React VDOM DIFF的可以再来思考一个问题，React中也用到了Map，只不过是把old拼了个Map，但是React中Map的value取值的是vnode，而我们这里却用的下标i，为什么？
这里就涉及到数据结构了，react中的old是fiber单链表结构，无法快速找到节点，所以想通过key快速找节点的话，只能存vnode。而vue的old是数组，也就意味着通过下标就能快速找到节点，既然如此，那value就存下标i就可以了，还可以记录位置，方便又省事儿~
4.2 记录节点位置
这一步主要是记录位置，部分代码你可以晚点再来看，可以先只看toBePatched和patched这两个值。
下面的注释很重要，可以结合后面文章反复阅读~
代码语言：javascript复制// 注意这里的命名patch不是指复用哈，而是包括了复用和新增
// 前面文章中我用绿色字体说过了，Vue3源码中的patch包括了复用和新增
// 本文中代码为了方便TDD，patch我只代表复用，而mountElement代表新增
const toBePatched = e2 - s2 1; // 还剩下多少个新节点没处理
// 计数值，就是算一算新增已经复用或者新增了多少个新节点了，每复用或者新增一个新节点，patched就加1
// 如果patched >= toBePatched，那么证明new处理完成。剩下的老节点就unmount就行啦
let patched = 0;
// 下面这3行段代码你可以看完4.3和4.4再来看~
// 这里做的事情很巧妙
const newIndexToOldIndexMap = new Array(toBePatched);
// 下标是新元素的相对下标，初始值是0，
// 在4.3中如果检查到节点能复用的话，值会更新为老元素的下标 1，那么最小值就是1
// 也就是说4.4中会根据newIndexToOldIndexMap[i]的值判断点是否有被复用过，如果是0，则证明没有被复用过。
for (i = 0; i < toBePatched; i ) {
newIndexToOldIndexMap[i] = 0;
}4.3 遍历old，patch节点
刚刚已经有了new的Map，那么我们接下来就可以遍历old了，然后把能复用的节点patch了，先看简版：
代码语言：javascript复制// *4.3 先遍历老元素 检查老元素是否要被复用，如果能复用就patch，如果不能复用就删除
for (i = s1; i <= e1; i ) {
const prevChild = c1[i];
if (patched >= toBePatched) {
unmount(prevChild.key);
continue;
}
const newIndex = keyToNewIndexMap.get(prevChild.key);
// 根据老节点的key去新节点的字段中找值，找到了就证明节点有复用，找不到就不复用呗
// 相当于你不确定这个钥匙是不是你的，那就开门试试呗，打开了就是你的嘛
if (newIndex === undefined) {
// 节点没法复用
unmount(prevChild.key);
} else {
// 参考4.3中代码的注释，这里对理解4.4很重要
newIndexToOldIndexMap[newIndex - s2] = i 1;
patch(prevChild.key);
patched ;
}
}4.4 遍历新元素 mount move
在4.3中我们已经遍历完了old，把能复用的节点和要删除的节点都处理完了，相当于这个例子中我们已经处理完了cde的复用，但是cde除了要执行patch函数，还要移动节点才能变成ecd呀，而且新增h我们也还没处理呢。
代码语言：javascript复制// old [i ... e1 1]: a b [c d e] f g
// new [i ... e2 1]: a b [e c d h] f g接下来我们还需要再来遍历new，从而执行move和mountElement。
遍历new很简单，但是问个小问题，这个遍历应该从前往后还是应该从后往前遍历呢？
先想下我们要做的事情，move或者mountElement对吧，而这两个函数其实用原生函数的方法都是通过appendChild或者insertBefore来实现的。而appendChild是在容器内末尾插入元素，insertBefore则是在某个元素前面插入。注意是前面，也就是垫脚石呗，那如果你的垫脚石还没有创建好呢，那还怎么垫脚。所以接下来我们最好先去创建这个后面的垫脚石。也就是遍历new可以从后面往前遍历~
另外注意，这里遍历的时候用的不是原先的数组下标，而是相对下标，用相对下标主要是为了判断节点是否需要移动的考虑~
代码语言：javascript复制// 相对下标
for (i = toBePatched - 1; i >= 0; i--) {
const nextChildIndex = s2 i;
const nextChild = c2[nextChildIndex];
// 判断nextChild是mount还是move
// 在老元素中出现的元素可能要move，没有出现过的要mount
if (newIndexToOldIndexMap[i] === 0) {
mountElement(nextChild.key);
} else {
// 可能move
}
}通过上面的代码，相信大家对mountElement已经理解透彻了，但是move我们还没有讲，也就是大家熟知的最长递增子序列。鉴于本文已经快六千字了，所以4.3和4.4的详解版，我会在下篇文章中继续讲解，也欢迎大家本公众号“bubucuo”~
在看下篇文章之前，建议大家如果对最长递增子序列不熟悉，可以先去LeetCode刷下这道题，这道题我在b站也有讲解，大家可以先了解下~
关于最长递增子序列这种动态规划题目，肯定有暴力法和优化法两种解法，考虑到性能，Vue肯定会选择优化法，但是就和diff算法一样，这里有实际应用场景，也就意味着算法 实际场景才是Vue的最终方案，大家可以思考下，也可以自行阅读下源码~
本篇文章可运行代码，关注本公众号”bubucuo“，回复”diff代码“即可获取~
