VUE DIFF算法之双端DIFFVUE DIFF系列讲解前言一、双端DIFF的代码实现二、实践总结

93 阅读 0 评论 62 点赞

我是靠谱客的博主火星上铃铛，这篇文章主要介绍VUE DIFF算法之双端DIFFVUE DIFF系列讲解前言一、双端DIFF的代码实现二、实践总结，现在分享给大家，希望可以做个参考。

VUE DIFF系列讲解

VUE 简单DIFF算法
VUE 快速DIFF算法

文章目录

VUE DIFF系列讲解
前言
一、双端DIFF的代码实现
二、实践
- 练习1
- 2. 练习2
总结

前言

本文主要讲解下双端diff, 双端diff是vue2中所用的diff算法，也是目前绝大部份面试中，大家对于vue diff回答较常用的答案。再最近的几次面试中，发现很多中级前端开发工程师，只能很模糊的描述下基本的想法，一旦给出一个具体实例进行分析，就露馅了。所以我们接下来，跟着简单的代码及demo, 再对双端diff，进行一个深入的复习

一、双端DIFF的代码实现

提示：不需要特别关注patch等函数的实现，和diff的关系不是很大。理解其大致想做的事即可，具体模拟实现可参考文末github链接
话不多说，我们直接上代码：

复制代码

