因为 DOM 性能瓶颈，大型列表存在难以克服的性能问题。 因此，就有了 “局部渲染” 的优化方案，这就是虚拟列表的核心思想。
虚拟列表的实现，需要重点关注的问题一有以下几点：
- 可视区域的计算方法
- 可视区域的 DOM 更新方案
- 事件的处理方案
下面逐一分解说明。
可视区域计算
可视区域的计算，就是使用当前视口的高度、当前滚动条滚过的距离，得到一个可视区域的坐标区间。 算出可视区域的坐标区间之后，在去过滤出落在该区间内的列表项，这个过程，列表项的坐标也是必须能算出的。
思考以下情况，
- 我们的视口高度为 100px
- 我们当前已经滚动了 100px
- 我们的列表项，每一项高度为 20px
根据这些条件，我们可以计算出，当前可视区域为第 11 项至第 20 项。
01 - 05，可视区域上方
+----+-----------+--------
| 06 | 100 ~ 120 |
+----+-----------+
| 07 | 120 ~ 140 |
+----+-----------+
| 08 | 140 ~ 160 | 可视区域
+----+-----------+
| 09 | 160 ~ 180 |
+----+-----------+
| 10 | 180 ~ 200 |
+----+-----------+--------
11 - N，可视区域下方
这是因为列表项高度是固定的，我们可以通过简单的四则运算算出已经滚动过去的 100px 中，已经滚动走了 5 个列表项，因此可视区域是从第 6 项开始，而视口高度为 100px，能容纳 100 / 20 即 5 个条目。
上面例子的情况非常简单，也不存在性能问题，因此实际上并没有展开讨论的价值。 而还有另一种复杂很多的情况，那就是，列表项高度不固定，根据内容决定高度。
此时，我们就没办法直接使用四则运算一步到位算出可视区域对应的条目了。
而必须实现一种机制，记录所有列表项的坐标，再通过检查列表项是否落在视口内。
下面重点讨论该问题。
列表项的坐标
列表项的坐标，可以通过以下公式定义：
<列表项 top 坐标值> = <上一项 top 坐标值> + <上一项的高度值>
第一个列表项的 top 坐标值为 0，因此，只要记录所有列表项目的高度，即可算出任意一个列表项的 top 坐标值。 于是，问题就变成了，必须使用某种方式来存储每个条目的高度。
我想，最容易想到的方案就是，使用一个数组，一一对应地存储列表每项的高度值。 然后获取特定项的坐标值时，提取第一项到目标项的值，进行累加运算。参考下面代码进行理解：
// 假设使用该数组存储列表每一项的高度
const itemHeightStore = [20, 20, 20, 20, 20]
// 使用该方法，可以算出列表中指定项的 top 坐标值
const getTop = (index) => {
let sum = 0
while (index--) sum += itemHeightStore[index] || 0
return sum
}
// 第一项
getTop(0) // 0
// 第二项
getTop(1) // 20
// ...
该实现可以很好地工作。
但是，该算法存在严重的性能问题，每获取一个列表项的坐标都要遍历列表，复杂度 O(n)，非常不划算。
如果换一种方式，直接存储每一项的坐标呢？
其实本质是一样的。因为我们的列表项高度是不固定的，我们快速拖动滚动条到不同的区域时，需要根据局部渲染结果算出高度用于更新数组记录，而在更新某一项时，该项后续的所有条目也需要全部更新，复杂度一样是 O(n)。
所以，使用数组来维护每一项的高度或者坐标，在列表规模比较大的时候，就会消耗大量的 CPU 时间。
也许使用 TypedArray 会有好的表现？
仔细观察上面例子中的数组，结合现实中列表的情况，我们可以观察到一个现象：
列表项往往是相似的，在许多情况下，高度也很可能是一致的。
基于这种经验，我们可以采用区间来存储列表项的高度。
通过折叠记录相邻的，相同高度的列表项，来减少列表遍历操作。
比如以下表示方式：
const range = {
start: 0,
end: 4,
value: 20
}
可以很好地表达列表第 1 项至第 5 项的高度都为 20px。
如果我们需要求第 6 项的高度的话，就只需进行一次简单的四则运算即可，无需遍历累加这 5 项。
很容易得出结论，如果列表大部分情况是相同高度，只有个别条目高度不一致时（例如文本换行），将会有非常优异的性能表现。
当然使用区间，也不是没有代价的。这又会带来数据结构的复杂性。
由于折叠了相邻相同高度的结点，会导致存储的列表无法跟原始条目一一对应。所以，我们就不能简单得知我们想查询的列表项的高度存储在哪里了， 为此需要设计一种专门的存储机制。
这种存储机制，需要拥有这些特性：
- 高效的查询。可以通过列表项序号，快速获得对应的 range，以及该 range 之前的所有 range。
- 高效地修改。可以高效地插入、移除 range，合并 range、拆分 range。
结合我们学过的数据结构知识，可以考虑使用某种 BST 来存储，从而获得良好的查询、插入性能。 而 range 的合并、拆分等，则可以实现一个专门的类来管理。
下面直接给出一个简单的代码实现供参考，代码中已经加上了大量的注释，直接阅读应该比解说要更清晰。
// Avl.ts
const SLIGHTLY_UNBALANCED_RIGHT = -1
const SLIGHTLY_UNBALANCED_LEFT = 1
const UNBALANCED_RIGHT = -2
const UNBALANCED_LEFT = 2
// 树结点
class AvlNode<K extends any = any> {
key: any
left: AvlNode<K> | null
right: AvlNode<K> | null
parent: AvlNode<K> | null
_height: number
_prevHeight: number
constructor(key: K) {
this.key = key
this.left = null
this.right = null
this.parent = null
this._height = 0
this._prevHeight = 0
}
// 刷新前的高度，方便平衡操作
get prevHeight() {
return this._prevHeight | 0
}
get height() {
return this._height | 0
}
set height(value) {
this._prevHeight = this._height | 0
this._height = value | 0
}
// 左子树高度
get leftHeight() {
if (this.left === null) return -1
return this.left.height | 0
}
// 右子树高度
get rightHeight() {
if (this.right === null) return -1
return this.right.height | 0
}
// 平衡因子
get balanceFactor() {
return this.leftHeight - this.rightHeight
}
updateHeight() {
const { leftHeight, rightHeight } = this
const height = ((leftHeight > rightHeight "htmlcode">
import { create as createSparseRangeList } from './SparseRangeList'
// 创建一个默认预估高度为 20 的列表项存储对象
const itemHeightStore = createSparseRangeList(wrappedItems.length, 20)
// 设置第二项为 40px
itemHeightStore.setValue(1, 40)
// 获取第二项的高度
itemHeightStore.getValueAt(1) // 40
// 获取列表项的 top 坐标
const top = (index: number): number => {
if (index === 0) return 0
// 0 ～ 上一项的高度累加
const rangeValues = itemHeightStore.intersecting(0, index - 1)
const sumHeight = rangeValues.reduce((sum: number, rangeValue: any) => {
const span = rangeValue.end - rangeValue.start + 1
return sum + rangeValue.value * span
}, 0)
return sumHeight
}
top(1) // 20
// 计算列表总高度：
const listHeight = itemHeightStore
.values()
.reduce((acc: number, rangeValue: any) => {
const span = rangeValue.end - rangeValue.start + 1
const height = rangeValue.value * span
return acc + height
}, 0)
计算可视条目
完成了列表项高度的管理，接下来需要解决的重点，就是计算出哪些条目是可视的。
最简单的实现方式，就是直接遍历我们的结点高度存储列表，逐个去跟视口的坐标区间比较，过滤出落在（或部分落在）视口内部的条目。 基于性能考虑，我们当然不能这么简单粗暴。我们可以做以下尝试来提高性能：
一、预估起点条目 + 二分法修正。
通过条目的预估高度或默认高度，算出可能出现在视口的第一条条目。 比如，我们视口上沿坐标（即滚动条滚过的距离）为 100px，我们条目预估高度为 20px，那么，我们可以猜测第一个出现在视口中的条目为 100 / 20 + 1，即第 6 条。 我们直接计算第 6 条的坐标，检查是否落在视口中，根据结果差距，再进行二分法猜测，直到找到真正的起点条目。
二、预估终点条目 + 二分法修正
在算出起点条目后，在使用视口高度除以预估条目高度，算出视口内部可能显示多少项，将起点序号加上这个数量，就是预估的终点条目序号。使用上述一样的修正逻辑，直到找到正确的视口终点条目。
描述可能比较难以理解，下面给出关键片段：
// 内部方法，计算局部渲染数据切片的起止点
private _calcSliceRange() {
if (!this.dataView.length) {
return { sliceFrom: 0, sliceTo: 0 }
}
// 数据总量
const MAX = this.dataView.length
// 视口上边界
const viewportTop = (this.$refs.viewport as any).scrollTop || 0
// 视口下边界
const viewportBottom = viewportTop + this.viewportHeight
// 预估条目高度
const estimatedItemHeight = this.defaultItemHeight
// 从估算值开始计算起始序号
let sliceFrom = Math.floor(viewportTop / estimatedItemHeight!)
if (sliceFrom > MAX - 1) sliceFrom = MAX - 1
while (sliceFrom >= 0 && sliceFrom <= MAX - 1) {
const itemTop = this._top(sliceFrom)
// 条目顶部相对于 viewport 顶部的偏移
const itemOffset = itemTop - viewportTop
// 1. 该条目距离视口顶部有距离，说明上方还有条目元素需要显示，继续测试上一条
if (itemOffset > 0) {
// 二分法快速估算下一个尝试位置
const diff = itemOffset / estimatedItemHeight!
sliceFrom -= Math.ceil(diff / 2)
continue
}
// 2. 恰好显示该条目的顶部，则该条目为本次视口的首条元素
if (itemOffset === 0) break
// 以下都是 itemOffset < 0
const itemHeight = this._itemHeight(sliceFrom)
// 3. 该条目在顶部露出了一部分，则该条目为本次视口的首条元素
if (itemOffset < itemHeight) break
// 4. 该条目已被滚出去视口，继续测试下一条
// 二分法快速估算下一个尝试位置
const diff = -itemOffset / estimatedItemHeight!
sliceFrom += Math.ceil(diff / 2)
}
// 从估算值开始计算结束序号
let sliceTo = sliceFrom + 1 + Math.floor(this.viewportHeight / estimatedItemHeight!)
if (sliceTo > MAX) sliceTo = MAX
while (sliceTo > sliceFrom && sliceTo <= MAX) {
const itemTop = this._top(sliceTo)
const itemHeight = this._itemHeight(sliceTo)
const itemBottom = itemTop + itemHeight
// 条目底部相对于 viewport 底部的偏移
const itemOffset = itemBottom - viewportBottom
// 1. 该条目的底部距离视口底部有距离，说明下方还有条目元素需要显示，继续测试下一条
if (itemOffset < 0) {
// 二分法快速估算下一个尝试位置
const diff = -itemOffset / estimatedItemHeight!
sliceTo += Math.ceil(diff / 2)
continue
}
// 2. 恰好显示该条目的底部，则该条目为视口中最后一项
if (itemOffset === 0) break
// 3. 该条目在底部被裁剪了一部分，则该条目为本次视口的末项
if (itemOffset < itemHeight) break
// 该条目还未出场，继续测试上一条
// 二分法快速估算下一个尝试位置
const diff = itemOffset / estimatedItemHeight!
sliceTo -= Math.ceil(diff / 2)
}
// slice 的时候，不含 end，所以 + 1
sliceTo += 1
return { sliceFrom, sliceTo }
}
以上就是计算可视区域的核心部分。完整的代码，会在后续给出。
DOM 更新
由于我们是使用 Vue 来实现虚拟列表的，所以 DOM 的更新方面，可以省去大量繁琐的细节管理。 我们只需要关心列表滚动到某处之后，如何计算出当前视口应该出现哪些条目即可。
尽管如此，考虑到滚动的流畅性，以及 IE11 等浏览器的 DOM 操作性能，我们不得不多做很多事情。
批量 DOM 操作
我们可以在 IE11 的开发者工具面板中看到，滚动过程，频繁地往虚拟列表首尾插入、移除结点，会带来非常严重的性能问题。 所以，我们必须控制 DOM 操作的频率。
批量可以部分解决这个问题。
具体的思路是，在滚动回调中，我们计算出可视区域的结点起止序号，不直接应用，而是加上一个额外渲染的数量。 比如我们计算出当前应该渲染 20 ~ 30 这些条目，我们可以在前后各加上 10 个额外渲染的条目，即 10 ~ 40，这样就一次性渲染了 30 个结点。在继续滚动时，我们检查新的起止范围，是否还在 10 ～ 40 范围内，如果是，我们就不做新的结点增删操作。
核心实现：
// 刷新局部渲染数据切片范围
private _updateSliceRange(forceUpdate"color: #ff0000">事件
由于虚拟列表的 DOM 需要不停地生成和销毁，因此，直接在列表项目上绑定事件是非常低效的。 所以，使用事件代理就成了很不错的方案，将事件注册在组件根结点上，再根据 event.target 来区分是由哪个列表项冒泡出来的事件，即可高效处理。
组件实现
import { Component, Vue, Prop, Watch } from 'vue-property-decorator'
import { createSparseRangeList } from './SparseRangeList'
// 列表项数据包裹，data 字段存放原始数据
// 组件所有操作不应该改变 data 的内容，而是修改该包裹对象的属性
class ItemWrapper {
// 原始数据
data: any
// 数据唯一 key
key: any
// 条目高度
// 1. 正数代表已经计算出来的高度
// 2. 0 代表未计算的高度，不显示
// 3. 负数代表需要隐藏的高度，绝对值为已经计算出来的高度，方便取消隐藏
height: number
// 记录是否已经根据实际 DOM 计算过高度
realHeight: boolean
// 条目在当前过滤视图中的序号
viewIndex: number
constructor(data: any, key: any, height: number) {
this.data = data
// 数据的唯一id，是初始化数据时候的序号
// 每次传入的 data 改变，都会重新生成
this.key = key
// 条目的高度缓存
// 1. 用于重建高度存储时快速恢复
// 2. 用于快速通过数据取高度
this.height = height 0
this.realHeight = false
// 每次生成 dataView 都刷新
this.viewIndex = -1
}
}
@Component({ name: 'VList' })
export default class VList extends Vue {
[key: string]: any
// 高度存储 不响应式
private itemHeightStore: any
// 组件宽度，不设置则为容器的 100%
@Prop({ type: Number })
private width"color: #ff0000">总结
以上所说是小白给大家介绍的使用 Vue 实现一个虚拟列表的方法，希望对大家有所帮助，如果大家有任何疑问欢迎给我留言，小编会及时回复大家的！
标签：
vue,虚拟列表