使用 Vue 实现一个虚拟列表的方法

2023-08-16 23:25:04 80

因为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坐标值。于是，问题就变成了，必须使用某种方式来存储每个条目的高度。

我想，最容易想到的方案就是，使用一个数组，一一对应地存储列表每项的高度值。然后获取特定项的坐标值时，提取第一项到目标项的值，进行累加运算。参考下面代码进行理解：

//假设使用该数组存储列表每一项的高度
constitemHeightStore=[20,20,20,20,20]

//使用该方法，可以算出列表中指定项的top坐标值
constgetTop=(index)=>{
letsum=0
while(index--)sum+=itemHeightStore[index]||0
returnsum
}
//第一项
getTop(0)//0

//第二项
getTop(1)//20
//...

该实现可以很好地工作。

但是，该算法存在严重的性能问题，每获取一个列表项的坐标都要遍历列表，复杂度O(n)，非常不划算。

如果换一种方式，直接存储每一项的坐标呢？

其实本质是一样的。因为我们的列表项高度是不固定的，我们快速拖动滚动条到不同的区域时，需要根据局部渲染结果算出高度用于更新数组记录，而在更新某一项时，该项后续的所有条目也需要全部更新，复杂度一样是O(n)。

所以，使用数组来维护每一项的高度或者坐标，在列表规模比较大的时候，就会消耗大量的CPU时间。

也许使用TypedArray会有好的表现？

仔细观察上面例子中的数组，结合现实中列表的情况，我们可以观察到一个现象：

列表项往往是相似的，在许多情况下，高度也很可能是一致的。
基于这种经验，我们可以采用区间来存储列表项的高度。

通过折叠记录相邻的，相同高度的列表项，来减少列表遍历操作。
比如以下表示方式：

constrange={
start:0,
end:4,
value:20
}

可以很好地表达列表第1项至第5项的高度都为20px。

如果我们需要求第6项的高度的话，就只需进行一次简单的四则运算即可，无需遍历累加这5项。

很容易得出结论，如果列表大部分情况是相同高度，只有个别条目高度不一致时（例如文本换行），将会有非常优异的性能表现。

当然使用区间，也不是没有代价的。这又会带来数据结构的复杂性。

由于折叠了相邻相同高度的结点，会导致存储的列表无法跟原始条目一一对应。所以，我们就不能简单得知我们想查询的列表项的高度存储在哪里了，为此需要设计一种专门的存储机制。

这种存储机制，需要拥有这些特性：

高效的查询。可以通过列表项序号，快速获得对应的range，以及该range之前的所有range。
高效地修改。可以高效地插入、移除range，合并range、拆分range。

结合我们学过的数据结构知识，可以考虑使用某种BST来存储，从而获得良好的查询、插入性能。而range的合并、拆分等，则可以实现一个专门的类来管理。

下面直接给出一个简单的代码实现供参考，代码中已经加上了大量的注释，直接阅读应该比解说要更清晰。

