React怎么實現核心Diff算法

本篇內容主要講解“React怎么實現核心Diff算法”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實用性強。下面就讓小編來帶大家學習“React怎么實現核心Diff算法”吧!

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算法呢？考慮到只有以上三種情況，一種常見的設計思路是：

• 首先判斷當前節點屬于哪種情況

• 如果是增刪，執行增刪邏輯

• 如果是屬性變化，執行屬性變化邏輯

• 如果是移動，執行移動邏輯

按這個方案，其實有個隱含的前提—— 不同操作的優先級是相同的。但在日常開發中，節點移動發生較少，所以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算法實現

核心邏輯包括三步：

• 遍歷前的準備工作

• 遍歷after

• 遍歷后的收尾工作

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);
});

到此，相信大家對“React怎么實現核心Diff算法”有了更深的了解，不妨來實際操作一番吧！這里是億速云網站，更多相關內容可以進入相關頻道進行查詢，關注我們，繼續學習！