前置知识

在解说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能够有更好、更平滑的烘托、动画和交互响应

图解DIFF算法介绍

为什么需求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判别

流程图

图解DIFF算法介绍

多节点处理流程

图解DIFF算法介绍

  • 首先会从左往右遍历新节点进行判别判别，直到遇到不相同的节点方位完毕，如图A是相同的所以不需求动

react在乱序的状况下会寻找在新结构和老结构节点顺序一向的来复用，从图中咱们能够发现，[C，E]和[C，D]不移动其他元素移动能够完成咱们想要的作用，那咱们挑选那个呢？react的策略是匹配到第一个元素后，以它为参阅，遍历剩下元素只要和它在旧节点上是正序的，就不需求移动，然后再以新找到的节点作为参阅，持续遍历，假如和参阅点在旧节点上不是正序摆放的，就需求移动。react是经过lastPlacedIndex来记录这个参阅点下标的

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

图解DIFF算法介绍

  • C和B明显不一致，此刻完毕遍历，创立一个根据旧节点的map映射用来做匹配，一起创立一个浮标（lastPlacedIndex）用来存储上一个不需求移动的下标，默认为0

图解DIFF算法介绍

  • 在上面断开的循环方位持续循环新节点进行判别，此刻发现C在Map内能匹配到，所以将以C为参阅，将lastPlacedIndex设置为C的下表2，一起在Map内删去C（防止被重复匹配）

图解DIFF算法介绍

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

图解DIFF算法介绍

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

图解DIFF算法介绍

  • G在Map内无法匹配到所以符号为新增，D符号为移动（4>3）
  • 一起将Map内没有被匹配的F顺次符号为删去

至此咱们整个查找进程就完了，一起已经能够知道哪些存在副作用，后续react会将这些有副作用的节点搜集起来在commit阶段遍历他们并将页面更新到最新状态

细心想想应该会发现react这种记录下标的方法有一个问题，如下图所示假如最终一个节点移动到了十分靠前的方位，理想状态下操作最少的方法应该是直接将D移动到A前面，可是现实却是D不动，A、B、C顺次往后刺进

图解DIFF算法介绍

vue独特的diff算法却不会有上面这种状况，虽然了解起来更杂乱但他却能够真实的最大程度的复用，接下来咱们再看看vue3是怎么完成的

VUE3.0 DIFF判别

流程图

图解DIFF算法介绍

有KEY的节点处理流程

图解DIFF算法介绍

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

图解DIFF算法介绍

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

图解DIFF算法介绍

  • 遍历剩下乱序的新节点，生成一个根据新节点的key和其索引的映射keyToNewIndexMap，一起生成一个长度为剩下节点长度的数组newIndexToOldIndexMap，默认值为0，代表没有匹配过，需求新增

图解DIFF算法介绍

  • 开端遍历剩下旧节点一起拿旧节点的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]
  • 剩下的是处理移动了，可是处理移动分两种状况，咱们先将最简单的一种：

图解DIFF算法介绍

  • 比方咱们有上图这种结构，肉眼可见，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的时分，此刻就需求核算哪些需求移动：

图解DIFF算法介绍

  • 经过最长递增子序列的算法求解出数组[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 算法