diff算法原理、 Vue、React区别

Myth丶恋晨 2024-03-31 11:06 142阅读 0赞

**目录**

传统Diff算法

React优化Diff算法

Vue的Diff算法

在了解Vue和React的区别之前，我们首先来了解一下MVC和MVVM架构，这个知识点有助于我们对后续知识的了解。一提到前端框架，相信大家都对Vue和React不陌生，这两个前端框架都是比较主流的，用户也都比较多，但是我们在使用这些框架的时候，是否对这两个框架之间的区别有所了解呢？接下来，让我们来一起的系统梳理这两个框架的区别是什么吧~

**MVC架构**  
首先MVC指的是Model-View-Controller，分别代表着模型层、视图层、控制器。

**Model**（模型层），主要管理的是业务模型的数据和处理数据的逻辑。

**View**（视图层）主要是接收用户的交互请求并展示数据信息给用户。

**Controller**（控制器层）主要担任的是Model和View之间的桥梁，用于控制程序的流程。Controller负责确保View可以访问到需要显示的Model对象的数据，View接收到用户的交互请求之后，会将请**求转发给控制器，控制器解析请求之后，会交给对应的Model处理。**

**MVVM架构**  
MVVM架构指的是**Model-View-ViewModel**，我们可以看到MVVM架构和MVC架构的区别在于有一个**ViewModel**部分，首先我们要知道在已经有了MVC架构的时候，为什么还要衍生出MVVM架构，这是因为View中很多控件的数据类型和Model中的属性不相同，例如Model中的时间数据可能是一串数字，View想要展示成日期的格式，这就需要一种转化，这个转换如果放在View不合适，因为View中不应该出现逻辑代码，放在Model中也不合适，这回导致Model臃肿庞大，因为这种问题的存在诞生了ViewModel，这一层可以帮助View转化为相应的数据给Model或者从Model中转化成View可以显示的内容。

**Vue和React的区别是什么？**  
**一、核心思想不同**  
Vue的核心思想是尽可能的降低前端开发的门槛，是一个灵活易用的渐进式双向绑定的MVVM框架。

React的核心思想是声明式渲染和组件化、单向数据流，React既不属于MVC也不属于MVVM架构。

React1：声明式是什么意思？  
声明式与之相对应的是命令式，命令式指的是通过DOM操作一步步把网页变成想要的样子，而声明式则是只需要通过状态去形容最后的网页长什么样子即可。

React2：组件化是什么意思？  
组件化指的是尽可能的将页面拆分成一个个较小的、可以复用的组件，这样让我们的代码更加方便组织和管理，并且拓展性页更强。

React3：如何理解React的单向数据流？  
React的单向数据流指的是数据主要从父节点通过props传递到子节点，如果顶层某个props改变了，React会重新渲染所有的子节点，但是单向数据流并非单向绑定，React想要从一个组件去更新另一个组件的状态，需要进行状态提升，即将状态提升到他们最近的祖先组件中，触发父组件的状态变更，从而影响另一个组件的显示。单向数据流的好处是能够保证状态改变的可追溯性，假如，父组件维护了一个状态，子组件如果能够随意更改父组件的状态，那么各组件的状态改变就会变得难以追溯。

**二、组件写法上不同**  
Vue的组件写法是通过template的单文件组件格式。

React的组件写法是JSX+inline style，也就是吧HTML和CSS全部写进JavaScript中。

**三、Diff算法不同**  
**Diff算法前置知识：虚拟DOM**

**虚拟Dom，其实很简单，就是一个用来描述真实Dom的对象**

**它有六个属性，sel表示当前节点标签名，data内是节点的属性，children表示当前节点的其他子标签节点，elm表示当前虚拟节点对应的真实节点（这里暂时没有），key即为当前节点的key，text表示当前节点下的文本，结构类似这样。**

let vnode = {
        sel: 'ul', 
        data: {},
        children: [ 
            {
                sel: 'li', data: { class: 'item' }, text: 'son1'
            },
            {
                sel: 'li', data: { class: 'item' }, text: 'son2'
            },    
        ],
        elm: undefined,
        key: undefined,
        text: undefined
    }

在了解Diff算法之前，我们首先要知道什么是虚拟DOM，虚拟DOM是一个用来描述真实DOM的对象，本质是对象。

