浅谈虚拟列表实现与原理分析

原理分析
========

虚拟长列表模型
--------------

长列表分为几个区域：

1. VirtualList：完整的列表区域
2. VisibleRange：视窗区域
3. RenderRange（PreScanRange + VisibleRange + PostScanRange）：实际渲染区域
4. LoadedRange：已加载区域
5. UnloadRange：未加载区域

如下图：
![](/media/202201/2022-01-07_1732470.007445689081525764.png)
计算公式如下：

* _RenderRange = PreScanRange + VisibleRange + PostScanRange = stop - start_
* _LoadedRange = lastMeasureIndex - 0_
* _UnloadRange = size(VirtualList) - lastMeasureIndex_

实际滚动过程中需要不断更新 start、stop、lastMeasureIndex，从而得出渲染区域和视窗区域。

位置缓存
--------

缓存的意义，一般在于提高性能。因此对 LoadedRange 中的元素已经得到计算的尺寸、偏移缓存在哈希表中，用以减少重复计算，提高性能。
![](/media/202201/2022-01-07_1732480.6815593303304616.png)

查找指定元素
------------

基于有序元素偏移列表：

* 在 LoadedRange 中使用二分查找算法，时间复杂度可降低到 O(lgN)；
* 在 UnloadRange 中使用指数查找算法，时间复杂度同样为 O(lgN)，但是可以将 N 值缩小，进一步提高搜索性能。

指数搜索如下：
![](/media/202201/2022-01-07_1732480.21469811256146065.png)

核心思想：先用指数搜索定位范围 low - high，内嵌二分查找 target。算法实现如下：
![](/media/202201/2022-01-07_1732480.115189241156756.png)

滚动偏移计算
------------

VirtualList 总长度计算公式如下：
_TotalSize = lastMeasuredSizeAndPosition.offset + lastMeasuredSizeAndPosition.size + (itemCount - lastMeasuredIndex - 1) * estimatedItemSize_
_
基本思路是使用已计算的偏移尺寸，加上未加载的预估尺寸，即为基本等价于整体尺寸。实现一个 SizeAndPositionManager 用以管理以及计算滚动偏移。代码概略如下：_
![](/media/202201/2022-01-07_1732480.5206637976297098.png)
通过 SizeAndPositionManager 的设计，将虚拟列表的偏移计算等相关逻辑抽离在此处，从而解耦和视图界面之间的关联。

不定尺寸的子元素
----------------

子元素的尺寸不定的情况下：

* 静态计算 ：提前预知所有元素的尺寸，并通过数组类型的 prop 传入，每个列表项的高度通过索引来获得。配置方式：prop:itemSize=[]number
* 动态延迟计算：传入获取列表项高度的方法，给这个方法传入 item 和 index ，返回对应列表项的高度。配置方式：prop:itemSize=[](undefined): number

将上述方式得出的尺寸作为计算依据，若无法获取对应尺寸，则使用预估尺寸（可配置）。
在 C 端项目中必然存在图片加载撑起高度等情况，子项高度大概率不确定。
如何动态估算子项高度？**可以使用 estimatedItemSize 类似配置，这样就能依赖预估高度计算列表内容的总高度，并且总高度随着列表项的渲染而渐进调整。这个在列表项是动态高度的场景下很有用，可以初始化内容的总长度以撑开容器元素，使其可在水平 / 垂直方向滚动。**
**
当然如果上述都满足不了需求。也有 react-virtualized 中的 CellMeasurer 作为一种提供尺寸度量的 HOC 组件提供。本质上桥接了组件调用方与虚拟列表组件内部通讯，组件调用方可以在元素尺寸稳定时显示通知组件更新计算。
调用方式如下：

```
function rowRenderer ({ index, isScrolling, key, parent, style }) {
  const source // This comes from your list data

return (
    <CellMeasurer
      cache={cache}
      columnIndex={0}
      key={key}
      parent={parent}
      rowIndex={index}
    >
      {({ measure, registerChild }) => (
        <div ref={registerChild} style={style}>
          <img
            // 图片加载成功时调用 measure 回调通知组件内部更新尺寸度量
            onLoad={measure}
            src={source}
          />
        </div>
      )}
    </CellMeasurer>
  );
}

function renderList (props) {
  return (
    <List
      {...props}
      deferredMeasurementCache={cache}
      rowHeight={cache.rowHeight}
      rowRenderer={rowRenderer}
    />
  );
}
复制代码
```

