引言

React 是基于 vdom 的前端框架，組件 render 產(chǎn)生 vdom，然后渲染器把 vdom 渲染出來。

state 更新的時(shí)候，組件會(huì)重新 render，產(chǎn)生新的 vdom，在瀏覽器平臺(tái)下，為了減少 dom 的創(chuàng)建，React 會(huì)對(duì)兩次的 render 結(jié)果做 diff，盡量復(fù)用 dom，提高性能。

diff 算法是前端框架中比較復(fù)雜的部分，代碼比較多，但今天我們不上代碼，只看圖來理解它。

首先，我們先過一下 react 的 fiber 架構(gòu)：

Fiber 架構(gòu)

React 是通過 jsx 描述頁面結(jié)構(gòu)的：

const profile = {
    return <div>
        <img src="avatar.png" className="profile" />
        <h3>{[user.firstName, user.lastName].join(" ")}</h3>
    </div>

經(jīng)過 babel 等的編譯會(huì)變成 render function：

import { jsx as _jsx } from "react/jsx-runtime";
import { jsxs as _jsxs } from "react/jsx-runtime";
const profile = _jsxs("div", {
  children: [
    _jsx("img", {
      src: "avatar.png",
      className: "profile",
    }),
    _jsx("h3", {
      children: [user.firstName, user.lastName].join(" "),
    }),
  ],
});

render function 執(zhí)行結(jié)果就是 vdom，也就是 React Element 的實(shí)例：

在 16 之前，React 是直接遞歸渲染 vdom 的，setState 會(huì)觸發(fā)重新渲染，對(duì)比渲染出的新舊 vdom，對(duì)差異部分進(jìn)行 dom 操作。

在 16 之后，為了優(yōu)化性能，會(huì)先把 vdom 轉(zhuǎn)換成 fiber，也就是從樹轉(zhuǎn)換成鏈表，然后再渲染。整體渲染流程分成了兩個(gè)階段：

• render 階段：從 vdom 轉(zhuǎn)換成 fiber，并且對(duì)需要 dom 操作的節(jié)點(diǎn)打上 effectTag 的標(biāo)記
• commit 階段：對(duì)有 effectTag 標(biāo)記的 fiber 節(jié)點(diǎn)進(jìn)行 dom 操作，并執(zhí)行所有的 effect 副作用函數(shù)。

從 vdom 轉(zhuǎn)成 fiber 的過程叫做 reconcile（調(diào)和），這個(gè)過程是可以打斷的，由 scheduler 調(diào)度執(zhí)行。

diff 算法作用在 reconcile 階段：

第一次渲染不需要 diff，直接 vdom 轉(zhuǎn) fiber。

再次渲染的時(shí)候，會(huì)產(chǎn)生新的 vdom，這時(shí)候要和之前的 fiber 做下對(duì)比，決定怎么產(chǎn)生新的 fiber，對(duì)可復(fù)用的節(jié)點(diǎn)打上修改的標(biāo)記，剩余的舊節(jié)點(diǎn)打上刪除標(biāo)記，新節(jié)點(diǎn)打上新增標(biāo)記。

接下來我們就來詳細(xì)了解下 React 的 diff 算法：

React 的 diff 算法

在講 diff 算法實(shí)現(xiàn)之前，我們要先想明白為什么要做 diff，不做行么？

當(dāng)然可以，每一次渲染都直接把 vdom 轉(zhuǎn)成 fiber 就行，不用和之前的做對(duì)比，這樣是可行的。

其實(shí) SSR 的時(shí)候就不用做 diff，因?yàn)闀?huì)把組件渲染成字符串，第二次渲染也是產(chǎn)生字符串，難道這時(shí)候還要和之前的字符串對(duì)比下，有哪些字符串可以復(fù)用么？

不需要，SSR 的時(shí)候就沒有 diff，每次都是 vdom 渲染出新的字符串。

那為什么瀏覽器里要做 diff 呢？

因?yàn)?dom 創(chuàng)建的性能成本很高，如果不做 dom 的復(fù)用，那前端框架的性能就太差了。

diff 算法的目的就是對(duì)比兩次渲染結(jié)果，找到可復(fù)用的部分，然后剩下的該刪除刪除，該新增新增。

那具體怎么實(shí)現(xiàn) React 的 diff 算法呢？

比如父節(jié)點(diǎn)下有 A、B、C、D 四個(gè)子節(jié)點(diǎn)，那渲染出的 vdom 就是這樣的：

經(jīng)過 reconcile 之后，會(huì)變成這樣的 fiber 結(jié)構(gòu)：

那如果再次渲染的時(shí)候，渲染出了 A、C、B、E 的 vdom，這時(shí)候怎么處理呢？

再次渲染出 vdom 的時(shí)候，也要進(jìn)行 vdom 轉(zhuǎn) fiber 的 reconcile 階段，但是要盡量能復(fù)用之前的節(jié)點(diǎn)。

