vue2採用了頭尾雙指針的方法,每次比對時,優先進行頭頭、尾尾、頭尾、尾頭的比對嘗試,如果都沒有命中才會進行亂序比對。 ...
什麼是虛擬DOM
DOM是很慢的,其元素非常龐大,當我們頻繁的去做 DOM更新,會產生一定的性能問題,我們可以直觀感受一下 div元素包含的海量屬性
在Javascript對象中,虛擬DOM
表現為一個 Object對象(以VNode 節點作為基礎的樹)。並且最少包含標簽名tag
、屬性attrs
和子元素對象children
三個屬性,不同框架對這三個屬性的名命可能會有差別。
<ul style="color: #de5e60; border: 1px solid #de5e60">
<li key="a">a</li>
<li key="b">b</li>
<li key="c">c</li>
</ul>
真實節點對應的虛擬DOM:
const VDOM = {
tag: 'ul',
data: {
style: { color: '#de5e60', border: '1px solid #de5e60' },
},
children: [
{
tag: 'li',
key: 'a',
data: {},
children: [{ text: 'a' }],
},
{
tag: 'li',
key: 'b',
data: {},
children: [{ text: 'b'}],
},
{
tag: 'li',
key: 'c',
data: {},
children: [{ text: 'c'}],
},
],
}
我們常說虛擬DOM可以提升效率。這句話是不嚴謹的❌
通過虛擬DOM
改變真正的 DOM並不比直接操作 DOM效率更高。恰恰相反,我們仍需要調用DOM API
去操作 DOM,並且虛擬DOM
還會額外占用記憶體!
but!!!我們可以通過 虛擬DOM
+ diff演算法
,找到需要更新的最小單位,最大限度地減少DOM操作,從而提升性能。
什麼是Diff
Dom 是多叉樹結構,完整對比兩棵樹的差異,時間複雜度是O(n³)
,這個複雜度會導致比對性能很差!
為了優化,Diff 演算法約定只做同層級節點比對,而不是跨層級節點比對,即深度優先遍歷演算法,其複雜度為O(n)
Diff原理
當數據修改後會觸發setter
劫持操作,我們在setter
中執行dep.notity()
,通知所有的訂閱者watcher
重新渲染。
訂閱者watcher
這時會在回調內部,通過vm._render()
獲取最新的虛擬DOM
;然後通過patch
方法比對新舊虛擬DOM
,給真實元素打補丁,更新視圖
createElm
利用vnode
創建真實元素,有一個巧妙的地方是,我們把真實元素掛載到了vnode
上,便於我們後續通過虛擬節點去操作對應的真實元素
export function createElm(vnode) {
let { tag, data, children, text } = vnode
// 標簽
if (typeof tag === 'string') {
// 將真實節點掛載到虛擬節點上
vnode.el = document.createElement(tag)
patchProps(vnode.el, {}, data)
children.forEach(child => {
vnode.el.appendChild(createElm(child))
})
} else {
// 文本
vnode.el = document.createTextNode(text)
}
return vnode.el
}
sameVnode
判斷是否是相同節點,節點的tag和節點的key都相同
export function isSameVnode(vnode1, vnode2) {
return vnode1.tag === vnode2.tag && vnode1.key === vnode2.key
}
patch
patch方法有兩大作用,一個是初始化元素 ,另一個是更新元素
export function patch(oldVNode, vnode) {
const isRealElement = oldVNode.nodeType
// 初渲染元素
if (isRealElement) {
const elm = oldVNode // 獲取真實元素
const parentElm = elm.parentNode // 拿到父元素
let newElm = createElm(vnode) // 根據vnode創建元素
parentElm.insertBefore(newElm, elm.nextSibling) // 插入剛剛創建的元素
parentElm.removeChild(elm) // 刪除舊節點
return newElm
} else {
// 更新元素
return patchVnode(oldVNode, vnode)
}
}
patchVnode
比對新舊虛擬節點打補丁,diff比對規則如下:
- 新舊節點不相同(判斷節點的tag和節點的key),直接用新節點替換舊節點,無需比對
- 新舊節點相同,且都是文本節點,更新文本內容即可
- 新舊節點是同一個節點,比較兩個節點的屬性是否有差異,復用舊的節點,將差異的屬性更新
- 節點比較完畢後,需要比較兩個節點的兒子
- 新舊節點都有兒子,調用
updateChildren()
,這裡是diff演算法核心邏輯!後面會詳細講解 - 新節點有兒子,舊節點沒有兒子,將新的子節點掛載到
oldVNode.el
上 - 舊節點有兒子,新節點沒有兒子,刪除
oldVNode.el
的所有子節點
- 新舊節點都有兒子,調用
function patchVnode(oldVNode, vnode) {
// 1. 新舊節點不相同(判斷節點的tag和節點的key),直接用新節點替換舊節點,無需比對
if (!isSameVnode(oldVNode, vnode)) {
let el = createElm(vnode)
oldVNode.el.parentNode.replaceChild(el, oldVNode.el)
return el
}
let el = (vnode.el = oldVNode.el)
// 2. 新舊節點相同,且是文本 (判斷節點的tag和節點的key),比較文本內容
if (!oldVNode.tag) {
if (oldVNode.text !== vnode.text) {
el.textContent = vnode.text // 用新的文本覆蓋掉舊的
}
}
// 3. 新舊節點相同,且是標簽 (判斷節點的tag和節點的key)
// 3.1 比較標簽屬性
patchProps(el, oldVNode.data, vnode.data)
let oldChildren = oldVNode.children || []
let newChildren = vnode.children || []
// 4 比較兩個節點的兒子
// 4.1 新舊節點都有兒子
if (oldChildren.length > 0 && newChildren.length > 0) {
// diff演算法核心!!!
updateChildren(el, oldChildren, newChildren)
}
// 4.2 新節點有兒子,舊節點沒有兒子,掛載
else if (newChildren.length > 0) {
mountChildren(el, newChildren)
}
// 4.3 舊節點有兒子,新節點沒有兒子,刪除
else if (oldChildren.length > 0) {
el.innerHTML = ''
}
}
updateChildren(Diff核心演算法)
這個方法是diff比對的核心!
vue2中採用了頭尾雙指針的方式,通過頭頭、尾尾、頭尾、尾頭、亂序五種比對方式,進行新舊虛擬節點的依次比對
在比對過程中,我們需要四個指針,分別指向新舊列表的頭部和尾部。為了方便我們理解,我使用了不同顏色和方向的箭頭加以區分,圖例如下:
雙端比對
頭頭比對
舊孩子的頭 比對 新孩子的頭
如果是相同節點,則調用patchVnode
打補丁並遞歸比較子節點;然後將 新舊列表的頭指針
都向後移動
終止條件:雙方有一方頭指針大於尾指針,則停止迴圈
if (isSameVnode(oldStartVnode, newStartVnode)) {
patchVnode(oldStartVnode, newStartVnode)
oldStartVnode = oldChildren[++oldStartIndex]
newStartVnode = newChildren[++newStartIndex]
}
尾尾比對
舊孩子的尾 和 新孩子的尾比較
如果是相同節點,則調用patchVnode
打補丁並遞歸比較子節點;然後將 新舊列表的尾指針
都向前移動
終止條件:雙方有一方頭指針大於尾指針,則停止迴圈
else if (isSameVnode(oldEndVnode, newEndVnode)) {
patchVnode(oldEndVnode, newEndVnode)
oldEndVnode = oldChildren[--oldEndIndex]
newEndVnode = newChildren[--newEndIndex]
}
頭尾比對
舊孩子的頭 和 新孩子的尾比較
如果是相同節點,則調用patchVnode
打補丁並遞歸比較子節點;然後將 oldStartVnode
移動到 oldEndVnode
的後面(把 舊列表頭指針指向的節點
移動到 舊列表尾指針指向的節點
後面)
最後把 舊列表頭指針
向後移動,新列表尾指針
向前移動
終止條件:雙方有一方頭指針大於尾指針,則停止迴圈
else if (isSameVnode(oldStartVnode, newEndVnode)) {
patchVnode(oldStartVnode, newEndVnode)
el.insertBefore(oldStartVnode.el, oldEndVnode.el.nextSibling)
oldStartVnode = oldChildren[++oldStartIndex]
newEndVnode = newChildren[--newEndIndex]
}
尾頭比對
舊孩子的尾 和 新孩子的頭比較
如果是相同節點,則調用patchVnode
打補丁並遞歸比較子節點;然後將 oldEndVnode
移動到 oldStartVnode
的前面(把 舊列表尾指針指向的節點
移動到 舊列表頭指針指向的節點
前面)
最後把 舊列表尾指針
向前移動,新列表頭指針
向後移動
終止條件:雙方有一方頭指針大於尾指針,則停止迴圈
else if (isSameVnode(oldEndVnode, newStartVnode)) {
patchVnode(oldEndVnode, newStartVnode)
el.insertBefore(oldEndVnode.el, oldStartVnode.el)
oldEndVnode = oldChildren[--oldEndIndex]
newStartVnode = newChildren[++newStartIndex]
}
亂序比對
每次比對時,優先進行頭頭、尾尾、頭尾、尾頭的比對嘗試,如果都沒有命中才會進行亂序比較
- 我們根據舊的列表創建一個
key -> index
的映射表,拿新的兒子去映射關係里查找。註意:查找時只能找得到key相同的老節點,並沒判斷tag - 若找的到相同key的老節點並且是相同節點,則復用節點移動到
oldStartVnode
(舊列表頭指針指向的節點)的前面,然後調用patchVnode
打補丁遞歸比較子節點(移動走的老位置要做空標記,表示這個舊節點已經被移動過了,後續比對時可直接跳過此節點) - 否則,創建節點並移動到
oldStartVnode
(舊列表頭指針指向的節點)的前面 - 只需將
新列表頭指針
向後移動即可 - 最後刪除老列表中多餘的節點,此過程在下一章掛載卸載階段刪除掉
終止條件:雙方有一方頭指針大於尾指針,則停止迴圈
----------------- 創建映射關係 -----------------------
function makeIndexByKey(children) {
let map = {}
children.forEach((child, index) => {
map[child.key] = index
})
return map
}
// 舊孩子映射表(key-index),用於亂序比對
let map = makeIndexByKey(oldChildren)
-------------------- 亂序比對 -------------------------
if (!oldStartVnode) {
oldStartVnode = oldChildren[++oldStartIndex]
continue
}
if (!oldEndVnode) {
oldEndVnode = oldChildren[--oldEndIndex]
continue
}
let moveIndex = map[newStartVnode.key]
// 找的到相同key的老節點,並且是相同節點
if (moveIndex !== undefined && isSameVnode(oldChildren[moveIndex], newStartVnode)) {
let moveVnode = oldChildren[moveIndex] // 復用舊的節點
el.insertBefore(moveVnode.el, oldStartVnode.el) // 將 moveVnode 移動到 oldStartVnode的前面(把復用節點 移動到 舊列表頭指針指向的節點 前面)
oldChildren[moveIndex] = undefined // 表示這個舊節點已經被移動過了
patchVnode(moveVnode, newStartVnode) // 遞歸比較子節點
}
// 找不到相同key的老節點 or 找的到相同key的老節點但tag不相同
else {
el.insertBefore(createElm(newStartVnode), oldStartVnode.el) // 將 創建的節點 移動到 oldStartVnode的前面(把創建的節點 移動到 舊列表頭指針指向的節點 前面)
}
newStartVnode = newChildren[++newStartIndex]
掛載卸載
終止條件:雙方有一方頭指針大於尾指針,則停止迴圈。當迴圈比對結束後,我們需要將新列表中多餘的節點插入到oldVNode.el
中,並將老列表中多餘的節點刪除掉。
我們將其劃分為4種場景,可參考頭頭比對、尾尾比對章節的圖輔助理解
- 同序列尾部掛載:
新列表頭指針
到新列表尾指針
的節點需要掛載新增,向後追加 - 同序列頭部掛載:
新列表頭指針
到新列表尾指針
的節點需要掛載新增,向前追加 - 同序列尾部卸載:
舊列表頭指針
到舊列表尾指針
的節點需要卸載刪除 - 同序列頭部卸載: 和 同序列尾部卸載 邏輯一致
tip:何時向後追加,何時向前追加,我們根據什麼去判斷的呢?
若 新列表尾指針指向的節點
的下一個節點存在,則向前追加,插入到newChildren[newEndIndex + 1].el
的前面;若不存在,則向後追加,插入到oldVNode.el
子節點列表的末尾處
// 同序列尾部掛載,向後追加
// a b c d
// a b c d e f
// 同序列頭部掛載,向前追加
// a b c d
// e f a b c d
if (newStartIndex <= newEndIndex) {
for (let i = newStartIndex; i <= newEndIndex; i++) {
let childEl = createElm(newChildren[i])
// 這裡可能是向後追加 ,也可能是向前追加
let anchor = newChildren[newEndIndex + 1] ? newChildren[newEndIndex + 1].el : null
el.insertBefore(childEl, anchor) // anchor為null的時候等同於 appendChild
}
}
// 同序列尾部卸載,刪除尾部多餘的舊孩子
// a b c d e f
// a b c d
// 同序列頭部卸載,刪除頭部多餘的舊孩子
// e f a b c d
// a b c d
if (oldStartIndex <= oldEndIndex) {
for (let i = oldStartIndex; i <= oldEndIndex; i++) {
if (oldChildren[i]) {
let childEl = oldChildren[i].el
el.removeChild(childEl)
}
}
}
總結
vue2採用了頭尾雙指針的方法,每次比對時,優先進行頭頭、尾尾、頭尾、尾頭的比對嘗試,如果都沒有命中才會進行亂序比對
當比對命中時(新舊節點是相同的),則調用patchVnode
打補丁並遞歸比較子節點;打完補丁後呢,如果該節點是頭指針指向的節點
就向後移動指針,是尾指針指向的節點
則向前移動指針
終止條件:雙方有一方頭指針大於尾指針,則停止迴圈
如果雙端比對中的頭尾、尾頭命中了節點,也需要進行節點移動操作,為什麼不直接用亂序比對呢,沒理解其優勢在哪?
但是雙端diff
相比於簡單diff
性能肯定會更好一些,例如:從 ABCD
到 DABC
。簡單diff
需要移動 ABC 三個節點,但是雙端diff
只需要移動 D 一個節點
關於簡單diff的介紹可移步此文章 - 聊聊 Vue 的雙端 diff 演算法
tip:vue3中並沒有頭尾、尾頭比對的概念;新增了最長遞增子序列演算法去優化亂序比對,減少了亂序比對中節點的移動次數
updateChildren 核心代碼如下:
function updateChildren(el, oldChildren, newChildren) {
let oldStartIndex = 0
let newStartIndex = 0
let oldEndIndex = oldChildren.length - 1
let newEndIndex = newChildren.length - 1
let oldStartVnode = oldChildren[0]
let newStartVnode = newChildren[0]
let oldEndVnode = oldChildren[oldEndIndex]
let newEndVnode = newChildren[newEndIndex]
function makeIndexByKey(children) {
let map = {}
children.forEach((child, index) => {
map[child.key] = index
})
return map
}
// 舊孩子映射表(key-index),用於亂序比對
let map = makeIndexByKey(oldChildren)
// 雙方有一方頭指針大於尾部指針,則停止迴圈
while (oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex) {
if (!oldStartVnode) {
oldStartVnode = oldChildren[++oldStartIndex]
continue
}
if (!oldEndVnode) {
oldEndVnode = oldChildren[--oldEndIndex]
continue
}
// 雙端比較_1 - 舊孩子的頭 比對 新孩子的頭;
// 都從頭部開始比對(對應場景:同序列尾部掛載-push、同序列尾部卸載-pop)
if (isSameVnode(oldStartVnode, newStartVnode)) {
patchVnode(oldStartVnode, newStartVnode) // 如果是相同節點,則打補丁,並遞歸比較子節點
oldStartVnode = oldChildren[++oldStartIndex]
newStartVnode = newChildren[++newStartIndex]
}
// 雙端比較_2 - 舊孩子的尾 比對 新孩子的尾;
// 都從尾部開始比對(對應場景:同序列頭部掛載-unshift、同序列頭部卸載-shift)
else if (isSameVnode(oldEndVnode, newEndVnode)) {
patchVnode(oldEndVnode, newEndVnode) // 如果是相同節點,則打補丁,並遞歸比較子節點
oldEndVnode = oldChildren[--oldEndIndex]
newEndVnode = newChildren[--newEndIndex]
}
// 雙端比較_3 - 舊孩子的頭 比對 新孩子的尾;
// 舊孩子從頭部開始,新孩子從尾部開始(對應場景:指針儘可能向內靠攏;極端場景-reverse)
else if (isSameVnode(oldStartVnode, newEndVnode)) {
patchVnode(oldStartVnode, newEndVnode)
el.insertBefore(oldStartVnode.el, oldEndVnode.el.nextSibling) // 將 oldStartVnode 移動到 oldEndVnode的後面(把當前節點 移動到 舊列表尾指針指向的節點 後面)
oldStartVnode = oldChildren[++oldStartIndex]
newEndVnode = newChildren[--newEndIndex]
}
// 雙端比較_4 - 舊孩子的尾 比對 新孩子的頭;
// 舊孩子從尾部開始,新孩子從頭部開始(對應場景:指針儘可能向內靠攏;極端場景-reverse)
else if (isSameVnode(oldEndVnode, newStartVnode)) {
patchVnode(oldEndVnode, newStartVnode)
el.insertBefore(oldEndVnode.el, oldStartVnode.el) // 將 oldEndVnode 移動到 oldStartVnode的前面(把當前節點 移動到 舊列表頭指針指向的節點 前面)
oldEndVnode = oldChildren[--oldEndIndex]
newStartVnode = newChildren[++newStartIndex]
}
// 亂序比對
// 根據舊的列表做一個映射關係,拿新的節點去找,找到則移動;找不到則添加;最後刪除多餘的舊節點
else {
let moveIndex = map[newStartVnode.key]
// 找的到相同key的老節點,並且是相同節點
if (moveIndex !== undefined && isSameVnode(oldChildren[moveIndex], newStartVnode)) {
let moveVnode = oldChildren[moveIndex] // 復用舊的節點
el.insertBefore(moveVnode.el, oldStartVnode.el) // 將 moveVnode 移動到 oldStartVnode的前面(把復用節點 移動到 舊列表頭指針指向的節點 前面)
oldChildren[moveIndex] = undefined // 表示這個舊節點已經被移動過了
patchVnode(moveVnode, newStartVnode) // 比對屬性和子節點
}
// 找不到相同key的老節點 or 找的到相同key的老節點但tag不相同
else {
el.insertBefore(createElm(newStartVnode), oldStartVnode.el) // 將 創建的節點 移動到 oldStartVnode的前面(把創建的節點 移動到 舊列表頭指針指向的節點 前面)
}
newStartVnode = newChildren[++newStartIndex]
}
}
// 同序列尾部掛載,向後追加
// a b c d
// a b c d e f
// 同序列頭部掛載,向前追加
// a b c d
// e f a b c d
if (newStartIndex <= newEndIndex) {
for (let i = newStartIndex; i <= newEndIndex; i++) {
let childEl = createElm(newChildren[i])
// 這裡可能是向後追加 ,也可能是向前追加
let anchor = newChildren[newEndIndex + 1] ? newChildren[newEndIndex + 1].el : null // 獲取下一個元素
// el.appendChild(childEl);
el.insertBefore(childEl, anchor) // anchor為null的時候等同於 appendChild
}
}
// 同序列尾部卸載,刪除尾部多餘的舊孩子
// a b c d e f
// a b c d
// 同序列頭部卸載,刪除頭部多餘的舊孩子
// e f a b c d
// a b c d
if (oldStartIndex <= oldEndIndex) {
for (let i = oldStartIndex; i <= oldEndIndex; i++) {
if (oldChildren[i]) {
let childEl = oldChildren[i].el
el.removeChild(childEl)
}
}
}
}
常見問題
為什麼不建議key用索引
我們先看一段代碼。其效果是:當點擊按鈕後,會在數組前面追加一項數據
/** template代碼 */
<div id="app">
<ul class="ul-wrap">
<li v-for="(item,index) in arr" :key="index">
{{item.name}} <input type="checkbox">
</li>
</ul>
<button @click="append">追加</button>
</div>
/** js代碼 */
let vm = new Vue({
el: '#app',
data() {
return {
arr: [{ id: 0, name: '柏成0號' },
{ id: 1, name: '柏成1號' },
{ id: 2, name: '柏成2號' }]
}
},
methods: {
append() {
this.arr.unshift({
id: 7,
name: '柏成7號'
});
}
}
})
index作為key
使用index作為key時,運行結果如下:
我們會發現一個神奇的現象,雖然只unshift
了一條數據,但是所有的li標簽
都更新了。並且新增的柏成7號節點
還復用了柏成0號節點
的checkbox多選框!!!
其原理就是,我們在進行頭頭比對時,前三項雖然可以匹配到相同節點(標簽名和key都相同),但其內容並非一致,所以進行了打補丁更新操作。然後我們又創建一個key為3
的柏成2號節點
插入到列表尾部
id作為key
使用id作為key時,運行結果如下:
這次的diff更新就符合了我們的預期效果,它找到需要更新的最小單位,即只會新增key為3
的柏成7號節點
,最大限度地減少DOM操作
此時我們在進行尾尾比對時,後三項都可以匹配到相同節點(標簽名和key都相同),而且會發現無需更新任何內容。然後去創建一個key為7
的柏成7號節點
插入列表頭部,嚴格來說是插入新列表頭指針下一個虛擬節點對應的真實元素newChildren[newEndIndex + 1].el
前面
參考文章
diff 演算法深入一下?
聊聊 Vue 的雙端 diff 演算法
15張圖,20分鐘吃透Diff演算法核心原理,我說的!!!
第三十篇 - diff 演算法