// 从n1和n2中分别取到oldChildren和newChildren
const oldChildren = n1.children;
const newChildren = n2.children;
// 获取四个索引值
let oldStartIdx = 0;
let oldEndIdx = oldChildren.length - 1;
let newStartIdx = 0;
let newEndIdx = newChildren.length - 1;
// 获取到四个索引值指向的vnode
let oldStartVNode = oldChildren[oldStartIdx];
let oldEndVNode = oldChildren[oldEndIdx];
let newStartVNode = newChildren[newStartIdx];
let newEndVNode = newChildren[newEndIdx];
while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
// 在双端匹配没有匹配上的时候，会用新的startVNode在旧的里边找，如果找到了，则会把对应vnode移走，并把对应位置置为undefined，所以oldChildren某些位置会为undefined.以下!oldStartVNode和!oldEndVNode就是对上述所说情况的处理
if (!oldStartVNode) {
oldStartVNode = oldChildren[++oldStartIdx];
} else if (!oldEndVNode) {
oldEndVNode = oldChildren[--oldEndIdx];
} else if (oldStartVNode.key === newStartVNode.key) {
// 如果首和首相等，则说明位置没有变，仅需要打补丁
patch(oldStartVNode, newStartVNode, container);
// 更新索引及对应的VNode
oldStartVNode = oldChildren[++oldStartIdx];
newStartVNode = newChildren[++newStartIdx];
} else if (oldEndVNode.key === newEndVNode.key) {
// 如果尾和尾相等，则说明位置没有变，仅需要打补丁
patch(oldEndVNode, newEndVNode, container);
// 更新索引及对应的VNode
oldEndVNode = oldChildren[--oldEndIdx];
newEndVNode = newChildren[--newEndIdx];
} else if (oldStartVNode.key === newEndVNode.key) {
// 打补丁
patch(oldStartVNode, newEndVNode, container);
// 如果oldChildren中的第一个是newChildre最后一个,则需要把oldChildren的第一个移到最后
insert(oldStartVNode.el, container, oldEndVNode.el.nextSibling);
// 更新索引及对应VNode
newEndVNode = newChildren[--newEndIdx];
oldStartVNode = oldChildren[++oldStartIdx];
} else if (oldEndVNode.key === newStartVNode.key) {
// 打补丁
patch(oldEndVNode, newStartVNode, container);
// 如果oldChildren的最后一个是newChildren的第一个，则需要把oldChildren的第一个移到开始
insert(oldEndVNode.el, container, oldStartVNode.el);
// 更新索引及对应VNode
oldEndVNode = oldChildren[--oldEndIdx];
newStartVNode = newChildren[++newStartIdx];
} else {
// 如果双端匹配没有找到，需要从newChildren中取出第一个，去oldChildren中进行匹配
const idxInOld = oldChildren.findIndex(node => node.key === newStartVNode.key);
if (idxInOld > 0) {
// 需要移动到节点
const vnodeToMove = oldChildren[idxInOld];
// 打补丁
patch(vnodeToMove, newStartVNode, container);
// 如果找到了，说明oldIdx对应的VNode已经移动到首位
insert(vnodeToMove.el, container, oldStartVNode.el);
// 将oldChildren的对应位置，置为undefinde
oldChildren[idxInOld] = undefined;
} else {
// 没有找到，则说明是新增节点，则挂载到对应位置
const anchor = oldStartVNode.el;
patch(null, newStartVNode, container, anchor);
}
// 更新索引及对应VNode
newStartVNode = newChildren[++newStartIdx];
}
}
if (oldEndIdx < oldStartIdx && newStartIdx <= newEndIdx) {
// 这种情况说明newChildren中有节点没有被遍历到，需要将未被遍历到到节点新增
for (let i = newStartIdx; i <= newEndIdx; i++) {
// 使用oldStartVNode才能保证不论新增遗留节点在最上/最下，放置的位置是正确的
patch(null, newChildren[i], container, oldStartVNode.el);
}
} else if (newStartIdx > newEndIdx && oldStartIdx <= oldEndIdx) {
// 这种情况说明旧的节点还有没有匹配上的，则需要把没有匹配的节点卸载
for (let i = oldStartIdx; i <= oldEndIdx; i++) {
unmount(oldChildren[i]);
}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
// 从n1和n2中分别取到oldChildren和newChildren
const oldChildren = n1.children;
const newChildren = n2.children;
// 获取四个索引值
let oldStartIdx = 0;
let oldEndIdx = oldChildren.length - 1;
let newStartIdx = 0;
let newEndIdx = newChildren.length - 1;
// 获取到四个索引值指向的vnode
let oldStartVNode = oldChildren[oldStartIdx];
let oldEndVNode = oldChildren[oldEndIdx];
let newStartVNode = newChildren[newStartIdx];
let newEndVNode = newChildren[newEndIdx];
while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
// 在双端匹配没有匹配上的时候，会用新的startVNode在旧的里边找，如果找到了，则会把对应vnode移走，并把对应位置置为undefined，所以oldChildren某些位置会为undefined.以下!oldStartVNode和!oldEndVNode就是对上述所说情况的处理
if (!oldStartVNode) {
oldStartVNode = oldChildren[++oldStartIdx];
} else if (!oldEndVNode) {
oldEndVNode = oldChildren[--oldEndIdx];
} else if (oldStartVNode.key === newStartVNode.key) {
// 如果首和首相等，则说明位置没有变，仅需要打补丁
patch(oldStartVNode, newStartVNode, container);
// 更新索引及对应的VNode
oldStartVNode = oldChildren[++oldStartIdx];
newStartVNode = newChildren[++newStartIdx];
} else if (oldEndVNode.key === newEndVNode.key) {
// 如果尾和尾相等，则说明位置没有变，仅需要打补丁
patch(oldEndVNode, newEndVNode, container);
// 更新索引及对应的VNode
oldEndVNode = oldChildren[--oldEndIdx];
newEndVNode = newChildren[--newEndIdx];
} else if (oldStartVNode.key === newEndVNode.key) {
// 打补丁
patch(oldStartVNode, newEndVNode, container);
// 如果oldChildren中的第一个是newChildre最后一个,则需要把oldChildren的第一个移到最后
insert(oldStartVNode.el, container, oldEndVNode.el.nextSibling);
// 更新索引及对应VNode
newEndVNode = newChildren[--newEndIdx];
oldStartVNode = oldChildren[++oldStartIdx];
} else if (oldEndVNode.key === newStartVNode.key) {
// 打补丁
patch(oldEndVNode, newStartVNode, container);
// 如果oldChildren的最后一个是newChildren的第一个，则需要把oldChildren的第一个移到开始
insert(oldEndVNode.el, container, oldStartVNode.el);
// 更新索引及对应VNode
oldEndVNode = oldChildren[--oldEndIdx];
newStartVNode = newChildren[++newStartIdx];
} else {
// 如果双端匹配没有找到，需要从newChildren中取出第一个，去oldChildren中进行匹配
const idxInOld = oldChildren.findIndex(node => node.key === newStartVNode.key);
if (idxInOld > 0) {
// 需要移动到节点
const vnodeToMove = oldChildren[idxInOld];
// 打补丁
patch(vnodeToMove, newStartVNode, container);
// 如果找到了，说明oldIdx对应的VNode已经移动到首位
insert(vnodeToMove.el, container, oldStartVNode.el);
// 将oldChildren的对应位置，置为undefinde
oldChildren[idxInOld] = undefined;
} else {
// 没有找到，则说明是新增节点，则挂载到对应位置
const anchor = oldStartVNode.el;
patch(null, newStartVNode, container, anchor);
}
// 更新索引及对应VNode
newStartVNode = newChildren[++newStartIdx];
}
}
if (oldEndIdx < oldStartIdx && newStartIdx <= newEndIdx) {
// 这种情况说明newChildren中有节点没有被遍历到，需要将未被遍历到到节点新增
for (let i = newStartIdx; i <= newEndIdx; i++) {
// 使用oldStartVNode才能保证不论新增遗留节点在最上/最下，放置的位置是正确的
patch(null, newChildren[i], container, oldStartVNode.el);
}
} else if (newStartIdx > newEndIdx && oldStartIdx <= oldEndIdx) {
// 这种情况说明旧的节点还有没有匹配上的，则需要把没有匹配的节点卸载
for (let i = oldStartIdx; i <= oldEndIdx; i++) {
unmount(oldChildren[i]);
}
}