**什么是Diff算法?**  
Diff算法是一种对比算法，主要是对比旧的虚拟DOM和新的虚拟DOM，找出发生更改的节点，并只更新这些接地那，而不更新未发生变化的节点，从而准确的更新DOM，减少操作真实DOM的次数，提高性能。

Diff算法是深度优先还是广度优先？时间复杂度是多少？  
**Diff算法是深度优先算法，时间复杂度是O(n³)。**

## 传统Diff算法 ##

> 处理方案: 循环递归每一个节点

*传统diff*

![c297eb7dd1054990856c505eb3cc0927.png][]

如上所示, 左侧树a节点依次进行如下对比:

> a->e、a->d、a->b、a->c、a->a

之后左侧树其它节点b、c、d、e亦是与右侧树每个节点对比, 算法复杂度能达到O(n^2)

查找完差异后还需计算最小转换方式，这其中的原理我没仔细去看，最终达到的算法复杂度是O(n^3)

> 将两颗树中所有的节点一一对比需要O(n²)的复杂度，在对比过程中发现旧节点在新的树中未找到，那么就需要把旧节点删除，删除一棵树的一个节点(找到一个合适的节点放到被删除的位置)的时间复杂度为O(n),同理添加新节点的复杂度也是O(n),合起来diff两个树的复杂度就是O(n³)

**(优化的)diff三点策略:**

*  web UI中DOM节点跨层级的移动操作特别少，可以忽略不计。
 *  拥有相同类型的两个组件将会生成相似的树形结构，拥有不同类型的两个组件将会生成不同树形结构。
 *  对于同一层级的一组自节点，他们可以通过唯一id进行区分。

> 即, 比较只会在同层级进行, 不会跨层级比较

## React优化Diff算法 ##

> 基于以上优化的diff三点策略，react分别进行以下算法优化

*  tree diff
 *  component diff
 *  element diff

tree diff

react对树的算法进行了分层比较。react 通过 updateDepth对Virtual Dom树进行层级控制，只会对相同颜色框内的节点进行比较，即同一个父节点下的所有子节点。当发现节点不存在，则该节点和其子节点都会被删除。这样是需要遍历一次dom树，就完成了整个dom树的对比

*分层比较 img*

![3aa6f23ecc3f4093988ad82e99ec2b1e.png][]

如果是跨层级的移动操作，如图

*跨层级操作 img*

![6323e1dd9e8945bfbb80bdf4e54cfda7.png][]

当根结点发现A消失了，会删除掉A以及他的子节点。当发现D上多了一个A节点，会创建A（包括其子节点）节点作为子节点

所以：当进行跨层级的移动操作，react并不是简单的进行移动，而是进行了删除和创建的操作，这会影响到react性能。所以要尽量避免跨层级的操作。（例如：控制display来达到显示和隐藏，而不是真的添加和删除dom）

component diff

*  如果是同类型的组件，则直接对比virtual Dom tree
 *  如果不是同类型的组件，会直接替换掉组件下的所有子组件
 *  如果类型相同，但是可能virtual DOM 没有变化，这种情况下我们可以使用shouldComponentUpdate() 来判断是否需要进行diff

*component vs img*

![eebaf568321041589d9f611be317c4c4.png][]

如果组件D和组件G，如果类型不同，但是结构类似。这种情况下，因为类型不同，所以react会删除D，创建G。所以我们可以使用shouldComponentUpdate()返回false不进行diff。

针对react15, 16出了新的生命周期

所以：component diff 主要是使用shouldComponentUpdate() 来进行优化

element diff

element diff 涉及三种操作：插入，移动，删除

*不使用key的情况 img*

![067c0a17a586454fae5f9c64f85d9b98.png][]

不使用key的话，react对新老集合对比，发现新集合中B不等于老集合中的A，于是删除了A，创建了B，依此类推直到删除了老集合中的D，创建了C于新集合。=

酱紫会产生渲染性能瓶颈，于是react允许添加key进行区分

*使用key的情况 img*![075a03d34e2f42a2b9c888a52ce7685b.png][]

react首先对新集合进行遍历，for( name in nextChildren),通过唯一key来判断老集合中是否存在相同的节点，如果没有的话创建，如果有的话，if (preChild === nextChild ) 进行移动操作

