常用框架的diff算法
完整高频题库仓库地址：https://github.com/hzfe/awesome-interview完整高频题库阅读地址：https://febook.hzfe.org/相关问题VirtualDOM是的virtualDOM的作用是什么？下面说说Vue的Diff算法，答重点。VirtualDOM时间复杂度O(n)大多数现代网站都具有复杂的布局、大量的节点和交互式操作。直接操作DOM的方法不当导致的性能问题在所难免。忽略。虚拟DOM的本质是一个JavaScript对象，它可以代表DOM的部分特性，是DOM的抽象和简化版本。通过提前操作虚拟DOM，在某一时刻找出虚拟DOM与真实DOM的差异并重新渲染，可以提高操作真实DOM的性能和效率。为了实现这个目标，我们需要关注两个问题：什么时候重新渲染，以及如何高效地选择重新渲染的范围。找出需要重新渲染的范围就是Diff的过程。React和Vue的Diff算法思路基本相同，只是比较同一层次的节点，使用唯一标识来区分节点。深入知识点1.Diff算法两棵树的比较和更新涉及到树编辑距离（TreeEditingDistance）算法：将一棵树转换成另一棵树的最小操作代价。操作类型包括：删除、插入、修改。时间复杂度为O(n^3)。为了降低时间复杂度，React和Vue的思想是降低递归迭代的规模，将Diff算法的时间复杂度降低到O(n)，基于以下两个假设：相同类型的组件产生相同的DOM结构，反之当然。所以不同类型组件的结构不需要进一步递归Diff。同一级别的一组节点可以通过唯一标识符来区分。2.ReactReconciliation在React中，将虚拟DOM与真实DOM进行比较和同步的过程称为Reconciliation。Fiber是React16中的新协调引擎。它的主要目标是启用虚拟DOM的增量渲染。Diff的大致过程是，React在比较两个虚拟DOM树时，先比较根元素。根据根元素的类型，会有不同的操作：不同类型的元素如果元素类型不同，React会丢弃旧树并构建新树。如果出现以下情况，将导致完全重建：HZFEHZFE
相同类型的元素如果元素是两个相同类型的ReactDOM元素，React将检查两者的属性，保留DOM节点，并且只更新更改的属性。在以下情况下，React仅更新颜色样式。
HZFEHZFE在元素类型相同的情况下，比较元素后，会递归该元素的子元素。默认情况下，React会迭代旧的和新的子列表。对于列表更新，React建议识别列表项的关键属性。避免以下低效率：2。Vue2.xDiffVue的Diff算法与React类似。只进行同层比较，不进行跨层比较。如果判断两个元素不同，则不继续递归比较。在Diff子元素处理过程中，采用双端比较的方式，设置了4个指针：oldStartIdx指向旧子元素链表中Diff从左开始的元素索引。初始值：第一个元素的索引。newStartIdx指向新子元素列表中从左边算起的Diff的元素索引。初始值：第一个元素的索引。oldEndIdx指向旧子元素列表中从右往右的Diff的元素索引。初始值：最后一个元素的索引。newEndIdx指向新子元素列表中从右往右的Diff的元素索引。初始值：最后一个元素的索引。Vue同时遍历新旧子元素的虚拟DOM列表，采用头尾比较。一般有4种情况：当新旧起始指针指向同一个节点时，重用该节点，并根据需要进行更新。新旧起始指针向右移动一位。当新旧结束指针指向同一个节点时，重新使用该节点并根据需要更新它。旧的和新的结束指针向左移动一位。当旧的起始指针和新的结束指针指向同一个节点时，重用该节点并按需更新，并将该节点对应的真实DOM移动到子元素列表的末尾。旧的起始指针向右移动一位。新的结束指针向左移动一位。当旧的结束指针和新的开始指针指向同一个节点时，重用该节点并按需更新，并将该节点对应的真实DOM移动到子元素列表的头部。旧的结束指针向左移动一位。新的起始指针向右移动一位。如果不满足上述条件，它将尝试检查新起始指针指向的节点是否具有唯一标识符键。如果有并且在旧链表中可以找到同类型同key的节点，则可以重用，按需更新，将节点移动到新的位置。新的起始指针向右移动一位。如果仍然不满足条件，则添加相关节点。当新旧链表中任意一个链表的头指针索引大于尾指针索引时，循环遍历结束，可以根据需要删除或添加相关节点。参考Reconciliationpatch
