本篇文章是《組件是怎樣寫的》系列文章的第一篇，該系列文章主要說一下各組件實現的具體邏輯，組件種類取自 element-plus 和 antd 組件庫。

每個組件都會有 vue 和 react 兩種實現方式，可以點擊 https://hhk-png.github.io/components-show/ 查看，項目的 github 地址為：https://github.com/hhk-png/components-show。

簡介

本片文章講解一下 虛擬列表 的實現，代碼主要來源于https://juejin.cn/post/7232856799170805820，然后在其基礎上做了一些優化。

如果在瀏覽器中渲染有大量數據數據的列表，比如 100 萬條，并且設置滾動，在打開這個頁面的時候，瀏覽器所承擔的渲染壓力將會急速放大，瀏覽器將會崩潰。虛擬列表應對該種情況的處理方式是將列表渲染時的計算量從渲染進程中轉換到了 js 中，從而降低瀏覽器的渲染壓力，使這種數量的列表可以正常渲染。

在用戶端，用戶對序列表做的操作主要是使用鼠標的滾輪滑動列表，或者通過拖拽滾動條的方式，兩者都會反映到元素的 scroll 事件上。因此，在實現虛擬列表時，主要是根據滑動距離挑選出特定的需要展示的列表項，每次滑動都執行該操作。

本文中，虛擬列表分為定高列表與不定高列表，僅考慮上下滑動的情況。在挑選需要展示的列表項時，要先獲取到列表項的起始位置與結束位置，然后將這一部分的元素截取出來。列表項的數量是手動設定的，對于定高列表，由于元素高度固定，所以元素總的高度也是固定的，選擇起始與結束位置時的時間復雜度和數組一樣是 O(1)。對于不定高列表，因為元素高度不確定，所以會在內部維護一個元素高度的緩存，需要根據該緩存得到要展示元素的起始坐標，元素高度通過 ResizeObserver 監聽元素獲取。

固定高度的虛擬列表 React 實現

本小節講一下 react 版本的定高虛擬列表的實現。虛擬列表和列表項的 props interface 如下：

export interface FixedRow {index: number // idstyle: React.CSSProperties
}export interface FixedSizeList {height: number // 虛擬列表所占用的高度width: number // 虛擬列表所占用的寬度itemSize: number // 列表項高度itemCount: number // 列表項數量children: React.ComponentType<FixedRow> // 被虛擬化的列表項
}

其中 FixedSizeList 為虛擬列表的 props interface，其中各變量的解釋以注釋的形式給出。children 為要虛擬的列表項，該值對應一個組件，其參數為 FixedRow。

組件的主要代碼如下，省略了 getCurrentChildren 的內容。

export const FixedSizeList: React.FC<FixedSizeList> = (props) => {const { height, width, itemCount, itemSize, children: Child } = propsconst [scrollOffset, setScrollOffset] = useState<number>(0)const cacheRef = useRef<Map<number, React.ReactNode>>(new Map())const containerStyle: CSSProperties = {position: 'relative',width,height,overflow: 'auto',}const contentStyle: CSSProperties = {height: itemSize * itemCount,width: '100%',}const getCurrentChildren = () => {/* ....省略 */}const scrollHandle = (event: React.UIEvent<HTMLDivElement>): void => {const { scrollTop } = event.currentTargetsetScrollOffset(scrollTop)}return (<div style={containerStyle} onScroll={scrollHandle}><div style={contentStyle}>{getCurrentChildren()}</div></div>)
}

html 的結構主要分為三個部分，最外層的 container 用于設置虛擬列表的寬高，對應的 style 為containerStyle，其中的 width 和 height 是從 props 中取出，然后設置了position: absolute 和 overflow:auto，這兩個屬性是為了模擬滾動條，并且可以監聽到 scroll 事件。第二部分是夾在中間的 content，目的是撐開外面的 container，使可以顯示出滾動條。在 contentStyle 中，寬度設置為了 100%，高度為列表項的數量乘以列表項的高度。最后一部分是虛擬化的列表項，通過 getCurrentChildren 函數獲得。

