虚拟滚动的实现
2020-09-16阅读量
在上家公司最后一个项目本来想用一下虚拟滚动的，结果项目黄了，没用上。正好最近面试某厂线下笔试题里有这么一道:
/**
* 使用 纯 JS / react/Vue/typescript 写一个 Grid 组件要求：
* 能够加载1W + 数据，加载和查看数据时不卡顿
* 能够对单元格进行格式化
* 扩展功能表头resize（拖拽等功能）
*/不就是虚拟滚动么，正好搞起来。实现上参(co)考(py)react-window的Grid组件，代码库：https://github.com/xiao555/virtual-scroll
基本思路
外层div固定宽高，监听滚动事件。内层div计算出总宽高，使外层div可滚动，其children为实际渲染的元素，通过相对内层div的定位展示到外层div范围内。
其实可以发现，每个元素对应内层div的相对位置都是固定的，滚动时动态变化的只有滚动距离，根据滚动距离计算出要展示的元素，渲染到页面上。
所以我们要计算的数据有：
- 每个元素的宽高，横竖向的偏移量(用于定位)
- 内层div总宽高
- 横竖向的滚动距离
而内层div总宽高其实就是每个元素的宽高和，但是如果数据量很大的情况下，很难高效的一次性计算出来，所以react-window实现了很巧妙的动态计算，未计算的元素宽高由初始传入的预估值代替。
我们以竖向为例，看一下具体实现。
数据
// 竖向滚动距离
const [scrollTop, setScrollTop] = useState(0)
// 行元数据Map key：行索引 value: { offset: 偏移量, size: 高度 }
const [rowMetadataMap] = useState({})
// 最后计算过的行索引
const lastMeasuredRowIndex = useRef(-1)之所以metadata内部的key叫offset和size而不是top和height，是为了横向和竖向逻辑能很好的复用，统一字段名。
计算元素高度
既然元素宽高是动态计算的，那什么时候计算元素高度呢，自然是用到的时候去计算。每次渲染我们要计算当前展示的元素范围：
const [rowStartIndex, rowStopIndex] = getVerticalRangeToRender()
const items = []
for (let rowIndex = rowStartIndex; rowIndex <= rowStopIndex; rowIndex++) {
items.push(
createElement(children, {
rowIndex,
key: itemKey({ rowIndex }),
style: getItemStyle(rowIndex),
})
)
}计算出需要渲染的行起止索引，渲染这个范围内的元素，items即内层div的children。这里createElement里的children是外层传入的，用户根据rowIndex和columnIndex自定义。我们看下怎么计算起止索引：
function getVerticalRangeToRender () {
const startIndex = getStartIndexForOffset(scrollTop)
const stopIndex = getRowStopIndexForStartIndex(startIndex)
return [
Math.max(0, startIndex - overscanBackward),
Math.max(0, Math.min(rowCount - 1, stopIndex + overscanForward)),
]
}getVerticalRangeToRender返回起止索引，先根据滚动距离计算起始索引，再根据起始索引计算终止索引。最后有防止越界的小技巧。overscanBackward和overscanForward是在外层div范围外额外渲染的元素数量，防止滚动出现空白。
function getStartIndexForOffset (offset) {
const lastMeasuredItemOffset =
lastMeasuredRowIndex.current > 0 ? rowMetadataMap[lastMeasuredRowIndex.current].offset : 0;
if (lastMeasuredItemOffset > offset) {
return findNearestItemBinarySearch(0, lastMeasuredRowIndex.current, offset)
} else {
return findNearestItemExponentialSearch(Math.max(0, lastMeasuredRowIndex.current), offset)
}
}通过最后一个计算过的元素的偏移量来判断，如果要找的元素在已经计算的元素里，采用二分法找到它，如果不在，则通过指数级增长的搜索找。我们先看不在的情况：
function findNearestItemExponentialSearch (index, target) {
let interval = 1
while (
index < rowCount &&
getMetedata(index).offset < target
) {
index += interval
interval *= 2
}
return findNearestItemBinarySearch(~~(index/2), Math.min(index, rowCount - 1), target)
}可以看到每次while循环索引一直增长，直到索引所在行偏移量超过了滚动的距离，而每次增长的数量是指数级增长的，1，2，4，8，16...最后通过二分法精确找到目标元素。但是二分法要求搜索范围内所有元素都是计算过的，那我们再看下getMetedata的实现：
function getMetedata (index) {
if (index > lastMeasuredRowIndex.current) {
let offset = 0
if (lastMeasuredRowIndex.current >= 0) {
const item = rowMetadataMap[lastMeasuredRowIndex.current]
offset += item.offset + item.size
}
for (let i = lastMeasuredRowIndex.current + 1; i <= index; i++) {
let size = getHeight(i)
rowMetadataMap[i] = {
offset: offset,
size
}
offset += size
}
lastMeasuredRowIndex.current = index
}
return rowMetadataMap[index]
}如果当前索引没有计算过，则会计算当前及之前的所有元素的尺寸。每个元素的偏移量等于上个元素偏移量加高度，高度由getHeight(外层组件提供)计算得出，
所以，在函数findNearestItemExponentialSearch中，最后调用二分法时，搜索范围内的元素都是已经计算过的。两条线最后都指向二分法，我们再看它的具体实现：
function findNearestItemBinarySearch (low, high, target) {
while (low <= high) {
let mid = low + ~~((high - low) >> 1)
let offset = getMetedata(mid).offset
if (offset === target) {
return mid
} else if (offset > target) {
high = mid - 1
} else {
low = mid + 1
}
}
return low > 0 ? low - 1 : 0
}经典二分查找，有个问题可能读者会疑惑，offset === target不可能这么精确吧，其实可以自己试一下，没有精确等于的情况下，最终还是会收敛到某一个元素上的。
ok, 现在我们找到起始索引，接下来要找终止索引了：
function getRowStopIndexForStartIndex (startIndex) {
let maxHeight = scrollTop + props.height
let stopIndex = startIndex
let data = getMetedata(stopIndex)
let height = data.offset + data.size
while (stopIndex < rowCount - 1 && height < maxHeight) {
stopIndex++
height += getMetedata(stopIndex).size
}
return stopIndex
}很简单，从起始索引一个一个向后找。
起止索引找到了，我们再看下元素样式怎么设置：
function getItemStyle (rowIndex) {
let style
if (itemStyleCache[rowIndex]) {
style = itemStyleCache[rowIndex]
} else {
let rowData = getMetedata(rowIndex)
itemStyleCache[rowIndex] = style = {
position: 'absolute',
top: rowData.offset,
height: rowData.size,
}
}
return style
}到这我们内层div渲染的children就准备好了，下一步再计算内层div的总高度。
计算总高度
function getEstimatedTotalHeight () {
let totalHeightOfMeasured = 0
if (lastMeasuredRowIndex.current >=0) {
const item = rowMetadataMap[lastMeasuredRowIndex.current]
totalHeightOfMeasured = item.offset + item.size
}
const numUnmeasuredItems = rowCount - lastMeasuredRowIndex.current - 1
const totalHeightOfUnmeasuredItems = numUnmeasuredItems * estimatedRowHeight
return totalHeightOfMeasured + totalHeightOfUnmeasuredItems
}分为两部分，已计算元素的高度和和未计算元素的预估高度和。已计算元素的高度和直接用最后计算过的行元数据的偏移量加上高度即可，未计算元素的预估高度和就是剩下未计算行数与预估行高(组件传参或默认值)的乘积，计算量并不大。
每次渲染时都会计算，所以只要元素宽高被计算过，总款高在计算时就会应用实际的宽高。
计算纵向滚动距离
function onScroll (event) {
const {
clientHeight,
scrollTop: targetScrollTop,
scrollHeight,
} = event.currentTarget;
if (targetScrollTop === scrollTop) return
setIsScrolling(true)
setScrollTop(Math.max(
0,
Math.min(targetScrollTop, scrollHeight - clientHeight)
))
}也很简单。触发重新渲染即可。
这样我们竖向的虚拟滚动的主要部分就实现好了。上面都是说的竖向的，代码我改成了只考虑竖向的情况，横向和竖向的逻辑复用可以参考这个函数：
function getStartIndexForOffset (type, offset) {
let lastMeasuredIndex, metadataMap
if (type === 'column') {
lastMeasuredIndex = lastMeasuredColumnIndex.current
metadataMap = columnMetadataMap
} else {
lastMeasuredIndex = lastMeasuredRowIndex.current
metadataMap = rowMetadataMap
}
const lastMeasuredItemOffset =
lastMeasuredIndex > 0 ? metadataMap[lastMeasuredIndex].offset : 0;
if (lastMeasuredItemOffset > offset) {
return findNearestItemBinarySearch(type, 0, lastMeasuredIndex, offset)
} else {
return findNearestItemExponentialSearch(type, Math.max(0, lastMeasuredIndex), offset)
}
}这是获取起始索引兼容横向竖向的代码，只需要根据传入的type在函数开头定好数据源即可，后面的核心功能代码是通用的，很方便的从竖向虚拟滚动扩展到横向虚拟滚动。
至于笔试题里扩展功能表头resize（拖拽等功能）, 我只做了拖拽，这里就不说了，有兴趣可以看代码库。注意触发重新渲染以及每个元素的key需要不一致即可。
最终实现下来感觉，虚拟滚动没有想象中的很难，实现效果渲染大量数据也很流畅。不过还没有测试实际渲染元素很多会怎么样。
v1.4.14