SparseArray的优缺点及适用的应用场景小结

男娘i 2022-04-05 15:40 347阅读 0赞

### **SparseArray的实现简介：** ###

使用两个数组保存键值对，mKeys:int\[\]和mValue:Object\[\]。

成员介绍：

mSize：是指mKeys中实际使用的到的长度。

DELETE：Objcet 用于填充被remove的值。

首先是使用mKeys\[0\],此时mSize=1。然后插入一个数，小于mKeys\[0\]的，那么此时要将mKey\[0\]向后移一位（需要使用system\#arraycopy(...)进行移位），然后将新插入的值放到mKeys\[0\](如果后面还有其他值的话要统一后移一位)。如果此时mSize>=mKeys.length,那么数组需要使用system\#arraycopy(...)为数组扩容了，扩容至原来的两倍，然后将数据移到新数组中。

键在mKeys的index和值在mValues的index是一致的。所以mKeys移位的同时，mValues也需要移位。

被删除的值使用一叫DELETE的固定Object对象填充。

###  ###

### **为什么叫做SparseArray** ###

而从上可以看出mSize一般是小于mKeys.length的，因为如果不做删除操作，index=0到index=mSize-1中都是满的，没有空的，所以插入时一般都需要从插入位置起，后面元素向后移一位。这应该就是这个类叫做SparseArray（稀疏数组）的原因。所以觉得这样的安排把所有元素都紧密的压缩到一起，即是index为0至mSize-1的位置，而不是分散的分布在0至mKeys.length-1的整个数组。而这样的考虑正符合JavaScript稀疏数组的目的，所以叫SparseArray。这都是我的猜测。

JavaScript中是这样定义稀疏数组：稀疏数组就是包含从0开始的不连续索引的数组。通常，数组的length属性值代表数组中元素的个数。如果数组是稀疏的，length属性值大于元素的个数。可以用Array（）构造函数或简单地指定数组的索引值大于当前数组长度来创建稀疏数组。

###  ###

### **和HashMap、ArrayMap对比，SparseArray的优缺点：** ###

SparseArray的限制在于键必须是int类型，值必须是Object类型。这样可以避免key自动装箱产生过多的Object。但是这样的话，如果key值相同，那么数据就会被直接覆盖。

SparseArray不能保证保留它们的插入顺序，在迭代的时候应该注意。SparseArray中没有Iterator，SparseArray只实现了Cloneable接口，而没有继承Collection、List或者Map接口。

查找数据的时候使用的是二分法，明显比通过hashcode慢，所以数据越大，查找速度慢的劣势越明显，所以SparseArray适于数据一千以内的场景中。

优点：

*  避免了基本数据类型的装箱操作
 *  不需要额外的结构体，单个元素的存储成本更低
 *  数据量小的情况下，随机访问的效率更高

缺点：

*  插入操作需要复制数组，增删效率降低
 *  数据量巨大时，复制数组成本巨大，`gc()`成本也巨大
 *  数据量巨大时，查询效率也会明显下降

参考自：[https://www.cnblogs.com/yjbjingcha/p/7074266.html][https_www.cnblogs.com_yjbjingcha_p_7074266.html]

[https_www.cnblogs.com_yjbjingcha_p_7074266.html]: https://www.cnblogs.com/yjbjingcha/p/7074266.html