二、实践

练习1

复制代码

// 旧子节点
p-1 p-2 p-3
// 新子节点
p-4 p-2 p-1 p-3
// 获取四个索引值
let oldStartIdx = 0
let oldEndIdx = 2
let newStartIdx = 0
let newEndIdx = 3
// 获取到四个索引值指向的vnode
let oldStartVNode = p-1
let oldEndVNode = p-3
let newStartVNode = p-4
let newEndVNode = p-3
// 进入双端循环对比
oldStartIdx(0)
newStartIdx(0)
是否相等
p-1
p-4
false
oldEndIdx(2)
newEndIdx(3)
是否相等
p-3
p-3
ture
因为 oldEndVNode.key === newEndVNode.key，既尾尾相等，仅进行patch，不需要移动。然后更新新旧idx及vnode
此时，真实节点为 p-1 p-2 p-3
oldEndIdx = 1
newEndIdx = 2
oldEndVNode = p-2
newEndIdx = p-1
oldStartIdx(0)
newStartIdx(0)
是否相等
p-1
p-4
false
oldEndIdx(1)
newEndIdx(2)
是否相等
p-2
p-1
false
oldStartIdx(0)
newEndIdx(2)
是否相等
p-1
p-1
ture
因为 oldStartVNode.key === newEndVNode.key, 即首尾相等，需要进行移动。因为oldStartVNode在新的中，变成了尾部节点，所以此时锚点为oldEndVNode.el.nextSibling
此时，真实节点为 p-2 p-1 p-3
oldStartIdx = 1
newEndIdx = 1
oldStartVNode = p-2
newEndIdx = p-2
oldStartIdx(1)
newStartIdx(0)
是否相等
p-2
p-4
false
oldEndIdx(1)
newEndIdx(1)
是否相等
p-2
p-2
true
因为 oldEndVNode.key === newEndVNode.key, 即尾尾相等，不需要移动
此时，真实节点为 p-2 p-1 p-3
oldEndIdx = 0
newEndIdx = 0
oldEndVNode = undefinde
newEndIdx = p-4
因oldEndIdx < oldStartIdx,所以跳出while循环
此时oldEndIdx(0) < oldStartIdx(1) && newStartIdx(0) <= newEndIdx(0),所以新的子节点未被遍历完，循环新的子节点，进行挂载
newStartIdx(0) 此时对应子节点p-4 锚点为oldStartVNode.el
最终，真实节点为 p-4 p-2 p-1 p-3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
// 旧子节点
p-1 p-2 p-3
// 新子节点
p-4 p-2 p-1 p-3
// 获取四个索引值
let oldStartIdx = 0
let oldEndIdx = 2
let newStartIdx = 0
let newEndIdx = 3
// 获取到四个索引值指向的vnode
let oldStartVNode = p-1
let oldEndVNode = p-3
let newStartVNode = p-4
let newEndVNode = p-3
// 进入双端循环对比
oldStartIdx(0)
newStartIdx(0)
是否相等
p-1
p-4
false
oldEndIdx(2)
newEndIdx(3)
是否相等
p-3
p-3
ture
因为 oldEndVNode.key === newEndVNode.key，既尾尾相等，仅进行patch，不需要移动。然后更新新旧idx及vnode
此时，真实节点为 p-1 p-2 p-3
oldEndIdx = 1
newEndIdx = 2
oldEndVNode = p-2
newEndIdx = p-1
oldStartIdx(0)
newStartIdx(0)
是否相等
p-1
p-4
false
oldEndIdx(1)
newEndIdx(2)
是否相等
p-2
p-1
false
oldStartIdx(0)
newEndIdx(2)
是否相等
p-1
p-1
ture
因为 oldStartVNode.key === newEndVNode.key, 即首尾相等，需要进行移动。因为oldStartVNode在新的中，变成了尾部节点，所以此时锚点为oldEndVNode.el.nextSibling
此时，真实节点为 p-2 p-1 p-3
oldStartIdx = 1
newEndIdx = 1
oldStartVNode = p-2
newEndIdx = p-2
oldStartIdx(1)
newStartIdx(0)
是否相等
p-2
p-4
false
oldEndIdx(1)
newEndIdx(1)
是否相等
p-2
p-2
true
因为 oldEndVNode.key === newEndVNode.key, 即尾尾相等，不需要移动
此时，真实节点为 p-2 p-1 p-3
oldEndIdx = 0
newEndIdx = 0
oldEndVNode = undefinde
newEndIdx = p-4
因oldEndIdx < oldStartIdx,所以跳出while循环
此时oldEndIdx(0) < oldStartIdx(1) && newStartIdx(0) <= newEndIdx(0),所以新的子节点未被遍历完，循环新的子节点，进行挂载
newStartIdx(0) 此时对应子节点p-4 锚点为oldStartVNode.el
最终，真实节点为 p-4 p-2 p-1 p-3

