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