【React】深入理解虚拟dom和diff算法
本篇文章同步发表在我的个人博客中：https://zhengyq.club
写在前面
在React中，Virtual Dom和diff的结合大大提高了渲染效率。diff算法由最初的O(n^3)复杂度变为了现在的O(n)，那么在这其中都做了哪些事情，本篇文章为你揭晓答案～
虚拟dom和diff
虚拟dom是什么？
Virtual DOM是一种编程概念。在这个概念里，UI以一种理想化的，或者说“虚拟的”表现形式被保存于内存中。在React中，render执行的结果得到的并不是真正的DOM节点，结果仅仅是轻量级的JavaScript对象。像这样：
<div class="box">
<span>111</span>
</div>
上面这段代码会转换为这样的虚拟DOM结构
{
tag: "div",
props: {
class: "box"
},
children: [
"hello world!"
]
}
diff算法又是什么？
diff算法，会对比新老虚拟DOM，记录下他们之间的变化，然后将变化的部分更新到视图上。其实之前的diff算法，是通过循环递归每个节点，然后进行对比，复杂程度为O(n^3)，n是树中节点的总数，这样性能是非常差的。
dom-diff的原理
diff算法会比较前后虚拟DOM，从而得到patches(补丁)，然后与老Virtual DOM进行对比，将其应用在需要更新的地方，得到新的Virtual DOM，在网上有一张非常直观的图可以帮忙参考
来解释下这张图：现有一个真实的DOM，首先会映射为虚拟DOM，这个时候，我们删除了最后一个p节点和son2的节点，得到了新的一个虚拟DOM，新的vdom会和旧的vdom进行差异对比，得到了pathes对象，之后，对旧的真实dom进行操作，得到了新的DOM。
diff的几种策略
Web UI中DOM节点跨层级的移动操作特别少，可以忽略不计。拥有相同类的两个组件将会生成相似的树形结构，拥有不同类的两个组件将会生成不同的树形结构。
对于同一层级的一组子节点，它们可以通过唯一
id进行区分。
基于以上三个策略，React分别对tree diff、component diff以及element diff进行了算法优化。
tree diff
基于第一个策略，react只会对同一层次的节点进行比较，如下图中，只对颜色相同框内的DOM节点进行比较，当发现节点不存在时，就会删除整个节点及其子节点，不会再进行比较，这样就只需要遍历一次，就能完成对整个DOM树的比较
如果出现了DOM节点的跨层级的移动操作，React diff会怎样呢？
React只会简单的考虑同层级节点的位置变换，对于不同层级的节点，只有创建和删除操作。如果A节点整个被移动到D节点下，根节点发现子节点中A不见了，就会销毁A；然后D 发现自己多了一个子节点，就会创建新的子节点（包含其中属于自己的子节点）作为其子节点。react diff就会按照这样的次序执行：craete a -> create b -> create c -> delete a。这种跨层级的节点移动，并不会出现移动的情况，而是会有创建、删除这些操作。这种操作会影响到React的性能，所以React官方也并不建议进行这种操作。在开发组件时，保持稳定的dom结构会有助于性能的提升
component diff
React对于组件间的比较采取的策略也是简洁高效
如果是同一类型的组件，按照原策略继续比较虚拟dom树
如果不是，则将该组件判断为
dirty component，从而替换整个组件下的所有子节点对于同一类型的组件，有可能其
Virtual DOM没有任何变化，如果能够确切的知道这点那可以节省大量的diff运算的时间，因此React允许用户通过shouldComponentUpdate()判断该组件是否需要进行diff
举个例子来说，当下图中componentD改变为componentG时，即使这两个compoent结构很相似，但是react会判断D和G并不是同类型组件，也就不会比较二者的结构了，而是直接删除了d，重新创建G及其子节点，这个时候会影响react的性能
element diff
当节点处于同一层级时，React diff提供了三种节点操作：插入、移动和删除
插入：新的
component类型不在老集合里 -> 全新的节点，需要对新节点执行插入操作移动：在老集合里有新
component类型，且element是可更新的类型，generateComponentChildren已调用receiveComponent，这种情况下prevChild=nextChild，就需要做移动操作，可以复用以前的dom节点删除：老的
component类型，在新集合中也有，但对应的element不同则不能直接复用和更新，需要执行删除操作，或者老component不在新集合里，也需要执行删除操作
举个🌰：看下图中，老集合中包含节点A、B、C、D，更新后的集合中包含节点B、A、D、C，此时进行新老集合差异化对比，发现B不等于A，则创建并插入了B至新集合，删除老集合A，以此类推。。。这样做很繁琐，因为这些都是相同的节点，只是位置发生了变化，针对这一现象，react提出了优化策略，允许开发者对同一层级的同组子节点，添加唯一key进行区分【注意：这里就体现了key的作用～】
上面我们叙述的情况是没key的情况，如果有key了(假设key为上图中每个节点对应的名字，例如节点A，对应key为A)，它就会这么对比：
diff会通过key发现新老集合中的节点是相同的节点，因此无需进行节点删除和创建，只需要将老集合中节点的位置进行移动，更新为新集合中节点的位置，此时React给出的diff结果为：B、D不做任何操作，A、C进行移动操作。
首先对新集合的节点进行循环遍历，通过唯一key可以判断新老集合中是否存在相同的节点，如果存在，则进行移动操作，但在移动前需要将当前节点在老集合中的位置与lastIndex进行比较，如果节点当前的位置<lastIndex，则进行节点移动操作，否则不执行该操作。这是一种顺序优化手段，lastIndex一直在更新，表示访问过的节点在老集合中最右的位置（即最大的位置），如果新集合中当前访问的节点比lastIndex大，说明当前访问节点在老集合中就比上一个节点位置靠后，则该节点不会影响其他节点的位置，因此不用添加到差异队列中，即不执行移动操作，只有当访问的节点比lastIndex小时，才需要进行移动操作
下面我们来说一下大致的过程（下面所说的_mountIndex是当前节点所在位置，lastIndex为参考位置）
1、从新集合中取到B，判断老集合中存在相同的节点，通过对比节点位置判读是否进行了移动操作，B在老集合中的位置为_mountIndex=1，此时lastIndex = 0，不满足child._mountIndex < lastIndex的条件，因此不对B进行移动操作；此时更新lastIndex = Math.max(prevChild._mountIndex, lastIndex)，[其中prevChild.mountIndex表示B在老集合中的位置]。lastIndex=1，并将B的位置更新为新集合中的位置prevChild._mountIndex=nextIndex，此时新集合中B._mountIndex=0，nextIndex++进入下一个节点的判断
2、从新集合中取得A，判断老集合中存在相同节点A，通过对比节点位置判断是否进行进行移动操作，A在老集合中的位置A._mountIndex=0，此时lastIndex=1，满足child.mountIndex<lastIndex的条件，因此对A进行移动操作enqueueMove(this, child._mountIndex, toIndex)，其中 toIndex 其实就是 nextIndex，表示 A 需要移动到的位置；更新 lastIndex = Math.max(prevChild._mountIndex, lastIndex)，则 lastIndex ＝ 1，并将 A 的位置更新为新集合中的位置 prevChild._mountIndex = nextIndex，此时新集合中A._mountIndex = 1，nextIndex++ 进入下一个节点的判断。
3、从新集合中取到D，判断老集合中是否存在相同节点，通过对比位置判断是否进行移动操作，D在老集合中的位置D._mountIndex=3，此时lastIndex=1，不满足child._mountIndex<lastIndex的条件，因此不对D进行移动操作；更新lastIndex=Math.max(prevChild._mountIndex, lastIndex)，则lastIndex=3，并将D的位置更新为新集合中的位置prevChild._mountIndex=nextIndex，此时新集合中D._mountIndex=2，nextIndex++进入下一个节点的判断
4、C节点同理
如果新老集合中，不只是存在位置互换的关系呢？React diff又如何进行操作？（下图中各节点的key为对应节点名称）
1、从新集合中取到B，判断老集合中是否存在相同的节点，找到B在老集合中的位置B._mountIndex=1，此时lastIndex=0，因此不对B进行移动操作；更新lastIndex=1，并将B的位置更新为新集合中的位置B._mountIndex=0，nextIndex++进入下一个节点的判断
2、取到新集合中E节点，由于老集合中不存在相同的节点，则创建新节点E；更新lastIndex=1，并将E的位置更新为新集合中的位置，nextIndex++进入下个节点的判断。
3、取到新集合中C节点，老集合中存在相同节点，C._mountIndex=2，lastIndex=1，此时C._mountIndex > lastIndex，因此不对C进行移动操作；更新lastIndex=2，并将C的位置更新为新集合中的位置，nextIndex++进入下一个节点的判断。
4、取到新集合中A节点，老集合中存在相同的节点，A._mountIndex=0，lastIndex=2，此时A._mountIndex < lastIndex，对A进行移动操作；更新lastIndex=2，并将A的位置更新为新集合中的位置，nextIndex++进入下一个节点的判断。
5、当完成新集合中的所有节点的diff时，最后还需要对老集合进行循环遍历，判断是否存在新集合中没有但老集合中仍存在的节点，发现存在这样的节点D，因此删除节点D，到此diff全部完成。
总结
基于diff这样的策略，所以react建议我们用添加唯一key的方式来进行优化，这里面可以牵扯出来一个问题：
如果用index作为key会有什么问题呢？
index作为key，如果我们删除了一个节点，那么数组的后一项可能会前移，这个时候移动的节点和删除的节点就是相同的key了，在react中，如果key相同，就会视为相同的组件，但这两个组件并不是相同的，这就会出现一些我们不想看到的问题～所以key的值我们要考虑好再确定哦~
最后
本篇文章详细的叙述了虚拟dom和diff算法，我们要分清有key没key是如何进行对比的，也还要知道为什么时间复杂度得到了很大的提升等～如果文章有不对之处，还请大家指出～我们共同学习，共同进步～～～
参考文章
React 源码剖析系列 － 不可思议的 react diff【https://zhuanlan.zhihu.com/p/20346379】
React源码分析与实现(三)：实操DOM Diff【https://github.com/Nealyang/PersonalBlog/issues/2】