关于javascript:精读DOM-diff-原理详解

DOM diff 作为工程问题，须要具备肯定算法思维，因而经常出现在面试场景中，毕竟这是难得呈现在工程畛域的算法问题。

无论出于面试目标，还是深刻学习目标，都有必要将这个问题搞懂，因而前端精读咱们就专门用一个章节说分明此问题。

精读

Dom diff 是所有当初框架必须做的事件，这背地的起因是，由 Jquery 时代的面向操作过程转变为数据驱动视图导致的。

为什么 Jquery 时代不须要 Dom diff？因为 Dom diff 交给业务解决了，咱们调用 .append 或者 .move 之类 Dom 操作函数，就是显式申明了如何做 Dom diff，这种计划是最高效的，因为怎么挪动 Dom 只有业务最分明。

但这样的问题也很显著，就是业务心智累赘太重，对于简单零碎，须要做 Dom diff 的中央太多，不仅写起来繁琐，当状态存在交织时，面向过程的手动 Dom diff 容易呈现状态脱漏，导致边界谬误，就算你没有写出 bug，代码的可维护性也相对算不上好。

解决方案就是数据驱动，咱们只须要关注数据如何映射到 UI，这样无论业务逻辑再简单，咱们永远只须要解决部分状态的映射，这极大升高了简单零碎的保护复杂度，以前须要一个老手写的逻辑，当初老手就能做了，这是十分了不起的变动。

但无利也有弊，这背地 Dom diff 就要交给框架来做了，所以是否能高效的做 Dom diff，是一个数据驱动框架是否利用于生产环境的重要指标，接下来，咱们来看看 Dom diff 是如何做的吧。

现实的 Dom diff

如图所示，现实的 Dom diff 天然是滴水不漏的复用所有能复用的，切实遇到新增或删除时，才执行插入或删除。这样的操作最贴近 Jquery 时代咱们手写的 Dom diff 性能。

惋惜程序无奈猜到你的想法，想要准确复用就必须付出昂扬的代价：工夫复杂度 O(n³) 的 diff 算法，这显然是无奈承受的，因而现实的 Dom diff 算法无奈被应用。

对于 O(n³) 的由来。因为左树中任意节点都可能呈现在右树，所以必须在对左树深度遍历的同时，对右树进行深度遍历，找到每个节点的对应关系，这里的工夫复杂度是 O(n²)，之后须要对树的各节点进行增删移的操作，这个过程简略能够了解为加了一层遍历循环，因而再乘一个 n。

简化的 Dom diff

如图所示，只按层比拟，就能够将工夫复杂度升高为 O(n)。按层比拟也不是广度遍历，其实就是判断某个节点的子元素间 diff，跨父节点的兄弟节点也不用比拟。

这样做的确十分高效，但代价就是，判断的有点傻，比方 ac 明明是一个挪动操作，却被误辨认为删除 + 新增。

好在跨 DOM 复用在理论业务场景中很少呈现，因而这种蠢笨呈现的频率实际上非常低，这时候咱们就不要太谋求学术思维上的谨严了，毕竟框架是给理论我的项目用的，理论我的项目中很少呈现的场景，算法是能够不思考的。

上面是同层 diff 可能呈现的三种状况，非常简单，看图即可：

那么同层比拟是怎么达到 O(n) 工夫复杂度的呢？咱们来看具体框架的思路。

Vue 的 Dom diff

Vue 的 Dom diff 一共 5 步，咱们联合下图先看前三步：

如图所示，第一和第二步别离从首尾中间向两头迫近，尽可能跳过首位雷同的元素，因为咱们的目标是 尽量保障不要产生 dom 位移 。

这种算法个别采纳双指针。如果前两步做完后，发现旧树指针重合了，新树还未重合，阐明什么？阐明新树剩下来的都是要新增的节点，批量插入即可。很简略吧？那如果反过来呢？如下图所示：

第一和第二步实现后，发现新树指针重合了，但旧树还未重合，阐明什么？阐明旧树剩下来的在新树都不存在了，批量删除即可。

当然，如果 1、2、3、4 步走完之后，指针还未解决完，那么就进入一个小小算法工夫了，咱们须要在 O(n) 工夫复杂度内把剩下节点解决完。相熟算法的同学应该很快能反映出，一个数组做一些检测操作，还得把工夫复杂度管制在 O(n)，得用一个 Map 空间换一下工夫，实际上也是如此，咱们看下图具体做法：

如图所示，1、2、3、4 步走完后，Old 和 New 都有残余，因而走到第五步，第五步分为三小步：

1. 遍历 Old 创立一个 Map，这个就是那个换工夫的空间耗费，它记录了每个旧节点的 index 下标，一会好在 New 里查出来。
2. 遍历 New，顺便利用下面的 Map 记录下下标，同时 Old 里不存在的阐明被删除了，间接删除。
3. 不存在的地位补 0，咱们拿到 e:4 d:3 c:2 h:0 这样一个数组，下标 0 是新增，非 0 就是移过来的，批量转化为插入操作即可。

