大家好，我卡颂。

但凡依赖虚构DOM的框架，都须要比拟前后节点变动的Diff算法。

网上有大量解说Diff算法逻辑的文章。然而，即便作者语言再简练，再图文并茂，置信大部分同学看完用不了多久就忘了。

明天，咱们换一种一劳永逸的学习办法 —— 实现React的外围Diff算法。

不难，只有40行代码。不信？往下看。

欢送退出人类高质量前端框架群，带飞

Diff算法的设计思路

试想，Diff算法须要思考多少种状况呢？大体分三种，别离是：

  1. 节点属性变动，比方：
// 更新前<ul>  <li key="0" className="before">0</li>  <li key="1">1</li></ul>// 更新后<ul>  <li key="0" className="after">0</li>  <li key="1">1</li></ul>
  1. 节点增删，比方：
// 更新前<ul>  <li key="0">0</li>  <li key="1">1</li>  <li key="2">2</li></ul>// 更新后 状况1 —— 新增节点<ul>  <li key="0">0</li>  <li key="1">1</li>  <li key="2">2</li>  <li key="3">3</li></ul>// 更新后 状况2 —— 删除节点<ul>  <li key="0">0</li>  <li key="1">1</li></ul>
  1. 节点挪动，比方：
// 更新前<ul>  <li key="0">0</li>  <li key="1">1</li></ul>// 更新后<ul>  <li key="1">1</li>  <li key="0">0</li></ul>

该如何设计Diff算法呢？思考到只有以上三种状况，一种常见的设计思路是：

  1. 首先判断以后节点属于哪种状况
  2. 如果是增删，执行增删逻辑
  3. 如果是属性变动，执行属性变动逻辑
  4. 如果是挪动，执行挪动逻辑

按这个计划，其实有个隐含的前提—— 不同操作的优先级是雷同的。但在日常开发中，节点挪动产生较少，所以Diff算法会优先判断其余状况。

基于这个理念，支流框架（React、Vue）的Diff算法都会经验多轮遍历，先解决常见状况，后处理不常见状况。

所以，这就要求解决不常见状况的算法须要能给各种边界case兜底。

换句话说，齐全能够仅应用解决不常见状况的算法实现Diff操作。支流框架之所以没这么做是为了性能思考。

本文会砍掉解决常见状况的算法，保留解决不常见状况的算法。

这样，只须要40行代码就能实现Diff的外围逻辑。

Demo介绍

首先，咱们定义虚构DOM节点的数据结构：

type Flag = 'Placement' | 'Deletion';interface Node {  key: string;  flag?: Flag;  index?: number;}

key是node的惟一标识，用于将节点在变动前、变动后关联上。

flag代表node通过Diff后，须要对相应的实在DOM执行的操作，其中：

  • Placement对于新生成的node，代表对应DOM须要插入到页面中。对于已有的node，代表对应DOM须要在页面中挪动
  • Deletion代表node对应DOM须要从页面中删除

index代表该node在同级node中的索引地位

注：本Demo仅实现为node标记flag，没有实现依据flag执行DOM操作。

咱们心愿实现的diff办法，接管更新前与更新后的NodeList，为他们标记flag：

