40行代码实现React核心Diff算法

更新日期: 2022-04-15阅读: 1k标签: diff

凡是依赖虚拟dom框架,都需要「比较前后节点变化」的Diff算法。

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

今天,我们换一种一劳永逸的学习方法 —— 实现react的核心Diff算法。

不难,只有40行代码。不信?往下看。

Diff算法的设计思路

试想,Diff算法需要考虑多少种情况呢?大体分三种,分别是:

节点属性变化,比如:

// 更新前
<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>

节点增删,比如:

// 更新前
<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>

节点移动,比如:

// 更新前
<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执行的操作,其中:

  1. Placement对于新生成的node,代表对应DOM需要插入到页面中。对于已有的node,代表对应DOM需要在页面中移动。
  2. 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中的index
let 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中的index
let 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地址[1]。

总结

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

跟着Demo多调试几遍,相信你能明白其中原理。

在线Demo地址:https://codesandbox.io/s/naughty-matan-6fq7n6?file=/src/diff.ts。
来源: 魔术师卡颂


链接: https://fly63.com/article/detial/11348

React Diff 算法

React 是 facebook 出的一个前端框架. 设计的关键处就是性能问题。在本文中,我主要是介绍 Diff 算法以及 React 渲染 ,这样你可以更好的优化你的应用程序。

浅析vue2.0的diff算法

如果不了解virtual dom,要理解diff的过程是比较困难的。虚拟dom对应的是真实dom, 使用document.CreateElement 和 document.CreateTextNode创建的就是真实节点。vue2.0才开始使用了virtual dom,有向react靠拢的意思。

简述dom diff原理

关于react的虚拟dom以及每次渲染更新的dom diff,网上文章很多。但是我一直信奉一个原则,即:但凡复杂的知识,理解之后都只需要记忆简单的东西,而想简单、精确描述一个复杂知识,是极困难的事。

传统diff、react优化diff、vue优化diff

传统diff计算两颗树形结构差异并进行转换,传统diff算法是这样做的:循环递归每一个节点;传统diff算法复杂度达到O(n^3 )这意味着1000个节点就要进行数10亿次的比较,这是非常消耗性能的

React 中 Virtual DOM 与 Diffing 算法的关系

Virtual DOM 是一种编程理念。UI 信息被特定语言描述并保存到内存中,再通过特定的库,例如 ReactDOM 与真实的 DOM 同步信息。这一过程成为 协调 (Reconciliation)。上述只是 协调算法

Vue2.x的diff算法记录

为什么在Vue3.0都已经出来这么久了我还要写这篇文章,因为目前自己还在阅读Vue2.x的源码,感觉有所悟。作为一个刚毕业的新人,对Vue框架的整体设计和架构突然有了一点认知,所以才没头没尾地突然写下了diff算法。

深入理解React Diff算法

fiber上的updateQueue经过React的一番计算之后,这个fiber已经有了新的状态,也就是state,对于类组件来说,state是在render函数里被使用的,既然已经得到了新的state

虚拟 DOM 与 Diff 算法的实现原理

Vue 源码中虚拟 DOM 与 Diff 算法的实现借鉴了 snabbdom 这个库,snabbdom 是一个虚拟 DOM 库,它专注于简单,模块化,强大的功能和性能。要彻底明白虚拟 DOM 与 Diff 算法就得分析 snabbdom 这个库到底做了什么?

手写一个虚拟DOM库,彻底让你理解diff算法

所谓虚拟DOM就是用js对象来描述真实DOM,它相对于原生DOM更加轻量,因为真正的DOM对象附带有非常多的属性,另外配合虚拟DOM的diff算法,能以最少的操作来更新DOM,除此之外

详解虚拟DOM与Diff算法

那么需要真实的操作DOM100w次,触发了回流100w次。每次DOM的更新都会按照流程进行无差别的真实dom的更新。所以造成了很大的性能浪费。如果循环里面是复杂的操作,频繁触发回流与重绘

点击更多...

内容以共享、参考、研究为目的,不存在任何商业目的。其版权属原作者所有,如有侵权或违规,请与小编联系!情况属实本人将予以删除!