**移动优化**  
在移动前，会将节点在新集合中的位置和在老集合中lastIndex进行比较，如果if (child.\_mountIndex < lastIndex) 进行移动操作，否则不进行移动操作。这是一种顺序移动优化。只有在新集合的位置 小于 在老集合中的位置 才进行移动。

如果遍历的过程中，发现在新集合中没有，但是在老集合中的节点，会进行删除操作

所以：element diff 通过唯一key 进行diff 优化。

总结：  
1.react中尽量减少跨层级的操作。 2.可以使用shouldComponentUpdate() 来避免react重复渲染。 3.添加唯一key，减少不必要的重渲染

## **Vue的Diff算法** ##

下面是Vue的diff算法的主要流程：

![2880b5c493884a13abb07523c237aa72.png][]

当**数据**发生变化的时候，会触发**setter**，然后通过**Dep**类的notify方法去通知所有的订阅者Watcher，订阅者会调用patch方法。

**patch**方法会通过sameVnode方法来判断当前同层的虚拟节点**是否**是同一种类型的节点，如果**是**则调用patchVnode方法，**不是**则直接替换成新的节点。  
如果是**同一类型**的节点，patchVnode会首先找到节点对应的真实DOM，然后判断**新旧节点**是否是指向的**同一个对象**，如果**是**则直接**return**。

如果不是则判断**文本节点**是否相等，不相等则将真实DOM的文本节点改为新节点的文本内容，然后看旧节点和新节点的子节点的关系，如果旧的有新的没有，则删除真实DOM的子节点，如果新有旧没有，则将虚拟节点真实化之后，添加上去，如果二者都有子节点则执行updateChildren函数比较子节点。

function patch (oldVnode, vnode) {
        // some code
        if (sameVnode(oldVnode, vnode)) {
            patchVnode(oldVnode, vnode)      //当结构一致时执行patchvnode函数
        } 
       else {//当结构不一样时执行的操作就简单多了，将之前的文本节点替换掉就行
            const oEl = oldVnode.el // 当前oldVnode对应的真实元素节点
            let parentEle = api.parentNode(oEl)  // 父元素
            createEle(vnode)  // 根据Vnode生成新元素
            if (parentEle !== null) {//判断父元素是否为空
                api.insertBefore(parentEle, vnode.el, api.nextSibling(oEl)) // 将新元素添加进父元素
                api.removeChild(parentEle, oldVnode.el)  // 移除以前的旧元素节点
                oldVnode = null //解除全局变量的引用，回收内存
            }
        }
        // some code 
        return vnode //最后更新虚拟dom
    }

那么接下来就分析结构一致的情况，那么什么情况下结构是一致的呢，看一下samevnode源码

function sameVnode (a, b) {
      return (
        a.key === b.key &&  // key值一致
        a.tag === b.tag &&  // 标签名一致
        a.isComment === b.isComment &&  // 是否都为注释节点
        // 是否都定义了data，data包含一些具体信息，例如onclick , style
        isDef(a.data) === isDef(b.data) &&  
        sameInputType(a, b) // 当标签是<input>的时候，type必须相同
      )
    }

那这些都一致了的话我们就要看他们的内容（文本）和子节点了

patchVnode (oldVnode, vnode) {
        const el = vnode.el = oldVnode.el
        let i, oldCh = oldVnode.children, ch = vnode.children
        if (oldVnode === vnode) return  //如果两个节点完全一样就直接return
        if (oldVnode.text !== null && vnode.text !== null && oldVnode.text !== vnode.text) {
            api.setTextContent(el, vnode.text) //如果是文本节点当两个节点的文本不为空并且不相等是，直接替换
        }else {
            updateEle(el, vnode, oldVnode)
            if (oldCh && ch && oldCh !== ch) {
                updateChildren(el, oldCh, ch)
            }else if (ch){
                createEle(vnode) //create el's children dom
            }else if (oldCh){
                api.removeChildren(el)
            }
        }
    }

当文本内容不同是直接替换，之后做了如下事情

