前端虛擬列表的實現原理
作者：字節跳動 fe @程翯
近期在某平臺開發迭代的過程中遇到了超長 List 嵌套在 antd Modal 里加載慢，卡頓的情況。於是心血來潮決定從零自己實現一個虛擬滾動列表來優化一下整體的體驗。
改造前：
我們可以看出來在改造之前，打開編輯窗口 Modal 的時候會出現短暫的卡頓，並且在點擊 Cancel 關閉後也並不是立即響應而是稍作遲疑之後才關閉的
改造後：
改造完成後我們可以觀察到整個 Modal 的打開比之前變得流暢了不少，可以做到立即響應用戶的點擊事件喚起 / 關閉 Modal
- 性能對比 Demo: https://codesandbox.io/s/a-v-list-has-dynamic-inner-height-modal-demo-l66py
0x0 基礎知識
所以什麼是虛擬滾動 / 列表呢？
一個虛擬列表是指當我們有成千上萬條數據需要進行展示但是用戶的 “視窗”（一次性可見內容）又不大時我們可以通過巧妙的方法只渲染用戶最大可見條數 +“BufferSize” 個元素並在用戶進行滾動時動態更新每個元素中的內容從而達到一個和長 list 滾動一樣的效果但花費非常少的資源。
(從上圖中我們可以發現實際用戶每次能看到的元素 / 內容只有 item-4 ~ item-13 也就是 9 個元素)
0x1 實現一個 “定高” 虛擬列表
-
首先我們需要定義幾個變量 / 名稱。
-
從上圖中我們可以看出來用戶實際可見區域的開始元素是 Item-4，所以他在數據數組中對應的下標也就是我們的
startIndex -
同理 Item-13 對應的數組下標則應該是我們的
endIndex -
所以 Item-1，Item-2 和 Item-3 則是被用戶的向上滑動操作所隱藏，所以我們稱它爲
startOffset(scrollTop)
因爲我們只對可視區域的內容做了渲染，所以爲了保持整個容器的行爲和一個長列表相似（滾動）我們必須保持原列表的高度，所以我們將 HTML 結構設計成如下
<!--ver 1.0 -->
<div class>
<div class>
...
<!-- item-1 -->
<!-- item-2 -->
<!-- item-3 -->
....
</div>
</div>-
其中：
-
vListContainer爲可視區域的容器，具有overflow-y: auto屬性。 -
在
phantom中的每條數據都應該具有position: absolute屬性 -
phantomContent則是我們的 “幻影” 部分，其主要目的是爲了還原真實 List 的內容高度從而模擬正常長列表滾動的行爲。 -
接着我們對
vListContainer綁定一個onScroll的響應函數，並在函數中根據原生滾動事件的 scrollTop 屬性來計算我們的startIndex和endIndex -
列表總高度:
phantomHeight = total * rowHeight -
可視範圍內展示元素數：
limit = Math.ceil(height/rowHeight) -
我們需要一個固定的列表元素高度：
rowHeight -
我們需要知道當前 list 一共有多少條數據:
total -
我們需要知道當前用戶可視區域的高度:
height -
在開始計算之前，我們先要定義幾個數值：
-
在有了上述數據之後我們可以通過計算得出下列數據：
（注意此處我們用的是向上取整）
- 所以我們可以在 onScroll 回調中進行下列計算：
onScroll(evt: any) {
// 判斷是否是我們需要響應的滾動事件
if (evt.target === this.scrollingContainer.current) {
const { scrollTop } = evt.target;
const { startIndex, total, rowHeight, limit } = this;
// 計算當前startIndex
const currentStartIndex = Math.floor(scrollTop / rowHeight);
// 如果currentStartIndex 和 startIndex 不同（我們需要更新數據了）
if (currentStartIndex !== startIndex ) {
this.startIndex = currentStartIndex;
this.endIndex = Math.min(currentStartIndedx + limit, total - 1);
this.setState({ scrollTop });
}
}
}- 當我們一旦有了 startIndex 和 endIndex 我們就可以渲染其對應的數據：
renderDisplayContent = () => {
const { rowHeight, startIndex, endIndex } = this;
const content = [];
// 注意這塊我們用了 <= 是爲了渲染x+1個元素用來在讓滾動變得連續（永遠渲染在判斷&渲染x+2）
for (let i = startIndex; i <= endIndex; ++i) {
// rowRenderer 是用戶定義的列表元素渲染方法，需要接收一個 index i 和
// 當前位置對應的style
content.push(
rowRenderer({
index: i,
style: {
width: '100%',
height: rowHeight + 'px',
position: "absolute",
left: 0,
right: 0,
top: i * rowHeight,
borderBottom: "1px solid #000",
}
})
);
}
return content;
};線上 Demo：https://codesandbox.io/s/a-naive-v-list-f0ghm
原理：
- 所以這個滾動效果究竟是怎麼實現的呢？首先我們在 vListContainer 中渲染了一個真實 list 高度的 “幻影” 容器從而允許用戶進行滾動操作。其次我們監聽了 onScroll 事件，並且在每次用戶觸發滾動是動態計算當前滾動 Offset（被滾上去隱藏了多少）所對應的開始下標（index）是多少。當我們發現新的下邊和我們當前展示的下標不同時進行賦值並且 setState 觸發重繪。當用戶當前的滾動 offset 未觸發下標更新時，則因爲本身 phantom 的長度關係讓虛擬列表擁有和普通列表一樣的滾動能力。當觸發重繪時因爲我們計算的是 startIndex 所以用戶感知不到頁面的重繪（因爲當前滾動的下一幀和我們重繪完的內容是一致的）。
優化：
- 對於上邊我們實現的虛擬列表，大家不難發現一但進行了快速滑動就會出現列表閃爍的現象 / 來不及渲染、空白的現象。還記得我們一開始說的 ** 渲染用戶最大可見條數 +“BufferSize” 麼？對於我們渲染的實際內容，我們可以對其上下加入 Buffer 的概念（即上下多渲染一些元素用來過渡快速滑動時來不及渲染的問題）。優化後的 onScroll 函數如下：
onScroll(evt: any) {
........
// 計算當前startIndex
const currentStartIndex = Math.floor(scrollTop / rowHeight);
// 如果currentStartIndex 和 startIndex 不同（我們需要更新數據了）
if (currentStartIndex !== originStartIdx) {
// 注意，此處我們引入了一個新的變量叫originStartIdx，起到了和之前startIndex
// 相同的效果，記錄當前的 真實 開始下標。
this.originStartIdx = currentStartIndex;
// 對 startIndex 進行 頭部 緩衝區 計算
this.startIndex = Math.max(this.originStartIdx - bufferSize, 0);
// 對 endIndex 進行 尾部 緩衝區 計算
this.endIndex = Math.min(
this.originStartIdx + this.limit + bufferSize,
total - 1
);
this.setState({ scrollTop: scrollTop });
}
}線上 Demo：https://codesandbox.io/s/A-better-v-list-bkw1t
0x2 列表元素高度自適應
現在我們已經實現了 “定高” 元素的虛擬列表的實現，那麼如果說碰到了高度不固定的超長列表的業務場景呢？
- 一般碰到不定高列表元素時有三種虛擬列表實現方式：
-
對輸入數據進行更改，傳入每一個元素對應的高度 dynamicHeight[i] = x x 爲元素 i 的行高
需要實現知道每一個元素的高度（不切實際）
-
將當前元素先在屏外進行繪製並對齊高度進行測量後再將其渲染到用戶可視區域內
這種方法相當於雙倍渲染消耗（不切實際）
-
傳入一個 estimateHeight 屬性先對行高進行估計並渲染，然後渲染完成後獲得真實行高並進行更新和緩存
會引入多餘的 transform（可以接受），會在後邊講爲什麼需要多餘的 transform...
- 讓我們暫時先回到 HTML 部分
<!--ver 1.0 -->
<div class>
<div class>
...
<!-- item-1 -->
<!-- item-2 -->
<!-- item-3 -->
....
</div>
</div>
<!--ver 1.1 -->
<div class>
<div class />
<div class>
...
<!-- item-1 -->
<!-- item-2 -->
<!-- item-3 -->
....
</div>
</div>-
在我們實現 “定高” 虛擬列表時，我們是採用了把元素渲染在
phantomContent容器裏，並且通過設置每一個 item 的position爲absolute加上定義top屬性等於i * rowHeight來實現無論怎麼滾動，渲染內容始終是在用戶的可視範圍內的。在列表高度不能確定的情況下，我們就無法準確的通過estimateHeight來計算出當前元素所處的 y 位置，所以我們需要一個容器來幫我們做這個絕對定位。 -
actualContent 則是我們新引入的列表內容渲染容器，通過在此容器上設置
position: absolute屬性來避免在每個 item 上設置。 -
有一點不同的是，因爲我們改用 actualContent 容器。當我們進行滑動時需要動態的對容器的位置進行一個 y-transform 從而實現容器永遠處於用戶的視窗之中：
getTransform() {
const { scrollTop } = this.state;
const { rowHeight, bufferSize, originStartIdx } = this;
// 當前滑動offset - 當前被截斷的（沒有完全消失的元素）距離 - 頭部緩衝區距離
return `translate3d(0,${
scrollTop -
(scrollTop % rowHeight) -
Math.min(originStartIdx, bufferSize) * rowHeight
}px,0)`;
}線上 Demo：https://codesandbox.io/s/a-v-list-achieved-by-transform-container-29mbc
(注：當沒有高度自適應要求時且沒有實現 cell 複用時，把元素通過 absolute 渲染在 phantom 裏會比通過 transform 的性能要好一些。因爲每次渲染 content 時都會進行重排，但是如果使用 transform 時就相當於進行了 ( 重排 + transform) > 重排）
-
回到列表元素高度自適應這個問題上來，現在我們有了一個可以在內部進行正常 block 排布的元素渲染容器（actualContent ），我們現在就可以直接在不給定高度的情況下先把內容都渲染進去。對於之前我們需要用 rowHeight 做高度計算的地方，我們統一替換成 estimateHeight 進行計算。
-
limit = Math.ceil(height / estimateHeight) -
phantomHeight = total * estimateHeight -
同時爲了避免重複計算每一個元素渲染後的高度 (getBoundingClientReact().height) 我們需要一個數組來存儲這些高度
interface CachedPosition {
index: number; // 當前pos對應的元素的下標
top: number; // 頂部位置
bottom: number; // 底部位置
height: number; // 元素高度
dValue: number; // 高度是否和之前(estimate)存在不同
}
cachedPositions: CachedPosition[] = [];
// 初始化cachedPositions
initCachedPositions = () => {
const { estimatedRowHeight } = this;
this.cachedPositions = [];
for (let i = 0; i < this.total; ++i) {
this.cachedPositions[i] = {
index: i,
height: estimatedRowHeight, // 先使用estimateHeight估計
top: i * estimatedRowHeight, // 同上
bottom: (i + 1) * estimatedRowHeight, // same above
dValue: 0,
};
}
};- 當我們計算完 (初始化完) cachedPositions 之後由於我們計算了每一個元素的 top 和 bottom，所以 phantom 的高度就是 cachedPositions 中最後一個元素的 bottom 值
this.phantomHeight = this.cachedPositions[cachedPositionsLen - 1].bottom;- 當我們根據 estimateHeight 渲染完用戶視窗內的元素後，我們需要對渲染出來的元素做實際高度更新，此時我們可以利用 componentDidUpdate 生命週期鉤子來計算、判斷和更新：
componentDidUpdate() {
......
// actualContentRef必須存在current （已經渲染出來） + total 必須 > 0
if (this.actualContentRef.current && this.total > 0) {
this.updateCachedPositions();
}
}
updateCachedPositions = () => {
// update cached item height
const nodes: NodeListOf<any> = this.actualContentRef.current.childNodes;
const start = nodes[0];
// calculate height diff for each visible node...
nodes.forEach((node: HTMLDivElement) => {
if (!node) {
// scroll too fast?...
return;
}
const rect = node.getBoundingClientRect();
const { height } = rect;
const index = Number(node.id.split('-')[1]);
const oldHeight = this.cachedPositions[index].height;
const dValue = oldHeight - height;
if (dValue) {
this.cachedPositions[index].bottom -= dValue;
this.cachedPositions[index].height = height;
this.cachedPositions[index].dValue = dValue;
}
});
// perform one time height update...
let startIdx = 0;
if (start) {
startIdx = Number(start.id.split('-')[1]);
}
const cachedPositionsLen = this.cachedPositions.length;
let cumulativeDiffHeight = this.cachedPositions[startIdx].dValue;
this.cachedPositions[startIdx].dValue = 0;
for (let i = startIdx + 1; i < cachedPositionsLen; ++i) {
const item = this.cachedPositions[i];
// update height
this.cachedPositions[i].top = this.cachedPositions[i - 1].bottom;
this.cachedPositions[i].bottom = this.cachedPositions[i].bottom - cumulativeDiffHeight;
if (item.dValue !== 0) {
cumulativeDiffHeight += item.dValue;
item.dValue = 0;
}
}
// update our phantom div height
const height = this.cachedPositions[cachedPositionsLen - 1].bottom;
this.phantomHeight = height;
this.phantomContentRef.current.style.height = `${height}px`;
};-
當我們現在有了所有元素的準確高度和位置值時，我們獲取當前 scrollTop (Offset) 所對應的開始元素的方法修改爲通過 cachedPositions 獲取：
因爲我們的 cachedPositions 是一個有序數組，所以我們在搜索時可以利用二分查找來降低時間複雜度
getStartIndex = (scrollTop = 0) => {
let idx = binarySearch<CachedPosition, number>(this.cachedPositions, scrollTop,
(currentValue: CachedPosition, targetValue: number) => {
const currentCompareValue = currentValue.bottom;
if (currentCompareValue === targetValue) {
return CompareResult.eq;
}
if (currentCompareValue < targetValue) {
return CompareResult.lt;
}
return CompareResult.gt;
}
);
const targetItem = this.cachedPositions[idx];
// Incase of binarySearch give us a not visible data(an idx of current visible - 1)...
if (targetItem.bottom < scrollTop) {
idx += 1;
}
return idx;
};
onScroll = (evt: any) => {
if (evt.target === this.scrollingContainer.current) {
....
const currentStartIndex = this.getStartIndex(scrollTop);
....
}
};- 二分查找實現：
export enum CompareResult {
eq = 1,
lt,
gt,
}
export function binarySearch<T, VT>(list: T[], value: VT, compareFunc: (current: T, value: VT) => CompareResult) {
let start = 0;
let end = list.length - 1;
let tempIndex = null;
while (start <= end) {
tempIndex = Math.floor((start + end) / 2);
const midValue = list[tempIndex];
const compareRes: CompareResult = compareFunc(midValue, value);
if (compareRes === CompareResult.eq) {
return tempIndex;
}
if (compareRes === CompareResult.lt) {
start = tempIndex + 1;
} else if (compareRes === CompareResult.gt) {
end = tempIndex - 1;
}
}
return tempIndex;
}- 最後，我們滾動後獲取 transform 的方法改造成如下:
getTransform = () =>
`translate3d(0,${this.startIndex >= 1 ? this.cachedPositions[this.startIndex - 1].bottom : 0}px,0)`;線上 Demo: https://codesandbox.io/s/a-v-list-has-dynamic-inner-height-yh0r7
本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/IC5yNkaOfvM9M-s3tj-jsg