简单 Diff 算法
简单 Diff 算法
为什么需要 diff 算法
最初当两组子节点之间存在差异时，采用了最简单粗暴的解法：卸载所有子节点，挂载所有新的节点。但这种方法是十分低效的，它需要大量无意义的 DOM 操作才能完成更新。我们开始思考，是否有办法识别出来哪些节点时不需要更新的，我们只去更新需要更新的节点即可。Diff 算法就是为了做这个事情。
简单 diff 算法最开始是遍历两组子节点中长度较短的那一组，并逐个调用 patch 方法进行打补丁。如果新的那组长度比较长，则证明需要挂载新的节点；如果旧的那组长度比较长，则证明需要卸载旧的节点。
key值
diff 算法中有一个十分重要的概念：key。key 值是每个节点的“身份证号”，用于唯一标识一个节点。在最开始我们通过比对 VNode 的 type 值，也就是节点类型来判读节点是否相同可复用，但在这种情况下，如果出现了节点顺序变更，其实所有 VNode 的 type 是没有变化的，因此识别不出来哪些节点需要更新和移动位置。因此我们引入了 key 这个概念，如果两个节点的 type 值和 key 值都相同，那么我们就认为两个节点相同可复用。
但其实我们在 Vue 开发的过程中，并没有时时刻刻给节点赋 key 值，所以我猜测 Vue 内部应该有逻辑用于给没有设置 key 值的 VNode 设置唯一 key 值的逻辑。
寻找需要移动的节点
简单 diff 算法的核心逻辑是双重循环，先遍历新的节点列表，再去遍历旧的节点列表，在旧的节点列表里面找新的节点，如果找到了就证明这个节点可复用。
找到后记录该节点处于旧节点列表中的位置索引，并称之为最大索引。由于我们的外层循环是按照新节点列表顺序去遍历节点的，在遍历旧节点列表找到可复用的节点的过程中，如果一个节点处于旧列表中的索引大于最大索引，则说明该节点对应的 DOM 元素需要移动，因为此时新旧节点列表的递增顺序不一样了。
举个例子，旧节点列表1、2、3，新节点列表1、2、3，如果在新列表中找旧列表顺序，就是0、1、2（这里指的是数组下标哈），有一个递增的序列规则。
那如果旧节点列表是1、2、3，新节点列表是3、1、2，在新列表中找旧列表顺序，就是2、0、1（这里指的是数组下标哈），这不符合递增序列的规则。
那要怎么移动呢
在找到需要移动的节点后，我们要知道节点需要移动到哪里。我们可以发现，新节点的顺序就是更新后的真实 DOM 节点应有的顺序。
以上面 1、2、3 -》 3、1、2 这个为例，第一步 3 不动，第二步 1 要动，就会在新的序列中找位置，发现它是在 3 后面的，那就移动到 3 后面就好了，移动到 3 后面其实就是移动到 3 后面的一个节点的前面，因此取 3 的下一个兄弟节点作为锚点，调用 insertBefore(el, anchor) 就可以了。最后发现 2 也要动，那 2 要在 1 后面，那就移动到 1 后面就好了，以此类推就可以实现。
新增和删除节点
聊完了移动节点我们聊聊新增和删除节点。
新增节点其实上面说到就是新的节点比旧的节点多，所以我们可以在遍历旧节点列表时进行判断，如果找不到可复用的新的节点，则证明这个新节点需要挂载，调用挂载操作即可。
删除节点就是旧的节点比新的节点多，那我们可以遍历旧节点列表去找新节点，如果没有找到和旧节点一样的新节点，那这个旧节点就需要卸载，调用卸载操作即可。