*  找到对应的真实dom，称为`el`
 *  判断`Vnode`和`oldVnode`是否指向同一个对象，如果是，那么直接`return`
 *  如果他们都有文本节点并且不相等，那么将`el`的文本节点设置为`Vnode`的文本节点。
 *  如果`oldVnode`有子节点而`Vnode`没有，则删除`el`的子节点
 *  如果`oldVnode`没有子节点而`Vnode`有，则将`Vnode`的子节点真实化之后添加到`el`
 *  如果两者都有子节点，则执行`updateChildren`函数比较子节点，这一步很重要

**updateChildren**方法的核心对比思路就是通过首尾指针的方法进行对比。

updateChildren (parentElm, oldCh, newCh) {
        let oldStartIdx = 0, newStartIdx = 0
        let oldEndIdx = oldCh.length - 1
        let oldStartVnode = oldCh[0]
        let oldEndVnode = oldCh[oldEndIdx]
        let newEndIdx = newCh.length - 1
        let newStartVnode = newCh[0]
        let newEndVnode = newCh[newEndIdx]
        let oldKeyToIdx
        let idxInOld
        let elmToMove
        let before //四个指针
        while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) { //四个指针往中间走，
    //当开始和结束指针位置相反时，表示有一个vnode已经走完了跳出循环
            if (oldStartVnode == null) {   // 后面用key值时会将已经移动的vnode用null替换，所以这里
    //如果遇到了只要将指针往后面移动就行
                oldStartVnode = oldCh[++oldStartIdx] 
            }else if (oldEndVnode == null) {
                oldEndVnode = oldCh[--oldEndIdx]
            }else if (newStartVnode == null) {
                newStartVnode = newCh[++newStartIdx]
            }else if (newEndVnode == null) {
                newEndVnode = newCh[--newEndIdx]
            }else if (sameVnode(oldStartVnode, newStartVnode)) { 
                patchVnode(oldStartVnode, newStartVnode)
                oldStartVnode = oldCh[++oldStartIdx]
                newStartVnode = newCh[++newStartIdx]
     //头指针和头指针比较如果相同调用patchVnode（）这里会有递归知道把后面的更新完才会return，
    //最简单的情况是两个内容相同直接return，之后两个头指针往中间走
            }else if (sameVnode(oldEndVnode, newEndVnode)) {
                patchVnode(oldEndVnode, newEndVnode)
                oldEndVnode = oldCh[--oldEndIdx]
                newEndVnode = newCh[--newEndIdx]
    //同理之后两个尾指针往中间走
            }else if (sameVnode(oldStartVnode, newEndVnode)) {
                patchVnode(oldStartVnode, newEndVnode)
                api.insertBefore(parentElm, oldStartVnode.el, api.nextSibling(oldEndVnode.el))
                oldStartVnode = oldCh[++oldStartIdx]
                newEndVnode = newCh[--newEndIdx]
    //这里的比较会很大的提升性能，将oldvnode的头指针和newnode的尾指针调用patchvonde（），这里和上面
    //也是一样的，不同的是这里会在真实dom上将返回的vnode从之前的位置到oldEndVnode指针对应的节点之前，
    //之后相同的key值的指针往前面走
            }else if (sameVnode(oldEndVnode, newStartVnode)) {
                patchVnode(oldEndVnode, newStartVnode)
                api.insertBefore(parentElm, oldEndVnode.el, oldStartVnode.el)
                oldEndVnode = oldCh[--oldEndIdx]
                newStartVnode = newCh[++newStartIdx]
    //这里会在真实dom上将返回的vnode插入到oldStartVnode指针对应的节点之前
            }else {
               // 当前面所用情况都没有时就使用key比较，那newvnode的当前头索引在oldvnode的key值里面找
                if (oldKeyToIdx === undefined) {
                    oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx)
     // 有key生成index表
                }
                idxInOld = oldKeyToIdx[newStartVnode.key]
                if (!idxInOld) {
                    api.insertBefore(parentElm, createEle(newStartVnode).el, oldStartVnode.el)
                    newStartVnode = newCh[++newStartIdx]
    //如果新的vnode中的key值在oldvode中不存在，则真实dom的在oldStartVnode前插入现在的newvnode节点，
    //指针向后
                }
                else {
                    elmToMove = oldCh[idxInOld]
                    if (elmToMove.sel !== newStartVnode.sel) {
                        api.insertBefore(parentElm, createEle(newStartVnode).el, oldStartVnode.el)
                    }else {
                        patchVnode(elmToMove, newStartVnode)
                        oldCh[idxInOld] = null
                        api.insertBefore(parentElm, elmToMove.el, oldStartVnode.el)
                    }
                    newStartVnode = newCh[++newStartIdx]
                }
    //如果存在则在真实dom的oldStartVnode前插入该节点，并将oldvnode的值设置为null，索引后移
            }
        }
        if (oldStartIdx > oldEndIdx) {
            before = newCh[newEndIdx + 1] == null ? null : newCh[newEndIdx + 1].el
            addVnodes(parentElm, before, newCh, newStartIdx, newEndIdx)
    //如果oldvnode里面头索引大于尾索引，说明newVnode里面还有节点，这时需要将newvnode里头索引到尾索引
    //的node添加到真实dom中
        }else if (newStartIdx > newEndIdx) {
            removeVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx)
        }
    //反之说明需要将oldvnode中多余的值删掉
    }