2. 练习2

复制代码

// 旧子节点
p-1 p-2 p-3
// 新子节点
p-4 p-1 p-3 p-2
// 获取四个索引值
let oldStartIdx = 0
let oldEndIdx = 2
let newStartIdx = 0
let newEndIdx = 3
// 获取到四个索引值指向的vnode
let oldStartVNode = p-1
let oldEndVNode = p-3
let newStartVNode = p-4
let newEndVNode = p-2
// 进入双端循环对比
oldStartIdx(0)
newStartIdx(0)
是否相等
p-1
p-4
false
oldEndIdx(2)
newEndIdx(3)
是否相等
p-3
p-2
false
oldStartIdx(0)
newEndIdx(3)
是否相等
p-1
p-2
false
oldEndIdx(2)
newStartIdx(0)
是否相等
p-1
p-4
false
因双端对比发现没有相同的，则从旧节点中遍历寻找newStartVNode, 发现找不到，则新增newStartVNode，锚点为oldStartVNode
此时，真实顺序为 p-4 p-1 p-2 p-3
更新idx及vnode
newStartIdx = 1
newStartVNode = p-1
//继续双端循环
oldStartIdx(0)
newStartIdx(1)
是否相等
p-1
p-1
true
因为 oldStartVNode.key === newStartVNode.key，既首首相等，仅进行patch，不需要移动。
此时，真实顺序为 p-4 p-1 p-2 p-3
更新idx及vnode
oldStartIdx = 1
newStartIdx = 2
oldStartVNode = p-2
newEndIdx = p-3
//继续双端循环
oldStartIdx(1)
newStartIdx(2)
是否相等
p-1
p-4
false
oldEndIdx(2)
newEndIdx(3)
是否相等
p-3
p-2
false
oldStartIdx(1)
newEndIdx(3)
是否相等
p-2
p-2
ture
因为 oldStartVNode.key === newEndVNode.key, 即首尾相等，需要进行移动。因为oldStartVNode在新的中，变成了尾部节点，所以此时锚点为oldEndVNode.el.nextSibling
此时，真实节点为 p-4 p-1 p-3 p-2
oldStartIdx = 2
newEndIdx = 2
oldStartVNode = p-3
newEndVNode = p-2
//继续双端循环
oldStartIdx(2)
newStartIdx(2)
是否相等
p-3
p-3
true
因为 oldStartVNode.key === newStartVNode.key，既首首相等，仅进行patch，不需要移动。
此时，真实顺序为
p-4 p-1 p-3 p-2
更新idx及vnode
oldStartIdx = 3
newStartIdx = 3
oldStartVNode = undefined
newStartIdx = p-2
因为oldStartIdx(3) > oldEndIdx(2) && newStartIdx(3) > newEndIdx(2),所以结束循环，此时新旧节点均为又遗留，对比完成

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
// 旧子节点
p-1 p-2 p-3
// 新子节点
p-4 p-1 p-3 p-2
// 获取四个索引值
let oldStartIdx = 0
let oldEndIdx = 2
let newStartIdx = 0
let newEndIdx = 3
// 获取到四个索引值指向的vnode
let oldStartVNode = p-1
let oldEndVNode = p-3
let newStartVNode = p-4
let newEndVNode = p-2
// 进入双端循环对比
oldStartIdx(0)
newStartIdx(0)
是否相等
p-1
p-4
false
oldEndIdx(2)
newEndIdx(3)
是否相等
p-3
p-2
false
oldStartIdx(0)
newEndIdx(3)
是否相等
p-1
p-2
false
oldEndIdx(2)
newStartIdx(0)
是否相等
p-1
p-4
false
因双端对比发现没有相同的，则从旧节点中遍历寻找newStartVNode, 发现找不到，则新增newStartVNode，锚点为oldStartVNode
此时，真实顺序为 p-4 p-1 p-2 p-3
更新idx及vnode
newStartIdx = 1
newStartVNode = p-1
//继续双端循环
oldStartIdx(0)
newStartIdx(1)
是否相等
p-1
p-1
true
因为 oldStartVNode.key === newStartVNode.key，既首首相等，仅进行patch，不需要移动。
此时，真实顺序为 p-4 p-1 p-2 p-3
更新idx及vnode
oldStartIdx = 1
newStartIdx = 2
oldStartVNode = p-2
newEndIdx = p-3
//继续双端循环
oldStartIdx(1)
newStartIdx(2)
是否相等
p-1
p-4
false
oldEndIdx(2)
newEndIdx(3)
是否相等
p-3
p-2
false
oldStartIdx(1)
newEndIdx(3)
是否相等
p-2
p-2
ture
因为 oldStartVNode.key === newEndVNode.key, 即首尾相等，需要进行移动。因为oldStartVNode在新的中，变成了尾部节点，所以此时锚点为oldEndVNode.el.nextSibling
此时，真实节点为 p-4 p-1 p-3 p-2
oldStartIdx = 2
newEndIdx = 2
oldStartVNode = p-3
newEndVNode = p-2
//继续双端循环
oldStartIdx(2)
newStartIdx(2)
是否相等
p-3
p-3
true
因为 oldStartVNode.key === newStartVNode.key，既首首相等，仅进行patch，不需要移动。
此时，真实顺序为
p-4 p-1 p-3 p-2
更新idx及vnode
oldStartIdx = 3
newStartIdx = 3
oldStartVNode = undefined
newStartIdx = p-2
因为oldStartIdx(3) > oldEndIdx(2) && newStartIdx(3) > newEndIdx(2),所以结束循环，此时新旧节点均为又遗留，对比完成