FixedSizeList 內部維護了一個 scrollOffset 狀態，onScroll 事件綁定在了 container 元素上，用戶觸發滾動、觸發 scroll 事件之后，會通過 setScrollOffset 重新指定 scrollOffset。狀態更新后，react 會重新渲染該組件，也會重新執行 getCurrentChildren 函數，getCurrentChildren 的返回值由 scrollOffset 狀態計算，所以在狀態更新之后就能夠看到預期的列表中的元素更新。getCurrentChildren 的實現如下：

const getCurrentChildren = () => {const startIndex = Math.floor(scrollOffset / itemSize)const finalStartIndex = Math.max(0, startIndex - 2)const numVisible = Math.ceil(height / itemSize)const endIndex = Math.min(itemCount, startIndex + numVisible + 2)const items = []for (let i = finalStartIndex; i < endIndex; i++) {if (cacheRef.current.has(i)) {items.push(cacheRef.current.get(i))} else {const itemStyle: React.CSSProperties = {position: 'absolute',height: itemSize,width: '100%',top: itemSize * i,}const item = <Child key={i} index={i} style={itemStyle}></Child>cacheRef.current.set(i, item)items.push(item)}}return items
}

getCurrentChildren 的目的是為了獲取在當前的 scrollOffset 下，后面需要展示的幾個連續的列表項，在這之后的列表項與 scrollOffset 之前的不予展示。起始索引為 Math.floor(scrollOffset / itemSize)，中間要展示的列表項的個數為 Math.ceil(height / itemSize)，結束位置的索引為 startIndex + numVisible，在起始位置之上加上要展示的項數。此處為了方式滑動時造成的空白區域，又將截取區間向外擴展了 2。

上述代碼中的 items 為要收集的列表項數組。每個列表項為一個組件，通過 position:absolute 的方式定位到展示區域，該子元素相對于前面講的最外層的 container 進行定位，top 設置為 itemSize * i 。子元素的索引作為子元素的 id，通過 cacheRef 緩存。

FixedSizeList 的使用方式如下：

const FixedRow: React.FC<FixedRow> = ({ index, style }) => {const backgroundColorClass = index % 2 === 0 ? 'bg-blue-100' : 'bg-white'return (<divclassName={`w-full ${backgroundColorClass} flex items-center justify-center`}style={{ ...style }}>Row {index}</div>)
}// ...;<FixedSizeList height={300} width={300} itemSize={50} itemCount={1000}>{FixedRow}
</FixedSizeList>

不固定高度的虛擬列表 React 實現

不定高的虛擬列表的實現邏輯與定高列表相似，但因為列表項的高度不固定，要做很多額外的處理。DynamicSizeList 的部分代碼如下：

interface MeasuredData {size: numberoffset: number
}type MeasuredDataMap = Record<number, MeasuredData>export interface DynamicRow {index: number
}export interface DynamicSizeListProps {height: numberwidth: numberitemCount: numberitemEstimatedSize?: numberchildren: React.ComponentType<DynamicRow>
}export const DynamicSizeList: React.FC<DynamicSizeListProps> = (props) => {const {height,width,itemCount,itemEstimatedSize = 50,children: Child,} = propsconst [scrollOffset, setScrollOffset] = useState(0)// 為了在接收到列表項高度發生變化時，觸發組件強制更新const [, setState] = useState({})// 緩存const measuredDataMap = useRef<MeasuredDataMap>({})const lastMeasuredItemIndex = useRef<number>(-1)const containerStyle: CSSProperties = {position: 'relative',width,height,overflow: 'auto',}const contentStyle: CSSProperties = {height: estimateHeight(itemEstimatedSize,itemCount,lastMeasuredItemIndex,measuredDataMap),width: '100%',}const sizeChangeHandle = (index: number, domNode: HTMLElement) => {/* ....省略 */}const getCurrentChildren = () => {/* ....省略 */}const scrollHandle = (event: React.UIEvent<HTMLDivElement>) => {const { scrollTop } = event.currentTargetsetScrollOffset(scrollTop)}return (<div style={containerStyle} onScroll={scrollHandle}><div style={contentStyle}>{getCurrentChildren()}</div></div>)
}

