我们都知道的一件事,就是vue和react框架,核心算法都是diff算法,啥叫diff算法可能有一部分人都是没有深究的,今天梳理一下vue和react的diff算法,也说一下有啥区别

什么叫虚拟dom,就是原本我们在页面上展示的dom结构叫做dom树,我们把数据和将要渲染的代码模拟dom结构生成的对象类型的数据结构,就叫虚拟dom树,将真实的DOM的数据抽取出来，以对象的形式模拟树形结构,我们先根据真实DOM生成一颗 virtual DOM ，当 virtual DOM 某个节点的数据改变后会生成一个新的 Vnode ，然后 Vnode 和 oldVnode 作对比，发现有不一样的地方就直接修改在真实的DOM上，然后使 oldVnode 的值为 Vnode 。

1.啥叫diff算法

• 原始的diff算法

1. 最初始的diff算法其实就是遍历循环比较,这里我就不画图了,简单的说一下,很重要,首先肯定要理解啥叫diff算法,然后才知道vue和react的diff算法是怎么做的优化
2. 原始diff算法就是,两个虚拟dom树,进行逐一对比,而且是不分层级的,就是说什么呢,如果是一个虚拟dom树,从根节点到以后分支的每一个节点,都要单独拿出来跟新生成的节点做比较,这就是最原始的diff算法,这个diff算法的时间复杂度是O(n ^3),表面上看是(n ^2),因为单独一个个的去跟另外的n个相比较,肯定是n ^2次就比较结束了,但是实际上不是的,比较完之后我们还要计算如何在最优的地方放置最佳的节点,所以就是O(n ^3)了,实际上我们从算法层面来看,原始的diff算法从功能上是解决了先对比再处理实际dom的需求,但是实际上我们的流程变得更加的复杂和笨拙

2.优化的diff算法

1. 这里其实要说一下就是vue和react的diff算法都是优化过的diff算法,而且有着相同的优化点,就是同级比较,不做跨级比较
2. 就是我们分析可以发现,在实际的web展示中,非同级的节点移动是非常少的,所以我们选择做同级比较
3. 同级比较的解释就是:只比较同层的节点，不同层不做比较。不同层的只需要删除原节点，并且新建插入更新节点
   
4. 这个是我在网上看到的图片,我实在是懒的画,如有侵权请联系我删除,简单来讲就是图上所说的,树结构是有层级的,那么新老树结构都是可以对比的,对比之后会进行实际的dom操作,也就减少了改变数据产生的整体回流或重绘

3.vue的diff算法

1. vue的diff算法是父子兄弟组件互不干扰的,所谓的互不干扰,就是说
   1.当父组件data修改的时候(非传递props值),子组件是不会自动更新的
   2.更新某个组件data中的数据时,兄弟组件是不更新的
   3.当更新子组件data中的数据时,父组件不更新
   4.当更新父组件传递给子组件的props变化时,子组件（第一级子组件）更新
2. vue的diff算法的比较规则:新旧列表的两端对比
   1.使用旧列表的头一个节点oldStartNode与新列表的头一个节点newStartNode对比
   2.使用旧列表的最后一个节点oldEndNode与新列表的最后一个节点newEndNode对比
   3.使用旧列表的头一个节点oldStartNode与新列表的最后一个节点newEndNode对比
   4.使用旧列表的最后一个节点oldEndNode与新列表的头一个节点newStartNode对比
   5.当前四个比较规则都失效的时候,把新列表的第一个节点newStartNode对旧列表进行循环遍历对比
3. vue的diff算法的移动规则:不同情况的移动规则不同
   1.当旧列表的头一个节点oldStartNode与新列表的头一个节点newStartNode对比时key相同,那么旧列表的头指针oldStartIndex与新列表的头指针newStartIndex同时向后移动一位,dom不动
   2.当旧列表的最后一个节点oldEndNode与新列表的最后一个节点newEndNode对比时key相同,那么旧列表的尾指针oldEndIndex与新列表的尾指针newEndIndex同时向前移动一位,dom不动
   3.当旧列表的头一个节点oldStartNode与新列表的最后一个节点newEndNode对比时key相同,那么旧列表的头指针oldStartIndex向后移动一位,新列表的尾指针newEndIndex向前移动一位,插入到旧列表的newEndNode所对应的dom后边
   4.当旧列表的最后一个节点oldEndNode与新列表的头一个节点newStartNode对比时key相同,那么旧列表的尾指针oldEndIndex向前移动一位,新列表的头指针newStartIndex向后移动一位,插入到就列表的oldStartIndex所对应的dom前边
   5.1.如果在旧节点列表找到了,相应的DOM移动后,由咱们将旧列表中的节点改成undefined,这是相当重要的一步,由于咱们已经作了节点的移动了因此咱们不须要进行再次的对比了,最后咱们将头指针newStartIndex向后移一位
   5.2.如果没有在旧节点列表找到,那么直接建立一个新的节点放到最前面就能够了，而后后移头指针newStartIndex

