Vue diff算法

虚拟DOM

1. 什么是虚拟DOM？（虚拟DOM以下简称vdom,VNode可以认为与vdom是一样）
   • vdom就是一个对象，一颗树，把dom的结构组成用一个对象来描述
   • 用一个属性描述dom标签
   • 用一个属性描述dom上的属性
   • 用一个属性描述dom上的子节点，子节点是应该是一个数组，且元素也是一个vdom

   const vdom = {
       tag: 'div',
       attr: {
           class: 'xx'
       },
       text: 'div的文本'
       children: [
           tag: 'input',
           attr: {
               value: 3
           }
       ]
   }
    

   • 那么虚拟DOM怎么渲染成真实DOM，本质上是一个树的遍历，然后调用相应的浏览器的API去创建节点，给节点设置它的属性，添加子节点。

   

什么是diff？

1. 比较两个虚拟DOM树（vdom）的差异，本质上是两个对象、两棵树的比较。在视图响应式更新时，尽可能的减少DOM操作的开销，因此我们不需要完全的更新整个视图，而是只更新他们差异的部分

热身算法

1. 将一个排好序的数组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

1. 第一步，新旧VNode的diff从根节点div开始，此时只需要根据新旧div的VNode，更新div的属性、事件、样式等即可，比较简单

2. 第二步，比较根节点div下的子节点更新子节点，也就是图中红框部分，这部分比较是最麻烦的
   – 最大的难题是如何在两个子节点数组中找到哪两个子节点是同一个子节点。因为新VNode的子节点有可能增加一个节点，有可能删除了一个节点，或者该节点插入到某一个节点之前，情况复杂
   – 如果要满足在所有情况下一定能找到新VNode的一个子节点对应在旧VNode的哪个子节点上。是不是用上面算法题的解就可以解决这个问题

3. 第三步，这时我们用上面算法题的解找到新VNode的子节点A对应在旧VNode的子节点，再用第一步的方式更新子节点A的事件、属性就可以了，然后继续更新子节点A的子节点。。。

   

4. 子节点更新优化

   • 上面第二步子节点的更新是一个n方时间复杂度的循环，鱿鱼吸想把它优化成一个n时间复杂度的算法
   • 鱿鱼吸总结了几种DOM变化的情况（这里只列举了几种常见的情况）
     1. 新子节点没有增删移动，只是某些子节点自身变化了
        • 旧Vnode: [1,2,3,4,5]
        • 新Vnode: [1,2,3,4,5]
     2. 新子节点删掉了一个DOM
        • 旧Vnode: [1,2,3,4,5]
        • 新Vnode: [1,2,3,4]
     3. 新子节点增加了一个DOM
        • 旧Vnode: [1,2,3,4,5]
        • 新Vnode: [1,2,3,4,5,6]
     4. 新子节点翻转了
        • 旧Vnode: [1,2,3,4,5]
        • 新Vnode: [5,4,3,2,1]
   • 发现大多数情况下子节点的变化都符合上述的情况。只有少数的情况下，是新的子节点顺序完全打乱的，这时候需要用n2n^2n2时间复杂度的循环来保证找到同一个VNode。
   • 那么针对上面几种特殊情况怎么优化呢？
     • 对于前三种情况是不是直接遍历一次新Vnode的子节点就可以了，因为新旧的子节点相同位置都是一一对应的。对于2、3多一个少一个的情况，在数组遍历完之后，把剩余的DOM添加或者删除即可，细节问题不大。
     • 对于第四种情况，直接遍历一次新Vnode，发现新的子节点5和旧的子节点1是不同的Vnode，那怎么办呢？鱿鱼吸就加多一种情况判断，新的子节点5和旧的子节点1发现不是同一个VNode，那就不从旧VNode的头开始判断，而是改为用新的子节点5和旧的子节点数组的尾部5来判断是否是同一个VNode，发现是同一个VNode，又可以往下走了。
   • 鱿鱼吸总结之后发现先用以下4种方式去判断子节点的VNode是否是同一个VNode可以极大概率减少遍历的次数
     

     为了方便说明，我们用A来表示旧的子节点数组，用B来表示新的子节点数组

     1. 先判断A的第一个节点与B的第一个节点是否是同一个节点

     2. 如果不行，再判断A的最后一个节点与B的最后一个节点是否是同一个节点

     3. 如果还不行，继续判断A的第一个节点与B的最后一个节点是否是同一个节点

     4. 如果还不行，继续判断A的最后一个节点与B的第一个节点是否是同一个节点

     5. 如果上述4种方式还匹配不到，没办法了，只能用暴力的方式，用B的节点去逐一匹配A的节点，找到B的节点对应在A中的节点

