图解DIFF算法介绍

前置知识

在讲解DIFF前我们需要先介绍下，DIFF算法是针对两颗Virtual DOM进行的对比，查找其中的差异，然后根据差异性来更新页面；其特性是深度优先，同层级比较

什么是Virtual DOM

Virtual DOM是真实DOM的一个轻量级副本，包含着当前DOM的基本结构和信息，它是现阶段MVVM框架可以如此快捷高效更新和渲染的最主要基石，通过差异计算可以做到在大量的、频繁的数据更新下能够对视图进行合理的高效的更新(细粒度的精准修改)，减少对操作无用DOM所带来的性能消耗

React在15及以前版本通过虚拟DOM树来存储旧的DOM结构，自16开始，改为Fiber这种节点之间关系更加明确的数据结构来存储DOM树结构（另一种虚拟DOM的表现形式），并在更新时和新生成虚拟DOM做DIFF计算，React Fiber的出现使实现异步渲染和任务优先级调度变得简单，协助React可以有更好、更平滑的渲染、动画和交互响应

为什么需要Virtual DOM，需要DIFF？

• DOM节点是一个超重量级的对象，每次创建它对性能的消耗都比较大，因此有效地复用已有DOM，减少DOM操作在复杂视图情况下能有效提升性能
• 作为真实DOM渲染与JS处理之间的缓冲区，短时间内，对大量DOM操作进行合并统一处理，减少reflow和repaint的触发次数
• 如果没有DIFF，React在数据变化后如果想实现页面更新只能通过重新渲染整个应用来展示最新效果，在只变更页面某行数据的情况下重新渲染整个页面无疑是对资源的大量浪费
• 为跨平台提供了解决方案

Virtual DOM的实现比直接操作DOM要快？

答案是否定的，网上都说操作真实 DOM 慢这篇文章尤雨溪对此问题从多方面进行了解释，有兴趣可以好好拜读下

DIFF和页面渲染是如何配合的？

vue及react15以前，副作用收集和渲染会交替执行的，而副作用收集就是在进行DIFF运算

react16后则改为分两步执行，Reconciler（协调器）和Renderer（渲染器）

• Reconciler阶段会先打effectTag标记（此步就是在进行DIFF运算）然后收集所有需要变更的fiber
• Renderer阶段进行渲染，

如何判断节点是否需要复用

节点类型（type）和唯一标识（key）是判断一个节点是否能够复用的判断依据，如果type相同，key不存在，则也会进行复用的逻辑处理;

DIFF算法介绍

diff的核心就是找到尽可能多的节点进行复用，因此如何在旧的结构里找到可以复用的结构是算法的关键；对于新节点是单节点、文本节点、空节点的情况，比较简单直接对比替换或者删除就可以，我们主要看其核心的多节点算法，也就是复杂结构下如何去处理。

React DIFF判断

流程图

多节点处理流程

• 首先会从左往右遍历新节点进行判断判断，直到遇到不相同的节点位置结束，如图A是相同的所以不需要动

react在乱序的情况下会寻找在新结构和老结构节点顺序一直的来复用，从图中我们可以发现，[C，E]和[C，D]不移动其他元素移动可以实现我们想要的效果，那我们选择那个呢？react的策略是匹配到第一个元素后，以它为参考，遍历剩余元素只要和它在旧节点上是正序的，就不需要移动，然后再以新找到的节点作为参考，继续遍历，如果和参考点在旧节点上不是正序排列的，就需要移动。react是通过lastPlacedIndex来记录这个参考点下标的

如下图，C能够匹配到，所以以C为参考，在旧节点上是正序的节点就是E，所以E不需要动，B和D虽然能匹配到但是和E不是不是正序

• C和B明显不一致，此时结束遍历，创建一个基于旧节点的map映射用来做匹配，同时创建一个浮标（lastPlacedIndex）用来存储上一个不需要移动的下标，默认为0

• 在上面断开的循环位置继续循环新节点进行判断，此时发现C在Map内能匹配到，所以将以C为参考，将lastPlacedIndex设置为C的下表2，同时在Map内删除C（防止被重复匹配）

• E也能在Map内匹配到，同时E在C的后面（4>2）,所以E不需要动，同时将lastPlacedIndex设置为4，在Map内删除C

• B虽然也能在Map内匹配到，但是B在旧节点内排在了E前面（4>1），所以B需要标记为移动

• G在Map内无法匹配到所以标记为新增，D标记为移动（4>3）
• 同时将Map内没有被匹配的F依次标记为删除

