SparseArray分析
一、SparseArray出现的背景
相信大家都用过HashMap用来存放键值对，最近在项目中使用HashMap的时候发现，有时候 IDE 会提示我这里的HashMap可以用SparseArray或者SparseIntArray等等来代替。
细心的朋友可能也发现了这个提示，并且会发现并不是所有的HashMap都会提示替换。今天就来一探究竟，到底SparseArray跟HaspMap相比有什么优缺点，又是在什么场景下来使用的呢？
二、SparseArray 的使用
1、创建
//java:
SparseArray sparseArray = new SparseArray<>();
SparseArray sparseArray = new SparseArray<>(capacity);
//kotlin:必须传入泛型
var list = SparseArray<Boolean>()
list.put(1,true)
首先来看看如何创建一个SparseArray，前文说了SparseArray是用来替换HashMap的，而SparseArray只需要指定一个泛型，似乎说明key的类型在SparseArray内部已经指定了呢？
SparseArray有两个构造方法，一个默认构造方法，一个传入容量。
2、put()
sparseArray.put(int key,E value);
原来SparseArray存放的键值对中的键是int型的数据，为什么呢？后面分析源码的时候再讲。
put()就跟HashMap的使用方法一样。
3、get()
sparseArray.get(int key);
sparseArray.get(int key,E valueIfNotFound);
sparseArray.remove(int key);
4、index
前面几个都跟HashMap没有什么太大区别，而这个index就是SparseArray所特有的属性了，这里为了方便理解先提一嘴，SparseArray从名字上看就能猜到跟数组有关系，事实上他底层是两条数组，一组存放key，一组存放value，知道了这一点应该能猜到index的作用了。
index — key在数组中的位置。SparseArray提供了一些跟index相关的方法：
sparseArray.indexOfKey(int key);
sparseArray.indexOfValue(T value);
sparseArray.keyAt(int index);
sparseArray.valueAt(int index);
sparseArray.setValueAt(int index);
sparseArray.removeAt(int index);
sparseArray.removeAt(int index,int size);
三、SparseArray 实现原理
前面简单的介绍了 SparseArray 的使用，为了在实际工作中最合理的选用数据结构，深入的了解每种数据结构的实现原理是很有必要的，这样可以更好的理解和比较不同数据结构之间的优缺点，比死记概念要更好，甚至可以根据自己的具体需求去实现最适合需求的数据结构。
SparseArrays map integers to Objects. Unlike a normal array of Objects,there can be gaps in the indices. It is intended to be more memory efficient than using a HashMap to map Integers to Objects, both because it avoids auto-boxing keys and its data structure doesn’t rely on an extra entry object for each mapping.
这段注释基本解释了该类的作用：使用int[]数组存放key，避免了HashMap中基本数据类型需要装箱的步骤，其次不使用额外的结构体（Entry)，单个元素的存储成本下降。
1、put源码解析
/**
* Adds a mapping from the specified key to the specified value,
* replacing the previous mapping from the specified key if there
* was one.
*/
public void put(int key, E value) {
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
if (i >= 0) {
mValues[i] = value;
} else {
i = ~i;
if (i < mSize && mValues[i] == DELETED) {
mKeys[i] = key;
mValues[i] = value;
return;
}
if (mGarbage && mSize >= mKeys.length) {
gc();
// Search again because indices may have changed.
i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
}
mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
mSize++;
}
}
插入的逻辑大概就这几点：
- 存放key的数组是有序的（二分查找的前提条件）
- 如果冲突，新值直接覆盖原值，并且不会返回原值（HashMap会返回原值）
- 如果当前要插入的 key 的索引上的值为DELETE，直接覆盖
- 前几步都失败了，检查是否需要gc()并且在该索引上插入数据
四、总结
了解了SparseArray的实现原理，就该来总结一下它与HashMap之间来比较的优缺点
1、优势：
- 避免了基本数据类型的装箱操作
- 不需要额外的结构体，单个元素的存储成本更低
- 数据量小的情况下，随机访问的效率更高
2、缺点
- 插入操作需要复制数组，增删效率降低
- 数据量巨大时，复制数组成本巨大，gc()成本也巨大
- 数据量巨大时，查询效率也会明显下降
————————————————
原文链接：https://blog.csdn.net/weixin_42600398/article/details/117652276
