請闡述vue的diff算法
diff是什么？diff就是比較兩棵樹，render會生成兩顆樹，一棵新樹newVnode，一棵舊樹oldVnode，然后兩棵樹進(jìn)行對比更新找差異就是diff，全稱difference，在vue里面 diff 算法是通過patch函數(shù)來完成的，所以有的時(shí)候也叫patch算法
? diff 發(fā)生的時(shí)機(jī)
diff發(fā)生在什么時(shí)候呢？當(dāng)然我們可以說在數(shù)據(jù)更新的時(shí)候發(fā)生diff，因?yàn)閿?shù)據(jù)更新會運(yùn)行render函數(shù)得到虛擬dom樹，最后頁面重新渲染。
當(dāng)組件創(chuàng)建的時(shí)候，組件所依賴的屬性或者數(shù)據(jù)變化時(shí)，會運(yùn)行一個函數(shù) (下面代碼中的updateComponent)，該函數(shù)會做兩件事：
運(yùn)行 _render生成一顆新的虛擬dom樹（vnode tree）運(yùn)行 _updata，傳入_render生成的虛擬dom樹的根節(jié)點(diǎn)，對新舊兩棵樹進(jìn)行對比，最終完成對真實(shí)dom的更新
核心代碼如下，跟原代碼有所差異，但都差不多，是這么個意思：
// vue構(gòu)造函數(shù)
function Vue(){
// ... 其他代碼
var updateComponent = () => {
this._update(this._render());
}
new Watcher(updateComponent);
// ... 其他代碼
}
diff就發(fā)生在_update函數(shù)的運(yùn)行過程中
代碼中先調(diào)用_render函數(shù)得到虛擬dom根節(jié)點(diǎn)，然后傳入_update函數(shù)中，在將updateComponent傳入Watcher中，watcher可以監(jiān)聽函數(shù)執(zhí)行的過程，監(jiān)測函數(shù)執(zhí)行期間用到了哪些響應(yīng)式數(shù)據(jù)并且進(jìn)行依賴收集，關(guān)于watcher可以瞅瞅我上一篇文章：一文帶你了解vue2之響應(yīng)式原理
?? _update函數(shù)在干什么？
_update函數(shù)會接收到一個vonde參數(shù)，這就是新生成的虛擬dom樹，同時(shí)，_update函數(shù)通過當(dāng)前組件的_vnode屬性，拿到舊的虛擬dom樹。_update函數(shù)首先會給組件的_vnode屬性重新賦值，讓它指向新樹
簡單用代碼表示：
function update(vnode){
//vnode新樹
//this._vnode舊樹
this._vnode = vnode
}
如果只考慮更新虛擬dom樹，這一步已經(jīng)完成了，但是最終目的是要更新頁面，所以就要用到diff進(jìn)行樹的節(jié)點(diǎn)對比，所以可以保存下舊樹oldVnode用于對比
簡單用代碼表示：
<body>
<div id="app"></div>
<script src="./vue.js"></script>
<script>
const vm = new Vue({
el: "#app",
});
function update(vnode) {
//vnode新樹
//this._vnode舊樹
let oldVnode = vm._vnode; //保存舊樹
this._vnode = vnode; //更新新樹
}
</script>
</body>
對比oldVnode和vnode就行了，「對比的目的就是更新真實(shí)dom」
接下來，會判斷舊樹oldVnode是否存在：
不存在：說明這是第一次加載組件，于是通過內(nèi)部的patch函數(shù)，直接遍歷新樹，為每個節(jié)點(diǎn)生成真實(shí)DOM，然后掛載到每個節(jié)點(diǎn)的 elm屬性上
簡單用代碼表示：
<body>
<div id="app"></div>
<script src="./vue.js"></script>
<script>
const vm = new Vue({
el: "#app",
});
console.log(vm);
function update(vnode) {
//vnode新樹
//this._vnode舊樹
let oldVnode = vm._vnode; //保存舊樹
this._vnode = vnode; //更新新樹
//如果舊樹oldVnode不存在
if(!oldVnode){
this.__patch__(vm.$el,vnode);
}
}
</script>
</body>
存在：說明之前已經(jīng)渲染過該組件，于是通過內(nèi)部的patch函數(shù)，對新舊兩棵樹進(jìn)行對比，從而達(dá)到下面兩個目標(biāo)：
完成對所有真實(shí)dom的最小化處理 讓新樹的節(jié)點(diǎn)對應(yīng)合適的真實(shí)dom
?? patch函數(shù)的對比流程
術(shù)語解釋：一會看到以下字眼，均代表以下意思
1.「相同」：是指兩個虛擬節(jié)點(diǎn)的標(biāo)簽類型和key值均相同，但input元素還要看type屬性。這個術(shù)語在vue源碼中叫sameVnode，它是一個函數(shù)，用來判斷兩個虛擬節(jié)點(diǎn)是不是同一個節(jié)點(diǎn)
例：兩個虛擬節(jié)點(diǎn)div是否相同
<div>法醫(yī)</div>
<div>前端獵手</div>
標(biāo)簽類型都為div，key值不僅僅在v-for遍歷中，也可以用在任何標(biāo)簽中，上面兩個div中沒有key值，所以都為undefined，所以標(biāo)簽類型和key值都相同，不用看內(nèi)容是否相同，它是另一個節(jié)點(diǎn)：文本節(jié)點(diǎn)
<div key="fayi">法醫(yī)</div>
<div key="qdls">前端獵手</div>
上面兩個虛擬節(jié)點(diǎn)是不同的，因?yàn)閗ey值不同
<input type="text">
<input type="radio">
上面兩個虛擬節(jié)點(diǎn)是不同的，因?yàn)閕nput不僅僅要看key值和標(biāo)簽類型，還要看type是否相同
2.「新建元素」：是指根據(jù)一個虛擬節(jié)點(diǎn)提供的信息，創(chuàng)建一個真實(shí)dom元素，同時(shí)掛載到虛擬節(jié)點(diǎn)的elm屬性上
3.「銷毀元素」：是指：vnode.elm.remove()
4.「更新」：是指對兩個虛擬節(jié)點(diǎn)進(jìn)行對比更新，它僅發(fā)生在兩個虛擬節(jié)點(diǎn)「相同」的情況下。具體過程稍后描述。
5.「對比子節(jié)點(diǎn)」：是指對兩個虛擬節(jié)點(diǎn)的子節(jié)點(diǎn)進(jìn)行對比，具體過程稍后描述
詳細(xì)流程
根節(jié)點(diǎn)比較
patch函數(shù)首先對根節(jié)點(diǎn)進(jìn)行對比
如果兩個節(jié)點(diǎn)：
「相同」，進(jìn)入「更新」流程
將舊節(jié)點(diǎn)的真實(shí)dom賦值到新節(jié)點(diǎn)： newVnode.elm = oldVnode.elem，舊節(jié)點(diǎn)會被垃圾回收機(jī)制回收對比新節(jié)點(diǎn)和舊節(jié)點(diǎn)的屬性，有變化的更新到真實(shí)dom中 當(dāng)前新舊兩個節(jié)點(diǎn)處理完成，開始 「對比子節(jié)點(diǎn)」
不 「相同」
新節(jié)點(diǎn) 「遞歸」，「新建元素」舊節(jié)點(diǎn) 「銷毀元素」
「對比子節(jié)點(diǎn)」
虛擬dom樹已經(jīng)完成，就剩修改真實(shí)dom了，但是修改真實(shí)dom的效率是比較耗時(shí)的，vue的原則是能不改就不改，盡量啥也別做，在「對比子節(jié)點(diǎn)」時(shí)，vue一切的出發(fā)點(diǎn)，都是為了：
盡量啥也別做
不行的話，盡量僅改動元素屬性
還不行的話，盡量移動元素，而不是刪除和創(chuàng)建元素
實(shí)在不行的話，刪除和創(chuàng)建元素
「對比流程：」
圖片說明：
黃色圓圈：表示舊子節(jié)點(diǎn)和新子節(jié)點(diǎn)所對應(yīng)的相同節(jié)點(diǎn)類型 數(shù)字：表示key值，用來區(qū)分是不是同一個節(jié)點(diǎn) 藍(lán)色方塊：表示對比之前舊子節(jié)點(diǎn)所對應(yīng)的真實(shí)dom 箭頭：分別表示頭指針和尾指針
接下來，我們要做的就是對比舊子節(jié)點(diǎn)和新子節(jié)點(diǎn)之間的差異，目標(biāo)是改變真實(shí)dom，并且將新虛擬子節(jié)點(diǎn)對應(yīng)到真實(shí)dom里面去，vue使用兩個指針分別指向新舊子節(jié)點(diǎn)樹的頭和尾
步驟：
首先對比新樹和舊樹的頭指針，瞅瞅兩個節(jié)點(diǎn)是否一樣，從圖中可以看到是一樣的，如果一樣則進(jìn)入 「更新」流程：先將舊節(jié)點(diǎn)的真實(shí)dom賦值到新節(jié)點(diǎn)（真實(shí)dom連線到新子節(jié)點(diǎn)），然后循環(huán)對比新舊節(jié)點(diǎn)的屬性，看看有沒有不一樣的地方，將有變化的更新到真實(shí)dom中，最后還要采用深度優(yōu)先（一顆樹的節(jié)點(diǎn)走到盡頭，再走另一個節(jié)點(diǎn)）的方式遞歸循環(huán)這兩個新舊子節(jié)點(diǎn)是否還有子節(jié)點(diǎn)，如果存在，則同理，這里我們就假設(shè)它不存子節(jié)點(diǎn)。灰色表示已經(jīng)處理完成，然后兩個頭指針往后移動
接下來，繼續(xù)比較兩個頭指針，看看兩個節(jié)點(diǎn)是否一樣，很明顯，兩個節(jié)點(diǎn)是不一樣的，因?yàn)閗ey值不同，不一樣的時(shí)候它不會銷毀刪除從建立，吃個??壓壓驚，淡定！前面有提到盡量別操作dom，它一定會找到一樣的節(jié)點(diǎn)，一條道走到黑，然后會對比尾指針，可以看到尾指針是一樣的，跟第一步是一樣的： 一頓操作猛如虎，先將舊節(jié)點(diǎn)的真實(shí)dom賦值到新節(jié)點(diǎn)（真實(shí)dom連線到新子節(jié)點(diǎn)），然后循環(huán)對比新舊節(jié)點(diǎn)的屬性，將有變化的更新到真實(shí)dom中，接著還要遞歸循環(huán)這兩個新舊子節(jié)點(diǎn)是否還有子節(jié)點(diǎn)，最后兩個尾指針往前移動
然后繼續(xù)比較頭指針，很明顯不一樣，尾指針呢？也不一樣，因?yàn)閗ey值還是不一樣。隨后它會比較頭指針和尾指針，看看是否一樣，可以看到舊節(jié)點(diǎn)的圓2頭指針和新節(jié)點(diǎn)圓2尾指針是一樣的，所以操作跟前兩步是一樣的，又是 一頓操作猛如虎，結(jié)果如下圖：
這里我們要注意的是真實(shí)dom必須和新虛擬子節(jié)點(diǎn)要一一對應(yīng)上的，所以除了更新變化的地方之外還要進(jìn)行位置移動，移動到舊樹尾指針的后面，最后舊樹頭指針往后移動，新樹尾指針往前移動，如下圖：
繼續(xù)比對，新舊頭指針不同，尾指針不同，兩個頭尾也不同，然后它會以新樹頭指針為基準(zhǔn)，循環(huán)舊虛擬子節(jié)點(diǎn)，看看新樹圓3是否存在于舊虛擬子節(jié)點(diǎn)，存在的話在哪個位置，找到之后進(jìn)行復(fù)用，連線，有變化的地方更新到真實(shí)dom，操作跟前面幾步一樣，真實(shí)dom也要進(jìn)行 位置移動，移動到舊樹頭指針之前。隨后新樹頭指針繼續(xù)往后移動到圓9位置，如下圖:
繼續(xù)比對，新舊頭指針不同，尾指針不同，但新樹頭指針和舊樹尾指針相同，操作跟前面幾步相同，但依然需要進(jìn)行位置移動，移動到舊樹頭指針之前。隨后新樹頭指針往后移動，與新樹尾指針重合，舊樹尾指針向前移動到圓1位置，如下圖：
繼續(xù)比對，新舊兩樹頭指針不同，尾指針不同，兩個頭尾也不同，然后它以新樹頭指針為基準(zhǔn)，循環(huán)舊虛擬子節(jié)點(diǎn)，找圓8在舊樹中存不存在，從圖中可以看出，并不存在，這個時(shí)候確實(shí)沒辦法了，只能 「新建元素」。隨后新樹頭指針繼續(xù)向后移動到圓2位置，如圖：
當(dāng)頭指針移動到圓2位置時(shí)，頭指針已經(jīng)不再是有效的了，當(dāng)頭指針超過尾指針的時(shí)候，循環(huán)結(jié)束，從過程我們可以看到新樹先循環(huán)完成，但是舊樹還有剩余的節(jié)點(diǎn)，這說明舊樹中剩余的節(jié)點(diǎn)都是應(yīng)該被刪除的節(jié)點(diǎn)，所對應(yīng)的真實(shí)dom也會被移除
最終真實(shí)dom生成完畢，整個過程我們只新建了一個元素，如下圖：
在面試的時(shí)候也會被問到關(guān)于diff算法的問題，以下是參考回答：
當(dāng)組件創(chuàng)建和更新時(shí)，vue會執(zhí)行內(nèi)部的update函數(shù)，該函數(shù)使用render函數(shù)生成的虛擬dom樹，將新舊兩樹進(jìn)行對比，找到差異點(diǎn)，最終更新到真實(shí)dom
對比差異的過程叫diff，vue在內(nèi)部通過一個叫patch的函數(shù)完成該過程
在對比時(shí)，vue采用深度優(yōu)先、同級比較的方式進(jìn)行比對。同級比較就是說它不會跨越結(jié)構(gòu)進(jìn)行比較
在判斷兩個節(jié)點(diǎn)是否相同時(shí)，vue是通過虛擬節(jié)點(diǎn)的key和tag來進(jìn)行判斷的
具體來說，首先對根節(jié)點(diǎn)進(jìn)行對比，如果相同則將舊節(jié)點(diǎn)關(guān)聯(lián)的真實(shí)dom的引用掛到新節(jié)點(diǎn)上，然后根據(jù)需要更新屬性到真實(shí)dom，然后再對比其子節(jié)點(diǎn)數(shù)組；如果不相同，則按照新節(jié)點(diǎn)的信息遞歸創(chuàng)建所有真實(shí)dom，同時(shí)掛到對應(yīng)虛擬節(jié)點(diǎn)上，然后移除掉舊的dom。
在對比其子節(jié)點(diǎn)數(shù)組時(shí)，vue對每個子節(jié)點(diǎn)數(shù)組使用了兩個指針，分別指向頭尾，然后不斷向中間靠攏來進(jìn)行對比，這樣做的目的是盡量復(fù)用真實(shí)dom，盡量少的銷毀和創(chuàng)建真實(shí)dom。如果發(fā)現(xiàn)相同，則進(jìn)入和根節(jié)點(diǎn)一樣的對比流程，如果發(fā)現(xiàn)不同，則移動真實(shí)dom到合適的位置。
這樣一直遞歸的遍歷下去，直到整棵樹完成對比。
?? 好了， 以上就是我的分享，大家對于diff算法還有其它理解的話可以在評論區(qū)討論鴨～
希望小伙伴們點(diǎn)贊 ?? 支持一下哦～ ??，我會更有動力的 ??