虚拟DOM和Diff算法 Q&A

狐七 Vue

# 问答题

# 一、Diff 算法

Diff算法是比较两棵树上所有的节点，方法很多，snabbdom使用的只是一种。 Vue3里面为了提高性能Diff算法又提高了一些性能。

对比两颗树上所有的节点，传统的方式使用依次比较两棵树的每一个节点，这样的时间复杂度是 O(n^3)。

（两个树节点的比较是n*n，再加上更新真实DOM，又要遍历一遍n，所以是n^3）

比如：当前有三个节点，比较完树上的每一个节点需要的时间是 O(n^3)。其中 n 是节点个数。

# 二、Diff 过程

<div id="app">
  <button @click="onClick">按钮</button>
<ul>
  <li v-for="item in arr" :key="item">{{ item }}</li>
</ul>
</div>

<script src="../node_modules/vue/dist/vue.js"></script>
<script>
  let vm = new Vue({
    el: '#app',
    data: {
      arr: [1, 2, 3]
    },
    methods: {
      onClick () {
        // 不是响应式的
        // this.arr[0] = 0
        // this.arr.splice(0, 1, 0)
        
        this.arr.reverse()
      }
    }
  })
</script>

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

旧节点 ---> [vnode, vnode, vnode]

新节点 ---> [vnode, vnode, vnode]

四种情况演示：
- 更改第一个元素的值，设置 key 和不设置 key
- 翻转数组，设置 key 和不设置 key
更改第一个元素的值，不设置 key
- 123
- 023

updateChildren() 的时候比较新旧 VNode 数组中的第一个 VNode   (li)，此时是 sameVnode()
调用 patchVnode() 比较 VNode   (li)，都有子节点（文本节点）继续调用 updateChildren()
文本节点也都是 sameVnode() 调用 patchVnode()，此时有 text 属性，直接更新 li 的 text
继续比较第二个 vnode。。。最终都是更新文本的操作

只更了一次文本节点

1
2
3
4
5
6

更改第一个元素的值，设置 key
123
023

如果把数组中的当前项，设置为 li 的 key 的话，第一个新的 VNode，和 第一个 老的 VNode 不是 sameVnode
于是比较 最后一个老的就节点和最后一个老的新节点，是sameVnode，节点内容也一样什么都不做
倒数第一个节点也一样
回到比较第一个节点的过程，新的第一个节点，在老节点中找不到相同节点，
这时候创建一个新的 li，插入到第一个老的li之前。
最后再把老的第一个li节点，从界面上移除

只有一次插入的 DOM 操作，和一次移除的 DOM 操作

1
2
3
4
5
6
7
8

翻转数组，不设置 key
- 1 2 3
- 3 2 1
- 1234
- 4321

不设置 key 的情况，对比 第一个旧的开始节点和新的开始节点，是 sameVnode
继续 updateChildren，更新文本节点的内容

继续往后都是相同的操作

二次更新文本的操作

1
2
3
4
5
6

翻转数组，设置 key
- 3 2 1
- 3 2 1

翻转数组，第一个旧节点和第一个新节点不是 sameVnode
然后比较第一个旧节点和最后一个新节点，是 sameVnode，
这时候继续比较，因为这两个节点的内容也是一样的，所以不更新，但是要移动位置，把第一个旧节点移动到结束节点之后

继续比较第二个开始节点和倒数第二个结束节点，是 sameVnode
把旧开始节点移动到旧结束节点之后

然后再比较旧的开始节点（3）和新的开始节点（3），此时是 sameVnode 什么都不做。

两次移动的操作（n-1次操作）

1
2
3
4
5
6
7
8
9
10

123465
123456

# 三、key 的作用

https://cn.vuejs.org/v2/api/#key

有相同父元素的子元素必须有独特的 key。重复的 key 会造成渲染错误。

<ul>
  <li v-for="item in items" :key="item.id">...</li>
</ul>

1
2
3

它也可以用于强制替换元素/组件而不是重复使用它

<transition>
  <span :key="text">{{ text }}</span>
</transition>

1
2
3