总结

双端DIFF作为面试中出现频率较高的知识点，原理并不难，主要理解的多为一下三部分

双端的遍历规则：即首(old)首(new)、尾(old)尾(new)、首(old)尾(new)、尾(old)首(new)对比
上述遍历规则无可复用节点的处理情况
需要进行挂载/移动时，锚点的选取规则
只要能真正理解上述情况，面试你就成功了

参考：<<vue设计与实现>>第10章
github：link

最后

以上就是火星上铃铛最近收集整理的关于VUE DIFF算法之双端DIFFVUE DIFF系列讲解前言一、双端DIFF的代码实现二、实践总结的全部内容，更多相关VUE内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。

本文分类：vue学习
浏览次数：93 次浏览
发布日期：2024-01-17 05:46:15
本文链接：https://www.kaopuke.com/article/k-p-k_13_u_23_ogf5_14_jc2.html

VUE DIFF算法之双端DIFFVUE DIFF系列讲解前言一、双端DIFF的代码实现二、实践总结

VUE DIFF系列讲解

文章目录

前言

一、双端DIFF的代码实现

二、实践

练习1

2. 练习2

总结

最后

评论列表共有 0 条评论

发表评论取消回复

VUE DIFF算法之双端DIFFVUE DIFF系列讲解前言一、双端DIFF的代码实现二、实践总结

VUE DIFF系列讲解

文章目录

前言

一、双端DIFF的代码实现

二、实践

练习1

2. 练习2

总结

最后

相关文章

评论列表共有 0 条评论

发表评论 取消回复

微信扫一扫：分享

发表评论取消回复