那怎么復(fù)用呢？

一一對(duì)比下不就行了？

先把之前的 fiber 節(jié)點(diǎn)放到一個(gè) map 里，key 就是節(jié)點(diǎn)的 key：

然后每個(gè)新的 vdom 都去這個(gè) map 里查找下有沒有可以復(fù)用的，找到了的話就移動(dòng)過來，打上更新的 effectTag：

這樣遍歷完 vdom 節(jié)點(diǎn)之后，map 里剩下一些，這些是不可復(fù)用的，那就刪掉，打上刪除的 effectTag；如果 vdom 中還有一些沒找到復(fù)用節(jié)點(diǎn)的，就直接創(chuàng)建，打上新增的 effectTag。

這樣就實(shí)現(xiàn)了更新時(shí)的 reconcile，也就是上面的 diff 算法。其實(shí)核心就是找到可復(fù)用的節(jié)點(diǎn)，剩下的舊節(jié)點(diǎn)刪掉，新節(jié)點(diǎn)新增。

但有的時(shí)候可以再簡(jiǎn)化一下，比如上次渲染是 A、B、C、D，這次渲染也是 A、B、C、D，那直接順序?qū)Ρ认戮托校瑳]必要建立 map 再找。

所以 React 的 diff 算法是分成兩次遍歷的：

第一輪遍歷，一一對(duì)比 vdom 和老的 fiber，如果可以復(fù)用就處理下一個(gè)節(jié)點(diǎn)，否則就結(jié)束遍歷。

如果所有的新的 vdom 處理完了，那就把剩下的老 fiber 節(jié)點(diǎn)刪掉就行。

如果還有 vdom 沒處理，那就進(jìn)行第二次遍歷：

第二輪遍歷，把剩下的老 fiber 放到 map 里，遍歷剩下的 vdom，從 map 里查找，如果找到了，就移動(dòng)過來。

第二輪遍歷完了之后，把剩余的老 fiber 刪掉，剩余的 vdom 新增。

這樣就完成了新的 fiber 結(jié)構(gòu)的創(chuàng)建，也就是 reconcile 的過程。

比如上面那個(gè)例子，第一輪遍歷就是這樣的：

一一對(duì)比新的 vdom 和 老的 fiber，發(fā)現(xiàn) A 是可以復(fù)用的，那就創(chuàng)建新 fiber 節(jié)點(diǎn)，打上更新標(biāo)記。

C 不可復(fù)用，所以結(jié)束第一輪遍歷，進(jìn)入第二輪遍歷。

把剩下的 老 fiber 節(jié)點(diǎn)放到 map 里，然后遍歷新的 vdom 節(jié)點(diǎn)，從 map 中能找到的話，就是可復(fù)用，移動(dòng)過來打上更新的標(biāo)記。

遍歷完之后，剩下的老 fiber 節(jié)點(diǎn)刪掉，剩下的新 vdom 新增。

這樣就完成了更新時(shí)的 reconcile 的過程。

總結(jié)

react 是基于 vdom 的前端框架，組件渲染產(chǎn)生 vdom，渲染器把 vdom 渲染成 dom。

瀏覽器下使用 react-dom 的渲染器，會(huì)先把 vdom 轉(zhuǎn)成 fiber，找到需要更新 dom 的部分，打上增刪改的 effectTag 標(biāo)記，這個(gè)過程叫做 reconcile，可以打斷，由 scheducler 調(diào)度執(zhí)行。reconcile 結(jié)束之后一次性根據(jù) effectTag 更新 dom，叫做 commit。

這就是 react 的基于 fiber 的渲染流程，分成 render（reconcile + schedule）、commit 兩個(gè)階段。

當(dāng)渲染完一次，產(chǎn)生了 fiber 之后，再次渲染的 vdom 要和之前的 fiber 對(duì)比下，再?zèng)Q定如何產(chǎn)生新的 fiber，目標(biāo)是盡可能復(fù)用已有的 fiber 節(jié)點(diǎn)，這叫做 diff 算法。

react 的 diff 算法分為兩個(gè)階段：

第一個(gè)階段一一對(duì)比，如果可以復(fù)用就下一個(gè)，不可以復(fù)用就結(jié)束。

第二個(gè)階段把剩下的老 fiber 放到 map 里，遍歷剩余的 vdom，一一查找 map 中是否有可復(fù)用的節(jié)點(diǎn)。

最后把剩下的老 fiber 刪掉，剩下的新 vdom 新增。

這樣就完成了更新時(shí)的 reconcile 過程。

其實(shí) diff 算法的核心就是復(fù)用節(jié)點(diǎn)，通過一一對(duì)比也好，通過 map 查找也好，都是為了找到可復(fù)用的節(jié)點(diǎn)，移動(dòng)過來。然后剩下的該刪刪該增增。

理解了如何找到可復(fù)用的節(jié)點(diǎn)，就理解了 diff 算法的核心。