最初一步的优化也很要害，咱们不要看见不同就轻易挪动，为了性能最优，要保障挪动次数尽可能的少，那么怎么能力尽可能的少挪动呢？假如咱们随便挪动，如下图所示：

但其实最优的挪动形式是上面这样：

为什么呢？因为挪动的时候，其余元素的地位也在绝对变动，可能做了 A 成果同时，也把 B 成果给满足了，也就是说，找到那些绝对地位有序的元素放弃不变，让那些地位显著谬误的元素移动即是最优的。

什么是绝对有序？a c e 这三个字母在 Old 原始程序 a b c d e 中是绝对有序的，咱们只有把 b d 移走，这三个字母的地位天然就正确了。因而咱们只须要找到 New 数组中的 最长间断子串 。具体的找法能够当作一个小算法题了，因为晓得每个元素的理论下标，比方这个例子中，下标是这样的：

[b:1, d:3, a:0, c:2, e:4]

肉眼看上去，间断自增的子串有 b d 和 a c e，因为 a c e 更长，所以抉择后者。

换成程序去做，能够采纳动静布局，设 dp(i) 为以第 i 个字符串结尾的最长间断子串长度，一次 O(n) 循环即可。

// dp(i) = num[i] > num[i - 1] ? dp(i - 1) + 1 : 1

React 的 Dom diff

假如这么一种状况，咱们将 a 移到了 c 后，那么框架从最终状态倒推，如何最快的找到这个动机呢？React 采纳了 仅右移策略 ，即对元素产生的地位变动，只会将其挪动到左边，那么左边移完了，其余地位也就有序了。

咱们看图阐明：

遍历 Old 存储 Map 和 Vue 是一样的，而后就到了第二步遍历 New，b 下标从原来的 1 变成了 0，须要左移才行，但咱们不左移，咱们只右移，因为所有右移做完后，左移就等于主动做掉了（后面的元素右移后，本人天然被顶到后面去了，实现了左移的成果）。

同理，c 下标从 2 变成了 1，须要左移才行，但咱们持续不动。

a 的下标从 0 变成 2，终于能够右移了！

前面的 d、e 下标没变，就不必动。咱们纵观整体能够发现，b 和 c 因为后面的 a 被抽走了，天然产生了左移。这就是用一个右移代替两个左移的高效操作。

同时咱们发现，这也的确找到了咱们开始提到的最佳位移策略。

那这个算法真的有这么聪慧吗？显然不是，这个算法只是歪打误撞碰对了而已， 有用右移代替左移的算法，就有用左移代替右移的算法 ，既然抉择了右移代替左移，那么肯定失落了左移代替右移的效率。

什么时候用左移代替右移效率最高？就是把数组最初一位移到第一位的场景：

显然左移只有一步，那么右移就是 n-1 步，在这个例子就是 4 步，咱们看右移算法图解：

首先找到 e，地位从 4 变成了 0，但咱们不能左移！所以只能放弃不动，喜剧从此开始。

尽管算法曾经不是最优了，但该做的还是要做，其实之前有一个 lastIndex 概念没有说，因为 e 曾经在 4 的地位了，所以再把 a 从 0 挪到 1 曾经不够了，此时 a 应该从 0 挪到 5。

办法就是记录 lastIndex = max(oldIndex, newIndex) => lastIndex = max(4, 0)，下一次挪动到 lastIndex + 1 也就是 5：

发现 a 从 0 变成了 5（留神，此时思考到 lastIndex 因素），所以右移。

同理，b、c、d 也一样。咱们最初发现，产生了 4 次右移，e 也因为天然左移了 4 次达到了首位，合乎预期。

所以这是一个有利有弊的算法。新增和删除比较简单，和 Vue 差不多。

PS：最新版 React Dom diff 算法如有更新，欢送在评论区指出，因为这种算法看来不如 Vue 的高效。

总结

Dom diff 总结有这么几点思考：

1. 齐全比照 O(n³) 无奈承受，故降级为同层比照的 O(n) 计划。
2. 为什么降级可行？因为跨层级很少产生，能够疏忽。
3. 同层级也不简略，难点是如何高效位移，即最小步数实现位移。
4. Vue 为了尽量不挪动，先左右夹击跳过不变的，再找到最长间断子串放弃不动，挪动其余元素。
5. React 采纳仅右移计划，在大部分从左往右移的业务场景中，失去了较好的性能。

探讨地址是：精读《DOM diff 原理详解》· Issue #308 · dt-fe/weekly

如果你想参加探讨，请 点击这里，每周都有新的主题，周末或周一公布。前端精读 – 帮你筛选靠谱的内容。

关注 前端精读微信公众号

版权申明：自在转载 - 非商用 - 非衍生 - 放弃署名（创意共享 3.0 许可证）