Vue diff 算法

虚拟判断

什么是虚拟 DOM？（虚拟DOM以下简称vdom，VNode可以认为与vdom相同）
- vdom 是一个对象，一棵树。判断的结构是用对象来描述的
- 使用属性来描述判断标签
- 使用属性来描述dom的属性
- 使用属性来描述域的子节点。子节点必须是数组，元素也是vdom
```
const vdom = {
    tag: 'div',
    attr: {
        class: 'xx'
    },
    text: 'div的文本'
    children: [
        tag: 'input',
        attr: {
            value: 3
        }
    ]
}
 
```
- 那么如何将虚拟DOM渲染为真实DOM，本质上就是树的遍历，然后调用对应的浏览器API创建节点，设置节点的属性，添加子节点。

什么是 diff？

比较两个虚拟 DOM 树（vdom）之间的差异本质上是两个对象和两棵树的比较。当视图进行响应式更新时，尽可能减少 DOM 操作的开销，因此我们不需要完全更新整个视图，而只更新它们之间的差异

预热算法

设置一个排序好的数组 A 经过扭曲后就变成了数组 B。如何找到数组 A 中与数组 B 对应的元素的位置
- A: [1, 2, 3, 4, 5, 6]
- B: [2, 5, 1, 3, 6, 4]
- 这道题很简单，可以用两个for循环解决了：
```
for(let i = 0; i < A.length; i++){    for(let j = 0; j < B.length; j++){        if(A[i] = B[j]) return j    }} 
```
- 为什么我想谈论这个问题？因为diff算法的“核心”就是这样。 diff其他部分的处理可以认为是基于这个

如何diff

第一步是区分新旧VNode。从根节点div开始，只需根据新旧div的VNode更新div的属性、事件、样式等即可。比较简单
第二步，比较根节点div下的子节点，更新子节点，也就是图中红框部分。这部分是比较起来最麻烦的
——最大的问题是如何在两个子节点数组中找到它。其中两个子节点是同一个子节点。因为新VNode的子节点可以添加节点、删除节点或者在某个节点之前插入节点，所以情况比较复杂
– 如果要满足要求，必须能够找到所有情况下的新 VNode。该节点对应旧VNode的哪个子节点。这个问题可以用上面算法问题的解法来解决吗
第三步，利用上面算法问题的解法找到旧VNode的子节点对应的新VNode的子节点A，然后利用第一步更新该新VNode的事件和属性子节点A。然后继续更新子节点A的子节点。。
子节点更新优化
- 上面第二步中子节点的更新是一个n倍复杂度的循环。 Squidward想将其优化为n倍复杂度的算法
- Squid Sucking总结了几种DOM变化的情况（这里只列出了几种常见的情况）
  1. 新的子节点没有添加、删除或移动，但部分子节点发生了变化。
    - 旧V节点：[1,2,3,4,5]
    - 新Vnode：[1,2,3,4,5]
  2. 新增子节点删除一个DOM
    - 旧V节点：[1,2,3,4,5]
    - 新Vnode：[1,2,3,4]
  3. 新的子节点添加了DOM
    - 旧V节点：[1,2,3,4,5]
    - 新Vnode：[1,2,3,4,5,6]
  4. 新子节点反转
    - 旧V节点：[1,2,3,4,5]
    - 新Vnode：[5,4,3,2,1]
- 发现大多数情况下子节点的变化都与上述情况一致。只有少数情况下，新子节点的顺序会完全打乱。这种情况下，需要一个时间复杂度为n2n^2n2的循环来保证找到相同的VNode。
- 那么针对以上特殊情况如何优化呢？
  - 对于前三种情况，直接交叉新Vnode的子节点就可以了，因为新旧子节点在同一位置是一一对应的。对于2和3多一少一的情况，遍历完矩阵后，只需添加或删除剩余的DOM即可，细节问题不大。
  - 对于第四种情况，直接遍历一次新的Vnode，发现新的子节点5和旧的子节点1是不同的Vnode，那怎么办呢？ Squid 很烂的情况来判断。如果新的子节点5和旧的子节点1发现它们不是同一个VNode，则不会从旧的VNode的头部开始评估，而是使用新的子节点5和旧的子节点1。子节点数组的tail 5用于判断是否是同一个VNode，如果发现是同一个VNode，则可能会再往下走。
- 总结后，Squidward发现使用以下四种方法来判断子节点的VNode是否是同一个VNode，可以大概率减少遍历次数
  1. 为了简单起见，我们用A代表旧的子节点矩阵，B代表新的子节点矩阵
    1. 首先判断A的第一个节点和B的第一个节点是否是同一个节点
    2. 如果不是，判断A的最后一个节点和B的最后一个节点是否是同一个节点
    3. 如果还不行，继续查找A的第一个节点和B的最后一个节点是否是同一个节点
    4. 如果还不行，继续查找A的最后一个节点和B的第一个节点是否是同一个节点
    5. 如果以上四种方法仍然无法匹配，那就没有其他办法了。直接暴力破解，用B的节点去一一匹配A的节点，发现B的节点和A中的节点一一对应
