diff算法原理 、 Vue、React区别

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

如上所示, 左侧树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

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

跨层级操作 img

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

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

component diff

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

component vs img

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

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

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

element diff

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

不使用key的情况 img

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

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

使用key的情况 img

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算法的主要流程：

当数据发生变化的时候，会触发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至少有一个已经遍历完了，就会结束比较

下面是从别处看到的例子

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渲染方法，进行渲染数据。