圖解 React 的 Diff 算法：核心就兩個(gè)字 — 復(fù)用
React 是基于 vdom 的前端框架，組件 render 產(chǎn)生 vdom，然后渲染器把 vdom 渲染出來。
state 更新的時(shí)候，組件會(huì)重新 render，產(chǎn)生新的 vdom，在瀏覽器平臺(tái)下，為了減少 dom 的創(chuàng)建，React 會(huì)對兩次的 render 結(jié)果做 diff，盡量復(fù)用 dom，提高性能。
diff 算法是前端框架中比較復(fù)雜的部分，代碼比較多，但今天我們不上代碼，只看圖來理解它。
首先，我們先過一下 react 的 fiber 架構(gòu)：
Fiber 架構(gòu)
React 是通過 jsx 描述頁面結(jié)構(gòu)的：
function 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ā)重新渲染，對比渲染出的新舊 vdom，對差異部分進(jìn)行 dom 操作。
在 16 之后，為了優(yōu)化性能，會(huì)先把 vdom 轉(zhuǎn)換成 fiber，也就是從樹轉(zhuǎn)換成鏈表，然后再渲染。整體渲染流程分成了兩個(gè)階段：
- render 階段：從 vdom 轉(zhuǎn)換成 fiber，并且對需要 dom 操作的節(jié)點(diǎn)打上 effectTag 的標(biāo)記。
- commit 階段：對有 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 做下對比，決定怎么產(chǎn)生新的 fiber，對可復(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 就行，不用和之前的做對比，這樣是可行的。
其實(shí) SSR 的時(shí)候就不用做 diff，因?yàn)闀?huì)把組件渲染成字符串，第二次渲染也是產(chǎn)生字符串，難道這時(shí)候還要和之前的字符串對比下，有哪些字符串可以復(fù)用么？
不需要，SSR 的時(shí)候就沒有 diff，每次都是 vdom 渲染出新的字符串。
那為什么瀏覽器里要做 diff 呢？
因?yàn)?dom 創(chuàng)建的性能成本很高，如果不做 dom 的復(fù)用，那前端框架的性能就太差了。
diff 算法的目的就是對比兩次渲染結(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ù)用呢？
一一對比下不就行了？
先把之前的 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í)候可以再簡化一下，比如上次渲染是 A、B、C、D，這次渲染也是 A、B、C、D，那直接順序?qū)Ρ认戮托校瑳]必要建立 map 再找。
所以 React 的 diff 算法是分成兩次遍歷的：
第一輪遍歷，一一對比 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è)例子，第一輪遍歷就是這樣的：
一一對比新的 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 對比下，再?zèng)Q定如何產(chǎn)生新的 fiber，目標(biāo)是盡可能復(fù)用已有的 fiber 節(jié)點(diǎn)，這叫做 diff 算法。
react 的 diff 算法分為兩個(gè)階段：
第一個(gè)階段一一對比，如果可以復(fù)用就下一個(gè)，不可以復(fù)用就結(jié)束。
第二個(gè)階段把剩下的老 fiber 放到 map 里，遍歷剩余的 vdom，一一查找 map 中是否有可復(fù)用的節(jié)點(diǎn)。
最后把剩下的老 fiber 刪掉，剩下的新 vdom 新增。
這樣就完成了更新時(shí)的 reconcile 過程。
其實(shí) diff 算法的核心就是復(fù)用節(jié)點(diǎn)，通過一一對比也好，通過 map 查找也好，都是為了找到可復(fù)用的節(jié)點(diǎn)，移動(dòng)過來。然后剩下的該刪刪該增增。
理解了如何找到可復(fù)用的節(jié)點(diǎn)，就理解了 diff 算法的核心。
