React diff 算法
一文讲通React的diff过程看完这篇文章，我们可以弄明白下面这几个问题： 传统diff 算法的瓶颈是什么？ Reac - 掘金 Fiber 节点的构建 从根节点开始深度优先搜索，经历【递】【归】两个阶段 “递”阶段 向下遍历，每个遍历到的 Fiber 节点会调用 beginWork 方法。 该方法会根据传入的 Fiber 节点创建子Fiber 节点，并将这两个 Fiber 节点连接起来。 当遍历到没有 child 的节点时就会进入“归”阶段。 “归”阶段 在“归”阶段会调用 completeWork 处理 Fiber 节点。 当某个 Fiber 节点执行完 completeWork，如果其存在兄弟Fiber节点，会进入其兄弟Fiber的“递”阶段。 如果不存在兄弟Fiber，会进入父Fiber的“归”阶段。 优化策略 前后两棵树完全对比的算法复杂程度为O(n3) diff 遵循了 3 个层级的优化策略：
只进行同层比较。 新、旧节点的 type 不同，直接删除旧节点，创建新节点。 通过 key 来复用节点。 Diff 算法 为什么不能用双指针遍历 虽然 newChildren 为数组形式，但是老节点是 fiber链表，同级的 Fiber 节点是由 sibling 指针链接形成的单链表，即不支持双指针遍历。即 newChildren[0]与fiber比较，newChildren[1]与fiber.sibling比较。 所以无法使用双指针优化。 算法过程 react 根据频率决定优先更新 更新 操作。 Diff 算法的整体逻辑会经历两轮遍历： 第一轮遍历：处理更新的节点。 第二轮遍历：处理剩下的不属于更新的节点。
第一轮遍历：比较 key，
可复用，继续遍历 (新节点 i++，老节点child.silbing)， 不可复用，就停止第一轮遍历，进入第二轮遍历，有 2 种不可复用的情况：
key 不同，直接停止 key 相同，type 不同，标记删除，停止 第二轮遍历：
老节点遍历完了，新节点还有，则将剩下的新节点插入 新节点遍历完了，老节点还有，则将剩下的老节点删除 新老节点都还有，则移动顺序，这是 diff 算法最精髓也是最难懂的部分，规则：遍历新节点，每个新节点有 2 个 index，一个 index 表示它在旧节点的位置，另一个 index 表示遍历中遇到的最大旧节点的位置，用 oldIndex 和 maxIndex 表示
当 oldIndex>maxIndex 时，将 oldIndex 的值赋值给 maxIndex 当 oldIndex=maxIndex 时，不操作 当 oldIndex<maxIndex 时，将当前节点移动到 index 的位置
移动的思想：如果当前节点在新集合中的位置比老集合中的位置靠前的话，是不会影响后续节点操作的，这时候不用动 举例子 diff 过程如下： 节点 B：此时 maxIndex=0，oldIndex=1；满足 maxIndex< oldIndex，因此 B 节点不动，此时 maxIndex= Math.max(oldIndex, maxIndex)，就是 1 节点 A：此时 maxIndex=1，oldIndex=0；不满足 maxIndex< oldIndex，因此 A 节点进行移动操作，此时 maxIndex= Math.max(oldIndex, maxIndex)，还是 1 节点 D：此时 maxIndex=1, oldIndex=3；满足 maxIndex< oldIndex，因此 D 节点不动，此时 maxIndex= Math.max(oldIndex, maxIndex)，就是 3 节点 C：此时 maxIndex=3，oldIndex=2；不满足 maxIndex< oldIndex，因此 C 节点进行移动操作，当前已经比较完了