代碼的整體結構與之前的定高列表幾乎相同，在組件初始化時，組件并不知道列表項的高度，為了彌補這一缺陷，設定了一個默認的預測高度 itemEstimatedSize，在組件掛載后再將真實的列表項高度反映到緩存中。

上述代碼中的 measuredDataMap 用于緩存列表項的數據，其鍵為列表項的索引，值為一個包含項偏移與高度的對象。lastMeasuredItemIndex 為最后一個測量到的元素的索引。這兩個緩存項也可以直接放到組件外面，但如果這樣做的話，如果頁面上有多個 DynamicSizeList 組件實例，就會導致緩存污染。如果虛擬列表實例頻繁掛載/卸載，就會導致緩存的項數只增不減，緩存也不會被釋放，造成內存泄漏。因此將兩者放到組件內部，并使用 useRef 包裹，這樣可以確保每個實例使用的是不同的緩存，且緩存可以通過垃圾回收釋放。

此處用于撐起 container 的 content 中間層的高度通過 estimateHeight 函數計算，在計算時，如果沒有獲取到某個元素的高度，就會使用默認高度來填補其空缺，其實現如下所示：

const estimateHeight = (defaultItemSize: number = 50,itemCount: number,lastMeasuredItemIndex: React.RefObject<number>,measuredDataMap: React.RefObject<MeasuredDataMap>
): number => {let measuredHeight: number = 0if (lastMeasuredItemIndex.current >= 0) {const lastMeasuredItem =measuredDataMap.current[lastMeasuredItemIndex.current]measuredHeight = lastMeasuredItem.offset + lastMeasuredItem.size}const unMeasutedItemsCount = itemCount - lastMeasuredItemIndex.current - 1return measuredHeight + unMeasutedItemsCount * defaultItemSize
}

lastMeasuredItemIndex 之前的元素的高度是已知的，截至到該元素，所有元素的累計高度為該元素的偏移 offset 加上其對應的 size。lastMeasuredItemIndex 后面的元素高度沒有獲得，數量為 itemCount - lastMeasuredItemIndex.current - 1，因此使用默認高度 defaultItemSize 計算。lastMeasuredItemIndex 的值小于 0，代表還沒有初始化，因此會將所有元素的高度都看作為 defaultItemSize。此種方式計算的總高度是一個近似的大小，隨著用戶滑動列表，由該函數計算的總高度也會逐漸逼近真實的總高度。也因為這種處理方式，在用戶拖動滾動條時，會出現鼠標與滾動條脫離的情況。

由于 lastMeasuredItemIndex 和 measuredDataMap 用 useRef 包裹，放在組件當中，所以在分離邏輯的時候要以參數的形式傳遞，才可以實現狀態的共享。

下面介紹一下 getCurrentChildren 函數：

const getCurrentChildren = () => {const [startIndex, endIndex] = getRangeToRender(props,scrollOffset,lastMeasuredItemIndex,measuredDataMap)const items: ReactNode[] = []for (let i = startIndex; i <= endIndex; i++) {const item = getItemLayoutdata(props,i,lastMeasuredItemIndex,measuredDataMap)const itemStyle: CSSProperties = {position: 'absolute',height: item.size,width: '100%',top: item.offset,}items.push(<ListItemkey={i}index={i}style={itemStyle}ChildComp={Child}onSizeChange={sizeChangeHandle}/>)}return items
}

函數中，獲取截取區間的邏輯被抽象為了 getRangeToRender 函數，并且由于獲取列表項的幾何屬性時需要處理緩存問題，該操作也被抽象為了 getItemLayoutdata 函數，列表項 style 的處理與定高列表幾乎相同。

不定高虛擬列表使用 ResizeObserver 來獲取元素的真實高度，通過在要顯示的列表項之外包一層 ListItem 組件來實現。ListItem 組件中，在列表項的組件掛載后，通過 sizeChangeHandle 回調來更新列表項幾何屬性的緩存，然后觸發組件強制更新。ListItem 組件如下：