因为对比规则非常的重要,这点完全决定了是否能可以真正理解vue的diff算法,所以这里我解释一下具体的对比规则,对比上图我们看到,刚进来就要进行最基础的1234步骤对比,我们分两种情况来看接下来的走向

1. 第一种是四种里边有对比成功的:那么我们就会把对比成功的那个旧节点和新节点的指针都向临近的元素进行一个移动,这里具体是什么意思呢,就是说当前旧节点和新节点已经有了相匹配的,我们进行了真实dom的操作之后,我们需要做的就是移动指针,这四个指针是依旧要进行比较的
2. 第二种就是没匹配到这四种情况,那么就需要我们拿当前的newStartNode指针指到的节点去跟旧节点列表中的所有节点去遍历比较,比较之后找到了匹配的旧节点的话,就把当前找到的旧节点所对应的dom移动到开头,然后把找到的旧节点设置成undefined,如果找不到,我们就在当前旧节点列表的oldStartIndex处创建新dom且插入,而且把newStartNode指针向后移动,设置成undefined的原因就是我们已经把当前找到的这个旧节点所对应的dom进行了处理,那么随着我们指针进行移动接着对比的时候,就要跳过已经被处理过的节点了
3. 总体来说就是我们拿新节点列表的首位和末尾去和旧列表的首位末尾依次对比,如果对比上了,就进行操作,如果没有对比上,我们就遍历处理新节点,直到对比上了或者处理好了新节点列表的首位,我们就会接着按照原逻辑去处理,比直接拿着一个个去遍历,多了一个首尾两端对比,避免了第一个和最后一个对上需要遍历所有的尴尬境地

4.react的diff算法

1. react的diff算法对父子兄弟组件的影响
   1.当更新父组件state中的数据时,父组件以及子组件和所有的子孙组件都会被更新,这个可以通过shouldComponentUpdate来优化解决
   2.更新某个组件,兄弟组件不更新
   3.当更新子组件,父组件不更新
2. react的diff算法的三种策略
   1.tree diff:这个跟vue的对比规则一样,也就是同级策略,只进行同级的对比
   2.component diff:
   同一类型的组件，按原策略（层级比较）
   同一类型的组件，a变化时，虚拟DOM没有变，可以在这里进行shouldComponentUpdate操作
   如果被判定为不同类型的组件，删除原组件，构建新组件
   3.element diff:
   元素的diff就是有差别的地方了,react采用的是比较vue而言更加简洁的对比方式,就是同级遍历,拿着新节点列表的节点一个个与旧节点列表做遍历对比,当对比成功的时候,就把旧节点插入到真实dom中当前新节点位置对应的真实dom的前边,若是没有找到对应的,就要在新节点所对应的真实dom的地方插入一个节点
   
   如图所示,就要对c/d进行移位操作,这也是react的diff算法的弊端,当首位新节点与末尾老节点相对应的时候,就会导致多个节点进行移位,结果是相同的,但是中间的比较计算以及操作时不友好的
   当所有的新节点都已经遍历对比完成之后,还有旧节点未参与对比的,遍历删除真实dom就可以了

5.vue与react的diff比较

1. vue和react的diff算法，都是忽略跨级比较，只做同级比较。vue diff时调动patch函数，参数是vnode和oldVnode，分别代表新旧节点。
2. vue对比节点。当节点元素相同，但是classname不同，认为是不同类型的元素，删除重建，而react认为是同类型节点，只是修改节点属性。
3. vue的列表对比，采用的是两端到中间比对的方式，而react采用的是从左到右依次对比的方式。当一个集合只是把最后一个节点移到了第一个，react会把前面的节点依次移动，而vue只会把最后一个节点移到第一个

总结:

1. react-diff: 遍历法对比
2. vue-diff: 双端对比
3. 总体来讲vue的diff算法更佳,总体规律就是找到新节点所对应的旧节点列表中的节点,而后给真实的对应的dom移动到正确的位置
4. vue3.0的diff算法还没有梳理过,以后可以在说vue3.0其他东西的时候带上,一些更改的地方该了解的还是要了解的