上述代码中的 measure 就是通信的一种方式。在图片加载成功后，会通知长列表组件更新计算。从而达到动态尺寸的诉求。

自定义 Header/Footer
--------------------

使用单独一个 slotManager 对 Header、Footer 进行插槽计算。即为将所有的 Header 和 Footer 当做虚拟列表的子项以外的插槽进行额外处理。
实现一个 SlotManager ，用以进行所有的插槽计算，如下：
![](/media/202201/2022-01-07_1732480.3112293601629945.png)
插槽队列示例图如下：
![](/media/202201/2022-01-07_1732480.5146615272512067.png)
附加上插槽的虚拟列表如图：
![](/media/202201/2022-01-07_1732480.358089073416735.png)
根据分析 VirtualList 的子节点获取得到插槽队列，然后通知 sizeAndPositionManager：

* 更新计算所有虚拟子节点的 offset
* 根据插槽的 start & end 划分 section

插槽的偏移计算公式如下：

* _SlotHeader(n).offset = SlotHeader(n).firstItem.offset - SlotHeader(n).size_
* _SlotFooter(n).offset = SlotHeader(n).lastItem.offset + SlotHeader(n).lastItem.size_

单列多 Section
--------------

遍历 VirutalList 内部的所有子元素，处理有 Section 和 无 Section 两种情况。最终处理为统一格式的 section 数组提供给后续渲染。
这种诉求场景是当我们渲染长列表时，我们可能会存在需要定制化个别元素作为某一段落的头部和尾部。
基本算法逻辑如下：
![](/media/202201/2022-01-07_1732480.13877213477710781.png)
上述的算法逻辑本质上就是在遍历所有子元素（this.props.children），根据类型（Section、Header、Footer）进行判断处理，统一处理为 Section 格式，从而交给上文所说的 SlotManager 继续插槽计算。最后才可以进行插槽以及虚拟列表子项的正确渲染。
使用方法如下：
![](/media/202201/2022-01-07_1732480.48229004103432416.png)
渲染效果如下：
![](/media/202201/2022-01-07_1732480.4050348167276727.png)

抛掷动画（自由滚动）
--------------------

实现基本逻辑：

* 若有浏览器原生支持的 ScrollToOptions，则默认使用
* 降级使用 easeInOutQuad 函数实现平滑动画曲线

实现代码如下：
![](/media/202201/2022-01-07_1732480.6766873217842132.png)
比较有趣的是，其中有一个 _flushTotalSize 是为了解决滚动偏移超出实际总尺寸的情况（还记得么，因为 UnloadRange 区域的列表子项都是使用预估的尺寸，所以是有可能存在此情况的）
然后 _flushTotalSize 和 _scrollTo 方法如下：
![](/media/202201/2022-01-07_1732480.2985799420915318.png)
当然，如果浏览器不支持 ScrollToOption，我们也可以使用贝塞尔函数曲线定时滚动去模拟平滑效果，实现优雅降级。不过肉眼看上去，还是远不如上者平滑。scrollTo 代码如下：
![](/media/202201/2022-01-07_1732480.1062261888393422.png)

横向与纵向
----------

如何让虚拟列表同时支持横向和纵向滚动呢？其实我们知道，二者的逻辑是十分相似的。比如说横向滚动，改变的是 scrollLeft，纵向滚动改变的是 scrollTop，还有分别对应的 width、height 等等。因此，我们只需要声明如下变量：
![](/media/202201/2022-01-07_1732480.6368667680888279.png)
然后在组件中取得滚动方向配置，用该配置在运行时动态读取对应的参数即可。

小结
====

完整虚拟列表实现以及 API 文档，请戳：[github.com/sulirc/reac…](https://github.com/sulirc/react-x-virtual "https://github.com/sulirc/react-x-virtual")
以上。感谢阅读~😎