//Avl.ts
constSLIGHTLY_UNBALANCED_RIGHT=-1
constSLIGHTLY_UNBALANCED_LEFT=1
constUNBALANCED_RIGHT=-2
constUNBALANCED_LEFT=2
//树结点
classAvlNode{
key:any
left:AvlNode|null
right:AvlNode|null
parent:AvlNode|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
}
//刷新前的高度，方便平衡操作
getprevHeight(){
returnthis._prevHeight|0
}
getheight(){
returnthis._height|0
}
setheight(value){
this._prevHeight=this._height|0
this._height=value|0
}
//左子树高度
getleftHeight(){
if(this.left===null)return-1
returnthis.left.height|0
}
//右子树高度
getrightHeight(){
if(this.right===null)return-1
returnthis.right.height|0
}
//平衡因子
getbalanceFactor(){
returnthis.leftHeight-this.rightHeight
}
updateHeight(){
const{leftHeight,rightHeight}=this
constheight=((leftHeight>rightHeight?leftHeight:rightHeight)+1)|0
this.height=height
}
}
//AVL树
exportclassAvl{
_root:AvlNode|null
_size:number
constructor(){
this._root=null
this._size=0
}
getsize(){
returnthis._size
}
//插入节点
insert(key:K){
constnode=newAvlNode(key)
constinsertPoint=this._nodeInsert(node)
//本次插入是重复结点，直接更新key/value
//无新结点插入，所以无需进行插入后的调整
if(insertPoint==null)return
//新增结点成功时，回溯调整搜索路径上的结点
this._adjustAfterInsertion(insertPoint)
}
//删除节点，返回是否成功删除结点
delete(key:K):boolean{
//搜索待删除结点
consttargetNode=this._nodeSearch(key)
//未找到value对应结点
if(targetNode==null)returnfalse
//执行删除结点操作
constbacktracking=this._nodeErase(targetNode)
constparent=backtracking[0]
//回溯调整搜索路径上的结点
if(parent!==null){
this._adjustAfterRemoval(parent)
}
returntrue
}
//通过key查找包含该key范围的节点key
search(key:K){
constnode=this._nodeSearch(key)
if(node!==null)returnnode.key
returnnull
}
//搜索start、end两个key之间的所有key列表
searchRange(start:K,end:K){
constresults:K[]=[]
//找到符合条件的root节点
letroot=this._root
while(root!==null){
constresult1=start.compareTo(root.key)
constresult2=end.compareTo(root.key)
//当前节点比start小，不再搜索左子树
if(result1>0){
root=root.right
continue
}
//当前节点大于end，不再搜索右子树
if(result2<0){
root=root.left
continue
}
break
}
if(!root)returnresults
conststack=[]
letcurrent:AvlNode|null=root
while(stack.length||current){
while(current){
stack.push(current)
//当前节点比start小，不再搜索current的左子树
if(start.compareTo(current.key)>0)break
current=current.left
}
if(stack.length){
//指向栈顶
current=stack[stack.length-1]
constgteStart=start.compareTo(current.key)<=0
constlteEnd=end.compareTo(current.key)>=0
if(gteStart&<eEnd){
results.push(current.key)
}
stack.pop()
//只有current比end小，才继续搜索current的右子树
if(lteEnd){
current=current.right
}
else{
current=null
}
}
}
returnresults
}
//增加结点数量
_increaseSize(){
this._size+=1
}
//减少结点数量
_decreaseSize(){
this._size-=1
}
//设置左子结点，同时维护parent关系
_setLeft(node:AvlNode,child:AvlNode|null){
//断开旧left结点
if(node.left!==null){
node.left.parent=null
}
//连接新结点
if(child!==null){
//从旧parent中断开
if(child.parent!==null){
child.parent.left===child?(child.parent.left=null):(child.parent.right=null)
}
child.parent=node
}
node.left=child
}
//设置右子结点，同时维护parent关系
_setRight(node:AvlNode,child:AvlNode|null){
//断开旧right结点
if(node.right!==null){
node.right.parent=null
}
//连接新结点
if(child!==null){
//从旧parent中断开
if(child.parent!==null){
child.parent.left===child?(child.parent.left=null):(child.parent.right=null)
}
child.parent=node
}
node.right=child
}
//获取中序遍历顺序的前驱结点
_inorderPredecessor(node:AvlNode|null){
if(node==null)returnnull
//1.有左子树，找到左子树最大元素
if(node.left!==null){
returnthis._maximumNode(node.left)
}
//2.没有左子树，往上搜索
letparent=node.parent
while(parent!=null){
if(node==parent.right){
returnparent
}
node=parent
parent=node.parent
}
//4.搜索到根
returnnull
}
//获取最大的结点
_maximumNode(subRoot:AvlNode){
letcurrent=subRoot
while(current.right!==null)current=current.right
returncurrent
}
//设置根结点
_setRoot(node:AvlNode|null){
if(node===null){
this._root=null
return
}
this._root=node
//如果本身在树中，则从树中脱落，成为独立的树根
if(node.parent!==null){
node.parent.left===node?(node.parent.left=null):(node.parent.right=null)
node.parent=null
}
}
//将树上某个结点替换成另一个结点
private_replaceNode(node:AvlNode,replacer:AvlNode|null){
if(node===replacer)returnnode
//node为root的情况
if(node===this._root){
this._setRoot(replacer)
}
else{
//非root，有父结点的情况
constparent=node.parentasAvlNode
if(parent.left===node)this._setLeft(parent,replacer)
elsethis._setRight(parent,replacer)
}
returnnode
}
//左旋，返回新顶点，注意旋转完毕会从原本的树上脱落
private_rotateLeft(node:AvlNode){
constparent=node.parent
//记录原本在树上的位置
constisLeft=parent!==null&&parent.left==node
//旋转
constpivot=node.rightasAvlNode
constpivotLeft=pivot.left
this._setRight(node,pivotLeft)
this._setLeft(pivot,node)
//旋转完毕
//新顶点接上树上原本的位置
if(parent!==null){
if(isLeft)this._setLeft(parent,pivot)
elsethis._setRight(parent,pivot)
}
//---
if(node===this._root){
this._setRoot(pivot)
}
node.updateHeight()
pivot.updateHeight()
returnpivot
}
//右旋，返回新顶点，注意旋转完毕会从原本的树上脱落
private_rotateRight(node:AvlNode){
constparent=node.parent
//记录原本在树上的位置
constisLeft=parent!==null&&parent.left===node
//旋转
constpivot=node.leftasAvlNode
constpivotRight=pivot.right
this._setLeft(node,pivotRight)
this._setRight(pivot,node)
//旋转完毕
//新顶点接上树上原本的位置
if(parent!==null){
if(isLeft)this._setLeft(parent,pivot)
elsethis._setRight(parent,pivot)
}
//---
if(node===this._root){
this._setRoot(pivot)
}
node.updateHeight()
pivot.updateHeight()
returnpivot
}
//搜索Node
private_nodeSearch(key:K){
letcurrent=this._root
while(current!==null){
letresult=key.compareTo(current.key)
if(result===0)returncurrent
if(result<0)current=current.left
elsecurrent=current.right
}
returnnull
}
//在树里插入结点或者刷新重复结点
//返回新插入（或刷新）的结点
private_nodeInsert(node:AvlNode){
//空树
if(this._root===null){
this._setRoot(node)
this._increaseSize()
returnnull
}
constkey=node.key
letcurrent=this._root
//查找待插入的位置
while(true){
constresult=key.compareTo(current.key)
if(result>0){
if(current.right===null){
this._setRight(current,node)
this._increaseSize()
returncurrent
}
current=current.right
}
elseif(result<0){
if(current.left===null){
this._setLeft(current,node)
this._increaseSize()
returncurrent
}
current=current.left
}
else{
//Noduplicates,justupdatekey
current.key=key
returnnull
}
}
}
//从树上移除一个结点
private_nodeErase(node:AvlNode){
//同时拥有左右子树
//先转换成只有一颗子树的情况再统一处理
if(node.left!==null&&node.right!==null){
constreplacer=this._inorderPredecessor(node)!
//使用前驱结点替换身份
//此时问题转换成删掉替代结点（前驱），
//从而简化成只有一个子结点的删除情况
node.key=replacer.key
//修改node指针
node=replacer
}
//删除点的父结点
constparent=node.parent
//待删结点少于两颗子树时，使用子树(或null，没子树时)顶替移除的结点即可
constchild=node.left||node.right
this._replaceNode(node,child)
this._decreaseSize()
return[parent,child,node]
}
//AVL树插入结点后调整动作
//自底向上调整结点的高度
//遇到离current最近的不平衡点需要做旋转调整
//注意:对最近的不平衡点调整后或者结点的高度值没有变化时
//上层结点便不需要更新
//调整次数不大于1
_adjustAfterInsertion(backtracking:AvlNode|null){
letcurrent=backtracking
//往上回溯，查找最近的不平衡结点
while(current!==null){
//更新高度
current.updateHeight()
//插入前后，回溯途径结点的高度没有变化，则无需继续回溯调整
if(current.height===current.prevHeight)break
//若找到不平衡结点，执行一次调整即可
if(this._isUnbalanced(current)){
this._rebalance(current)
//调整过，则上层无需再调整了
break
}
current=current.parent
}
}
//AVL树删除结点后调整动作
//自底向上调整结点的高度
//遇到离current最近的不平衡点需要做旋转调整
//注意:对最近的不平衡点调整后，其上层结点仍然可能需要调整
//调整次数可能不止一次
_adjustAfterRemoval(backtracking:AvlNode|null){
letcurrent=backtracking
while(current!==null){
//更新高度
current.updateHeight()
//删除前后，回溯途径结点的高度没有变化，则无需继续回溯调整
if(current.height===current.prevHeight)break
if(this._isUnbalanced(current)){
this._rebalance(current)
}
//与插入不同，调整过后，仍然需要继续往上回溯
//上层结点（若有）仍需判断是否需要调整
current=current.parent
}
}
//LL
_adjustLeftLeft(node:AvlNode){
returnthis._rotateRight(node)
}
//RR
_adjustRightRight(node:AvlNode){
returnthis._rotateLeft(node)
}
//LR
_adjustLeftRight(node:AvlNode){
this._rotateLeft(node.left!)
returnthis._rotateRight(node)
}
//RL
_adjustRightLeft(node:AvlNode){
this._rotateRight(node.right!)
returnthis._rotateLeft(node)
}
//检查结点是否平衡
_isUnbalanced(node:AvlNode){
constfactor=node.balanceFactor
returnfactor===UNBALANCED_RIGHT||factor===UNBALANCED_LEFT
}
//重新平衡
_rebalance(node:AvlNode){
constfactor=node.balanceFactor
//Rightsubtreelonger(node.factor:-2)
if(factor===UNBALANCED_RIGHT){
letright=node.right!
//RL,node.right.factor:1
if(right.balanceFactor===SLIGHTLY_UNBALANCED_LEFT){
returnthis._adjustRightLeft(node)
}
else{
//RR,node.right.factor:0|-1
//即right.rightHeight>=right.leftHeight
returnthis._adjustRightRight(node)
}
}
elseif(factor===UNBALANCED_LEFT){
//Leftsubtreelonger(node.factor:2)
letleft=node.left!
//LR,node.left.factor:-1
if(left.balanceFactor===SLIGHTLY_UNBALANCED_RIGHT){
returnthis._adjustLeftRight(node)
}
else{
//LL,node.left.factor:1|0
//即left.leftHeight>=left.rightHeight
returnthis._adjustLeftLeft(node)
}
}
returnnode
}
}
exportfunctioncreateAvl(){
returnnewAvl()
}
//SparseRangeList.ts
import{createAvl,Avl}from'./Avl'
//区间类
classRange{
start:number
end:number
constructor(start:number,end?:number){
this.start=start
this.end=end||start
}
//用于Avl中节点的比较
//
//列表中项目范围是连续的，必定不会重叠的
//如果传入的key为重叠的，则意味着希望通过构造一个子Range搜索所在的RangeValue
//例如构造一个{start:10,end:10,value:'any'}，搜索树中
//范围包含10~10的RangeValue，如{start:0,end:20,value:'any'}
compareTo(other:Range){
if(other.start>this.end!)return-1
if(other.end!extendsRange{
value:T
constructor(start:number,end:number,value:T){
super(start,end)
this.value=value
}
clone():RangeValue{
returnnewRangeValue(this.start,this.end!,this.value)
}
}
//最终存储区间-值的类，内部使用Avl存储所有RangeValue
exportdefaultclassSparseRangeList{
_size:number
defaultValue:T
valueTree:Avl
constructor(size:number,defaultValue:T){
this._size=size
this.defaultValue=defaultValue
this.valueTree=createAvl()
}
getsize(){
returnthis._size
}
resize(newSize:number){
newSize=newSize|0
//无调整
if(this._size===newSize)return
//扩容
if(this._size=this.size)end=this.size-1
//所有与当前传入区间范围有重叠部分，
//-1，+1将接壤的毗邻RangeValue也纳入（如果存在的话），
//毗邻的RangeValue要检查否要合并。
letprevSiblingEnd=start-1
letnextSiblingStart=end+1
letrangeValues=this.treeIntersecting(prevSiblingEnd,nextSiblingStart)
//如果没有重叠的部分，则作为新的RangeValue插入，直接结束
//如果有重叠的部分，就要处理合并、拆分
if(rangeValues.length){
letfirstRange=rangeValues[0]
letlastRange=rangeValues[rangeValues.length-1]
//end边界比传入的start小，说明是接壤毗邻的更小的RangeValue
//
//1.如果毗邻的RangeValue的值跟当前带插入的值不一致，
//则直接将毗邻的RangeValue从列表中移除，
//不需要做任何特殊操作，正常的插入操作即可
//
//2.否则如果毗邻的RangeValue的值跟当前待插入的值一致，
//则将两个RangeValue的Range合并（修改start即可），
//然后这个毗邻的RangeValue也自然变成重叠的，正常执行后续
//的重叠处理逻辑即可（拆分）
if(firstRange.endend){
if(lastRange.value!==value){
rangeValues.pop()
}
else{
end=lastRange.end
}
}
//结束毗邻RangeValue合并逻辑
//开始处理相交的RangeValue流程
constlength=rangeValues.length
letindex=0
while(index=start&¤tEnd<=end){
index+=1
continue
}
//Case2.部分相交，该RangeValue的大的一侧在传入的范围内，而小的一侧不在。
//需要做切分操作，以重叠的位置作为切分点，比较小的一侧（不重叠的部分）重新插入，
//比较大的的那一部分，会被传入的值覆盖掉
if(currentStartend){
if(currentValue!==value){
this._insert(end+1,currentEnd,currentValue)
}
else{
end=currentEnd
}
}
index+=1
}
}
this._insert(start,end,value)
}
setValue(index:number,value:T){
this.setRangeValue(index,index,value)
}
/**
*筛选出与指定区间有重叠的RangeValue，即：
*
*1.相互部分重叠
*
*o----------oo---------o
*>start------------------end<
*
*
*2.相互完全重叠关系
*
*o----------------o
*>start--------end<
*
*
*3.包含或被包含关系
*
*o--------------------------------------o
*o-------------------------------o
*o-------------------------------o
*o-----oo-----oo----o
*>start--------------------end<
*
*/
treeIntersecting(start:number,end:number):RangeValue[]{
conststartRange=newRange(start)
constendRange=newRange(end)
returnthis.valueTree.searchRange(startRange,endRange)
}
/**
*返回指定范围内所有RangeValue
*范围内有无值的Range的话，则使用
*携带默认值的RangeValue代替
*从而确保返回的结果是线性的、每个区间都有值的，如:
*
*start>...start------|-----|-----------|-----|--------end<
*
*/
intersecting(start:number,end:number):RangeValue[]{
constranges=this.treeIntersecting(start,end)
if(!ranges.length){
if(!this.size)return[]
return[newRangeValue(start,end,this.defaultValue)]
}
letresult=[]
letrange
letindex=0
letlength=ranges.length
while(indexstart){
result.push(newRangeValue(start,range.start-1,this.defaultValue))
}
result.push(range)
//将start的位置右移，
//以便下个range的比较
start=range.end+1
index+=1
}
//如果最后一个range，与传入的范围只有左侧重叠，
//而右侧没有重叠的地方，则手动塞入一个携带默认值
//的RangeValue
if(range.endend){
//否则如果最后一个range的范围已经超出需要的范围，则裁剪
range.end=end
}
returnresult
}
values(){
if(!this.size)return[]
returnthis.intersecting(0,this.size-1)
}
_insert(start:number,end:number,value:T){
if(value!==this.defaultValue){
constrangeValue=newRangeValue(start,end,value)
this.valueTree.insert(rangeValue)
}
}
}
exportfunctioncreate(size:number,value:T){
returnnewSparseRangeList(size,value)
}

有了这套存储机制之后，我们就可以更高效地管理列表项的高度，和统计列表高度了。

看代码理解：

import{createascreateSparseRangeList}from'./SparseRangeList'
//创建一个默认预估高度为20的列表项存储对象
constitemHeightStore=createSparseRangeList(wrappedItems.length,20)
//设置第二项为40px
itemHeightStore.setValue(1,40)
//获取第二项的高度
itemHeightStore.getValueAt(1)//40
//获取列表项的top坐标
consttop=(index:number):number=>{
if(index===0)return0
//0～上一项的高度累加
constrangeValues=itemHeightStore.intersecting(0,index-1)
constsumHeight=rangeValues.reduce((sum:number,rangeValue:any)=>{
constspan=rangeValue.end-rangeValue.start+1
returnsum+rangeValue.value*span
},0)
returnsumHeight
}
top(1)//20
//计算列表总高度：
constlistHeight=itemHeightStore
.values()
.reduce((acc:number,rangeValue:any)=>{
constspan=rangeValue.end-rangeValue.start+1
constheight=rangeValue.value*span
returnacc+height
},0)

计算可视条目

完成了列表项高度的管理，接下来需要解决的重点，就是计算出哪些条目是可视的。

最简单的实现方式，就是直接遍历我们的结点高度存储列表，逐个去跟视口的坐标区间比较，过滤出落在（或部分落在）视口内部的条目。基于性能考虑，我们当然不能这么简单粗暴。我们可以做以下尝试来提高性能：

一、预估起点条目+二分法修正。

通过条目的预估高度或默认高度，算出可能出现在视口的第一条条目。比如，我们视口上沿坐标（即滚动条滚过的距离）为100px，我们条目预估高度为20px，那么，我们可以猜测第一个出现在视口中的条目为100/20+1，即第6条。我们直接计算第6条的坐标，检查是否落在视口中，根据结果差距，再进行二分法猜测，直到找到真正的起点条目。

二、预估终点条目+二分法修正

在算出起点条目后，在使用视口高度除以预估条目高度，算出视口内部可能显示多少项，将起点序号加上这个数量，就是预估的终点条目序号。使用上述一样的修正逻辑，直到找到正确的视口终点条目。

描述可能比较难以理解，下面给出关键片段：

//内部方法，计算局部渲染数据切片的起止点
private_calcSliceRange(){
if(!this.dataView.length){
return{sliceFrom:0,sliceTo:0}
}
//数据总量
constMAX=this.dataView.length
//视口上边界
constviewportTop=(this.$refs.viewportasany).scrollTop||0
//视口下边界
constviewportBottom=viewportTop+this.viewportHeight
//预估条目高度
constestimatedItemHeight=this.defaultItemHeight
//从估算值开始计算起始序号
letsliceFrom=Math.floor(viewportTop/estimatedItemHeight!)
if(sliceFrom>MAX-1)sliceFrom=MAX-1
while(sliceFrom>=0&&sliceFrom<=MAX-1){
constitemTop=this._top(sliceFrom)
//条目顶部相对于viewport顶部的偏移
constitemOffset=itemTop-viewportTop
//1.该条目距离视口顶部有距离，说明上方还有条目元素需要显示，继续测试上一条
if(itemOffset>0){
//二分法快速估算下一个尝试位置
constdiff=itemOffset/estimatedItemHeight!
sliceFrom-=Math.ceil(diff/2)
continue
}
//2.恰好显示该条目的顶部，则该条目为本次视口的首条元素
if(itemOffset===0)break
//以下都是itemOffset<0
constitemHeight=this._itemHeight(sliceFrom)
//3.该条目在顶部露出了一部分，则该条目为本次视口的首条元素
if(itemOffsetMAX)sliceTo=MAX
while(sliceTo>sliceFrom&&sliceTo<=MAX){
constitemTop=this._top(sliceTo)
constitemHeight=this._itemHeight(sliceTo)
constitemBottom=itemTop+itemHeight
//条目底部相对于viewport底部的偏移
constitemOffset=itemBottom-viewportBottom
//1.该条目的底部距离视口底部有距离，说明下方还有条目元素需要显示，继续测试下一条
if(itemOffset<0){
//二分法快速估算下一个尝试位置
constdiff=-itemOffset/estimatedItemHeight!
sliceTo+=Math.ceil(diff/2)
continue
}
//2.恰好显示该条目的底部，则该条目为视口中最后一项
if(itemOffset===0)break
//3.该条目在底部被裁剪了一部分，则该条目为本次视口的末项
if(itemOffset
以上就是计算可视区域的核心部分。完整的代码，会在后续给出。
DOM更新

由于我们是使用Vue来实现虚拟列表的，所以DOM的更新方面，可以省去大量繁琐的细节管理。我们只需要关心列表滚动到某处之后，如何计算出当前视口应该出现哪些条目即可。
尽管如此，考虑到滚动的流畅性，以及IE11等浏览器的DOM操作性能，我们不得不多做很多事情。
批量DOM操作


我们可以在IE11的开发者工具面板中看到，滚动过程，频繁地往虚拟列表首尾插入、移除结点，会带来非常严重的性能问题。所以，我们必须控制DOM操作的频率。
批量可以部分解决这个问题。
具体的思路是，在滚动回调中，我们计算出可视区域的结点起止序号，不直接应用，而是加上一个额外渲染的数量。比如我们计算出当前应该渲染20~30这些条目，我们可以在前后各加上10个额外渲染的条目，即10~40，这样就一次性渲染了30个结点。在继续滚动时，我们检查新的起止范围，是否还在10～40范围内，如果是，我们就不做新的结点增删操作。
核心实现：
//刷新局部渲染数据切片范围
private_updateSliceRange(forceUpdate?:boolean){
//上下方额外多渲染的条目波动量
constCOUNT=this._preRenderingCount()

//预渲染触发阈值
constTHRESHOLD=this._preRenderingThreshold()

//数据总量
constMAX=this.dataView.length

//计算出准确的切片区间
constrange=this._calcSliceRange()

//检查计算出来的切片范围，是否被当前已经渲染的切片返回包含了
//如果是，无需更新切片，（如果forceUpdate，则无论如何都需要重新切片）
letfromThreshold=range.sliceFrom-THRESHOLD
if(fromThreshold<0)fromThreshold=0
lettoThreshold=range.sliceTo+THRESHOLD
if(toThreshold>MAX)toThreshold=MAX

//无需强制刷新，且上下两端都没有触达阈值时，无需重新切片
if(!forceUpdate&&((this.sliceFrom<=fromThreshold)&&(this.sliceTo>=toThreshold))){
return
}

//下面是更新切片的情况

//在切片区间头部、尾部，追加预渲染的条目
let{sliceFrom,sliceTo}=range
sliceFrom=sliceFrom>COUNT?sliceFrom-COUNT:0
sliceTo=sliceTo+COUNT>MAX?MAX:sliceTo+COUNT

this.sliceFrom=sliceFrom
this.sliceTo=sliceTo
if(forceUpdate)this._doSlice()
}
使用了这种批量操作之后，可以看到，正常的鼠标滚动下，IE也能比较顺畅地滚动了。
事件
由于虚拟列表的DOM需要不停地生成和销毁，因此，直接在列表项目上绑定事件是非常低效的。所以，使用事件代理就成了很不错的方案，将事件注册在组件根结点上，再根据 event.target来区分是由哪个列表项冒泡出来的事件，即可高效处理。
组件实现
import{Component,Vue,Prop,Watch}from'vue-property-decorator'
import{createSparseRangeList}from'./SparseRangeList'
//列表项数据包裹，data字段存放原始数据
//组件所有操作不应该改变data的内容，而是修改该包裹对象的属性
classItemWrapper{
//原始数据
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'})
exportdefaultclassVListextendsVue{
[key:string]:any
//高度存储不响应式
privateitemHeightStore:any
//组件宽度，不设置则为容器的100%
@Prop({type:Number})
privatewidth?:number
//组件高度，不设置则为容器的100%
@Prop({type:Number})
privateheight?:number
//传入高度值，固定条目高度
@Prop({type:Number})
privatefixedItemHeight?:number
//预估元素高度，
//在高度不确定的列表中，未计算出高度时使用，
//该值与元素平均高度越相近，则越高效（修正时估算次数越少）
@Prop({type:Number,default:30})
privateestimatedItemHeight!:number
//数据列表
@Prop({type:Array,default:()=>([])})
privatedata!:any[]
//计算条目高度的方法
@Prop({
type:Function,
default(node:Node,wrappedData:ItemWrapper){
return(nodeasHTMLElement).clientHeight
}
})
privateitemHeightMethod!:(node:Node,wrappedItem:ItemWrapper)=>number
//数据过滤方法（可以用于外部实现搜索框过滤）
@Prop({type:Function})
privatefilterMethod?:(data:any)=>boolean
//数据排序方法（可以用于外部实现数据自定义过滤）
@Prop({type:Function})
privatesortMethod?:(a:any,b:any)=>number
//包裹后的数据列表（必须freeze，否则大列表性能撑不住）
privatewrappedData:ReadonlyArray=Object.freeze(this._wrapData(this.data))
//真实渲染上屏的数据列表切片
privatedataSlice:ReadonlyArray=[]
//viewport宽度
privateviewportWidth=this.width||0
//viewport高度
privateviewportHeight=this.height||0
//当前viewport中第一条数据的序号
privatesliceFrom=0
//当前viewport中最后一条数据的序号
privatesliceTo=0
//列表高度
privatelistHeight=0
//检查是否固定高度模式
privategetisFixedHeight(){
returnthis.fixedItemHeight!>=0
}
//获取默认条目高度
privategetdefaultItemHeight(){
returnthis.isFixedHeight?this.fixedItemHeight!:this.estimatedItemHeight
}
//当前筛选条件下的数据列表
//依赖：wrappedData,filterMethod,sortMethod
privategetdataView(){
const{wrappedData,filterMethod,sortMethod}=this
letdata=[]
if(typeoffilterMethod==='function'){
constlen=wrappedData.length
for(letindex=0;indexi)
}
if(typeofsortMethod==='function'){
data.sort((a,b)=>{
returnsortMethod(a,b)
})
}
//重新记录数据在视图中的位置，用于隐藏部分条目时，可以精确计算高度、坐标
constsize=data.length
for(letindex=0;index{
//小于零的需要隐藏，所以高度为0
this.itemHeightStore.setValue(index,
wrappedItem.height>0?wrappedItem.height:0)
})
//刷新列表高度
this.updateListHeight()
//重置滚动位置
//TODO,锚定元素
const{viewport}=this.$refsasany
if(viewport)viewport.scrollTop=0
//重新切片当前viewport需要的数据
this._updateSliceRange(true)
this.$emit('data-view-change',this.dataSlice.map((wrappedItem)=>wrappedItem.data))
}
privatecreated(){
constestimatedItemHeight=this.defaultItemHeight
this.itemHeightStore=createSparseRangeList(this.dataView.length,estimatedItemHeight)
this.layoutObserver=newMutationObserver(this.redraw.bind(this))
this.childObserver=newMutationObserver((mutations:MutationRecord[])=>{
this._updateHeightWhenItemInserted(mutations)
})
this.$watch(((vm:any)=>`${vm.sliceFrom},${vm.sliceTo}`)asany,this._doSlice)
}
privatemounted(){
this.redraw()
this.layoutObserver.observe(this.$el,{attributes:true})
//非固定高度场景，监听子元素插入，提取高度
if(!this.isFixedHeight){
this.childObserver.observe(this.$refs.content,{childList:true})
}
}
privatebeforeDestory(){
this.layoutObserver.disconnect()
if(!this.isFixedHeight){
this.childObserver.disconnect()
}
this.itemHeightStore=null
}
//DOM结构比较简单，无需template，直接使用渲染函数输出VDOM
privaterender(createElement:any){
returncreateElement(
'div',//组件容器，与外部布局
{
class:'VList',
style:{
'box-sizing':'border-box',
display:'inline-block',
margin:'0',
padding:'0',
width:this.width?this.width+'px':'100%',
height:this.height?this.height+'px':'100%',
}
},
[
createElement(
'div',//滚动区域的可见范围
{
ref:'viewport',
class:'VList_viewport',
style:
'box-sizing:border-box;position:relative;overflow:hidden;width:100%;height:100%;margin:0;padding:0;overflow:auto;overflow-scrolling:touch;',
on:{scroll:this._onScroll}
},
[
createElement(
'div',//内容容器，内容真实高度由此容器体现
{
class:'VList_scollable',
ref:'content',
style:{
'box-sizing':'border-box',
position:'relative',
margin:'0',
padding:'0',
height:this.listHeight+'px'
}
},
//列表项
this.dataSlice.map((wrappedItem)=>{
returncreateElement(
'div',
{
key:wrappedItem.key,
class:`VList_itemVList_item-${wrappedItem.key%2===0?'even':'odd'}`,
attrs:{
'data-key':wrappedItem.key
},
style:{
'box-sizing':'border-box',
'z-index':'1',
position:'absolute',
right:'0',
bottom:'auto',
left:'0',
margin:'0',
padding:'0',
cursor:'default',
//注：使用transfrom有黑屏bug
//transform:`translate(0,${top})`
//transform:`translate3d(0,${top},0)`
top:this._top(wrappedItem.viewIndex)+'px'
}
},
//将原始数据，key注入到slot里，
//以便自定义条目内容使用
this.$scopedSlots.default!({
item:wrappedItem.data,
listKey:wrappedItem.key
})
)
})
)
]
)
]
)
}
//重绘界面，确保列表渲染正确
publicredraw(){
constviewport=this.$refs.viewportasHTMLElement
const{clientWidth,clientHeight}=viewport
this.viewportWidth=clientWidth
this.viewportHeight=clientHeight
this.updateListHeight()
this._updateSliceRange(true)
}
//刷新列表总高度
publicupdateListHeight(){
const{itemHeightStore}=this
constrangeValues=itemHeightStore.values()
if(!rangeValues.length){
this.listHeight=0
return
}
constlistHeight=rangeValues.reduce((sum:number,rangeValue:any)=>{
constspan=rangeValue.end-rangeValue.start+1
constheight=rangeValue.value*span
returnsum+height
},0)
this.listHeight=listHeight
}
//Dom插入时候，计算高度，然后
//批量刷新高度，避免频繁调整列表高度带来性能问题
publicbatchUpdateHeight(records:Array<{wrappedItem:ItemWrapper,height:number}>){
records.forEach(({wrappedItem,height})=>{
this._updateHeight(wrappedItem,height,true)
})
this.updateListHeight()
this._updateSliceRange()
}
//通过数据key，设置对应条目的高度
publicupdateHeightByKey(key:any,height:number){
constwrappedItem=this.wrappedData[key]
if(!wrappedItem)return
this._updateHeight(wrappedItem,height)
this.updateListHeight()
this._updateSliceRange()
}
//通过数据key，设置对应条目的显示状态
publicshowByKey(key:any){
constwrappedItem=this.wrappedData[key]
if(!wrappedItem)return
if(wrappedItem.height<=0){
constheight=-wrappedItem.height||this.defaultItemHeight
this._updateHeight(wrappedItem,height!)
this.updateListHeight()
this._updateSliceRange()
//强制重绘
this._doSlice()
}
}
//通过数据key，设置对应条目的显示状态
publichideByKey(key:any){
constwrappedItem=this.wrappedData[key]
if(!wrappedItem)return
if(wrappedItem.height>0){
constheight=-wrappedItem.height
wrappedItem.height=height
this._updateHeight(wrappedItem,height)
this.updateListHeight()
//强制重绘
this._updateSliceRange(true)
}
}
//通过数据key列表，设置对应条目的显示状态
publicshowByKeys(keys:any[]){
constwrappedItems=keys.map((key)=>this.wrappedData[key])
.filter((wrappedItem)=>wrappedItem&&wrappedItem.height<=0)
wrappedItems.forEach((wrappedItem)=>{
constheight=(-wrappedItem.height||this.defaultItemHeight)!
this._updateHeight(wrappedItem,height)
})
this.updateListHeight()
//强制重绘
this._updateSliceRange(true)
}
//通过数据key列表，设置对应条目的显示状态
publichideByKeys(keys:any[]){
constwrappedItems=keys.map((key)=>this.wrappedData[key])
.filter(wrappedItem=>wrappedItem&&wrappedItem.height>0)
wrappedItems.forEach((wrappedItem)=>{
//设置为负数，表示隐藏
constheight=-wrappedItem.height
wrappedItem.height=height
this._updateHeight(wrappedItem,height)
})
this.updateListHeight()
//强制重绘
this._updateSliceRange(true)
}
//内部方法，计算局部渲染数据切片的起止点
private_calcSliceRange(){
if(!this.dataView.length){
return{sliceFrom:0,sliceTo:0}
}
//数据总量
constMAX=this.dataView.length
//视口上边界
constviewportTop=(this.$refs.viewportasany).scrollTop||0
//视口下边界
constviewportBottom=viewportTop+this.viewportHeight
//预估条目高度
constestimatedItemHeight=this.defaultItemHeight
//从估算值开始计算起始序号
letsliceFrom=Math.floor(viewportTop/estimatedItemHeight!)
if(sliceFrom>MAX-1)sliceFrom=MAX-1
while(sliceFrom>=0&&sliceFrom<=MAX-1){
constitemTop=this._top(sliceFrom)
//条目顶部相对于viewport顶部的偏移
constitemOffset=itemTop-viewportTop
//1.该条目距离视口顶部有距离，说明上方还有条目元素需要显示，继续测试上一条
if(itemOffset>0){
//二分法快速估算下一个尝试位置
constdiff=itemOffset/estimatedItemHeight!
sliceFrom-=Math.ceil(diff/2)
continue
}
//2.恰好显示该条目的顶部，则该条目为本次视口的首条元素
if(itemOffset===0)break
//以下都是itemOffset<0
constitemHeight=this._itemHeight(sliceFrom)
//3.该条目在顶部露出了一部分，则该条目为本次视口的首条元素
if(itemOffsetMAX)sliceTo=MAX
while(sliceTo>sliceFrom&&sliceTo<=MAX){
constitemTop=this._top(sliceTo)
constitemHeight=this._itemHeight(sliceTo)
constitemBottom=itemTop+itemHeight
//条目底部相对于viewport底部的偏移
constitemOffset=itemBottom-viewportBottom
//1.该条目的底部距离视口底部有距离，说明下方还有条目元素需要显示，继续测试下一条
if(itemOffset<0){
//二分法快速估算下一个尝试位置
constdiff=-itemOffset/estimatedItemHeight!
sliceTo+=Math.ceil(diff/2)
continue
}
//2.恰好显示该条目的底部，则该条目为视口中最后一项
if(itemOffset===0)break
//3.该条目在底部被裁剪了一部分，则该条目为本次视口的末项
if(itemOffsetMAX)toThreshold=MAX
//无需强制刷新，且上下两端都没有触达阈值时，无需重新切片
if(!forceUpdate&&((this.sliceFrom<=fromThreshold)&&(this.sliceTo>=toThreshold))){
return
}
//更新切片的情况
//在切片区间头部、尾部，追加预渲染的条目
let{sliceFrom,sliceTo}=range
sliceFrom=sliceFrom>COUNT?sliceFrom-COUNT:0
sliceTo=sliceTo+COUNT>MAX?MAX:sliceTo+COUNT
this.sliceFrom=sliceFrom
this.sliceTo=sliceTo
if(forceUpdate)this._doSlice()
}
//当前需要渲染的数据切片
private_doSlice(){
const{dataView,sliceFrom,sliceTo}=this
constslice=dataView.slice(sliceFrom,sliceTo)
.filter((wrappedItem)=>wrappedItem.height>0)
this.dataSlice=Object.freeze(slice)
this.$emit('slice',slice.map((wrappedItem)=>wrappedItem.data))
}
//`index`数据在dataView中的index
private_itemHeight(index:number):number{
returnthis.itemHeightStore.getValueAt(index)
}
//`index`数据在dataView中的index
private_top(index:number):number{
if(index===0)return0
//0～上一项的高度累加
constrangeValues=this.itemHeightStore.intersecting(0,index-1)
constsumHeight=rangeValues.reduce((sum:number,rangeValue:any)=>{
constspan=rangeValue.end-rangeValue.start+1
returnsum+rangeValue.value*span
},0)
returnsumHeight
}
//包裹原始数据列表
private_wrapData(list:any[]):ItemWrapper[]{
returnlist.map((item,index)=>newItemWrapper(item,index,this.defaultItemHeight!))
}
//通过DOMNode获取对应的数据
private_getDataByNode(node:Node):ItemWrapper{
returnthis.wrappedData[(nodeasany).dataset.key]
}
//刷新列表项高度
private_updateHeight(wrappedItem:ItemWrapper,height:number,isRealHeight?:boolean){
height=height>>0
//更新结点高度缓存
wrappedItem.height=height
if(isRealHeight){
wrappedItem.realHeight=true
}
//如果wrappedItem为当前过滤下的项目，
//则同时刷新高度存储store
constindex=this.dataView.indexOf(wrappedItem)
if(index!==-1){
//小于等于零表示折叠不显示，计算高度为零
//负值存在wrappedItem中，用于反折叠时恢复
this.itemHeightStore.setValue(index,height>0?height:0)
}
}
//节点插入时，检查是否首次插入，如果是，计算高度并更新对应的ItemWrapper
private_updateHeightWhenItemInserted(mutations:MutationRecord[]){
constaddedNodes:Node[]=mutations
.map((mutation:MutationRecord)=>mutation.addedNodes)
.reduce((result:any,items:NodeList)=>{
result.push(...items)
returnresult
},[])
constbatch:Array<{wrappedItem:ItemWrapper,height:number}>=[]
addedNodes.forEach((node:Node)=>{
constwrappedItem=this._getDataByNode(node)
//如果wrappedItem中已经存储了计算过的高度，
//则直接返回，不访问clientHeight
//以避免性能开销（IE11中访问clientHeight性能非常差）
if(wrappedItem.realHeight){
return
}
constheight=this.itemHeightMethod(node,wrappedItem)>>0
if(wrappedItem.height!==height){
batch.push({wrappedItem,height})
}else{
//计算出来的高度跟默认值一致，
//则无需更新，但是设置已经计算状态
//以便下次可以直接使用缓存
wrappedItem.realHeight=true
}
})
if(batch.length){
this.batchUpdateHeight(batch)
}
}
//滚动事件处理器
private_onScroll(){
this._updateSliceRange()
}
}
总结
以上所说是小白给大家介绍的使用Vue实现一个虚拟列表的方法，希望对大家有所帮助，如果大家有任何疑问欢迎给我留言，小编会及时回复大家的！

使用 Vue 实现一个虚拟列表的方法

热门推荐

随机推荐