简单 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 后面就好了,以此类推就可以实现。
新增和删除节点
聊完了移动节点我们聊聊新增和删除节点。
新增节点其实上面说到就是新的节点比旧的节点多,所以我们可以在遍历旧节点列表时进行判断,如果找不到可复用的新的节点,则证明这个新节点需要挂载,调用挂载操作即可。
删除节点就是旧的节点比新的节点多,那我们可以遍历旧节点列表去找新节点,如果没有找到和旧节点一样的新节点,那这个旧节点就需要卸载,调用卸载操作即可。