是什么
diff 算法是一种对同层 DOM 节点进行比较的高效算法，传统 diff 算法通过循环递归对节点进行依次对比，效率低下，算法复杂度达到 O(n^3)，而改进后的 diff 算法避免了对 DOM 树进行逐层搜索遍历，所以时间复杂度只有 O(n)。diff 算法的在很多场景下都有应用，例如在 Vue 虚拟 DOM 渲染成真实 DOM 的新旧虚拟 DOM 节点比较更新时，就用到了该算法。
diff 算法特点：
- 不会跨层级比较，只会在同层级进行比较。
- 在 diff 比较的过程中，循环从两边向中间比较。
注意❗
- Key 和标签名一致就为同一节点。
- 能交换就尽量不删除和新增。
比较方式
diff 整体策略为：深度优先，同层比较。
基本原理
diff 算法的基本原理有以下几点：
- 对于同层级节点首先对比新旧节点的头尾，头与头、尾与尾分别进行对比，寻找未移动的节点。
- 新旧节点头尾对比完后，然后进行头与尾、尾与头的交叉对比，这一步的目的是寻找可复用的节点。
- 在交叉对比结束后，因为有可能还有可复用的节点，所以创建一个老节点 keyToIndex 的哈希表 map 记录 key，然后继续遍历新节点索引通过 key 查找可以复用的旧的节点。
- 节点遍历完成后，通过新老索引，移除多余旧节点或者增加新节点。
举例说明
下面举个vue通过diff算法更新的例子：
- 比较只会在同层级进行, 不会跨层级比较
- 比较的过程中，循环从两边向中间收拢
新旧 VNode 节点如下图所示：
第一次循环后，发现旧节点 D 与新节点 D 相同，直接复用旧节点 D 作为 diff 后的第一个真实节点，同时旧节点 endIndex 移动到 C，新节点的 startIndex 移动到了 C。
第二次循环后，同样是旧节点的末尾和新节点的开头(都是 C)相同，同理，diff 后创建了 C 的真实节点插入到第一次创建的 D 节点后面。同时旧节点的 endIndex 移动到了 B，新节点的 startIndex 移动到了 E。
第三次循环中，发现 E 没有找到，这时候只能直接创建新的真实节点 E，插入到第二次创建的 C 节点之后。同时新节点的 startIndex 移动到了 A。旧节点的 startIndex 和 endIndex 都保持不动。
第四次循环中，发现了新旧节点的开头(都是 A)相同，于是 diff 后创建了 A 的真实节点，插入到前一次创建的 E 节点后面。同时旧节点的 startIndex 移动到了 B，新节点的 startIndex 移动到了 B。
第五次循环中，情形同第四次循环一样，因此 diff 后创建了 B 真实节点插入到前一次创建的 A 节点后面。同时旧节点的 startIndex 移动到了 C，新节点的 startIndex 移动到了 F。
新节点的 startIndex 已经大于 endIndex 了，需要创建 newStartIdx 和 newEndIdx 之间的所有节点，也就是节点 F，直接创建 F 节点对应的真实节点放到 B 节点后面。
小结
更新流程
updateChildren
首尾指针法
- 当数据发生改变时，订阅者
watcher就会调用patch给真实的DOM打补丁 - 通过
isSameVnode进行判断，相同则调用patchVnode方法 patchVnode做了以下操作：- 找到对应的真实
dom，称为el - 如果都有都有文本节点且不相等，将
el文本节点设置为Vnode的文本节点 - 如果
oldVnode有子节点而VNode没有，则删除el子节点 - 如果
oldVnode没有子节点而VNode有，则将VNode的子节点真实化后添加到el - 如果两者都有子节点，则执行
updateChildren函数比较子节点
- 找到对应的真实
updateChildren主要做了以下操作：- 设置新旧
VNode的头尾指针 - 新旧头尾指针进行比较，循环向中间靠拢，根据情况调用
patchVnode进行patch重复流程、调用createElem创建一个新节点，从哈希表寻找key一致的VNode节点再分情况操作。
- 设置新旧