interface ListItemProps {index: numberstyle: React.CSSPropertiesChildComp: React.ComponentType<{ index: number }>onSizeChange: (index: number, domNode: HTMLElement) => void
}const ListItem: React.FC<ListItemProps> = React.memo(({ index, style, ChildComp, onSizeChange }) => {const domRef = useRef<HTMLDivElement>(null)useEffect(() => {if (!domRef.current) returnconst domNode = domRef.current.firstChild as HTMLElementconst resizeObserver = new ResizeObserver(() => {onSizeChange(index, domNode)})resizeObserver.observe(domNode)return () => {resizeObserver.unobserve(domNode)}}, [index, onSizeChange])return (<div style={style} ref={domRef}><ChildComp key={index} index={index} /></div>)},(prevProps, nextProps) =>prevProps.index === nextProps.index &&prevProps.style.top === nextProps.style.top &&prevProps.style.height === nextProps.style.height
)const sizeChangeHandle = (index: number, domNode: HTMLElement) => {const height = domNode.offsetHeightif (measuredDataMap.current[index]?.size !== height) {measuredDataMap.current[index].size = heightlet offset = measuredDataMap.current[index].offset + heightfor (let i = index + 1; i <= lastMeasuredItemIndex.current; i++) {const layoutData = measuredDataMap.current[i]layoutData.offset = offsetoffset += layoutData.size}setState({})}
}

ListItem 外面添加了一層 React.memo 緩存，設置為在 props 的 index 等屬性改變后進行緩存的更新。在 ResizeObserver 檢測到組件長寬發生變化后，就會調用 onSizeChange 回調更新元素高度。

在 sizeChangeHandle 函數中，在接收到更新后的元素高度后，會首先更新對應緩存中元素的高度，然后依此更新該位置之后元素的 offset，因為 index 位置元素高度的變化只會影響到該元素之后所有元素的 offset。更新完成之后通過更新之前定義的一個空狀態觸發組件的強制更新，即 setState({})。

getItemLayoutdata 函數用于獲取元素的幾何屬性，首先通過與 lastMeasuredItemIndex 判斷，查看 index 位置的元素是否已經獲取到，如果是，則直接返回結果。在 index 位置的元素的幾何屬性沒有被初始化時，則從 lastMeasuredItemIndex 開始更新這之間元素的幾何屬性緩存，元素的 size，也就是高度，被初始化為默認的值 itemEstimatedSize。之后將 lastMeasuredItemIndex 調整為 index，返回結果。直到元素掛載后，通過 sizeChangeHandle 才能獲取到真實值，更新到視圖上。

const getItemLayoutdata = (props: DynamicSizeListProps,index: number,lastMeasuredItemIndex: React.RefObject<number>,measuredDataMap: React.RefObject<MeasuredDataMap>
): MeasuredData => {const { itemEstimatedSize = 50 } = propsif (index > lastMeasuredItemIndex.current) {let offset = 0if (lastMeasuredItemIndex.current >= 0) {const lastItem = measuredDataMap.current[lastMeasuredItemIndex.current]offset += lastItem.offset + lastItem.size}for (let i = lastMeasuredItemIndex.current + 1; i <= index; i++) {measuredDataMap.current[i] = { size: itemEstimatedSize, offset }offset += itemEstimatedSize}lastMeasuredItemIndex.current = index}return measuredDataMap.current[index]
}

獲取當前 scrollOffset 下所需要展示的列表項的 getRangeToRender 函數如下所示，其中又分為 getStartIndex 和 getEndIndex，在其中如果要獲取元素的 offset 和 size，都需要經過 getItemLayoutdata。

getStartIndex 是為了獲取 scrollOffset 對應位置元素的索引，如果最后一個測量的元素的 offset 大于 scrollOffset，則直接啟動二分查找，如果不是，則使用指數查找，該算法在后面介紹。

getEndIndex 依賴于 getStartIndex，其 startIndex 參數為 getStartIndex 的返回值，在函數中 startIndex 對應 startItem。該函數的目的是獲取到 startItemoffset + height 位置對應的元素索引。