# 四、请简述 Diff 算法的执行过程

答：Diff算法出现在虚拟DOM更新的同级子节点相互对比的情形中，将新老节的同级子元素进行对比。

新老节点都有开始索引和结束索引，将同级子元素进行循环遍历，从1步骤开始，当新老节点中但凡一个开始索引比结束索引要大，就可以结束循环，进入下面的9步骤。

PS: 新节点开始索引对应的节点称为新开始节点，结果索引对应的节点称为新结束节点老节点开始索引对应的节点称为老开始节点，结果索引对应的节点称为老结束节点相同节点的标准是：sel（选择器）和key相同下面步骤中1-7是循环，里面进入下一次循环的意思是，从1步骤开始。

将新开始节点和老开始节点进行对比，如果是相同节点，就用patchVnode方法对比这两个节点渲染DOM，并将新老开始索引向后移动，进入下一次循环，跳到步骤8。如果不相同跳到2步骤。
如果1的对比不是相同节点，就比较新老结束节点，如果是相同节点，就用patchVnode方法对比这两个节点渲染DOM，并将新老开始索引向前移动，进入下一次循环，跳到步骤8。如果不相同就跳到3步骤。
如果2的对比不是相同节点，就比较老开始节点和新结束节点，如果是相同节点，就用patchVnode方法对比这两个节点渲染DOM，把老开始节点移动到老结束节点之后，将老开始索引后移，新结束索引前移，进入下一次循环，跳到步骤8。如果不相同就跳到4步骤。
如果3的对比不是相同节点，就比较老结束节点和新开始节点，如果是相同节点，就用patchVnode方法对比这两个节点渲染DOM，把老结束节点移动到老开始节点之前，将老结束索引前移，新开始索引后移，进入下一次循环，跳到步骤8。如果不相同就跳到5步骤。
如果4的对比也不是相同节点，那么将新开始节点的key去老节点用key组成的Map对象中找，如果没有找到就说明是新增节点，将新节点新增DOM插到老开始节点之前，将新开始索引后移，进入下一次循环，跳到步骤8。如果找到了跳到6步骤。
如果5中新开始节点的key在Map对象中找到了，就对比两个节点的sel选择器是否相同，如果不同说明此对象被修改过了，需要重新，就创建新的DOM并查到老开始节点之前，新开始索引后移，进入下一次循环，跳到步骤8。如果比较sel相同，跳到7步骤。
如果6中新开始节点的key在Map对象中找到了老节点，对比sel也相同，用patchVnode方法比较两个节点的差异更新到DOM上，并在老节点数组中将此元素置为undefined，将这个老节点移动到老开始节点之前，新开始索引后移，进入下一次循环，跳到步骤8。
判断新数组或者旧数组是否有一个遍历完（判断新节点数组开始索引比结束索引大 or 判断老节点数组开始索引比结束索引的大），如果不满足条件进入1步骤，如果满足一个就退出循环，进入9步骤。
根据开始索引和结束索引判断，是哪一个没有遍历完，如果是新节点没有遍历完，说明剩下的都是新增的节点，将其一个一个进行添加。如果老节点没有遍历完，说明剩下的都是要删除的节点，将其一个一个进行删除。
本层级的diff算法完成。

# 五、请简述虚拟 DOM 中 Key 的作用和好处

答：从源码中可以看出来，key主要有两处很重要的用处

在重要判断两个节点是否相同的函数sameVnode函数的标准，一个是tag一个是key，如果两个都相同就会最大化的进行复用，这相比只有一个tag相同，更可以增加复用，减少DOM操作
第二个是updateChildren中如果新旧开始和结束节点都不同的时候，要拿着新节点的key去老节点数组中寻找先相同的key的节点索引，如果没有key，只能依次去老节点数组中寻找，有key的话寻找效率更高

# 编程题

# 五、参考 Snabbdom 提供的电影列表的示例，利用Snabbdom 实现类似的效果

见code/snabbdom-demo文件夹，npm install之后直接使用 npx parcel index.html即可

Snabbdom源码解析

狐七的个人博客

Choose mode