5. 注意diff算法，在一开始会定义4个数字变量，分别指向新旧子节点的开始节点和尾节点的下标。定义4个对象变量，分别指向新旧子节点的开始节点和尾节点。为什么要这么做，因为他每一次走完上面的操作，找到对应的VNode之后，新旧子节点的开始节点和尾节点都会往中间收缩。因为已经处理过，不需要再重头开始处理了。源码如下：

   

   • 大致过程如下

   

总结

1. 优先确定头尾4种情况能否匹配上，如果匹配不上就暴力用n2n^2n2的方式循环匹配
2. 在这种优化方式下，最好情况的时间复杂度是n,最坏情况是n2+4nn^2+4nn2+4n，也是n2n^2n2
3. diff算法的核心是两个数组的遍历，但是它在此基础上进行了优化，使得diff在大多数情况下实际时间复杂度接近n
4. 所以diff算法实际并没有这么恐怖，其他博文上来不讲diff的核心部分，按代码顺序先讲解它的优化部分，上来就是一大堆的变量，什么oldStartVnode旧VNode开始节点、oldEndVnode旧VNode尾节点、newStartVnode新VNode开始节点…把人转晕了。

diff触发流程

1. diff触发分两种方式：
   • 第一种是Vue实例初始化时第一次diff
   • 第二种是响应式更新时diff，data.setter是Object.defineProperty给对象属性加的代理，当数据被更改时会触发

   

2. 注意更新视图的_update方法其实也是响应式的，也需要收集依赖，你可以简单将Vue的视图更新视为一个computed。他与Vue上的Computed和Watcher是分开的，注意computed和watcher的响应式与视图更新没有半毛钱关系。只有视图真正用到了computed和data里的值，且值变化了，视图才会更新。给_upodate加上响应式更新是在mountComponent里面做的。

思考

1. 为什么判断是否是同一个VNode需要通过tag和key来判断
   

   不应该站在必须要用key这一前提去思考这个问题，而应思考diff的作者为什么会想到多加一个key来标识同一个VNode。

   • 首先diff的作者最开始肯定是先思考其他方案是否可行，那么此时判断两个VNode是否是同一个VNode有如下方案：
     • 引用比较，认为如果是同一个引用的话，就是同一个VNode。但是这样改了新VNode旧VNode也会变化就没有新旧VNode而言了，所以新旧VNode必须是不同的引用，即两个不相关的对象，此方案不行
     • 两个对象的比较，深层遍历他们是否都具有相同的属性。首先性能不好，其次同一个DOM在其上增删DOM属性也是正常的，此方案也不能适配很多情况。
   • 如此看100%确定两个VNode到底是不是同一个VNode是不可能，主要原因是因为新VNode相对于旧VNode是可以任意变化的。
   • 所以早期diff作者才采用了用tag和额外定义的key来标识是否是同一个VNode这种不太完美的方式
     • 所以才有了在写for循环的时候要额外添加一个key值，大家在刚开始用vue、react框架的时候肯定都疑惑过为什么写for循环还要写一个与开发无关的key属性。
     • 为什么说不完美？如果使用for循环的index作为key值的话，那么在patch的时候，尽管他实际上不是同一个VNode,这种方式还是会认为旧VNode的第二个子节点b和新Vnode的第二个子节点c是同一个VNode

     

2. diff有什么作用
   • 模仿浏览器DOM的回流重绘
   • 提高开发效率
     • 提高框架的开发效率，Vue这部分代码是鱿鱼吸在Snabbdom的基础上改造的，emmm，高级复制粘贴工程[狗头]
     • 也提高了我们的开发效率，因为我们不需要手动操作DOM
   • 跨平台和兼容性
     • vdom本质上是一个js对象，准确的说是ECMAScript对象，这是与平台无关的，而真实DOM是与平台强相关的

     js包含ECMAScript、window、document。ECMAScript是遵循标准开发的，而window和document对象则对于不同的平台可能会略有不同。vdom不需要渲染成真实DOM，不需要调用与平台相关的window和document实现跨平台兼容性高

   • 对于有些观点认为可以提高性能，我更认同保证了性能的下限这一说法。我的观点如下：
     • 实际上对于网上普遍认为的可以加快渲染速度，有人专门做过测评，实际在速度上并没有优势，因为vdom渲染成真实DOM实际也同样需要调用浏览器原生API createElement、append、insertBefore
     • 从理论上来讲，封装后的代码的运行效率应该是大于等于不封装的，为什么？因为封装后的代码要考虑多种情况容错，参考语言封装。