const getStartIndex = (props: DynamicSizeListProps,scrollOffset: number,lastMeasuredItemIndex: React.RefObject<number>,measuredDataMap: React.RefObject<MeasuredDataMap>
) => {if (scrollOffset === 0) {return 0}if (measuredDataMap.current[lastMeasuredItemIndex.current].offset >=scrollOffset) {return binarySearch(props,0,lastMeasuredItemIndex.current,scrollOffset,lastMeasuredItemIndex,measuredDataMap)}return expSearch(props,Math.max(0, lastMeasuredItemIndex.current),scrollOffset,lastMeasuredItemIndex,measuredDataMap)
}const getEndIndex = (props: DynamicSizeListProps,startIndex: number,lastMeasuredItemIndex: React.RefObject<number>,measuredDataMap: React.RefObject<MeasuredDataMap>
): number => {const { height, itemCount } = propsconst startItem = getItemLayoutdata(props,startIndex,lastMeasuredItemIndex,measuredDataMap)const maxOffset = startItem.offset + heightlet offset = startItem.offset + startItem.sizelet endIndex = startIndexwhile (offset <= maxOffset && endIndex < itemCount - 1) {endIndex++const currentItemLayout = getItemLayoutdata(props,endIndex,lastMeasuredItemIndex,measuredDataMap)offset += currentItemLayout.size}return endIndex
}const getRangeToRender = (props: DynamicSizeListProps,scrollOffset: number,lastMeasuredItemIndex: React.RefObject<number>,measuredDataMap: React.RefObject<MeasuredDataMap>
): [number, number] => {const { itemCount } = propsconst startIndex = getStartIndex(props,scrollOffset,lastMeasuredItemIndex,measuredDataMap)const endIndex = getEndIndex(props,startIndex,lastMeasuredItemIndex,measuredDataMap)return [Math.max(0, startIndex - 2), Math.min(itemCount - 1, endIndex + 2)]
}

getStartIndex 函數中，expSearch 是二分查找的一個變體，但也只能用于有序列表。其首先指數級的擴大查找范圍，然后確定了元素在某個范圍之后，再在這個范圍中進行二分查找。在前面的實現中，expSearch 的第二個參數 index 并不為 0，這可以理解為在進行查找之前設定了一個偏移，如果沒設置就會從 0 位置開始查找，如果設置，就會從 index 位置開始查找。

const expSearch = (props: DynamicSizeListProps,index: number,target: number,lastMeasuredItemIndex: React.RefObject<number>,measuredDataMap: React.RefObject<MeasuredDataMap>
) => {const { itemCount } = propslet exp = 1while (index < itemCount &&getItemLayoutdata(props, index, lastMeasuredItemIndex, measuredDataMap).offset < target) {index += expexp *= 2}return binarySearch(props,Math.floor(index / 2),Math.min(index, itemCount - 1),target,lastMeasuredItemIndex,measuredDataMap)
}const binarySearch = (props: DynamicSizeListProps,low: number,high: number,target: number,lastMeasuredItemIndex: React.RefObject<number>,measuredDataMap: React.RefObject<MeasuredDataMap>
) => {while (low <= high) {const mid = low + Math.floor((high - low) / 2)const currentOffset = getItemLayoutdata(props,mid,lastMeasuredItemIndex,measuredDataMap).offsetif (currentOffset === target) {return mid} else if (currentOffset < target) {low = mid + 1} else {high = mid - 1}}return Math.max(low - 1)
}

Vue 版本的虛擬列表實現

vue 版本的虛擬列表使用 SFC 實現，與 tsx 所不相同的是一個文件只能放置一個組件，因此需要將 tsx 中的組件拆到單個文件中。然后 vue 中嵌套組件需要通過 slot 的方式來實現。

vue 版本的具體實現邏輯與之前講的幾乎相同，因為寫代碼的時間距離寫博客相差較遠，所以基本上忘了兩者的異同，可以點擊http://localhost:5173/components-show或者https://github.com/hhk-png/components-show/tree/main/vue-components/src/components-show/VirtualList以查看具體實現，在此不作講述。

參考資料

https://juejin.cn/post/7232856799170805820