过程可以概括为：oldCh和newCh各有两个头尾的变量StartIdx和EndIdx，它们的2个变量相互比较，一共有4种比较方式。如果4种比较都没匹配，如果设置了key，就会用key进行比较，在比较的过程中，变量会往中间靠，一旦StartIdx>EndIdx表明oldCh和newCh至少有一个已经遍历完了，就会结束比较

![f83a65709f3f470b968f113c106a25a9.png][]

下面是从别处看到的例子

![format_png][]

![format_png 1][]

![format_png 2][]

![format_png 3][]

**React的diff和Vue的diff算法的不同之处**  
vue和react的diff算法都是进行同层次的比较，主要有以下两点不同：

vue对比节点，如果节点元素类型相同，但是className不同，认为是不同类型的元素，会进行删除重建，但是react则会认为是同类型的节点，只会修改节点属性。  
vue的列表比对采用的是首尾指针法，而react采用的是从左到右依次比对的方式，当一个集合只是把最后一个节点移动到了第一个，react会把前面的节点依次移动，而vue只会把最后一个节点移动到最后一个，从这点上来说vue的对比方式更加高效。

**四、响应式原理不同**  
React的响应式原理  
React主要是通过setState()方法来更新状态，状态更新之后，组件也会重新渲染。

Vue的响应式原理  
vue会遍历data数据对象，使用Object.definedProperty()将每个属性都转换为getter和setter，每个Vue组件实例都有一个对应的watcher实例，在组件初次渲染的时候会记录组件用到了那些数据，当数据发生改变的时候，会触发setter方法，并通知所有依赖这个数据的watcher实例调用update方法去触发组件的compile渲染方法，进行渲染数据。

###  ###

[c297eb7dd1054990856c505eb3cc0927.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/dd03b50b99684d7b9636b7e95e4d3241.png
[3aa6f23ecc3f4093988ad82e99ec2b1e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/498c92f3f07b45088ce0830233769906.png
[6323e1dd9e8945bfbb80bdf4e54cfda7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/618e4b09c4624bf3a9ab5dc97db21c21.png
[eebaf568321041589d9f611be317c4c4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/6e4a85c370644cb089bb25d54794aa26.png
[067c0a17a586454fae5f9c64f85d9b98.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/6489982bb2344bbba2ee740606604ea6.png
[075a03d34e2f42a2b9c888a52ce7685b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/0c338eeeeede49e2a2878d36691f1a25.png
[2880b5c493884a13abb07523c237aa72.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/a729b33505004d47959c78781b685a46.png
[f83a65709f3f470b968f113c106a25a9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/3b95a0253590427c94fbfa7b41103e90.png
[format_png]: https://img-blog.csdnimg.cn/img_convert/a8ff9d042eac67fa627a5012d0ffcfa7.webp?x-oss-process=image/format,png
[format_png 1]: https://img-blog.csdnimg.cn/img_convert/1d9058cb2312fb70c45afcab0fcbcd8c.webp?x-oss-process=image/format,png
[format_png 2]: https://img-blog.csdnimg.cn/img_convert/52186e07964d4fb7f18e793d3dde1514.webp?x-oss-process=image/format,png
[format_png 3]: https://img-blog.csdnimg.cn/img_convert/7204ec39a907f191800d1cc73e3ed059.webp?x-oss-process=image/format,png