至此我们整个查找过程就完了，同时已经可以知道哪些存在副作用，后续react会将这些有副作用的节点收集起来在commit阶段遍历他们并将页面更新到最新状态

仔细想想应该会发现react这种记录下标的方式有一个问题，如下图所示如果最后一个节点移动到了非常靠前的位置，理想状态下操作最少的方式应该是直接将D移动到A前面，但是现实却是D不动，A、B、C依次往后插入

vue独特的diff算法却不会有上面这种情况，虽然理解起来更复杂但他却能够真正的最大程度的复用，接下来我们再看看vue3是如何实现的

VUE3.0 DIFF判断

流程图

有KEY的节点处理流程

• 先从头开始遍历，直到遇到无法匹配的节点为止

• 再从尾部开始遍历，直到遇到无法匹配的节点为止，此时就剩下了中间看起来杂乱无章的乱序节点

• 遍历剩余乱序的新节点，生成一个基于新节点的key和其索引的映射keyToNewIndexMap，同时生成一个长度为剩余节点长度的数组newIndexToOldIndexMap，默认值为0，代表没有匹配过，需要新增

• 开始遍历剩余旧节点同时拿旧节点的key去和keyToNewIndexMap做匹配，如果匹配不到就把当前节点删除，否则就将当前旧节点索引放置在数组newIndexToOldIndexMap的对一个位置（源码为了防止0代表实际索引，会将所有匹配到的下标+1）
• 如果，旧节点B在新节点内可以找到，那么就会将旧节点B的索引1放置在数组newIndexToOldIndexMap对应的B的位置，数组就变成了[0,0,0,1+1,0]，旧节点C在新节点也可以找到，将C的索引3放在数组内变成了[3+1,0,0,1+1,0],以此类推，最后数组变成了[4,6,0,2,5]
• 剩下的是处理移动了，但是处理移动分两种情况，我们先将最简单的一种：

• 比如我们有上图这种结构，肉眼可见，B、C、D不需要移动，只需要插入E和G就可以了，为了实现这个操作，会定义两个变量maxNewIndexSoFar=0和moved=false，同时遍历旧节点；maxNewIndexSoFar代表的是当前旧节点在新节点内的索引下标，一旦maxNewIndexSoFar大于前值就会将moved设置为true
  • 遍历到B的时候，B在新数组内索引是2，2>0，所以moved=false，maxNewIndexSoFar=2
  • 遍历到C的时候，C在新数组索引是3，3>2，所以moved=false，maxNewIndexSoFar=3
  • D同理，最后moved=false，maxNewIndexSoFar=4
  • 最后遍历数组newIndexToOldIndexMap，标记为0的节点需要新建，其他节点不动

第二种情况就是moved为true的时候，此时就需要计算哪些需要移动：

• 通过最长递增子序列的算法求解出数组[4,6,0,2,5]内稳定的元素，存放在increasingNewIndexSequence=[3,4]，3和4代表前面数组的索引，
  • 关于vue3最长递增子序列的详细算法说明可以看我以前的文章：最长递增子序列及vue3.0中diff算法,会详细说明如何找到最长子序列，又如何通过回溯的方式找到最长子序列的索引
• 从后往前遍历数组newIndexToOldIndexMap，在索引为第4和第3位置的节点不需要移动，其他的元素如果是0则新建，否则需要移动
  • 遍历到5时，此时它下标是4，同时和increasingNewIndexSequence最后一个一样都是4，所以此处对应的节点不需要动
  • 遍历到2时，此时它在数组下标是3，同时和increasingNewIndexSequence倒第二个一样都是3，所以此处对应的节点不需要动，并让j-1
  • 遍历到0时，代表此处对应的节点需要新建
  • 遍历到6和4时，此时increasingNewIndexSequence已经用完，就会将6和4对应的节点依次移动到对应位置，至此整个DIFF过程就算结束了

总结

两种框架都是尝试寻找到尽可能多的节点进行复用，但看起来vue的算法更加合理一些，那么为什么react不在一开始的时候使用双端对比的方式呢，对此react源码内也给了解释，大概意思就是说我们先观察react的性能，如果需要再优化的话才会取考虑，但是如果用双端对比的话也会对这种方式做进一步优化

参考

react 多节点DIFF算法逻辑官方github源码

vue3 DIFF 官方github源码

手写vue2 DIFF 算法

小红包免费领

小礼物走一走