React實現(xiàn)核心Diff算法的示例代碼
Diff算法的設計思路
試想，Diff算法需要考慮多少種情況呢？大體分三種，分別是：
節(jié)點屬性變化，比如：
// 更新前 <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>
節(jié)點增刪，比如：
// 更新前 <ul> <li key="0">0</li> <li key="1">1</li> <li key="2">2</li> </ul> // 更新后 情況1 —— 新增節(jié)點 <ul> <li key="0">0</li> <li key="1">1</li> <li key="2">2</li> <li key="3">3</li> </ul> // 更新后 情況2 —— 刪除節(jié)點 <ul> <li key="0">0</li> <li key="1">1</li> </ul>
節(jié)點移動，比如：
// 更新前 <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算法呢？考慮到只有以上三種情況，一種常見的設計思路是：
- 首先判斷當前節(jié)點屬于哪種情況
- 如果是增刪，執(zhí)行增刪邏輯
- 如果是屬性變化，執(zhí)行屬性變化邏輯
- 如果是移動，執(zhí)行移動邏輯
按這個方案，其實有個隱含的前提—— 不同操作的優(yōu)先級是相同的。但在日常開發(fā)中，節(jié)點移動發(fā)生較少，所以Diff算法會優(yōu)先判斷其他情況。
基于這個理念，主流框架（React、Vue）的Diff算法都會經(jīng)歷多輪遍歷，先處理常見情況，后處理不常見情況。
所以，這就要求處理不常見情況的算法需要能給各種邊界case兜底。
換句話說，完全可以僅使用處理不常見情況的算法完成Diff操作。主流框架之所以沒這么做是為了性能考慮。
本文會砍掉處理常見情況的算法，保留處理不常見情況的算法。
這樣，只需要40行代碼就能實現(xiàn)Diff的核心邏輯。
Demo介紹
首先，我們定義虛擬DOM節(jié)點的數(shù)據(jù)結構：
type Flag = 'Placement' | 'Deletion';
interface Node {
key: string;
flag?: Flag;
index?: number;
}key是node的唯一標識，用于將節(jié)點在變化前、變化后關聯(lián)上。
flag代表node經(jīng)過Diff后，需要對相應的真實DOM執(zhí)行的操作，其中：
Placement對于新生成的node，代表對應DOM需要插入到頁面中。對于已有的node，代表對應DOM需要在頁面中移動Deletion代表node對應DOM需要從頁面中刪除
index代表該node在同級node中的索引位置
注：本Demo僅實現(xiàn)為node標記flag，沒有實現(xiàn)根據(jù)flag執(zhí)行DOM操作。
我們希望實現(xiàn)的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需要被刪除。
執(zhí)行后的結果就是：頁面中的a變?yōu)閐。
再比如：
// 更新前
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之前已經(jīng)存在，{key: "b", flag: "Placement"}代表b對應DOM需要向后移動（對應parentNode.appendChild方法）。abc經(jīng)過該操作后變?yōu)?code>acb。
由于a之前已經(jīng)存在，{key: "a", flag: "Placement"}代表a對應DOM需要向后移動。acb經(jīng)過該操作后變?yōu)?code>cba。
執(zhí)行后的結果就是：頁面中的abc變?yōu)閏ba。
Diff算法實現(xiàn)
核心邏輯包括三步：
- 遍歷前的準備工作
- 遍歷
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，這是一個新節(jié)點
afterNode.flag = 'Placement';
result.push(afterNode);
}遍歷后的收尾工作
經(jīng)過遍歷，如果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多調(diào)試幾遍，相信你能明白其中原理。
到此這篇關于React實現(xiàn)核心Diff算法的示例代碼的文章就介紹到這了,更多相關React Diff算法內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
在本篇博客中,我們將介紹如何在 React 應用中搜索 GitHub 用戶并顯示他們的信息,文中通過代碼示例給大家介紹的非常詳細,對大家的學習或工作有一定的幫助,需要的朋友可以參考下2024-02-02
這篇文章主要介紹了React?的數(shù)據(jù)流和生命周期,本文給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2022-08-08
React.memo函數(shù)中的參數(shù)示例詳解
這篇文章主要為大家介紹了React.memo函數(shù)中的參數(shù)示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2022-09-09
采用React編寫小程序的Remax框架的編譯流程解析(推薦)
這篇文章主要介紹了采用React編寫小程序的Remax框架的編譯流程解析(推薦),本文通過實例代碼給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2021-04-04
本篇文章主要介紹了react-router4 嵌套路由的使用方法，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-07-07
這篇文章主要介紹了React 三大屬性之state的使用詳解，幫助大家更好的理解和學習使用React，感興趣的朋友可以了解下2021-04-04
本篇文章主要介紹了深入掌握 react的 setState的工作機制，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-09-09
這篇文章主要介紹了react+redux仿微信聊天IM實例|react仿微信界面 ，本文圖文并茂給大家介紹的非常詳細，具有一定的參考借鑒價值,需要的朋友可以參考下2019-06-06
這篇文章主要介紹了React中的for循環(huán)解讀，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2023-01-01
electron其實是一個桌面應用程序，不是一個標準的前端web程序，所有沒有什么請求的發(fā)生，控制臺network看不到請求，而是只能通過console.log去打印查看，而且通信協(xié)議使用的不是http而是gRPC協(xié)議，這篇文章主要介紹了Electron+React如何進行通信,需要的朋友可以參考下2022-06-06