SparseArray
SparseArray 的使用
创建
SparseArray有两个构造方法，一个默认构造方法，一个传入容量。
SparseArray sparseArray = new SparseArray<>();
SparseArray sparseArray = new SparseArray<>(capacity);
首先来看看如何创建一个SparseArray，而SparseArray只需要指定一个泛型表示value类型，而key的类型在SparseArray内部已经指定了为int类型
put()
看看怎么往里面存放数据吧
sparseArray.put(int key,Student value);
put()就跟HashMap的使用方法一样。
get()
sparseArray.get(int key);
sparseArray.get(int key,Student valueIfNotFound);
SparseArray 实现原理
简介：
用int[]数组存放key，避免了HashMap中基本数据类型需要装箱的步骤，其次不使用额外的结构体（Entry)，单个元素的存储成本下降。
要理解SparseArray 的实现原理，需要看代码：
SparseArray用两个数组来存放key和value：
private int[] mKeys;
private Object[] mValues;
key的存放按照从小到大的顺序，这样就能保证使用二分查找，而SparseArray内部查找数据也就是使用的二分查找，这样查找的效率比较高。我们来看下put方法，就能大概理解SparseArray的原理了：
//参数是传进来的 int类型的key 和 范形的value
public void put(int key, E value) {
int i = ContainerHelpers.binarySearch(mKeys, mSize, key); //使用二分查找寻找key应该在的位置，具体实现请先看下面的讲解
if (i >= 0) {
mValues[i] = value; //如果寻找到lo就直接覆盖value
} else {
i = ~i;
if (i < mSize && mValues[i] == DELETED) { //如果没有找到，并且返回的数组索引对应的值是DELETED那就直接覆盖value
mKeys[i] = key;
mValues[i] = value;
return;
}
if (mGarbage && mSize >= mKeys.length) { //如果当前数组已满，检查数组中是否有DELETED的值，然后将其删除gc的操作：可查看下面具体源码
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++;
}
}
二分查找
//这里传递过来的value是上面的key
static int binarySearch(int[] array, int size, int value) {
int lo = 0;
int hi = size - 1;
while (lo <= hi) {
final int mid = (lo + hi) >>> 1;
final int midVal = array[mid];
if (midVal < value) {
lo = mid + 1;
} else if (midVal > value) {
hi = mid - 1;
} else {
return mid; // value 找到，直接返回key的索引
}
}
return ~lo; // 没有找到就直接返回最终lo的取反值，此时的lo值就正好是排好序的lo
}
gc：
private void gc() {
// Log.e("SparseArray", "gc start with " + mSize);
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;
// Log.e("SparseArray", "gc end with " + mSize);
}
总结：
SparseArray的优点：
避免了基本数据类型的装箱操作
不需要额外的结构体，单个元素的存储成本更低
数据量小的情况下，随机访问的效率更高
SparseArray的缺点：
插入操作需要复制数组，增删效率降低
数据量巨大时，复制数组成本巨大，gc()成本也巨大
数据量巨大时，查询效率也会明显下降
ArrayMap的原理
ArrayMap是一个<key,value>映射的数据结构，它设计上更多的是考虑内存的优化，内部是使用两个数组进行数据存储，一个数组记录key的hash值，另外一个数组记录Value值，它和SparseArray一样，也会对key使用二分法进行从小到大排序，在添加、删除、查找数据的时候都是先使用二分查找法得到相应的index，然后通过index来进行添加、查找、删除等操作，所以，应用场景和SparseArray的一样，如果在数据量比较大的情况下，那么它的性能将退化至少50%。
总结：
假设数据量都在千级以内的情况下：
1、如果key的类型已经确定为int类型，那么使用SparseArray，因为它避免了自动装箱的过程，如果key为long类型，它还提供了一个LongSparseArray来确保key为long类型时的使用
2、如果key类型为其它的类型，则使用ArrayMap