type NodeList = Node[];function diff(before: NodeList, after: NodeList): NodeList {  // ...代码}

比方对于：

// 更新前const before = [  {key: 'a'}]// 更新后const after = [  {key: 'd'}]// diff(before, after) 输入[  {key: "d", flag: "Placement"},  {key: "a", flag: "Deletion"}]

{key: "d", flag: "Placement"}代表d对应DOM须要插入页面。

{key: "a", flag: "Deletion"}代表a对应DOM须要被删除。

执行后的后果就是：页面中的a变为d。

再比方：

// 更新前const before = [  {key: 'a'},  {key: 'b'},  {key: 'c'},]// 更新后const after = [  {key: 'c'},  {key: 'b'},  {key: 'a'}]// diff(before, after) 输入[  {key: "b", flag: "Placement"},  {key: "a", flag: "Placement"}]

因为b之前曾经存在，{key: "b", flag: "Placement"}代表b对应DOM须要向后挪动（对应parentNode.appendChild办法）。abc通过该操作后变为acb。

因为a之前曾经存在，{key: "a", flag: "Placement"}代表a对应DOM须要向后挪动。acb通过该操作后变为cba。

执行后的后果就是：页面中的abc变为cba。

Diff算法实现

外围逻辑包含三步：

  1. 遍历前的筹备工作
  2. 遍历after
  3. 遍历后的收尾工作
function diff(before: NodeList, after: NodeList): NodeList {  const result: NodeList = [];  // ...遍历前的筹备工作  for (let i = 0; i < after.length; i++) {    // ...外围遍历逻辑  }  // ...遍历后的收尾工作  return result;}

遍历前的筹备工作

咱们将before中每个node保留在以node.key为key，node为value的Map中。

这样，以O(1)复杂度就能通过key找到before中对应node：

// 保留后果const result: NodeList = [];  // 将before保留在map中const beforeMap = new Map<string, Node>();before.forEach((node, i) => {  node.index = i;  beforeMap.set(node.key, node);})

遍历after

当遍历after时，如果一个node同时存在于before与after（key雷同），咱们称这个node可复用。

比方，对于如下例子，b是可复用的：

// 更新前const before = [  {key: 'a'},  {key: 'b'}]// 更新后const after = [  {key: 'b'}]

对于可复用的node，本次更新肯定属于以下两种状况之一：

  • 不挪动
  • 挪动

如何判断可复用的node是否挪动呢？

咱们用lastPlacedIndex变量保留遍历到的最初一个可复用node在before中的index：

// 遍历到的最初一个可复用node在before中的indexlet lastPlacedIndex = 0;

当遍历after时，每轮遍历到的node，肯定是以后遍历到的所有node中最靠右的那个。

如果这个node是可复用的node，那么nodeBefore与lastPlacedIndex存在两种关系：

注：nodeBefore代表该可复用的node在before中的对应node
  • nodeBefore.index < lastPlacedIndex

代表更新前该node在lastPlacedIndex对应node右边。

而更新后该node不在lastPlacedIndex对应node右边（因为他是以后遍历到的所有node中最靠右的那个）。

这就代表该node向右挪动了，须要标记Placement。

  • nodeBefore.index >= lastPlacedIndex

该node在原地，不须要挪动。

// 遍历到的最初一个可复用node在before中的indexlet lastPlacedIndex = 0;  for (let i = 0; i < after.length; i++) {const afterNode = after[i];afterNode.index = i;const beforeNode = beforeMap.get(afterNode.key);if (beforeNode) {  // 存在可复用node  // 从map中剔除该 可复用node  beforeMap.delete(beforeNode.key);  const oldIndex = beforeNode.index as number;  // 外围判断逻辑  if (oldIndex < lastPlacedIndex) {    // 挪动    afterNode.flag = 'Placement';    result.push(afterNode);    continue;  } else {    // 不挪动    lastPlacedIndex = oldIndex;  }} else {  // 不存在可复用node，这是一个新节点  afterNode.flag = 'Placement';  result.push(afterNode);}

遍历后的收尾工作

通过遍历，如果beforeMap中还剩下node，代表这些node没法复用，须要被标记删除。

比方如下状况，遍历完after后，beforeMap中还剩下{key: 'a'}：

// 更新前const before = [  {key: 'a'},  {key: 'b'}]// 更新后const after = [  {key: 'b'}]

这意味着a须要被标记删除。

所以，最初还须要退出标记删除的逻辑：

beforeMap.forEach(node => {  node.flag = 'Deletion';  result.push(node);});

残缺代码见在线Demo地址

总结

整个Diff算法的难点在于lastPlacedIndex相干逻辑。

跟着Demo多调试几遍，置信你能明确其中原理。