注意diff算法会在开头定义4个数值变量，分别指向新老子节点的起始节点和尾节点的下标。定义4个对象变量，分别指向新旧子节点的起始节点和尾节点。你为什么做这个？他每次完成上述操作，找到对应的VNode，新旧子节点的起始节点和尾节点都会向中心收缩。因为已经处理完毕，所以不需要重新开始。源码如下：
- 大致流程如下

总结

优先级，判断前四种情况是否可以匹配。如果匹配不到就暴力使用n2n^2n2循环匹配
在此优化方法中，最好情况的时间复杂度为n，最坏情况的时间复杂度为n2+4nn^2+4nn2+4n，也就是n2n^2n2
diff算法的核心是两个数组的遍历，但在此基础上进行了优化，使得大多数情况下diff的实际时间复杂度接近n
所以 diff 算法其实并没有那么可怕。其他博文不会讲diff的核心部分。我们首先按代码顺序解释优化部分。开头有很多变量，如oldStartVnode、old VNode startnode、oldEndVnode、old VNode。尾节点、newStartVnode、new VNode、起始节点……让人头晕。

diff触发流程

diff 有两种触发方式：
- 第一个是Vue实例初始化时的第一个diff
- 第二种是响应式更新期间的 diff。 data.setter 是 Object.defineProperty 添加到对象属性的代理。数据变化时触发
注意，更新视图的_update方法实际上是响应式的，需要收集依赖关系。你可以简单地将 Vue 的视图更新视为一种计算更新。它与 Vue 上的 Computed 和 Watcher 是分开的。请注意，compute 和 watcher 的响应与视图更新无关。只有当视图实际使用了calculated和data中的值，并且值发生变化时，视图才会被更新。向 _upodate 添加响应式更新是在 mountComponent 中完成的。？识别同一个VNode的密钥。
- 首先，diff的作者首先要思考其他解决方案是否可行。那么此时判断两个VNode是否是同一个VNode有以下几种解决方案：
  - 参考比较，认为如果是相同的参考，就是同一个VNode。但如果这样改变新的VNode和旧的VNode，旧的VNode也会改变。不会有新旧VNode，所以新旧VNode一定是不同的引用，即两个不相关的对象。这个解决方案行不通
  - 比较两个对象，深度遍历看它们是否具有相同的属性。首先，性能不好。其次，在同一个 DOM 上添加和删除 DOM 属性是正常的。该解决方案无法适应许多情况。
- 这样看来，不可能100%确定两个VNode是否是同一个VNode。主要原因是因为新的VNode相对于旧的VNode可以任意改变。
- 这就是为什么早期的 diff 作者采用了不完美的方法，即使用标签和额外定义的键来识别它们是否是同一个 VNode。
  - 这就是为什么在编写for循环时需要添加额外的键值。当你刚开始使用vue和react框架时，你一定很奇怪，为什么在写for循环的时候需要写一个与开发无关的关键属性。
  - 为什么不完美？如果使用for循环的索引作为key值，这种方法在patch时，即使实际上不是同一个VNode，仍然会认为旧VNode的第二个子节点b和新VNode的第二个子节点c是同一个VNode
diff的作用是什么
- 模仿浏览器DOM的流程和重绘
- 提高开发效率
  - 提高框架的开发效率。这部分Vue代码是Squidward基于Snabbdom修改的，嗯，高级复制粘贴工程[狗头]
  - 也提高了我们的开发效率，因为我们不需要手动操作DOM
- 。 - 平台和兼容性
  - vdom 本质上是一个 js 对象，准确的说是一个 ECMAScript 对象，它与平台无关，而真正的 DOM 是与平台强相关的
  js 包括 ECMAScript、window 和 document。 ECMAScript是根据标准开发的，窗口和文档对象对于不同的平台可能略有不同。 vdom不需要渲染为真正的DOM，不需要调用平台相关的窗口和文档，实现高度的跨平台兼容性
- 对于一些认为性能可以提升的人来说，我更同意性能下限有保证的说法。我的看法如下：
  - 其实网上普遍认为它可以加快渲染速度。有人专门评价过。其实并没有速度上的优势，因为将vdom渲染成真正的DOM其实还需要调用浏览器原生API createElement、append、insertBefore
  - 理论上，封装代码的执行效率应该大于或等于未封装代码的执行效率。为什么？因为封装的代码必须考虑各种情况下的容错，请参见语言封装。

虚拟判断

什么是 diff？

预热算法

如何diff

总结

diff触发流程

版权声明

作者文章