见名知意
SparseArray "稀疏数组", 是数组，key是整数，但key不是连续的。如下图，key并不是4到10连续的，它只是零星地存储了几个自己想要的数据。跟HashMap理解一样。
SparseArray内部维持着2个数组keys,values。通过找到key在数组中的索引index,从而找到key对应的数据values[index]。
SparseArray内部数据结构
基本操作
- 创建实例： 可以指定初始的容量(keys和values数组)大小，也可以不传，如果不传入的话，默认大小为10。
val sparseArray = SparseArray<String>(5)
- 增加数据 : put和append都可以。注意append并不像我们平常接触的那样是在末尾追加，它最终还是调用put，还是保持key从小到大的顺序。
sparseArray.apply {
put(7, "seven")
put(10, "ten")
append(4, "four") //尽管是append的，数据还是在最前面
}
- 数据迭代: keyAt(), get(key), 按照key的从小到大的顺序显示
Log.d(TAG,"==> iterator before remove.")
for (i in 0 until sparseArray.size()) {
val key = sparseArray.keyAt(i)
val value = sparseArray.get(key)
Log.d(TAG,"key = $key,value = $value")
}
// key = 4,value = four
// key = 7,value = seven
// key = 10,value = ten
- 删除数据: remove(key)或者delete(key)。 remove(key)代码实现还是调用delete(key)
sparseArray.remove(7)
sparseArray.remove(8)
Log.d(TAG,"==> iterator after remove.")
for (i in 0 until sparseArray.size()) {
val key = sparseArray.keyAt(i)
val value = sparseArray[key]
Log.d(TAG,"key = $key,value = $value")
}
// key = 4,value = four
// key = 10,value = ten
与HashMap区别
看这用法，跟HashMap没啥区别，难道HashMap不香嘛？
我们知道当HashMap中的key是普通的数字类型的话，我们key是要经过装箱过程的，如int到Integer, long 到 Long。这个装箱的过程存在一定的性能消耗。而且，HashMap存储value的时候需要依赖额外的Entry类型，这也带来一定的开销。
所以当我们需要一个简单的key为int这种原始数字类型时，可以使用SparseArray, 而key为long时，可使用LongSparseArray。
但是，为维持key的有序性，增删的过程需要使用二分搜索key数组，查的过程也需要通过二分搜索找到key的索引，当数据量过大的时候，二分搜索带来的开销会比装箱、类型创建带来的开销要大。
因此使用SparseArray要求：
- 数据的key为int或者long
- 数据量小
源码分析
主要分析put和delete的过程，这2过程直接奠定了其他算法的实现。
- 增加的过程 put(key1,value)。
- 通过二分搜索key, 判断是否已经有历史数据
- 有历史数据直接覆盖，没有的话， 垃圾回收清除删除的数据，扩容数组，再插入到指定索引位置
public void put(int key, E value) {
// 1. 二分搜索找到key在keys数组中的位置
// 如果key在keys中找到，那么返回对应索引位置
//如果没有找到的话，返回插入位置的取反 ~insertIndex 为负值
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
if (i >= 0) {
mValues[i] = value;
} else {
i = ~i;
// 2. 1如果找到了，但是数据时处于删除的状态(删除key,不会直接从keys中删除key, 而是把其值负值为DELETED的内部常量，见delete过程)，直接覆盖
if (i < mSize && mValues[i] == DELETED) {
mKeys[i] = key;
mValues[i] = value;
return;
}
// 2.2 垃圾回收(有删除了的值)，并且数据满员了，进行垃圾回收见gc(), 并重新获得插入的位置
// 如果垃圾数清除的话，那么清除了，后续就不需要再进行扩容数组操作了
if (mGarbage && mSize >= mKeys.length) {
gc();
// Search again because indices may have changed.
i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
}
// 2.2 插入数据，扩容数组或者直接插入数据，见insert()
mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
mSize++;
}
}
private static int[] insert(int[]array,int currentSize, int index, int element){
assert currentSize <= array.length;
if(currentSize + 1 <= array.length){ //数据未满
System.arraycopy(array,index,array,index + 1,currentSize - index);
array[index] = element;
return array;
}
//扩容数组 * 2
int[] newArray = new int[growSize(currentSize)];
System.arraycopy(array,0,newArray,0,index);
newArray[index] = element;
System.arraycopy(array,index,newArray,index + 1 , array.length - index);
return newArray;
}
private static int growSize(int currentSize){
return currentSize <= 4 ? 8 : currentSize * 2;
}
// 垃圾回收，清除多余的值，快慢指针，覆盖清除DELETED
private void gc() {
int n = mSize;
int o = 0;
int[] keys = mKeys;
Object[] values = mValues;
for (int i = 0; i < n; i++) {
Object val = values[i];
if (val != DELETED) {
if (i != o) {
keys[o] = keys[i];
values[o] = val;
values[i] = null;
}
o++;
}
}
mGarbage = false;
mSize = o;
}
- 删除过程 delete(key1)
删除的过程中，并没有直接通过删除key的方式来缩短key数组，而是将其值标记为删除状态，赋值为DELETED。这样避免不必要的删除和插入操作，当重新增加数据时，可以直接将值更新为最新的值。
例如： remove(7); put(7,"Seven") 这两个连续操作的过程就不需要先删除7，然后key数组和value数组7之后的元素整体往前移动，而后插入过程也不用整体向后移动。
不过也正是因为删除过程不进行实际删除，当我们需要获得真实的内部数据(如size)的时候，如果mGarbage为true,即有垃圾数据的时候，我们每次都需要先进行垃圾回收删除数据，再返回真实的数据。
public void delete(int key) {
// 一样是二分搜索
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
if (i >= 0) {
if (mValues[i] != DELETED) {
mValues[i] = DELETED; //标记为DELETED
mGarbage = true;
}
}
}
